Weźmy wszystkie liczby naturalne mniejsze od 10, które są wielokrotnościami liczb 3 lub 5. Otrzymamy liczby: 3, 5, 6, 9. Ich suma wynosi 25. Znajdź sumę wielokrotności liczb 3 lub 5 mniejszych od 1000.
Najprostszy z możliwych algorytm powinien sprawdzić wszystkie liczby z podanego zakresu oraz zsumować tylko te, które są wielokrotnościami liczb 3 lub 5.
/** * Projekt Euler - Problem nr 1 * @author kodatnik.blogspot.com */ public class PEProblem1 { public static void main(String args[]) { // zmienna przechowująca sumę int suma = 0; // pętla dla liczb naturalnych mniejszych od 1000 (zaczynamy od 3) for(int i = 3; i < 1000; i++) // jeśli liczba jest podzielna przez 3 lub 5 dodajemy ją do sumy if((i % 3 == 0) || (i % 5 == 0)) suma += i; //wyświetlamy wynik System.out.println("Suma wynosi: " + suma); } }Otrzymany wynik to:
Suma wynosi: 233168Pozostaje kwestia optymalizacji algorytmu. Czy można prościej, szybciej? Oczywiście. Pytanie tylko czy dla górnego zakresu (1000) jest to opłacalne?
10 Komentarzy - Projekt Euler - Problem numer 1
Witam,
Powyższe rozwiązanie można rozwiązać w minutę na kartce papieru (a nawet w pamięci). Wystarczy podstawowa znajomość ciągów arytmetycznych i 'zasady włączeń i wyłączeń'.
Jeśli ktoś zechce napisać to w javie może zrobić to tak:
===============================================
// zmienna przechowująca sumę
int suma = 0;
int liczba;
int najwiekszy;
//dla 3
liczba = (1000-1)/3;
najwiekszy = liczba*3;
suma += (3+najwiekszy)*liczba/2;
//dla 5
liczba = (1000 -1)/5;
najwiekszy = liczba*5;
suma += (5+najwiekszy)*liczba/2;
//dla 15
liczba = (1000 -1)/15;
najwiekszy = liczba*15;
suma -= (15+najwiekszy)*liczba/2;
System.out.println("Suma to: " + suma);
===============================================
Zaletą tego rozwiązania jest oczywiście złożoność obliczeniowa.
Pozdrawiam,
Jacek Rutkowski
@Jacek: Jak najbardziej się z Tobą zgadzam, dlatego napisałem, że można prościej i szybciej :)
Całkowicie się zgadzam przy czym jak uważacie, czy drobna zmiana kosmetyczna może choć o ciut przyspieszyć algorytm:
zamiast używać konstrukcji:
liczba = (999)/3;
najwiekszy = liczba*3;
dać:
najwiekszy = 999 - 999%3
pozdrawiam,
Mateusz Cieślak
3 + 5 + 6 + 9 = 23 a nie 25
Mamy tu oczywiście dwa ciągi arytmetyczne:
c1 = 5 + 10 + 15 ...
c2 = 3 + 6 + 9 + ...
czyli dla liczb mniejszych od n = 10^p i p = 3 będzie to:
p = 3;
n = 10 ^ p;
s1 = ((5 + (n - 5)) * (n / 5 - 1)) / 2;
s2 = ((3 + (n - 1)) * (n-1) / 3) / 2;
Wczoraj oczywiście zapomniałem jeszcze o jednym ciągu, którego sumę trzeba odjąć od (S1 + S2):-)
S3 = 15 + 30 + 45 + … + N - 10
Ostateczenie po skróceniu otrzymujemy wzór:
Dla p <= 1, 2, 3, …
n = 10 ^ p
S = (7 * n^2 - 5 * n + 40) / 30;
Co do pytania o opłacalność to liczenie sumy ze wzoru jest około 1 500 razy szybsze od algorytmu naiwnego.
super
Prześlij komentarz
Możesz użyć niektórych tagów HTML, takich jak <b>, <i>, <u>, <a> Nie spamuj :)