Dziś drugi problem z listy Eulera, czyli dla odmiany posumujemy sobie trochę liczb całkowitych. Podobnie zresztą jak w poprzedniej Pchełce, gdzie sumowaliśmy wielokrotności trójek i piątek, oraz w jeszcze poprzedniej, gdzie z kolei sumowaliśmy liczby pierwsze.
Dziś posumujemy sobie wyrazy ciągu Fibonacciego, ale tylko te parzyste.
A po cholerę? Zamiast tego moglibyśmy na przykład pójść na piwo…
Z tym, że akurat autor tego bloga nie pije piwa w ilościach większych niż pół na kwartał. A co, jak szaleć, to szaleć…
Dlatego właśnie będziemy dziś sumować parzyste wyrazy ciągu Fibonacciego, a jak się komuś to nie podoba, to niech sobie idzie pooglądać obrady Sejmu. Zapewniam, że są o wiele bardziej emocjonujące.
Starczy tego pseudohumoru, weźmy się do rzeczy…
Najpierw, jak to zwykle bywa, podejście prymitywne. A więc prościutki generator kolejnych wyrazów ciągu Fibonacciego…
nie chce mi się pisać całego tego włoskiego nazwiska, bo jest długie, więc będę pisał “ciąg F” albo po prostu “F”
… Fibon…, znaczy, tego, F, posprawdzamy które z nich są parzyste i te posumujemy. O, tak:
def fib_gen():
a, b = 0, 1
while 1:
yield a
a, b = b, a + b
s = 0
for f in fib_gen():
if not(f % 2):
s = s + f
if(f > 4000000):
break
print(s)
Na wyjściu otrzymałem wartość 4613732, Wujek G twierdzi, że się zgadza, a więc oklaski, kurtyna…
… albo nie, spróbujmy jeszcze troszkę to usprytnić:
def fib_gen():
a, b = 2, 3
while 1:
yield a
a, b = b, a + b
a, b = b, a + b
a, b = b, a + b
s = 0
for f in fib_gen():
if(f > 4000000):
break
s = s + f
print(s)
Cóż, do licha? Takie pytanie powinien sobie postawić zaniepokojony Czytelnik, gdyby którykolwiek dotarł aż tutaj. Dlaczego, do diaska, nie sprawdzamy parzystości kolejnych wyrazów, tylko sumujemy jak leci? A dlaczego fib_gen() zawiera teraz tą samą linijkę trzy razy? Czyżby się ktoś pomylił i zrobił za dużo ^C – ^V?
Otóż – nie. Skoro wynik wychodzi poprawny, to znaczy, że kod też jest poprawny. A dlaczemu?
No dlatemu, że w ciągu F co trzeci wyraz jest parzysty. A zagadka mówi wyraźnie: podać sumę wszystkich PARZYSTYCH liczb z tego ciągu, mniejszych bądź równych czterem milionom.
A czemu co trzeci wyraz jest parzysty?
Proszę sobie na spokojnie spojrzeć na ciąg F i samemu wywnioskować, dlaczego tak jest. Obiecuję, że olśnienie nadejdzie w czasie krótszym, niż czas potrzebny na przeliterowanie Chrzęskrzyboczka Pacionkociewiczarokrzysztofonicznego pięć centygigaheptatrybilionardów razy. Czyli praktycznie od razu.
Bardzo dzisiejsza Pchełka jest prościutka. Smacznego…
Na zakończenie podam rozwiązanie zagadki z poprzedniej Pchełki – otóż, oczywiście, poprawną odpowiedzią jest metoda 2 – ponieważ tylko w tej metodzie ilość operacji potrzebnych do uzyskania wyniku jest stała w czasie, niezależnie od tego, czy sumujemy do miliona, kwadryliona czy supercentygigaheptatrybilionarda do kwadratu.
Poprawnej odpowiedzi udzieliło 50% wszystkich biorących udział w ankiecie – niestety, tym razem nie przewidziałem żadnych nagród, a więc pozostaje tylko dzika satysfakcja. Gratuluję!
I dobranoc.