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. def czyFibodzielna(n):
2.   mn = 10;
3.   for i in range(0, int(math.log10(n))):
4.     a = int(n / mn)
5.     b = n % mn
6.     t = 0
7.     while(t < n):
8.       t = a + b
9.       a, b = b, t
10.     if(t == n):
11.       return True
12.     mn *= 10
13.   return False

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 (7. - 9.) iteracyjnie wyliczaj, aż ostatnio wyliczona wartość jest większa lub równa n. Nastepnie (10.) sprawdź czy znaleziona wartość to n. Jeśli tak to (11.) zwróć prawdę, a w przeciwnym (12.) przejdź do następnej iteracji przygotowując mn do nastepnego podziału. (13.) 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. k = int(input("Ile liczb Fibodzielnych wypisac:\n k = "));
2. i = 1
3. while (k > 0):
4.   if (czyFibodzielna(i)):
5.     print(i)
6.     k = k - 1
7.   i = i + 1

• Kod źródłowy Implementacja