Zagadkę o liczbie 711 podrzucił mi Rozie - i u niego należy szukać rozwiązania. O ile mi wiadomo planowanych jest kilka wpisów, pierwszy tutaj:
Rozwiązaniem zagadki - przy założeniu, że szukamy "idealnego" wyniku (tj. bez zaokrągleń) - są kwoty 1.20, 1.25, 1.50 i 3.15.
Do zagadki podeszło dwóch Czytelników: Waldek po prostu podał rozwiązanie bez ujawniania drogi do niego, natomiast Canthar poza wynikiem pokazał również kod w Pythonie, którego użył do wyszukania powyższej czwórki. Kod jest wcale niegłupi, opiera się na rozkładzie liczby 711 na czynniki pierwsze. (Myślę, że Rozie będzie miał tu więcej do powiedzenia / napisania w ramach swojej serii o optymalizacji). A oto kod Canthara (czas wykonania: poniżej 1s):
import itertools
number = 711
divisors = list()
for i in range(1, number + 1):
if number * 1000000 % i == 0:
divisors.append(i)
for i in itertools.combinations_with_replacement(divisors, 4):
if sum(i) == number and i[0] * i[1] * i[2] * i[3] == number * 1000000:
print(i)Rozwiązań "nieidealnych" według Waldka jest trochę ponad 1300 jeżeli przyjmiemy, że kalkulator zaokrągla wynik mnożenia do najbliższej całości, oraz sporo więcej jeżeli po prostu obcina ostatnią cyfrę (zamiast zaokrąglać).
Można jeszcze założyć, że kalkulator ma uszkodzone niektóre segmenty, wtedy robi się jeszcze ciekawiej, ale w ten sposób zaraz dojdziemy do wpływu neutrin na wynik mnożenia 😉
Tak czy siak, zainteresowanych dalszymi rozważaniami zapraszam na blog zakr.es.
Kod, a w zasadzie algorytm Canthara jest bardzo fajny. Z takim algorytmem (plus parę innych własności o których piszę u siebie) można to próbować policzyć na piechotę, w skończonym czasie. Bowiem dzielników 711 jest równo 62, łącznie z 1 i 711.
Więc jak niezupełnie planowałem serię wpisów, tak teraz zdecydowanie jest na nią materiał. 🙂
“Waldek po prostu podał rozwiązanie bez ujawniania drogi do niego”
Mój program był nieco dłuższy, gdyż przeczuwałem podstęp typowy dla zadań “sklepowych”, czyli zaokrąglanie wyniku do groszy (lub centów). Zrobiłem więc iteracje po kolejnych cyfrach, eliminując przy drugiej i następnych zbędne zakresy. Pozwoliło mi to uwzględnić zarówno wynik 7,105, jak i 7,114999999999 oraz, przy okazji, zliczyć liczbę wszystkich wyników z tego zakresu. Kod zajmuje trochę miejsca, więc go pominąłem. Czas obliczeń to ok. 0,3 sekundy.
Ale w zadaniu podstępu nie było, więc wygląda na to, że podszedłem do niego zbyt poważnie, czyli wygłupiłem się.
Po namyśle: w zadaniu sklepowym nie było podstępu, więc nie było poważne, czyli wygłupiło się.