Algorytm mnożenia każdy z każdym

0

Cześć :)
Mam problem z algorytmem mnożącym "każdy z każdym". Na wejściu podane są przez użytkownika n liczb m cyfrowych, które mają zostać mnożone w taki oto sposób:
np. dla n=4 i m=4
9999 9999 9999 9999
9999 9999 9999 9998
.
.
.
9999 9999 9999 1000
9999 9999 9998 9999
9999 9999 9998 9998
.
.
.
9999 9999 9998 1000
.
.
.
9999 9998 9999 9999
9999 9998 9999 9998
.
.
.
9999 9998 9998 9999
.
.
.
1000 1000 1000 1000

Oto fragment kodu, który niby to robi ale nie do końca dobrze, brakuje mi jakiegoś warunku
result jest listą tablicową, która przechowuje n liczb

            if(result.get(y)==start && y>0){
                result.set(y, stop);
                result.set(y-1, result.get(y-1)-1);
            }
            if(result.get(y)>start)
                result.set(y, result.get(y)-1);
            if(result.get(y-1)==start)
                y--;
            for(int i=result.size()-1; i>y; i--){
                    result.set(i, stop);
                }

Proszę o jakieś naprowadzenie mnie jak to zrobić bo jestem w kropce. Myślałem też o iloczynie kartezjańskim ale nie jestem do końca przekonany czy to by było to.
Jeśli zajdzie taka potrzeba to podam cały kod źródłowy.

0

Co mnożysz przez co w podanym przez Ciebie przykładzie?

0

Te liczby które wypisałem
9999 * 9999 * 9999 * 9999
następnie zmniejszam o jeden ostatnią liczbę i znów mnożę
9999999999999998
aż dana liczba będzie najmniejszą z m cyfrowych (w tym wypadku m=4 jest to 1000)
9999
999999991000
gdy osiągnę ten poziom zmniejszam przedostatnią liczbę o jeden, a ostatnią daję jako max m cyfrową i tak w kółko Macieju, aż będzie mnożenie
100010001000*1000

0

może policz sumę od 1000 do 9999 ze wzoru (a1+an/2)n i mnóż raz

0

Niestety jest mi potrzebny sposób który opisałem wyżej do znalezienia największego palindromu z iloczynu n liczb m cyfrowych.

0

Zmagałem się kiedyś z tym zadaniem. Wydajniejszy jest trochę inny balgorytm: n - ilość czynników, m - ilość cyfr.

  1. Wyznaczamy najmniejszą i największą liczbę m-cyfrową i tworzymy listę wszystkich liczb m-cyfrowych
        lowerBound = (int)Math.pow(10,m - 1);
        upperBound = (int)Math.pow(10,m) - 1;
        for(int i=Math.max(2,lowerBound);i<=upperBound;i++)
        {
            factors.add(i);
        }
  1. W pętli (malejącej) od max = upperBoundn do min = lowerBoundn sprawdzamy czy liczba jest palindromem, jeśli jest, to sprawdzamy czy wśród rozkładów na czynniki jest rozkład na n czynników m-cyfrowych
        for(int i=max;i>=min;i--)
        {
            if(isPalindrome(i))
            {
                boolean founded = true;
                HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>();
                ArrayList<Integer> list = new ArrayList<Integer>();
                list.add(i);
                set.add(list);
                for(int k=n-1;k>0;k--)
                {
                    set = dividers(set,k);
                    if(set.isEmpty())
                    {
                        founded = false;
                        break;
                    }
                }
                if(founded)
                {
                    System.out.println(set.iterator().next());
                    System.out.println(i);
                    break;
                }
            }
        }
...
    private HashSet<ArrayList<Integer>> dividers(HashSet<ArrayList<Integer>> input, int depth)
    {
        HashSet<ArrayList<Integer>> result = new HashSet<ArrayList<Integer>>();
        int min = (int)Math.pow(lowerBound,depth);
        int max = (int)Math.pow(upperBound,depth);
        ArrayList<Integer> newlist = null;
        Iterator<ArrayList<Integer>> it = input.iterator();
     
        while(it.hasNext())
        {
            ArrayList<Integer> list = it.next();
            ArrayList<Integer> temp = new ArrayList<Integer>();          
            for(int n: list)
            {
                if(n <= upperBound)
                {
                    temp.add(n);
                }
            }
            for(int n: list)
            {
                if(n > upperBound)
                {
                    for(int k: factors)
                    {
                        if(n % k == 0)
                        {                            
                            int m = n/k;
                            if(m >= min && m <= max)
                            {                               
                                newlist = new ArrayList<Integer>(temp);
                                newlist.add(k);
                                newlist.add(m);
                                result.add(newlist);
                            }
                        }
                    }
                }             
            }
        }
        return result;
    }

Wynik dla m = n = 3, to 967262769 = 979999989.
Dla większych n i m trzeba zmienić typ zmiennych (long lub BigInteger).
Jeśli koniecznie chcesz mnożyć, to zajrzyj tu http://4programmers.net/Java/Zagnie%C5%BCd%C5%BCone_p%C4%99tle_if

0
  1. Wydaje mi się, że nie ma potrzeby wypisywania wszystkich liczb m cyfrowych skoro można wypisać n liczb największych m cyfrowych na n=3, a m=2 będzie to 99 99 99 i na nich działać. W sumie mam pomysł, że zamiast odejmować od jednej liczby i czekać aż będzie miała wartość minimalną robić odejmowanie od wszystkich czynników po kolei tj.
    99 99 99
    99 99 98
    99 98 98
    98 98 98
    z tym, że wtedy opuszczę "parę" mnożeń i dalej jestem w kropce.
  2. Staram się przeanalizować Twój kod ale mam małe doświadczenie i bardziej oczywistym wydawał mi się mój sposób, a nie lubię czegoś używać jak nie zrozumiem.

Nie rozumiem trochę działania tych pętli, można prosić o krótkie wyjaśnienie? Byłbym wdzięczny.

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;
    }

E:// Już doszedłem do tego, teraz widzę, że to o wiele lepszy pomysł od mojego :) tylko teraz zastanawiam się czy nie można było użyć ArrayList zamiast HashSet?

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