Pchełki Python: Euler II

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.