Rozkładanie liczby na sumy i iloczyny.

0

Dzień dobry,
potrzebuję pomocy w napisaniu programu, który podaną liczbę rozłoży na sumy i iloczyny np.
dla n=5:
1+4
12+3
2+3
albo dla n=10:
1+2+3+4
1+2+7
1+3+6
1+4+5
1+9
1
2+3+5
12+8
1
23+4
1
25
1
3+7
14+6
2+3+5
2+8
2
3+4
2*5
3+7
4+6

Niestety prowadzący nie podał, żadnego polecenia do tego zadania więc te dane, które mam to jedyne moje informacje.
Czy zna ktoś jakiś algorytm mogący rozkładać podane liczby na takie sumy i iloczyny, które mógłbym zaimplementować w javie czy raczej muszę kombinować coś samemu?

Z góry dziękuję za pomoc i pozdrawiam.

0

Rozkład na iloczyny to rozkład na czynniki pierwsze. Ale tak ogólnie to wygląda to na jakąś rekurencję z powrotami.

0

ale nie widzę tu żadnej reguły
jak można napisać algorytm do zadania które nie jest jasno sprecyzowane

przecież to można "rozkładać" w nieskończoność

111111111111111 + 111111111 + 1 + 1*2 = 5

0

No mnożenie przez 1 i 0 raczej nie wchodzi w grę, a do tego liczby są dodawane do siebie bądź mnożone, rosnąco czyli np nie może być 6+4, tylko 4+6, tak mi się wydaję.
Bądź co bądź to były nasze pierwsze zajęcia z javy więc niby jakiś trudnych programów nie powinno być, ale prostego rozwiązania to tutaj nie widzę.
Ogólnie to było jeszcze coś o zachowaniu kolejności działań, np:
(((x+y)+z)+w)=n

0
Mefa2 napisał(a):

Ogólnie to było jeszcze coś o zachowaniu kolejności działań, np:
(((x+y)+z)+w)=n

Raczej nie o taką kolejność chodzi, a w przykładach tego nie widać. To coś w stylu 1+2*3 ma być równe 7 a nie 9.
Powinieneś najpierw ogarnąć problem z samym algorytmem, a potem dopiero bawić się w implementację. Takie oczywiste podejście to dla liczby N znaleźć wszystkie rosnące ciągi z największym wyrazem < N, a potem wstawiać w każdym znaki między liczby. Zależy jaki masz zakres tych liczb do zbadania, nie wiem dla jak dużych może być problem.

0

Ok, więc posiadam treść zadania:
"Napisz program podający wszystkie rozkłady danej liczby naturalnej n<0, na sumę i/lub iloczyn różnych między sobą składników naturalnych (różnych od 0) występujących w kolejności rosnącej."
Z wskazówek wiem, iż ma to być zrobione tak, że jeśli występuje mnożenie to występuje ono na początku, przez co nie martwimy się kolejnością wykonywania działań.
Jakieś sugestie? Algorytmy przydatne? Podpowiedzi?
Przyjmę każdą formę pomocy.
Z góry dziękuję i pozdrawiam.

0

Czyli powinienem wygenerować wszystkie możliwe podzbiory zbioru n i sprawdzać je za pomocą ONP czy sumują się do zadanej wartości n?

0

ja by zaczął od tego, że tak naprawdę można przedstawić problem inaczej: można sprawdzić kolejne kombinacje trzech operacji: brak liczby, dodaj liczbę, pomnóż liczbę; dla kolejnych liczb całkowitych.
Pamiętaj że musisz cały czas sprawdzać czy nadal warto testować daną kombinację, czy może uzyskujesz już wartości większe od n.

0

Jeżeli wybierasz pomysł @_13th_Dragon'a, to raczej generujesz wpierw wszystkie rosnące ciągi liczb o sumie <= n. Potem do każdego wygenerowanego ciągu wstawiasz operatory (+ lub *) po drugiej, trzeciej, czwartej,...,ostatniej liczbie i wyliczasz wartość otrzymanego ciągu. Ciąg już jest zapisany w formacie ONP.

0
bogdans napisał(a):

Jeżeli wybierasz pomysł @_13th_Dragon'a, to raczej generujesz wpierw wszystkie rosnące ciągi liczb o sumie <= n. Potem do każdego wygenerowanego ciągu wstawiasz operatory (+ lub *) po drugiej, trzeciej, czwartej,...,ostatniej liczbie i wyliczasz wartość otrzymanego ciągu. Ciąg już jest zapisany w formacie ONP.

Nie, nie, nie!

1 2 + 3 4 + * - inaczej (1+2)*(3+4) nie zapiszesz.

Nie ma sensu wstawianie najpierw liczb a potem operatorów operatory można dodać jeżeli ilość liczb - ilość operatorów > 1

Nie wolno wstawiać tego samego operatora pod rzad: 1 2 3 + + bo 1 2 + 3 + już był i jest tym samym.

0

Uważam, że do tego zadania trzeba podejść inaczej. Wcześniej pisałem, że 1+23=7, ale teraz, wnioskując z informacji z treści skłaniam się ku temu, że 1+23=9, bo trzeba to traktować ((1+2)*3). A idąc tą drogą to do rozwiązania nie potrzeba generować wszystkich możliwych ciągów i wstawiać wszystkie kombinacje znaków. Zamiast tego można zapamiętywać dotychczasowy wynik i ostatnią liczbę i do obecnego stanu dopisywać wszystkie możliwe znaki i liczby. W zależności od tego, czy otrzymamy N, przekroczymy N czy wynik będzie mniejszy wykonuje się kolejne czynności. Myślę, że na całość potrzeba ze 30 linijek 42 linijki kodu.

0

Dziękuję wszystkim za odpowiedzi :)

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