Mnożenie n liczb m cyfrowych. JAVA

0

Cześć wszystkim :)

Mam mały problem, przesiedziałem na google pół dnia i nic z tego, próbowałem rysować na kartce algorytm żeby zobrazować sobie rozwiązanie problemu i nic z tego więc jestem zmuszony założyć wątek.

Ogólnie piszę program, który zwraca największy palindrom z iloczyny n liczb o m cyfrach, czyli użytkownik podaje ile liczb ma być pomnożonych oraz ile cyfr mają te liczby. Przykład: n=2, m=3 czyli np 123954.
Sprawdzanie palindromów potrafię zrobić oraz ilo cyfrowe mają być liczby. Problem natomiast polega na tym, że za cholerę nie mogę wymyślić jak mając w liście tablicowej wypisane liczby mogę je wymnożyć ileś tam razy oraz aby działania nie powtarzały się tj 50
65 i 65*50 chociaż z tym to mniejszy problem.

Prosiłbym o jakieś sugestie jak to ugryźć ;)
Pozdrawiam

0

Kłopoty biorą się stąd, że w czasie pisania programu nie znasz stopnia zagnieżdżenia pętli for (liczby n)? Zajrzyj tu Zagnieżdżone pętle for

0

hmmm... nie jestem pewny czy dobrze rozumiem bo dla mnie to troszkę zbyt ubogo opisane ale ArrayList<Point> ranges jest i i j w pętlach tak? Natomiast do czego służy ArrayList<Integer> indexes?

0

ArrayList<Point> ranges to zakresy zmiennych, dla pętli

for (int i=5,i<=77;i++)
   for(int j=3;j<=100;j++)
      for(int k=-2;k<=18;k++)
          //coś policz

ranges = (new Point(5,77),new Point(3,100),new Point(-2,18))
ArrayList<Integer> indexes to aktualne wartość zmiennych sterujących, te dla których wykonywane są obliczenia.

0

Sprawdziłem, sposób z utworzeniem na starcie wszystkich dopuszczalnych iloczynów dość szybko (m=3, n=3) działa nieakceptowalnie wolno i wymaga zwiększenia pamięci dla JVM.
Poniższy kod działa zadowalająco dla:

 
n=3 m=3  wynik = 967 262 769, 
n=4 m=2  wynik = 67 144 176,
n=2 m=4  wynik = 99 000 099

dalej nie sprawdzałem - wyniki pośrednie nie mieszczą się w typie int.

import java.util.*;
import java.awt.Point;

public class Products
{
    ArrayList<Integer> factors = new ArrayList<Integer>();
    int lowerBound;
    int upperBound;
    int n;
    //------------------------
    public static void main(String[] args)
    {
        new Products();
    }
    //------------------------
    public Products()
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Ile czynnikow: ");
        n = sc.nextInt();
        System.out.print("Ile cyfr: ");
        int m = sc.nextInt();
        lowerBound = (int)Math.pow(10,m - 1);
        upperBound = (int)Math.pow(10,m) - 1;
        for(int i=lowerBound;i<=upperBound;i++)
        {
            factors.add(i);
        }
        int max = (int)Math.pow(upperBound,n);
        int min = (int)Math.pow(lowerBound,n);
        for(int i=max;i>=min;i--)
        {
            if(isPalindrome(i))
            {
                boolean founded = true;
                Set<Integer> set = new HashSet<Integer>();
                set.add(i);
                for(int k=n-1;k>0;k--)
                {
                    set = dividers(set,k);
                    if(set.isEmpty())
                    {
                        founded = false;
                        break;
                    }
                }
                if(founded)
                {
                    System.out.println(set);
                    System.out.println(i);
                    break;
                }
            }
        }
    }
    //------------------------
    private boolean isPalindrome(int n)
    {
        ArrayList<Integer> digits = new ArrayList<Integer>();
        while(n > 0)
        {
            digits.add(n % 10);
            n/=10;
        }
        int len = digits.size();
        for(int i=0;i<len/2;i++)
        {
            if(digits.get(i) != digits.get(len-1-i))
            {
                return false;
            }
        }
        return true;
    }
    //------------------------
    private Set<Integer> dividers(Set<Integer> input, int depth)
    {
        Set<Integer> result = new HashSet<Integer>();
        int min = (int)Math.pow(lowerBound,depth);
        int max = (int)Math.pow(upperBound,depth);
        for(int k: factors)
        {
            for(int n: input)
            {
                if(n % k == 0)
                {
                    int m = n/k;
                    if(m >= min && m <= max)
                    {
                        result.add(m);
                    }
                }
            }
        }            
        return result;
    }
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1