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

Liczby iccanobiF

https://mattomatti.com/a0104

Wstęp

Liczby iccanobiF ma bardzo ciekawą nazwę, która nawiązuje do liczb Fibonacciego (wystarczy przeczytać nazwę wspak!). Zmieniona została jedynie reguła dotycząca sumowania dwóch poprzednich wyrazów.

Definicja

Przyjęto, że pierwsza liczba ciągu iccanobiF to 0, a druga to 1. Każda następna liczba to suma dwóch poprzednich liczb zapisanych wspak. Według niektórych definicji 0 jest pomijane jako pierwszy element ciągu.

Przykład

Pierwsze sześć wyrazów jest takich samo jak w ciągu Fibonacciego. Jednak po liczbach .., 8, 13 jest 39, ponieważ 39 = 31 + 8. Następny wyraz powstaje z liczb 13 i 39, więc 31 + 93 = 124. Tego typu liczby bardzo szybko rosną.

Ciąg liczb

Pierwsze 15 wyrazów ciągu to: 0, 1, 1, 2, 3, 5, 8, 13, 39, 124, 514, 836, 1053, 4139, 12815 ..

Implementacja

Strategia

Podobnie jak w przypadku ciągu Fibonacciego najbardziej efektywną metodą na wyznaczenie ciągu liczb iccanobiF będzie zastosowanie iteracji. Będzie to polegało na tym, że w każdej iteracji mamy przechowane dwa poprzednie wyrazy a i b. Na ich podstawie wyliczony zostanie nowy wyraz c. Następnie para ostatnich liczb (a, b) zostanie zastąpiona parą (b, c).

Liczby wspak

W celu odwrócenia liczby wspak potrzebna jest funkcja. Będzie ona przyjmować liczbę całkowitą a i zwracać ją zapisaną wspak. Oto kod funkcji wspak():

C++
C#
  1. int wspak(int a) {
  2.   int b = 0;
  3.   while (a > 0) {
  4.     b = b * 10 + a % 10;
  5.     a /= 10;
  6.   }
  7.   return b;
  8. }

(2.) Przygotuj zmienną do zapisu wyniku, a następnie (3. - 6.) tak długo wybieraj kolejne cyfry, aż do uzyskania wartości 0. Następnie po przepisaniu wszystkich cyfr (7.) zostaje zwrócona wartość zapisana w zmiennej b.

Wyznaczanie ciągu

Teraz można przejść do napisania funkcji generujCiagiccanobiF(), która wygeneruje tablice liczb. Funkcja przyjmuje tylko jeden argument n, który określa ile kolejnych wyrazów ma zostać wyliczonych.

C++
C#
  1. int* generujCiagiccanobiF(int n) {
  2.   int* dane = new int[n];
  3.   dane[0] = 0;
  4.   dane[1] = 1;
  5.   for (int i = 2; i < n; i++)
  6.     dane[i] = wspak(dane[i - 1]) + wspak(dane[i - 2]);
  7.   return dane;
  8. }

(2.) Przygotuj tablicę do zapisu wyliczanych liczb i (3. - 4.) przypisz dwa pierwsze wyrazy ciągu. Następnie (5. - 6.) rozpocznij wyliczanie kolejnych liczb. Na koniec (7.) zwróć tablice.

Testowanie funkcji

Napisane funkcje można przetestować poniższym programem. Wczyta on od użytkownika ile wyrazów ma zostać wypisanych i je wypisze.

C++
C#
  1. int main () {
  2.   int n;
  3.   cout << "Ile liczb ciagu iccanobiF wypisac?\n n = ";
  4.   cin >> n;
  5.   int* dane = generujCiagiccanobiF(n);
  6.   cout << "Pierwsze " << n << " liczb to:" << endl;
  7.   for (int i = 0; i < n; i++)
  8.     cout << dane[i] << " ";
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

Napisz funkcję iccanobiFRek(), która będzie przyjmować jeden argument: liczbę całkowitą k. Funkcja powinna zwrócić k-ty element ciągu iccanobiF. Przyjmujemy, że pierwszy wyraz 0 ma indeks 0. Przetestuj działanie napisanej funkcji.

Przykładowo jeśl użytkownik wprowadzi 9 to program powinien wyświetlić:

  1. 124