Wpisany przez Dominik Goździuk,
24 października 2011 10:14
Liczba doskonała to liczba naturalna, która jest sumą wszystkich swych dzielników właściwych (to znaczy dzielników od niej mniejszych). Najmniejszą liczbą doskonałą jest 6, ponieważ jej dzielniki czyli liczby, które dzielą ją bez reszty to 3, 2 oraz 1, co daje nam 6 = 3 + 2 + 1. Następną jest 28 (28 = 14 + 7 + 4 + 2 + 1), a kolejne to 496, 8128, 33550336, 8589869056 i 137438691328.
Największą znaną dziś liczbą doskonałą parzystą jest 243112608 * (243112609-1) – liczy ona 25 956 377 cyfr w rozwinięciu dziesiętnym. Jak dotąd nie udało się znaleźć liczby doskonałej nieparzystej, ani dowodu, że liczby takie nie istnieją. Wiadomo też, że jeśli liczba taka istnieje, to musi być większa od 10300.
Metodę sprawdzania czy dana liczba x jest liczbą doskonałą można przedstawić następująco:
Taki sposób postępowania możemy zapisać następującym schematem blokowym:
Niech x będzie równe 5.
Na początku suma_dzielnikow = 0 oraz i = 1.
Sprawdzamy czy 1 <= 5/2?
Tak, a więc przechodzimy do decyzji czy 5 mod 1 = 0?
Tak, reszta z dzielenia 5 przez 1 wynosi 0, a więc do zmiennej suma_dzielnikow dodajemy 1, a więc suma_dzielnikow = 1.
Zwiększamy i o jeden, sprawdzamy czy 2 <= 5/2?
Tak, a więc przechodzimy do decyzji czy 5 mod 2 = 0?
Nie, reszta z dzielenia 5 przez 2 wynosi 1.
Zwiększamy i o jeden, sprawdzamy czy 3 <= 5/2?
Nie, a więc przechodzimy do sprawdzenia czy x oraz suma_dzielnikow są sobie równe. 5 nie jest równe 1, a więc liczba 5 nie jest liczbą doskonałą.
Niech x będzie teraz równe 6.
Na początku suma_dzielnikow = 0 oraz i = 1.
Sprawdzamy czy 1 <= 6/2?
Tak, a więc przechodzimy do decyzji czy 6 mod 1 = 0?
Tak, reszta z dzielenia 6 przez 1 wynosi 0, a więc do zmiennej suma_dzielnikow dodajemy 1, a więc suma_dzielnikow = 1.
Zwiększamy i o jeden, sprawdzamy czy 2 <= 6/2?
Tak, a więc przechodzimy do decyzji czy 6 mod 2 = 0?
Tak, reszta z dzielenia 6 przez 2 wynosi 0, a więc do zmiennej suma_dzielnikow dodajemy 2, a więc suma_dzielnikow = 3.
Zwiększamy i o jeden, sprawdzamy czy 3 <= 6/2?
Tak, a więc przechodzimy do decyzji czy 6 mod 3 = 0?
Tak, reszta z dzielenia 6 przez 3 wynosi 0, a więc do zmiennej suma_dzielnikow dodajemy 3, a więc suma_dzielnikow = 6.
Zwiększamy i o jeden, sprawdzamy czy 4 <= 6/2?
Nie, a więc przechodzimy do sprawdzenia czy x oraz suma_dzielnikow są sobie równe. 6 jest równe 6, a więc liczba 6 jest liczbą doskonałą.
Załóżmy, że chcemy znaleźć trzy pierwsze liczby doskonałe. Tworzymy pustą tablicę 3-elementową oraz zmienne: znalezione (przechowuje ilość znalezionych liczb doskonałych), x (bieżąca liczba którą sprawdzamy), suma_dzielnikow (przechowuje sumę dzielników bieżącej liczby). Wchodzimy do pętli, która sprawdza czy liczba znalezionych liczb doskonałych jest mniejsza od 3. Jeżeli warunek został spełniony, sprawdzamy czy wszystkie liczby od 1 do liczby bieżącej podzielonej przez 2, są dzielnikami naszej liczby bieżącej. Jeżeli tak dodajemy tę liczbę do sumy dzielników. Na koniec sprawdzamy czy suma dzielników jest równa liczbie bieżącej, jeśli tak, dodajemy ją do tablicy i powiększamy zmienną znalezione.
Pseudokod ma zatem następującą postać:
Największą znaną dziś liczbą doskonałą parzystą jest 243112608 * (243112609-1) – liczy ona 25 956 377 cyfr w rozwinięciu dziesiętnym. Jak dotąd nie udało się znaleźć liczby doskonałej nieparzystej, ani dowodu, że liczby takie nie istnieją. Wiadomo też, że jeśli liczba taka istnieje, to musi być większa od 10300.
Metodę sprawdzania czy dana liczba x jest liczbą doskonałą można przedstawić następująco:
- ustaw zmienną suma_dzielników na 0,
- dla każdej liczby i od 1 do zaokrąglonego w dół x/2:
- sprawdzaj czy jest ona dzielnikiem liczby x. Jeśli tak do suma_dzielnikow dodaj i,
- jeśli suma_dzielnikow jest równa x, to x jest liczbą doskonałą.
Taki sposób postępowania możemy zapisać następującym schematem blokowym:

