Strona główna » Algorytmy » Teoria Liczb » Liczby Praktyczne
 

Liczby Praktyczne

Opis Liczb

Liczba Praktyczna n to taka liczba naturalna dla której wszystkie liczby naturalne mniejsze od niej samej można uzyskać jako sumę dowolnych dzielników właściwych liczby n. W trakcie sumowania wybrany dzielnik można dodać tylko raz.

Przykład

Liczbą Praktyczną jest 12, ponieważ dzielniki właściwe tej liczby to: {1, 2, 3, 4, 6}. Kolejne wartości mniejsze od 12 można uzyskać następująco:

LiczbaSuma
11
22
33 lub 2 + 1
44 lub 3 + 1
54 + 1 lub 3 + 2
66 lub 4 + 2 lub 3 + 2 + 1
74 + 3 lub 4 + 2 + 1 lub 6 + 1
86 + 2 lub 4 + 3 + 1
96 + 3 lub 6 + 2 + 1 lub 4 + 3 + 2
106 + 4 lub 4 + 3 + 2 + 1
116 + 4 + 1 lub 6 + 3 + 2

Uwaga

Jedyną nieparzystą liczbą Praktyczną jest 1. Jest to spowodowane faktem, że każda liczba nieparzysta ma tylko nieparzyste dzielniki. Z tego powodu nie jest możliwe uzyskanie sumy 2 dla każdej liczby nieparzystej.

Implementacja

Strategia

Na początku algorytm może odrzucić wszystkie liczby nieparzyste prócz 1. Jednak dla liczb parzystych na początek należałoby zebrać wszystkie dzielniki właściwe liczby. Następnie w pętli dla każdej mniejszej wartości od zadanej liczby sprawdzimy czy można zsumować dzielniki do tej wartości.

Podczas sumowania należy pamiętać, że należy sumować najpierw jak największe wartości, a potem coraz mniejsze. Dzięki temu zagwarantowane jest znalezienie odpowiedzi czy taka suma istnieje w czasie liniowym. Gdyby sumować od najmniejszych wartości póki można to mogłoby się okazać, że nie ma już możliwości dodania większego dzielnika.

Kod

Przedstawiona funkcja czyPraktyczna() sprawdza czy podana liczba a jest liczbą Praktyczną, a wynikiem jest wartość logiczna.

C++
C#
  1. bool czyPraktyczna(int a) {
  2.   if (a == 1)
  3.     return true;
  4.   if (a % 2 == 1)
  5.     return false;
  6.   vector<int> v;
  7.   for (int i = a / 2; i >= 1; i--) {
  8.     if (a % i == 0) {
  9.       v.push_back(i);
  10.     }
  11.   }
  12.   for (int i = a - 1; i >= 2; i--) {
  13.     int k = i;
  14.     for (int j = 0; j < v.size(); j++) {
  15.       if (v[j] <= k) {
  16.         k -= v[j];
  17.       }
  18.     }
  19.     if (k != 0) {
  20.       return false;
  21.     }
  22.   }
  23.   return true;
  24. }

(2. - 6.) Na początku algorytmu eliminowane są przypadki, gdy a jest nieparzyste. Następnie (7. - 12.) generowana jest lista dzielników właściwych a. Dzielniki są zapisywane od największego do najmniejszego. Ostatni etap polega na (13. - 23.) znalezieniu takiego i, aby nie można było do tej wartości wysumować dzielników właściwych. W każdej iteracji k jest przypisywana wartość do wysumowania. Potem dla każdego dzielnika o ile jest mniejszy od aktualnej wartości k to jest on odejmowany od k. Jeśli na koniec k jest różne od 0 oznacza to, że danej wartości nie można uzyskać.

Testowanie funkcji

Poniższy fragment kodu wypisuje wszystkie liczby Praktyczne z zakresu [1, 100]

C++
C#
  1. int main () {
  2.   for (int i = 1; i < 100; i++) {
  3.     if (czyPraktyczna(i)) {
  4.       cout << i << " ";
  5.     }
  6.   }
  7.   system("pause");
  8.   return 0;
  9. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1