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

Liczby Fibodzielne

Definicja

Liczby Fibodzielne to takie liczby naturalne n, które można podzielić na dwie liczby a i b w taki sposób, że po zapisaniu ciągu Fibonacciego o początkowych wyrazach a i b w ciągu wystąpi liczba n.

Przykład

Najmniejszą liczbą Fibodzielną jest 14, ponieważ można ją podzielić na dwie liczby a = 1 oraz b = 4. Ciąg Fibonacciego o początkowych wyrazach a i b to 1, 4, 5, 9, 14, .., więc w rozwinięciu ciągu wystepują liczba 14.

Bardziej skomplikowanym przykładem jest liczba 122. Jednak wystarczy ją podzielić na a = 12 i b = 2. Wtedy powstający ciąg liczb to kolejno: 12, 2, 14, 16, 30, 46, 76, 122, ..

Ciąg liczb

Liczby Fibodzielne można ustawić w nastepujący ciąg: 14, 19, 28, 47, 61, 75, 122, 149, 183, 199, 244, 298, 305, 323, 366, ..

Implementacja

Zadanie

Napisz program, który wypisze k pierwszych liczb Fibodzielnych. Przykładowo dla k = 5 program powinien wypisać:

  1. 14 19 28 47 61

Strategia

Podział ma tylko i wyłącznie sens, gdy sprawdzana liczba ma co najmniej dwie cyfry, a a i b mają co najmniej jedną cyfrę. Oznacza to, że dla dowolnej liczby n o c cyfrach jest do sprawdzenia dokładnie c - 1 podziałów. Należy pamiętać, że tylko jeden z nich może się okazać prawdziwy!

Podczas obliczania ciągu Fibonacciego dla pewnych początkowych wartości a i b warto skorzystać z algorytmu iteracyjnego. (Wyjaśnienie tutaj.) Jednak algorytm ten powinien obliczać kolejne wyrazy tak długo, aż dalsze obliczenia nie będą miały sensu. W tym przypadku oznacza to obliczenie wartości, która jest większa, równa wartości wejściowej n.

Rozwiazanie

Poniższa funkcja czyFibodzielna() dla podanego argumentu n zwraca czy jest to liczba Fibodzielna.

  1. bool czyFibodzielna(int n) {
  2.   int mn = 10, t;
  3.   for (int i = 1; i < log10(n); i++) {
  4.     int a = n / mn;
  5.     int b = n % 10;
  6.     do {
  7.       t = a + b;
  8.       a = b;
  9.       b = t;
  10.     } while (t < n);
  11.     if (t == n)
  12.       return true;
  13.     mn *= 10;
  14.   }
  15.   return false;
  16. }

W celu tworzenia podziału liczby (2.) zadeklarowana zostaje dodatkowa zmienna mn. (3.) Dla każdego możliwego podziału: (4. - 5.) wykonaj podział i (6. - 10.) iteracyjnie wyliczaj, aż ostatnio wyliczona wartość jest większa lub równa n. Nastepnie (11.) sprawdź czy znaleziona wartość to n. Jeśli tak to (12.) zwróć prawdę, a w przeciwnym (13.) przejdź do następnej iteracji przygotowując mn do nastepnego podziału. (15.) Jeśli żaden podział nie okazuje się poprawny to zwróć fałsz.

Testowanie funkcji

W celu przetestowania napisanej funkcji można skorzystać z poniższego fragmentu kodu, który wczyta od użytkownika liczbę k - ile kolejnych liczb Fibodzielnych ma zostać wypisanych.

  1. int main () {
  2.   int k;
  3.   cout << "Ile liczb Fibodzielnych wypisac:\n k = ";
  4.   cin >> k;
  5.   int i = 0;
  6.   while (k > 0) {
  7.     if (czyFibodzielna(i)) {
  8.       cout << i << " ";
  9.       k--;
  10.     }
  11.     i++;
  12.   }
  13.   system("pause");
  14.   return 0;
  15. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1