BartoIT Blog

W poprzednim wpisie udało nam się dotrzeć do sukcesu po najmniejszej najkrótszej linii oporu. Dziś dalej będziemy sprawdzać, czy liczba, którą zaproponujemy jest liczbą doskonałą – tym razem jednak mając gotowy kod i wyciągając z niego jak i samego algorytmu kolejne nowe wnioski postaramy się poprawić wydajność.

Idąc drastycznie w oszczędność

No to moglibyśmy pisać jak masochista wszystko nieprzejrzyście, byle zaoszczędzić miejsce na ekranie. Jednak skupmy się teraz tylko na tym w jaki sposób dochodzimy do wyniku.

Aktualny algorytm sprawdza n-3 wyrazów, czy faktycznie dzielą bez reszty naszą liczbę n. Zdecydowanie marnujemy nasze zasoby i czas. Pierwszym postanowieniem będzie
ograniczenie ilości wykonywanych obliczeń i porównań

Próba 1 – ograniczenie przez grupy

Mamy w zasadzie dwie grupy liczb naturalnych w tym zadaniu – parzyste i nieparzyste.
Wiemy, że z dwóch nieparzystych otrzymamy parzystą po zsumowaniu ale parzyste niezależnie od wszystkiego zostają parzystymi – tak jakoś wyszło.

Zróbmy pewne grupowanie za pomocą liczb pierwszych.
Rób dopóki
n%2==0 , a n/2 zapisz w tablicy lub zmiennej
potem
Rób dopóki
n%3==0 , a n/3 zapisz w tablicy lub zmiennej
Rób dopóki
n%5==0 , a n/5 zapisz ………

I tak by można w nieskończoność, po liczbach pierwszych. Niestety nie tędy droga. Zamiast posługiwać się więc liczbami pierwszymi przyjrzyjmy się jeszcze raz algorytmowi, np dla 6.

6%1 == 6 r 0 ; p=1
6%2 == 3 r 0 ; p=2+1
6%3 == 2 r 0 ; p=3+2+1

Czy zauważyłeś, że rozwiązanie 6%2 daje nam najwyższy z możliwych dzielników w tym wypadku?
Przeszukując wikipedię w sprawie liczb doskonałych nie trafiłem na przykład liczby nieparzystej. Podobnie jest z innymi stronami www, które piszą coś odnośnie liczb doskonałych i sposobu ich obliczania. Wszędzie za przykłady podawane są liczby parzyste.
Zagłębiwszy się w lekturę na wikipedii odnajduję takie oto słowa

Jak dotąd nie udało się znaleźć liczby doskonałej nieparzystej, ani dowodu, że liczby takie nie istnieją. Euler udowodnił, że każda liczba doskonała nieparzysta musi być postaci , gdzie p jest liczbą pierwszą postaci 4m+1. Wiadomo też, że jeśli liczba taka istnieje, to musi być większa od 101500.

Wniosek – nie mamy się czego obawiać, jeżeli chodzi o egzamin maturalny, czy kolokwium.

– liczba musi być parzysta
– wynik działania n/2 da nam największy możliwy dzielnik

Właśnie w ten oto sposób dokonaliśmy wielkiego kroku milowego, jeżeli chodzi o poprawę wydajności naszego programu.Czas przebudować ciało funkcji. Schemat działania powinien wyglądać teraz tak.

1.Wybierzmy dowolną liczbę naturalną n
– określmy licznik jako x,
2.Sprawdź, czy n jest parzysta ( czy reszta z dzielenia przez parzystą liczbę daje 0 ).
– jeżeli tak
–Dopóki x>n/2 sprawdź, czy n/2 div x = 0 ( div reszta z dzielenia )
— jeżeli tak dodaj nam do tablicy x
— jeżeli nie biegnij dalej
3.Zsumuj wszystkie elementy tablicy
4.Jeżeli suma elementów tablicy jest równa n napisz „liczba n jest liczbą doskonała”;w innym wypadku napisz „n nie jest liczbą doskonała”.

Po modyfikacji nasz kod będzie wyglądał mniej więcej tak:

cin >> n;

if(n%2 == 0)
{
 for(int x=2;x>n/2 ; x++)
 if(n/2%x==0) p +=x;
 
 if(p==n) cout << "tak"
 else cout << "nie";
}
else cout << "nie";