BartoIT Blog

Dziś prezentacja kolejnego algorytmu. Tym razem będziemy sprawdzać, czy podana liczba jest liczbą doskonałą.Dziś zaprezentuję Ci najprostsze rozwiązanie problemu, które może przyprawić Twój komputer, bądź Twojego profesora o siódme poty.Ale czasem z naszego algorytmu zrobimy ferrari pod kątem prędkości w swojej dziedzinie. Pytanie, czy da się prościej i szybciej? Na pewno. Nie rozpisując się dłużej przejdźmy do działania.

Najpierw trochę teorii.

O liczbie możemy powiedzieć, że jest doskonała jeżeli suma jej dzielników, bez niej samej jest sobie równa. W praktyce wygląda to mniej więcej tak…

1. Wybierzmy dowolną liczbę naturalną – dla przykładu wybieram 6, bo jest to pierwsza z liczb doskonałych.
2. Wypisujemy jej dzielniki:
dla 6 to odpowiednio : {1,2,3,6}
3. Sprawdzamy, czy jest doskonała.
Czy 1+2+3=6 ? – Tak, a więc 6 jest liczbą doskonałą.

 

Frontalny atak na zadanie

My widząc liczbę już mniej więcej wiemy jakie kroki podjąć i które mniejsze są dzielnikami. Pisząc jednak algorytm nie jesteśmy w stanie przewidzieć zadanej wartości, więc oczywistym sposobem wydaje się toporne sprawdzanie, które z liczb naturalnych dadzą resztę z dzielenia 0.Wyglądałoby to mniej więcej tak:

1.Wybierz liczbę dowolną naturalną n.
– określmy licznik, jako x, ,
2.Dopóki x<n-1 sprawdź, czy n 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, że „n jest liczbą doskonałą”, w innym wypadku napisz „n nie jest liczbą doskonała”.

Powoli do skutku można dojść tym sposobem, dla 5, 9, 15, 29, może 56, a nawet 100, czy 1000 – muszę kiedyś sprawdzić na swojej maszynie. Swoją drogą załączam kod algorytmu, o którym wspominałem.

Algorytm w C++

#include <iostream>
#include <cstdlib>

using namespace std;

int n, p;
bool czy(int n);

int main()
{
&nbsp; &nbsp; cin >> n;
&nbsp; &nbsp; if(czy(n)==1)
&nbsp; &nbsp; &nbsp; &nbsp; cout << "tak" << endl;
&nbsp; &nbsp; else
&nbsp; &nbsp; &nbsp; &nbsp; cout << "nie" << endl;


&nbsp; &nbsp; system("PAUSE");
&nbsp; &nbsp; return 0;
}
bool czy(int n)
{
&nbsp; &nbsp; for(int x=2; x < n; x++)
&nbsp; &nbsp; {
&nbsp; &nbsp; &nbsp; &nbsp; if(n%x == 0)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; p=p+x;

&nbsp; &nbsp; }
&nbsp; &nbsp; if(n==p)return 1;
}