Projekt Euler - Problem numer 1

Projekt Euler (http://projecteuler.net) to strona internetowa zawierająca pokaźny zbiór (ponad 300) problemów obliczeniowych, do rozwiązania których potrzebny jest (w większości przypadków) komputer oraz dowolny język programowania. Rozwiązaniem każdego zadania jest wynik, który podajemy, aby sprawdzić czy nasz sposób obliczeń jest poprawny. Oczywiście sednem zabawy jest opracowanie odpowiedniego dla danego problemu algorytmu. Przyjrzyjmy się zatem pierwszemu zadaniu.

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: 233168
Pozostaje 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

Anonimowy pisze...

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

Devon pisze...

@Jacek: Jak najbardziej się z Tobą zgadzam, dlatego napisałem, że można prościej i szybciej :)

Mateusz Cieślak pisze...

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

DKnoto pisze...

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;

DKnoto pisze...

Wczoraj oczywiście zapomniałem jeszcze o jednym ciągu, którego sumę trzeba odjąć od (S1 + S2):-)

S3 = 15 + 30 + 45 + … + N - 10

DKnoto pisze...

Ostateczenie po skróceniu otrzymujemy wzór:

Dla p <= 1, 2, 3, …
n = 10 ^ p

S = (7 * n^2 - 5 * n + 40) / 30;

DKnoto pisze...
Ten komentarz został usunięty przez autora.
DKnoto pisze...
Ten komentarz został usunięty przez autora.
DKnoto pisze...

Co do pytania o opłacalność to liczenie sumy ze wzoru jest około 1 500 razy szybsze od algorytmu naiwnego.

Anonimowy pisze...

super

Prześlij komentarz

Możesz użyć niektórych tagów HTML, takich jak <b>, <i>, <u>, <a> Nie spamuj :)

Popularne posty