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

Liczby Knutha

https://mattomatti.com/a55

Definicja

Liczby Knutha są opisywane następującą zależnością rekurencyjną:

Przyjmujemy, że K0 = 1. Wtedy dla

Kolejne liczby Knutha to: 1, 3, 3, 4, 7, 7, 7, 9, 9, 10, 13, ....

Implementacja

Napisanie programu polegającego na wyznaczaniu liczb Knutha jest dosłownym przetłumaczeniem zapisu ciągu rekurencyjnego na funkcję. Jednak przed przystąpieniem do tej części warto najpierw napisać funkcje min(), która będzie przyjmować dwie liczby całkowite a i b. Wynikiem działania funkcji będzie mniejsza liczba spośród podanych. Kod realizujący tę część:

  1. int min (int a, int b){
  2.   return (a < b) ? a : b;
  3. }

Warto jeszcze zwrócić uwagę na wzór funkcji: warto go tak zmienić, aby otrzymać wzór dla Kn:

Teraz możemy przystąpić do pisania funkcji głównej knuth(). Jako argument będzie przyjmować pojedynczą liczbę całkowitą n:

  1. int knuth(int n){
  2.   if(n == 0){
  3.     return 1;
  4.   } else {
  5.     return 1 + min (2 * knuth((n - 1) / 2), 3 * knuth((n - 1) / 3));
  6.   }
  7. }

Funkcja knuth() musi rozpatrzeć dwa przypadki: (3.) dla n = 0 oraz (5.) przeciwny przypadek n ≠ 0. O tym co należy zwrócić decyduje warunek w linijce (2.). W przypadku rekurencyjnego wywoływania funkcji knuth() nie trzeba się martwić o część ułamkową - jest ona obcinana w związku z typem zmiennej int.

k-wyrazów ciągu

Do wyznaczania k pierwszych liczb można zastosować pętle for:

  1. void knumbers(int k){
  2.   for(int i = 0; i < k; i++){
  3.     cout << knuth(i) << " ";
  4.   }
  5. }

Jednak tego typu rozwiązanie będzie miało niską wydajność. Dla każdej liczby wykonujemy obliczenia liczb wcześniejszych. Rozwiązaniem tego problemu byłoby zadeklarowanie dodatkowej tablicy w której będziemy przechowywać dotychczas wyliczone wyniki. Na podstawie zapisanych danych będziemy obliczać kolejne. Warto zauważyć, że n-ty wyraz polega na poprzednich wyrazach. Na tej podstawie można stwierdzić, że nie ma sensu deklarować tablicy długości k - wystarczy tylko połowa tej tablicy.

  1. void knumbers_faster(int k){
  2.   int* knuths = new int[k/2];
  3.   knuths[0] = 1;
  4.   cout << knuths[0] << " ";
  5.   for(int i = 1; i < k; i++){
  6.     if(i < k / 2){
  7.       knuths[i] = 1 + min (2 * knuths[(i - 1) / 2], 3 * knuths[(i - 1) / 3]);
  8.       cout << knuths[i] << " ";
  9.     } else {
  10.       cout << 1 + min (2 * knuths[(i - 1) / 2], 3 * knuths[(i - 1) / 3]) << " ";
  11.     }
  12.   }
  13.   delete[] knuths;
  14. }

(2.) Alokujemy pamięć pod tablice. (3.) Przypisujemy pierwszemu wyrazowi wartość 1. i (4.) go wypisujemy. (5.) Dla każdego następnego wyrazu dla i = 1, 2, ..., k: (6.) sprawdzamy czy trzeba zapisać. Jeśli tak to (7.) wyliczamy nową wartość i zapisujemy do tablicy. Potem pozostaje tylko (8.) wypisać wartość. Jeśli jednak liczby nie zapisujemy to (10.) wypisujemy tylko wyliczoną wartość. (13.) Przed zakończeniem funkcji zwalniamy zarezerwowaną pamięć.

Tego typu rozwiązanie może okazać się niestabilne dla bardzo dużych wartości. Jest to związane z limitem pamięci. Od pewnych wartości k należołoby użyć do poprzedniej wersji funkcji, która choć będzie obliczała dłużej to jest praktycznie nieograniczona znacząco przez żadne zasoby komputera.

Czy liczba Knuhta?

Liczby Knutha tworzą ciąg rosnący, dlatego możemy napisać funkcję, która będzie sprawdzać kolejne liczby Knutha. Jeśli i-ty wyraz jest równy podanej wartości to zwrócimy prawdę. Jednak, gdy i-ta wartość jest większa od danej oznacza to, że dana liczba nie należy do liczb Knutha. Kod realizujący tę część:

  1. bool isKnuth(int a){
  2.   int i = 0, temp = 0;
  3.   while (a >= (temp = knuth(i++))){
  4.     if(temp == a)
  5.       return true;
  6.   }
  7.   return false;
  8. }

W podanym przykładzie i - przechowuje, który wyraz aktualnie sprawdzamy, a temp to wyliczona wartość i-tego wiersza.

Testowanie funkcji

Wykorzystanie dotychczas napisanych funkcji:

  1. int main () {
  2.   int a;
  3.   cout << "Podaj liczbe a: ";
  4.   cin >> a;
  5.   cout << "Jest to " << whichKnuth(a) << " wyraz\n";
  6.   cout << "Wystąpień: " << howManyInKnuth(a);
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Każdą funkcję przetestuj wpisując odpowiedni kod w funkcji main().

Zadanie 1

Napisz funkcję min() tak, aby nie używała operatora porównania

Zadanie 2

Napisz funkcję whichKnuth(), która będzie zwracała jaki indeks ma podana liczba w ciągu utworzonym z liczb Knutha. W przypadku, gdy dana liczbę nie jest liczbą Knutha funkcja ma zwrócić -1

Zadanie 3

Napisz funkcję howManyInKnuth(), która będzie zwracała ile razy dana wartość występuje w ciągu Knutha