Pchełki Python: Euler I

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″]

 

Autor: xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a'capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

Bądź pierwszy!

Powiadom o
avatar
wpDiscuz