algorytm.org

Liczby doskonałe

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Liczby doskonałe
Ocena użytkowników:***** / 34
SłabyŚwietny 
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:

schemat blokowy - liczba doskonała


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ć:

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Dominik GoździukC/C++C++
.cpp
.cpp
***** / 19
Dominik GoździukJava
.java
.java
***** / 4
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 30 stycznia 2013 22:38
Dodaj komentarz