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. static bool czyFibodzielna(int n) {
2.   int mn = 10, t;
3.   for (int i = 1; i < Math.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. static void Main(string[] args) {
2.   Console.Write("Ile liczb Fibodzielnych wypisac:\n k = ");
3.   int k = Convert.ToInt32(Console.ReadLine());
4.   int i = 0;
5.   while (k > 0) {
6.     if (czyFibodzielna(i)) {
7.       Console.Write("{0} ", i);
8.       k--;
9.     }
10.     i++;
11.   }
12.   Console.ReadKey();
13. }

• Kod źródłowy Implementacja