Takie zadanko mam:
Problem polega na skonstruowaniu wyrazenia arytmetycznego zlozonego z dwuargumentowych operatorow dodawania i mnozenia oraz wartosci 0,3. w przypadku gdy liczba n uzytych operatorow wynosi 2 wyrazeniem o najwiekszej wartosci jest 0,3 +(0,3 + 0,3) = 0,9. Należy znaleźć rozwiązanie dla n=21.
ktoś ma jakiś pomysł? niby możnaby policzyć każdą możliwość, ale to nam da 2^21 mozliwosci jesli dobrze kombinuje... może coś z programowaniem dynamicznym?
(0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3) * (0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3) = 9,9
taka mała uwaga - każdy czynnik musi być > 1 aby wynik rósł a nie malał więc zaczynasz od
(0,3 + 0,3 + 0,3 + 0,3) * (0,3 + 0,3 + 0,3 + 0,3) * (0,3 + 0,3 + 0,3 + 0,3) * (0,3 + 0,3 + 0,3 + 0,3) * (0,3 + 0,3 + 0,3 + 0,3 +0,3) = 3,1104
a potem dalej
1 operator więcej powinien być.
czyli ogólnie mówisz zeby sprawdzić każdą możliwość dla sum >1? no na pewno jest to juz spore uproszczenie w stosunku do sprawdzania kazdej mozliwosci :P ale ciagle wydaje mi sie ze mozna to zrobić na jakiś inny sposób. jak cos wymysle to napisze :)
myślę, że
(0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3+0,3) * (0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3) = 10,89
jest rozwiązaniem
no i jeszcze dla x i y < 2 x * y < x + y więc nie ma sensu mnożyć dwóch liczb mniejszych od 2 ale już np. 4 * 1,5 > 4 + 1,5
z tym, że cały czas twierdzę, że najwyższy wynik to będzie właśnie 10,89 z mojego (poprawionego) pierwszego równania
(0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3) * (0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3) = 10,89
suma samych 0,3 to 23 * 0,3 = 6,6
iloczyn dwóch równych sum to
(0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3) * (0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3) = 10,89
jeśli teraz chciałbyś to rozbić na iloczyn trzech, biorąc pod uwagę pierwsze twierdzenie, rozbijamy je na takie, żeby były > 2 co nam nie daje za dużo możliwości, bo pierwsza większa od 2 to 2,1 i składa się z sumy 7 0,3, czyli zostaje nam
(0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3) * (0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3) * (0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3) = 10,584
2 razy suma 7 i raz suma 8
dzieląc to inaczej
(0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3) * (0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3) * (0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3 + 0,3) = 10,206
czyli suma 6, 7 i 9
widzisz, że masz coraz mniejsze wyniki
Generalnie musisz dążyć do takiego momentu, kiedy iloczyn dwóch sum będzie większy od ich sumy i dodatkowo suma pozostałych liczb będzie conajmniej większa od 1
chyba nie pogubiłem nigdzie znaków :)
Można skorzystać z wzoru rekurencyjnego:
P(n)=Max(P(n-1)*P(1),P(n-2)*P(2),P(n-3)*P(3)...,P(n-1)+P(1),P(n-2)+P(2)...);
Przy czym założyłem że n oznacza ilość 0,3 w wyrażeniu a nieilość operatorów.
a dla wiekszych n z:
Dla n>31 i n mod 9 <6 wyrażenie bedzie się składało z pomnożonych sum 9 i 10 liczb 0,3.
Dla n>31 i n mod 9 >5 wyrażenie bedzie się składało z pomnożonych sum 8 i 9 liczb 0,3.
Mam głębokie przekonanie (chociaż, na razie, bez dowodu), że dla danej liczby a >0 (w pytaniu a=0,3) i danej liczby naturalnej n (w pytaniu n=22) największą wartość otrzymamy budując wyrażenie tak: (a+a+...+a)(a+a+...+a)...(a+a+...+a), ilość składników w każdym nawiasie jest "taka sama". Trzeba tylko ustalić ilość czynników k, rachunek różniczkowy prowadzi do wzoru
, wyliczona w ten sposób liczba k nie jest na ogół całkowita (w pytaniu k = 2,42800431173), trzeba ją zatem zastąpić przybliżeniem z dołu lub z góry.
Fajny problem.
Analizując go matematycznie, łatwo sprawdzić kiedy się opłaca dzielić sumę na iloczyn dwóch sum:
niech a będzie liczbą a n liczbą działań (nieparzystą by było prościej - dwie równe sumy w iloczynie), wtedy warunek opłacalności wygląda tak:
normalna suma < iloczyn sum
Ciąg operacji można dzielić kilkakrotnie mnożeniem, więc wygodniej jest rozwiązać tą nierówność względem n (przy czym wiadomo, że n musi być dodatnie) i wynik wygląda tak:
Czyli dla a =0,3 wartość graniczna od której opłaca się dzielić na pól sumę to 13.
Tak samo można rozwiązać problem od kiedy zamiast podziału na dwie sumy bardziej opłaca się dzielić na trzy sumy. Wychodzi:
Czyli dla 0,3 jest to zaczynając od n = 22
(tu też dla uproszenia założyłem, że n+1 jest podzielne przez trzy i powinno się sprawdzić co się dzieje dla innych przypadków, w szczególności co dla n=22).
Jak widać metoda brutal force nie ma ty uzasadnienia, wystarczy trochę niekomplikowanej analizy matematycznej.
Ogólnie podział na m iloczynów jest bardziej opłacalny niż na m-1 iloczynów, gdy:
@MarekR22, nie mam kartki pod ręka i nie mogę sprawdzić czy nasze wyniki sa równowazne, ale mam wrażenie że z mojego wzoru łatwiej wyznaczyć ilośc czynników k niz z twojego
.
mój wzór jest dokładniejszy, ale wygląda na to, że asymptotycznie jest to samo, szczególnie, że liczbę e definiuje się przez granicę ciągu (1+1/n)^n.