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. }

• Kod źródłowy Implementacja