Strona główna » Algorytmy » Artykuły » Złożoność Liczby
 

Złożoność Liczby

Definicja

Złożoność liczby a to taka liczba, która określa z ilu minimalnie jedynek można utworzyć liczbę a poprzez dodawanie, mnożenie oraz używanie nawiasów. Inne operacje są niedozwolone.

Przykład

Liczba 1 ma złożoność 1, ponieważ 1 = 1. Z kolei liczba 2 = 1 + 1, więc ma złożoność 2. Bardziej złożonym przypadkiem jest liczba 7. Można ją zapisać jako 7 = 1 + 1 + 1 + 1 + 1 + 1 + 1, ale można tu zastosować mnożenie w celu ograniczenia liczby 1 w zapisie liczby 7. Otóż 7 = 6 + 1 = (1 + 1)·(1 + 1 + 1) + 1, więc faktyczna złożoność liczby 1 wynosi 6.

Ciąg liczb

Dla kolejnych liczb naturalnych złożoności tworzą następujący ciąg: 1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, ...

Wyznaczanie najmniejszego rozkładu

Liczba ma najmniejszy rozkład kiedy operator mnożenia zostanie użyty największą ilość razy, ponieważ zastępuje on wiele operatorów dodawania. Istnieją dwa typy liczb: złożone, które można zapisać jako iloczyn liczb pierwszych oraz liczby pierwsze, które nie mają żadnego dzielnika prócz 1 i samej siebie. Innymi słowy na początek rozkładamy liczbę złożoną na jej czynniki pierwsze. Następnie każdy czynniki, który jest liczbą pierwszą zmniejszamy o 1 i rozkładamy na czynniki pierwsze. Proces ten można powtarzać dopóki nie otrzymamy samych wartości 1.

Przykład 1

Weźmy liczbę 33. Postaramy się dla niej znaleźć minimalny rozkład na liczby 1. Otóż:

33 = 3·11 = (2 + 1)·(10 + 1)
= (1 + 1 + 1)·(2·5 + 1)
= (1 + 1 + 1)·((1 + 1)·(4 + 1) + 1)
= (1 + 1 + 1)·((1 + 1)·(2·2 + 1) + 1)
= (1 + 1 + 1)·((1 + 1)·((1 + 1)·(1 + 1) + 1) + 1)

Teraz zliczając kolejne wartości 1 otrzymujemy złożoność liczby, która wynosi 11.

Przykład 2

Dla liczb, które są potęgami 2 zadanie znalezienie rozkładu na najmniejszą liczbę 1 jest zadaniem prostszym, ponieważ bardzo szybko można uzyskać rozkład na czynniki pierwsze. Otóż:

16 = 2·2·2·2 = (1 + 1)(1 + 1)(1 + 1)(1 + 1)

Zliczając kolejne wartości 1 otrzymujemy złożoność liczby, która wynosi 11.

Implementacja

Zadanie

Napisz funkcję generujCiag(), która przyjmie jeden argument n. Funkcja powinna zwrócić tablicę w której będzie znajdować się n kolejnych złożoności dla n pierwszych liczb naturalnych.

Strategia

W celu wyznaczenia kolejnej złożoności liczby można skorzystać z rozkładu poprzednich liczb. Otóż jeśli znamy rozkład liczby 2 = 1 + 1 oraz 3 = 1 + 1 + 1 to po zamianie otrzymamy 6 = 2·3 = (1 + 1)(1 + 1 + 1). Oznacza to, że wystarczy zachować poprzednie rozkłady, aby po zapisaniu liczby na czynniki pierwsze otrzymać złożoność kolejnej liczby. Oczywiście należy wyszczególnić tu przypadek liczby pierwszej, ponieważ rozkład liczby pierwszej p na 1·p powodowałby nieskończone wykonywanie kodu.

Rozwiązanie

W celu wyznaczenia rozkładu liczby a na iloczyn czynników wystarczy znaleźć jakikolwiek dzielnik d. Wtedy iloczyn wynosi a = (a/d)·d. Taka metoda oczywiście zadziała w przypadku, gdy liczba jest złożona. W przypadku, gdy natrafimy na liczbę pierwszą to za przyjmuje, że jej złożoność to złożoność liczby a - 1 powiększona o 1. Takie rozwiązanie zostało zaimplementowane w poniższej funkcji generujące szukaną tablice:

C++
C#
  1. int* generujCiag(int n) {
  2.   int* dane = new int[n + 1];
  3.   dane[0] = 1;
  4.   for (int i = 1; i <= n; i++) {
  5.     int a = i + 1, ile = 0;
  6.     int dzielnik = 2;
  7.     while (a % dzielnik != 0 && dzielnik <= sqrt(a))
  8.       dzielnik++;
  9.     if (dzielnik > sqrt(a)) {
  10.       a--;
  11.       ile = dane[a - 1] + 1;
  12.     } else {
  13.       ile += dane[dzielnik - 1];
  14.       ile += dane[a / dzielnik - 1];
  15.     }
  16.     dane[i] = ile;
  17.   }
  18.   return dane;
  19. }

(2.) Deklarujemy tablicę wynikową i (3.) przyjmujemy, że dla liczby 1 złożoność jest równa 1. Tutaj należy pamiętać, że pod indeksem 0 jest złożoność liczby 1. To będzie bardzo ważne, ponieważ w celu pobrania zapisanego rozkładu liczby a należy wiedzieć, że wartość w tablicy leży na pozycji a - 1. Następnie (3.) dla każdej kolejnej liczby naturalnej: (4.) określ liczbę a oraz zadeklaruj zmienną ile, która pomoże zliczyć łaczną złożoność. Później w pętli (5. - 7.) znajdź jakikolwiek dzielnik liczby a. Tutaj należy pamiętać, żeby (6.) ograniczyć wyszukiwanie, bo a może być liczbą pierwszą.

W dalszej części kodu (7.) na podstawie wartości dzielnika, albo wykonujemy (8. - 9.) część, gdy a jest pierwsze, albo (11. - 12.) przypadek, gdy a ma jakikolwiek dzielnik. W obu przypadkach nie rozbijamy czynników dalej, ponieważ zznamy już dla nich konkretną złożoność, więc nie ma takiej potrzeby. Na koniec każdej iteracji należy (14.) dopisać znalezioną złożoność. Zwracana wartość (16.) to oczywiście zadeklarowana na samym początku tablica.

Testowanie funkcji

W celu przetestowania napisanej funkcji można posłużyć się poniższym kodem. Program wczytuje od użytkownika ile pierwszych liczb ciągu złożoności liczb ma zostać wypisanych.

C++
C#
  1. int main() {
  2.   int n;
  3.   cout << "Podaj jak dlugi ciag wygenerowac\n n = ";
  4.   cin >> n;
  5.   int* dane = generujCiag(n);
  6.   cout << "Oto " << n << " pierwszych wartosci:\n";
  7.   for (int i = 0; i < n; i++)
  8.     cout << dane[i] << " ";
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

Napisz program, który będzie wyznaczał złożoność liczby w sposób rekurencyjny. Przetestuj napisaną funkcję i porównaj złożoność algorytmu rekurencyjnego z napisanym wcześniej.