Przykład:
Niech x będzie równe 5.
Na początku suma_dzielnikow = 0 oraz i = 1.
Sprawdzamy czy 1 <= 5/2?
Tak, a więc przechodzimy do decyzji czy 5 mod 1 = 0?
Tak, reszta z dzielenia 5 przez 1 wynosi 0, a więc do zmiennej suma_dzielnikow dodajemy 1, a więc suma_dzielnikow = 1.
Zwiększamy i o jeden, sprawdzamy czy 2 <= 5/2?
Tak, a więc przechodzimy do decyzji czy 5 mod 2 = 0?
Nie, reszta z dzielenia 5 przez 2 wynosi 1.
Zwiększamy i o jeden, sprawdzamy czy 3 <= 5/2?
Nie, a więc przechodzimy do sprawdzenia czy x oraz suma_dzielnikow są sobie równe. 5 nie jest równe 1, a więc liczba 5 nie jest liczbą doskonałą.
Niech x będzie teraz równe 6.
Na początku suma_dzielnikow = 0 oraz i = 1.
Sprawdzamy czy 1 <= 6/2?
Tak, a więc przechodzimy do decyzji czy 6 mod 1 = 0?
Tak, reszta z dzielenia 6 przez 1 wynosi 0, a więc do zmiennej suma_dzielnikow dodajemy 1, a więc suma_dzielnikow = 1.
Zwiększamy i o jeden, sprawdzamy czy 2 <= 6/2?
Tak, a więc przechodzimy do decyzji czy 6 mod 2 = 0?
Tak, reszta z dzielenia 6 przez 2 wynosi 0, a więc do zmiennej suma_dzielnikow dodajemy 2, a więc suma_dzielnikow = 3.
Zwiększamy i o jeden, sprawdzamy czy 3 <= 6/2?
Tak, a więc przechodzimy do decyzji czy 6 mod 3 = 0?
Tak, reszta z dzielenia 6 przez 3 wynosi 0, a więc do zmiennej suma_dzielnikow dodajemy 3, a więc suma_dzielnikow = 6.
Zwiększamy i o jeden, sprawdzamy czy 4 <= 6/2?
Nie, a więc przechodzimy do sprawdzenia czy x oraz suma_dzielnikow są sobie równe. 6 jest równe 6, a więc liczba 6 jest liczbą doskonałą.
Załóżmy, że chcemy znaleźć trzy pierwsze liczby doskonałe. Tworzymy pustą tablicę 3-elementową oraz zmienne: znalezione (przechowuje ilość znalezionych liczb doskonałych), x (bieżąca liczba którą sprawdzamy), suma_dzielnikow (przechowuje sumę dzielników bieżącej liczby). Wchodzimy do pętli, która sprawdza czy liczba znalezionych liczb doskonałych jest mniejsza od 3. Jeżeli warunek został spełniony, sprawdzamy czy wszystkie liczby od 1 do liczby bieżącej podzielonej przez 2, są dzielnikami naszej liczby bieżącej. Jeżeli tak dodajemy tę liczbę do sumy dzielników. Na koniec sprawdzamy czy suma dzielników jest równa liczbie bieżącej, jeśli tak, dodajemy ją do tablicy i powiększamy zmienną znalezione.
Pseudokod ma zatem następującą postać:
- Utwórz pustą tablicę 3-elementową
- Utwórz zmienną znalezione i nadaj jej wartość 0
- Utwórz zmienną x i nadaj jej wartość 1
- Utwórz zmienną suma_dzielnikow i nadaj jej wartość 0
- Dopóki znalezione < 3:
- Sprawdź każdą liczbę od i = 1 do (x/2) czy jest ona dzielnikiem liczby x. Jeśli tak do suma_dzielnikow dodaj i.
- Jeśli suma_dzielnikow jest równa x, dodaj x do tablicy, do znalezione dodaj 1
- Do x dodaj 1, wyzeruj zmienną suma_dzielnikow.
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Dominik Goździuk | C/C++ | C++ | .cpp | .cpp | ***** / 21 |
Dominik Goździuk | Java | .java | .java | ***** / 4 |
Poprawiony: 30 stycznia 2013 22:38