Pchełki Python: Euler I

https://xpil.eu/mxm79 📋

Dziś maleńka pchełka potrójna, pokazująca jak na wiele różnych sposobów można rozwiązać prosty problem matematyczny, w zależności od tego, jak dobrze się go rozumie.

Problemem będzie pierwszy problem z listy Project Euler, czyli - dla odmiany po ostatniej Pchełce - również sumowanie.

Tym razem nie sumujemy liczb pierwszych, tylko liczby podzielne przez 3 lub 5, mniejsze od 1000.

Wśród pierwszej dziesiątki takie liczby to 3, 5, 6 i 9, ich suma to 23. A ile wyjdzie, jak się posumuje wszystkie takie liczby od 0 do 999?

Najpierw rozwiązanie prymitywne, czyli po prostu sprawdzimy każdą liczbę, czy dzieli się przez 3 lub 5, i jeżeli tak, dodamy ją do wyniku, a jeżeli nie - pominiemy.

 

a, s = 1, 0
while a < 1000:
    if not(a % 3 and a % 5):
       s += a
    a += 1
print("Metoda 1: %1", s)

Jak widać, kod jest przejrzysty i nie ma tu za wiele do opowiadania. Może tylko szybki komentarz o tym, co dzieje się w trzeciej linii: if not (a%3 and a%5) to inaczej if not (a%3) or not (a%5) czyli innymi słowy if (a%3==0 or a%5==0). A więc sprawdzamy, czy liczba jest podzielna przez trzy lub pięć.

Spróbujmy teraz spojrzeć na zagadnienie w trochę bardziej inteligentny sposób: suma wszystkich liczb podzielnych przez trzy mniejszych od tysiąca to nic innego jak suma ciągu arytmetycznego zaczynającego się od trójki, kończącego na 999, o różnicy 3. Jak wiemy z podstawówki, sumę taka liczymy jako wartość elementu środkowego (czyli ostatni minus pierwszy przez dwa) przemnożona przez ilość elementów.

To samo działa dla piątki - trzeba zsumować elementy ciągu arytmetycznego zaczynającego się od piątki, kończącego na 995, o skoku 5.

Wynikiem będzie suma tych dwóch sum, pomniejszona o liczby, które dzielą się przez piętnaście (ponieważ są one wspólne dla obydwu ciągów, w związku z czym były liczone dwukrotnie, a więc trzeba je odjąć).

Kod wygląda, o, tak:

 

def suma_ciagu_arytm(pierwszy, ostatni, skok):
    return ((pierwszy + ostatni) * ostatni) // (2 * skok)

print("Metoda 2: %1", suma_ciagu_arytm(3, 999, 3) + suma_ciagu_arytm(5, 995, 5) - suma_ciagu_arytm(15,990,15))

Tutaj też nie ma zbyt wiele do opisywania, koń, jaki jest, każdy widzi. Definiujemy sobie funkcję, która wylicza sumę ciągu arytmetycznego o zadanym elemencie początkowym, końcowym oraz skoku, a następnie wywołujemy tę funkcję trzykrotnie.

Na koniec przedstawię jeszcze metodę opartą na arytmetyce zbiorów, czyli najbardziej "czystą" pod kątem matematycznym, a także najbardziej zwięzłą w zapisie:

s3, s5 = set(range(0,1000,3)), set(range(0,1000,5))
print("Metoda 3: %1", sum(s3.union(s5)))

W ostatniej metodzie mamy tylko dwie linie kodu: w pierwszej wyliczamy sobie zbiór wszystkich wielokrotności trójki (s3) oraz piątki (s5), a w drugiej sumujemy te dwa zbiory za pomocą operatora union (tutaj przy okazji eliminujemy duplikaty, czyli liczby podzielne przez piętnaście), a następnie wyznaczamy sumę arytmetyczną elementów tych zsumowanych zbiorów.

Wszystkie trzy metody zwracają tę samą wartość, czyli 233168. Google twierdzi, że to prawidłowa odpowiedź, mogę więc udać się na zasłużony odpoczynek...

... zanim jednak to zrobię, jeszcze tylko szybka zagadka: która z podanych metod jest najszybsza? A co, jeżeli zamiast tysiąca mielibyśmy milion, albo kwadrylion? Której metody powinniśmy użyć?

[yop_poll id="55"]

 

https://xpil.eu/mxm79 📋