Тема 12*

Алгоритм Евкліда. Числа Фібоначчі

Розглянемо використання циклу з умовою для реалізації алгоритму Евкліда для пошуку НСД (найбільшого спільного дільника двох чисел) та пошуку чисел Фібоначчі.

З 6 класу математики Вам відомо, що для знаходження НСД двох чисел, їх потрібно розкласти на прості множники і взяти їх спільну частину. Наприклад, знайдемо НСД(24,36). 24=2³∙3, 36=2²∙3². Спільна частина 2²∙3=12. Тому НСД(24,36)=12.  Такий спосіб складно реалізувати у програмуванні, тому скористаємося іншим, який запропонований давньогрецьким математиком Евклідом. Якщо числа а і b мають спільний дільник k, то вони на нього діляться націло, а також ділиться і їх різниця. Тому можна записати, що НСД(а,b)=НСД(a-b,b). Причому віднімати можна скільки завгодно, тому можна записати і так НСД(а,b)=НСД(a%b,b). Так потрібно повторювати, поки a%b не стане рівним 0, тобто відповіддю буде число b. Розглянемо на прикладі:

НСД(36,24)=НСД(12,24)=НСД(24,12)=НСД(0,12)=НСД(12,0)=12.

Зверніть увагу, що потрібно обмінювати значення змінних а і b. Запис у програмі

a=b

b=a

буде невірний, бо після першої команда змінна а втратить своє значення (стане рівною b), і змінна bне зміниться. У багатьох мовах програмування користуються допоміжною змінною t:

t=a

a=b

b=t

Але у мові Python є можливість обміну будь-якої кількості змінних за допомогою кортежу. Кортеж – це послідовність змінних, записаних через кому. Операція обміну запишеться так a,b=b,a.

Отже, в циклі слід повторювати обмін а,b=b,a%b, поки b!=0.

Приклад 1. Знайти НСД двох чисел, що задані у окремих рядках

Вхід                                           Вихід

24                                               12

36

a=int(input())

b=int(input())

while b!=0:

a,b=b,a%b

print(a)

Найменше спільне кратне (НСК) двох чисел можна знайти, знаючи їх НСД. З математики відомо, що

 НСД(а,b)∙ НСК(а,b)= а∙b, тому НСК(а,b)=а∙b//НСД(а,b)

Числа Фібоначчі задаються співвідношенням φ_n= φ_n-1+ φ_n-2, φ₀=0, φ₁=1. Для їх знаходження потрібно постійно змінювати перший і другий доданок, яке зробимо за допомогою кортежу.

Приклад 2. Дано натуральне число n. Знайти n-е число Фібоначчі.

Вхід                                           Вихід

6                                                8

n=int(input())

a=0

b=1

i=0

while i<n:

a,b=a+b,a

    i+=1

print(a)

Практична частина

Завдання 12.1. Дано натуральне число.Якщо воно є числом Фібоначчі, то визначити його номер, а якщо ні, то вивести -1.

Вхід                                           Вихід

8                                                6

Вхід                                           Вихід

10                                              -1

Завдання 12.2. У двох рядках дано по одному натуральному числу. Знайти їх НСК.

Вхід                                           Вихід

8                                                24

12

Завдання 12.3. Скоротити дріб a/b.У двох рядках дано по одному натуральному числу aі b (a<b) – чисельник і знаменник дробу. Вивести нескоротний дріб у вигляді a/b.

Вхід                                           Вихід

8                                                2/3

12

Завдання 12.4. Додати два дроби  a/b і c/d.У одному рядку дано чотири натуральних числаa, b, c, d. Вивести спочатку цілу частину дробу, а потім чисельник і знаменник нескоротного дробу. Якщо дробової частини немає, то нічого виводити непотрібно.

Вхід                                           Вихід

1 2 2 3                                        1 1 6

Вхід                                           Вихід

3 4 2 8                                        1

Вхід                                           Вихід

1 6 1 3                                        0 1 2