Лекція № 6. ЧИСЛА ФІБОНАЧЧІ І ПРОСТІ ЧИСЛА

6.1. Завдання|задача| Фібоначчі

Потрібно визначити, скільки кроликів буде на фермі через n місяців, якщо в початковий момент часу був тільки|лише| один новонароджений кролик.

Очевидно, що фермер має одного кролика в перший місяць і одного кролика – в другий місяць. На третій місяць буде вже два кролики, на четвертий – три і т.д. Позначимо кількість кроликів в n місяці як . Таким чином: , , , , , …

Можна побудувати|спорудити| алгоритм, що дозволяє знайти при будь-якому n.

Згідно умові завдання|задачі| загальна|спільна| кількість кроликів в n+1 місяці розкладається на три складові:

· одномісячні кролики, не здібні до розмноження, в кількості

;

· кролики, здібні до розмноження, в кількості ;

· новонароджені кролики, їх кількість також рівна .

Таким чином, одержимо|отримаємо|

. (6.1)

Формула (6.1) дозволяє обчислити|обчисляти,вичислити| ряд|лаву,низку| чисел: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 , ...

Числа в даній послідовності називаються числами Фібоначчі.

Якщо прийняти і , то за допомогою формули (6.1) можна визначити всю решту чисел Фібоначчі. Формула (6.1) називається рекурентною формулою (recurrence – «повернення» на латині).

У наступному|такому| випадку n = 4, маємо 5 можливостей|спроможності| (1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2).

Для того, щоб відповісти на поставлене питання при довільному n, позначимо кількість варіантів як , і спробуємо визначити по відомихі . Якщо ми стартуємо з одиничного|поодинокого| кроку, то маємо комбінацій для n сходинок, що залишилися. Якщо стартуємо з подвійного кроку, то маємо комбінацій для тих, що залишилися n–1 сходинок. Загальна|спільна| кількість варіантів для n+1 сходинок рівно

. (6.2)

Це справедливо для n = 1, 2, і також справедливо для кожного n. Числа Фібоначчі і кількість комбінацій обчислюються за однією і тією ж формулою, проте|однак| початкові значення, і у|в,біля| них розрізняються.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Підстановки	\|	Сума чисел Фібоначчі

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.