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

Liczby Keitha

https://mattomatti.com/a89

Definicja

Liczbą Keitha nazywamy n-cyfrową liczbę całkowitą k, która tworzy ciąg liczbowy. Pierwsze n wyrazów to cyfry liczby k, a każdy kolejny wyraz to suma poprzedzających go n wyrazów.

Przykład

Przykładowo dwucyfrową liczbą Keitha jest 61. Na początku ciągu znajdują się cyfry, a każde kolejny element to suma dwóch poprzednich: 6, 1, 7, 8, 15, 23, 38, 61, ... Jak widać w trakcie wypisywania kolejnych elementów jeden z nich równa się liczbie początkowej. Jako bardziej skomplikowany przypadek można podać liczbę 742: 7, 4, 2, 13, 19, 34, 66, 119, 219, 404, 742, ...

Oczywiście do liczb Keitha zaliczane są liczby jednocyfrowe. W takim przypadku dowolna liczba k ze zbioru {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} tworzy ciąg k, k, k, k, k, ... co dowodzi, że k jest liczbą Keitha. Warto też zauważyć, że jeśli k jest liczbą Keitha to -k również.

Implementacja

Długość liczby

Na podstawie liczby należy utworzyć listę, która będzie miała tyle elementów co liczba cyfr. Z tego powodu potrzebna jest implementacja algorytmu zliczającego długość liczby. Zadanie to realizuje przykładowa funkcja intDlugosc():

  1. int intDlugosc(int a) {
  2.   int licznik = 0;
  3.   do {
  4.     licznik++;
  5.     a /= 10;
  6.   } while (a > 0);
  7.   return licznik;
  8. }

(1.) Funkcja jako argument przyjmuje liczbę a i zwraca jej długość. (2.) Długość liczby jest zliczana do zmiennej licznik. (3. - 6.) Dopóki liczba jest większa od 0, czyli ma niezerowe cyfry to (4.) zwiększ licznik i (5.) usuń ostatnią cyfrę. (6.) Zwróć wartość zmiennej licznik.

Rozkład Keitha

Kolejna funkcja czyKeith() ma za zadanie określić czy podana liczba k jest liczbą Keitha. Dodatkowym, opcjonalnym argumentem tej funkcji jest rozklad, który przyjmuje wartość logiczną. Domyślnie jest ustawiony na fałsz, ale po przekazaniu wartości prawda funkcja prócz dokonania sprawdzenia wypisze ciąg utworzony na podstawie podanej liczby.

  1. bool czyKeith(int k, bool rozklad = false) {
  2.   int n = intDlugosc(k);
  3.   int* lista = new int[n];
  4.   int k_kopia = k;
  5.   for (int i = n - 1; i >= 0; i--) {
  6.     lista[i] = k_kopia % 10;
  7.     k_kopia /= 10;
  8.   }
  9.   if (rozklad) {
  10.     for (int i = 0; i < n; i++) {
  11.       cout << lista[i] << " ";
  12.     }
  13.   }

Pierwsza część tej funkcji polega na (2.) obliczeniu długości liczby k i (3.) zaalokowaniu pamięci pod listę liczb początkowych ciągu. Po (4.) wykonaniu kopii liczby k można (5. - 8.) kolejne cyfry dopisać na listę. (6.) Cyfry są dopisywane od końca listy, ponieważ najłatwiej się pobiera ostatnią cyfrę liczby. (7.) Jeśli rozklad został włączony to (8. - 10.) wypisz wszystkie dotychczasowe wartości na liście. Nie można tego połączyć z poprzednią pętlą, ponieważ wtedy pierwsze n cyfr zostałoby wypisane wspak.

Kolejna część polega na wyliczaniu kolejnych wartości ciągu. W celu optymalizacji programu. Na liście zawsze jest zastępowana najmniejsza wartość na liście poprzez sumę wszystkich dotychczasowych elementów na liście. Jest to możliwe (12.) dzięki licznikowi j wiadomo, który element na liście jest najmniejszy.

  1.   int j = 0, suma = 0;
  2.   do {
  3.     suma = 0;
  4.     for (int i = 0; i < n; i++)
  5.       suma += lista[i];
  6.     lista[j] = suma;
  7.     j = (j + 1) % n;
  8.     if (rozklad)
  9.       cout << suma << " ";
  10.   } while (suma < k);
  11.   delete[] lista;
  12.   if (rozklad)
  13.     cout << (suma == k ? "" : "nie ") << "liczba Keitha\n";
  14.   return suma == k;
  15. }

W pętli obliczaj kolejne elementy, dopóki (21.) obliczona suma aktualnych elementów jest mniejsza od liczby k. W każdej iteracji: (14.) zeruj suma i (15. - 16.) oblicz sumę wszystkich elementów na liście. Następnie należy (17.) obliczoną sumę zapisać na liście zamiast najmniejszego elementu i (18.) obliczyć pozycję następnego najmniejszego elementu. (19. - 20.) Jeśli rozklad jest włączony to wypisz kolejny element ciągu i (21.) sprawdź warunek ograniczenia ciągu. (22.) Należy potem prawidłowo zwolnić pamięć i (23. - 24.) wypisać ewentualnie czy została wykryta liczba k, a następnie (25.) wystarczy zwrócić porównanie ostatniej sumy i liczby k.

Testowanie funkcji

W celu przetestowania funkcji warto spróbować wypisać rozkład wszystkich liczb, które program określił jako liczby Keitha. Poniższa funkcja main() wypisuje wszystkie liczby i ciągi jakie tworzą w zakresie [0, 1000].

  1. int main () {
  2.   for (int i = 0; i < 1000; i++) {
  3.     if (czyKeith(i)) {
  4.       czyKeith(i, true);
  5.     }
  6.   }
  7.   system("pause");
  8.   return 0;
  9. }