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.