Складання програми для обчислення чисел Фібоначчі
ПРАКТИЧНА РОБОТА 15
Завдання: скласти програму для розрахунку n-го числа Фібоначчі.
Обладнання: комп’ютер із середовищем програмування Python.
Леонардо Пізанський, відоміший як Фібоначчі, — це італійський математик ХІІІ ст., автор математичних трактатів, завдяки яким Європа довідалася про вигадану індійцями позиційну систему числення, відому зараз як арабські цифри.
Числами Фібоначчі називають послідовність чисел, які обчислюють за таким правилом:
[latex]F_1=F_2=1[/latex], [latex]F_n=F_{n-1}+F_{n-2}[/latex].
Інакше кажучи, перші два члени послідовності — одиниці, а кожний наступний — сума значень двох попередніх чисел: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55… При діленні числа з ряду Фібоначчі на попереднє частка зі збільшенням номера числа наближається до так званого золотого перетину (≈ 1,618; таке співвідношення розмірів вважають естетично привабливим).
Для обчислення n-го числа виконується така послідовність дій (див. рисунок):
1) виділяються змінні [latex]a[/latex] і [latex]b[/latex] для зберігання двох поточних чисел Фібоначчі [latex]F_{n-1}[/latex] і [latex]F_{n-2}[/latex];
2) сума чисел [latex]a+b[/latex] заноситься в змінну [latex]c[/latex] (на рисунку — 1);
3) на наступній ітерації циклу:
[latex]b = F_{n-1}[/latex] стає [latex](n-2)[/latex]-м членом ряду, тому [latex]A=B[/latex] (на рисунку — 2);
[latex]c = F_{n}[/latex] стає [latex](n-1)[/latex]-м членом, тому [latex]B=C[/latex] (на рисунку — 3).
Хід роботи
Під час роботи за комп’ютером дотримуйтеся правил безпеки.
1. Відкрийте IDLE Python і створіть файл із назвою Pract15.
Запишіть команду введення значення змінної n для збереження номера шуканого числа:
n = int(input('Уведіть номер числа:'))
2. Запишіть програмний код, що реалізує алгоритм обчислення n-го числа.
a = b = 1 # Перші два числа послідовності дорівнюють 1
for i in range(3, n+1): # F1 = F2 = 1, тому обчислення починається з n = 3
c = a+b # і-те число дорівнює сумі двох попередніх чисел
a = b # b стає (і–2)-м членом ряду
b = с # с стає (і–1)-м членом ряду
3. Запишіть команду виведення значення с після завершення роботи циклу.
4. Знайдіть числа Фібоначчі з номерами 10; 20; 30.
5. Запишіть програму для визначення номера першого числа Фібоначчі, більшого за 1000.
Кількість повторень циклу невідома, тому використовуймо цикл із умовою:
a = b = 1 # Перші два числа послідовності дорівнюють 1
n = 2
while c<1000:
n = n+1 # Номер числа збільшується на 1
c = a+b # n-е число дорівнює сумі двох попередніх чисел
a = b # b стає (і–2)-м членом ряду
b = с # с стає (і–1)-м членом ряду
6. Запишіть команду виведення значення n після завершення роботи циклу.
Випробуйте програму.
Зробіть висновок: як виконуються циклічні алгоритми для обчислення чисел у певній послідовності.