Досліджуючи рекурсію

Мета цього уроку — познайомити студентів з поняттям рекурсії, зрозуміти її основи та оволодіти її реалізацією в програмуванні. До кінця цього уроку студенти повинні бути здатні:

• Дати визначення рекурсії та описати її основні характеристики.

• Розібратися в механізмі роботи рекурсивних функцій.

• Реалізувати базові рекурсивні алгоритми.

• Ідентифікувати ситуації, в яких рекурсія є підходящим рішенням.

Вступ:

• Почніть з короткого обговорення методів розв’язання задач у програмуванні.

• Наведіть приклад рекурсії з реального життя.

• Визначіть рекурсію як техніку програмування, при якій функція викликає саму себе прямо чи опосередковано для розв’язання задачі.

• Поясніть ключові характеристики рекурсії: базис, рекурсивний крок і виклик самої себе.

Розуміння рекурсивних функцій:

• Поясніть механізм роботи рекурсивних функцій, використовуючи простий приклад (факторіал, обчислення степеня $x^n$ чи послідовність Фібоначчі).

• Продемонструйте роботу рекурсивних функцій крок за кроком, підкреслюючи важливість базового випадку.

• Обговоріть стек викликів і його використання при рекурсивних викликах функцій.

• Поясніть концепцію нескінченної рекурсії та способи її уникнення.

Реалізація рекурсивних алгоритмів:

• Представте серію задач з програмування, які підходять для розв'язання за допомогою рекурсії.

• Розділіть студентів на пари або невеликі групи для розв'язання цих задач рекурсивним способом.

• Заохочуйте студентів писати рекурсивні функції з нуля, приділяючи особливу увагу визначенню базового та рекурсивного випадків.

• Слідкуйте за роботою груп, щоб за потреби надавати їм допомогу та поради.

Огляд і практика:

• Нехай кожна група представить свої рекурсивні рішення класу.

• Обговоріть оптимальність та зрозумілість різних рекурсивних підходів.

• Розберіть загальні труднощі та помилки, з якими зіткнулися учасники під час виконання завдання.

• Надайте додаткові задачі для практики, щоб студенти могли працювати над ними індивідуально або в групах.

Висновок:

• Підсумуйте основні моменти, розглянуті на уроці, підкресливши силу та універсальність рекурсії в програмуванні.

• Заохочуйте студентів продовжувати вивчати рекурсію у своїх проєктах і завданнях.

Домашнє завдання:

• Дайте домашнє завдання для закріплення вивчених у класі понять. Наприклад, реалізувати рекурсивні алгоритми для конкретних задач або проаналізувати існуючі рекурсивні функції в бібліотеках коду.

Оцінювання:

• Оцініть розуміння студентів через їхню участь у дискусіях на семінарах, здатність розв'язувати рекурсивні задачі з програмування та вміння чітко пояснювати рекурсивні рішення.

• Перевірте домашні завдання, щоб оцінити індивідуальне засвоєння концепцій рекурсії та навичок їхньої реалізації.

Вступ

Почнемо з короткого обговорення методів розв'язання задач у програмуванні

У програмуванні розв'язання задач є фундаментальною навичкою, яку Ви будете використовувати кожного разу, коли писатимете код. Перш ніж ми заглибимося в особливості рекурсії, давайте поговоримо про методи розв'язання задач.

Думайте про розв'язання задач як про подорож. Ви починаєте з задачі, програму для якої слід написати. І Вам потрібно зрозуміти, як перейти від точки $А$ (умови) до точки $В$ (розв'язання). Ця подорож включає в себе поділ задачі на менші частини, з якими зручніше працювати, розуміння правил або обмежень, а також розробку плану досягнення бажаного результату.

Існує кілька технік, які програмісти використовують для ефективного розв'язання задач. Ось деякі з них:

• Розуміння задачі: перш ніж Ви почнете розв'язувати задачу, Вам необхідно повністю зрозуміти її. Це включає в себе читання та аналіз її умови, визначення вхідних та вихідних даних, а також роз'яснення будь-яких неясностей.

• Розділяй і володарюй: багато складних задач можна розв'язати, поділивши їх на менші, простіші підзадачі. Цей підхід, відомий як "розділяй і володарюй", дозволяє Вам розв'язувати кожну підзадачу окремо, а потім комбінувати розв'язання, щоб розв'язати більшу.

• Алгоритмічне мислення: алгоритми — це покрокові процедури для розв'язання задач. Коли Ви стикаєтеся із задачею, спробуйте мислити алгоритмічно, розбиваючи розв'язання на послідовність логічних кроків.

• Абстракція: абстракція передбачає зосередження на суттєвих деталях задачі, ігноруючи несуттєву або відволікаючу інформацію. Абстрагуючи непотрібні деталі, Ви зможете спростити задачу і зосередитися на важливому.

• Ітерація та рекурсія: ітерація передбачає розв'язання задачі шляхом багаторазового виконання циклу або послідовності команд. Рекурсія, з іншого боку, передбачає розв'язання задачі шляхом її поділу на менші екземпляри тієї ж самої задачі. Як ітерація, так і рекурсія є потужними методами розв'язання задач, з якими Ви часто будете стикатися у програмуванні.

Оволодівши зазначеними методами розв'язання задач, Ви будете краще підготовлені до розв'язання широкого спектра задач з програмування, включаючи ті, що пов'язані з рекурсією. Тому, заглиблюючись у вивчення рекурсії, пам'ятайте про ці стратегії розв'язання задач — вони стануть цінними інструментами у Вашому арсеналі програмування.

Приведіть концепцію рекурсії на прикладі з реального життя

Давайте на мить відійдемо від програмування і подумаємо про рекурсію на прикладах з реального життя. Уявіть, що Ви стоїте перед набором російських матрьошок. Ці ляльки бувають різних розмірів, і кожна поміщається всередину наступної, більшої за розміром.

Тепер давайте подумаємо, як Ви могли б описати процес відкриття кожної матрьошки в наборі. Починаєте Ви з найбільшої, і коли її відкриваєте, то знаходите всередині меншу матрьошку. Потім Ви відкриваєте цю меншу матрьошку і знаходите всередині ще меншу, і так далі, поки не досягнете найменшої — тієї, яка не містить всередині себе інших матрьошок.

Процес відкриття кожної матрьошки можна вважати рекурсивним. Чому? Тому що кожна матрьошка має схожу структуру з іншими, і дія по її відкриттю однакова для кожної – вона включає в себе погляд усередину, щоб побачити, чи є там менша матрьошка.

У термінах програмування рекурсія працює аналогічно. Замість відкриття російських матрьошок ми "відкриваємо" функції або методи. Рекурсивна функція — це функція, яка викликає саму себе, або прямо, або опосередковано, щоб розв'язати задачу, поділивши її на менші екземпляри тієї ж самої задачі.

Як і з матрьошками, рекурсія розв'язує задачу шляхом її поділу на менші, подібні підзадачі, доти, поки ми не досягнемо точки, де задача стає настільки малою і простою, що ми можемо розв'язати її безпосередньо. Ця найменша і найпростіша версія задачі називається базовим випадком.

Розуміючи рекурсію через приклади з реального життя, такі як російські матрьошки, ми бачимо, як вона застосовується у програмуванні, і наскільки вона може бути потужним інструментом для розв'язання складних задач. Тому, заглиблюючись у вивчення рекурсії, тримайте цю візуальну аналогію в умі — вона допоможе Вам інтуїтивно зрозуміти концепцію.

Визначте рекурсію як метод програмування, при якому функція викликає саму себе прямо чи опосередковано для розв'язання задачі

Тепер давайте спростимо визначення рекурсії. Уявіть, що у Вас є функція — набір інструкцій, що виконують певну задачу у Вашій програмі. А тепер уявіть, що ця функція може викликати саму себе. Так, Ви не ослухалися! Це і називається рекурсією.

Рекурсія схожа на цикл, але замість того, щоб повторювати набір інструкцій до тих пір, поки не буде виконано умову, рекурсивна функція повторює саму себе, викликаючи саму себе — прямо чи опосередковано — до тих пір, поки не досягне певної умови, зазвичай званої базовим випадком.

Дозвольте пояснити це на прикладі. Уявіть, що у Вас є функція "countDown", яка виводить числа від $n$ до $1$. Замість використання циклу ми можемо визначити "countDown" рекурсивно. Ось як це працює:

• На вхід функції "countDown" подається число $n$.

• Якщо число дорівнює $1$ (базовий випадок), то функція виводить "$1$" і завершується.

• Якщо число більше $1$, то функція виводить поточне число, а потім викликає саму себе з меншим наступним числом.

• Цей процес триває до тих пір, поки функція не досягне базового випадку, після чого вона перестає викликати саму себе, і рекурсія "розгортається" назад до вихідного виклику.

def countDown(n):
  # Базовий випадок: якщо n = 1, то виводимо його та зупиняємо рекурсію
  if n == 1:
    print(n)
  else:
    # Виводимо поточне число
    print(n)
    # Викликаємо функцію countDown з наступним меншим числом
    countDown(n - 1)

# Приклад визову:
countDown(5)  # Вивести числа від 5 до 1 по спаданню

Таким чином, рекурсія — це спосіб розв'язання задач шляхом поділу їх на менші, подібні підзадачі, а потім розв'язання цих підзадач шляхом багаторазового виклику однієї і тієї ж функції, поки ми не досягнемо базового випадку, де задачу можна розв'язати безпосередньо.

Майте на увазі, що рекурсія може спочатку здаватися трохи заплутаною, але з практикою і розумінням її принципів Ви зможете використовувати її як потужний інструмент у своїх уроках з програмування.

Виділіть ключові характеристики рекурсії: базис, рекурсивний крок і виклик самої себе

Тепер, коли ми розуміємо, що таке рекурсія і як вона працює, давайте заглибимося в її ключові характеристики. Рекурсія схожа на добре налагоджений механізм — у неї є певні частини, які працюють разом, щоб забезпечити її функціонування. Ось три ключові характеристики рекурсії, на яких ми зупинимося: базис, рекурсивний виклик і виклик самої себе.

Базис:

• Уявіть базис рекурсії як точку зупинки для рекурсивної функції. Це умова, яка вказує функції, коли припинити викликати саму себе і почати повертати значення.

• Без базису рекурсивна функція продовжувала б викликати саму себе нескінченно, що призвело б до так званої нескінченної рекурсії, чого ми не бажаємо.

• У попередньому прикладі з функцією “countDown” базовим був випадок, коли $n$ ставало рівним $1$. У цей момент ми просто виводили $1$ і припиняли виклик функції.

Крок рекурсії:

• Рекурсивний крок є тим місцем, де відбувається магія рекурсії. Це частина функції, в якій ми викликаємо саму функцію.

• Кожного разу, коли функція здійснює рекурсивний виклик, ми на крок наближаємось до базового випадку. Ми розбиваємо задачу на все менші і менші підзадачі, поки не досягнемо базового випадку.

• У функції "countDown" рекурсивний крок виконується, коли $n$ більше $1$. Ми виводимо поточне значення $n$, а потім знову викликаємо функцію "countDown" з аргументом $n-1$.

Виклик самої себе:

• Ця характеристика може звучати складно, але насправді вона доволі проста. Самовиклик означає, що функція викликає саму себе.

• Коли ми визначаємо рекурсивну функцію, ми по суті кажемо: "Гей, функція, ти можеш викликати саму себе, якщо це необхідно".

• Природа самовиклику дозволяє рекурсії розв'язувати складні задачі, розбиваючи їх на менші екземпляри тієї ж задачі.

• У функції "countDown" ми бачили самовиклик у дії, коли викликали "countDown" всередині самої функції.

Отже, підсумуємо. Рекурсія має три ключові характеристики:

1. базовий випадок, який описує, коли зупинитися;

2. крок рекурсії, який розбиває задачу на менші підзадачі;

3. самовиклик, який дозволяє функції викликати саму себе.

Розуміння і освоєння цих характеристик необхідне для того, щоб розуміти рекурсію і ефективно використовувати її в програмуванні.

Розуміння рекурсивних функцій

Пояснення механізму рекурсивних функцій на прикладі

Давайте розглянемо механізм рекурсивних функцій на прикладі обчислення факторіала числа.

Факторіал невід'ємного цілого числа $n$, позначуваний як $n!$, є добутком усіх додатних цілих чисел, менших або рівних $n$. Наприклад, $5!$ (читається як "п'ять факторіал") дорівнює $5\cdot 4\cdot 3\cdot 2\cdot 1$, що дорівнює $120$.

Тепер давайте реалізуємо це за допомогою рекурсивної функції:

# Функція fact обчислює факторіал числа n
def fact(n):
  if n == 0: return 1
  return n * fact(n-1)

# Основна частина програми. Читаємо вхідне значення n
n = int(input())

# Обчислюємо та виводимо відповідь
print(fact(n))

Тепер давайте зрозуміємо, як працює ця рекурсивна функція:

Базовий випадок:

• У функції обчислення факторіала базовий випадок — це коли значення $n$ дорівнює $0$. Ми знаємо, що факторіал $0$ дорівнює $1$. Тому ми повертаємо $1$.

Крок рекурсії:

• Для будь-якого іншого значення $n$ (коли $n$ більше $1$), ми обчислюємо факторіал рекурсивно. Ми викликаємо функцію факторіала з аргументом $n-1$ та множимо результат на $n$.

• Це означає, що для обчислення $fact(n)$ нам спочатку потрібно обчислити $fact(n-1)$, а потім помножити результат на $n$. Цей процес триває до тих пір, поки ми не досягнемо базового випадку.

Давайте розглянемо приклад.

• Якщо ми хочемо обчислити $fact(5)$, то функція викличе $fact(4)$, яка в свою чергу викличе $fact(3)$ і так далі, поки ми не досягнемо базового випадку.

• Коли ми досягаємо базового випадку $(fact(1))$, тоді починаємо "розгортати" рекурсивні виклики.

• Кожен рекурсивний виклик повертає свій результат і множить його на поточне значення $n$.

• У результаті факторіал $fact(5)$ обчислюється як $fact(4)\cdot 5$, який далі обчислюється як $fact(3)\cdot 4\cdot 5$ і так далі, поки ми не отримаємо остаточний результат.

Отже, ось як працює рекурсія! Це схоже на зняття шарів з цибулі — шар за шаром — до тих пір, поки ми не дійдемо до середини. Розуміння цього рекурсивного процесу необхідне для вивчення рекурсивних функцій в програмуванні.

Продемонструйте пошагову роботу рекурсивних функцій, підкреслюючи важливість базового випадку

Тепер давайте крок за кроком розглянемо, як працюють рекурсивні функції, використовуючи послідовність Фібоначчі в якості прикладу. Послідовність Фібоначчі — це ряд чисел, в якому кожне число є сумою двох попередніх, зазвичай починаючи з $0$ та $1$. Таким чином, послідовність виглядає наступним чином: $0,1,1,2,3,5,8,13$ і так далі.

Послідовність Фібоначчі має наступний вигляд:

Найбільше число Фібоначчі, що вміщується у типі int, дорівнює

Для $n\le 40$ достатньо використовувати тип даних int.

Нехай функція $fib(n)$ обчислює $n$-те число Фібоначчі. Тоді маємо наступне рекурентне співвідношення:

Тепер давайте реалізуємо рекурсивну функцію для обчислення чисел Фібоначчі:

# Функція fib обчислює n-е число Фібоначчі
def fib(n):
  if (n == 0): return 0
  if (n == 1): return 1
  return fib(n - 1) + fib(n - 2)

# Основна частина програми. Читаємо вхідне значення n
n = int(input())

# Обчислюємо та виводимо відповідь
print(fib(n))

Тепер давайте крок за кроком розберемо, як працює ця рекурсивна функція:

Базовий випадок:

• Базовий випадок відбувається, коли $n$ дорівнює $0$ або $1$. У цих випадках ми вже знаємо числа Фібоначчі: $F_0=0$ і $F_1=1$. Це найпростіший випадок, коли нам не потрібні додаткові обчислення.

Крок рекурсії:

• Для будь-якого іншого значення $n$ (коли $n>1$) ми обчислюємо число Фібоначчі рекурсивно. Це відбувається шляхом сумування чисел Фібоначчі двох попередніх значень у послідовності ($fib(n-1)$ і $fib(n-2)$).

• Це означає, що для обчислення $fib(n)$ нам потрібно спочатку обчислити $fib(n-1)$ і $fib(n-2)$, а потім додати ці результати. Цей процес триває доти, доки ми не досягнемо базового випадку.

Давайте розглянемо приклад.

• Якщо ми хочемо обчислити $fib(4)$, функція спочатку викличе $fib(3)$ та $fib(2)$.

• $fib(3)$ в свою чергу викличе $fib(2)$ та $fib(1)$, а $fib(2)$ викличе $fib(1)$ та $fib(0)$.

• $fib(1)$ і $fib(0)$ є базовими випадками, тому вони повернуть $1$ та $0$ відповідно.

• Як тільки ми отримаємо результати $fib(1)$ та $fib(0)$, $fib(2)$ додасть їх разом $(0+1=1)$.

• $fib(3)$ аналогічним чином додасть результати $fib(2)$ та $fib(1)$ $(1+1=2)$.

• Нарешті, $fib(4)$ додасть $fib(3)$ та $fib(2)$ $(2+1=3)$, і ми отримаємо результат $3$.

Цей покроковий процес демонструє, як працюють рекурсивні функції. Задача поступово розбивається на менші підзадачі, поки не будуть досягнуті базові випадки, а потім результати об'єднуються для вирішення початкової задачі. І, як ми бачили, базові випадки грають вирішальну роль у зупиненні рекурсії та забезпеченні вихідних точок для наших обчислень.

Обговоріть стек викликів та його використання при рекурсивних викликах функцій

Тепер давайте заглибимося в поняття стеку викликів та його використання при рекурсивних викликах функцій. Уявіть стек викликів як стопку тарілок у кафетерії. Коли Ви заходите до кафетерію, Ви берете тарілку і кладете її на верх стопки. Аналогічно, коли програма викликається функцією, інформація про цей виклик додається до стеку викликів.

Давайте розглянемо, як це працює з рекурсивними викликами функцій:

Виклики функцій та стек викликів:

• Коли викликається функція, на вершині стеку викликів створюється новий фрейм для зберігання інформації про цей виклик. Цей фрейм включає параметри функції, локальні змінні та адресу повернення — точку в програмі, де має продовжитися виконання після завершення функції.

• Кожен раз, коли відбувається виклик функції (будь то рекурсивний виклик чи звичайний виклик функції), новий фрейм додається на вершину стеку.

Рекурсивні виклики функцій:

• У випадку рекурсивних викликів функція викликає саму себе всередині свого тіла. Це означає, що кожен рекурсивний виклик створює новий фрейм на вершині стеку викликів.

• По мірі прогресування рекурсії до стеку викликів додаються все більше фреймів, і кожен з них представляє собою окремий екземпляр виклику функції.

• Стек викликів відстежує всі ці виклики функцій, забезпечуючи тим самим, що програма знає, куди повернутися після завершення кожного виклику функції.

Базовий випадок і розгортання стеку:

• Зрештою, по мірі прогресування рекурсії досягається базовий випадок. Це умова зупинки, яка запобігає безкінечному продовженню рекурсії.

• Коли досягається базовий випадок, функція припиняє додаткові рекурсивні виклики і починає "розгортати" стек викликів.

• Кожен фрейм знімається з вершини стеку викликів, і програма повертається до точки, де функція була спочатку викликана. Цей процес триває, поки весь стек викликів не буде повністю розгорнутий.

Питання пам'яті:

• Важливо зазначити, що стек викликів має обмежений розмір, і надмірна рекурсія може призвести до помилки переповнення стеку, якщо стек стає занадто глибоким.

• Тому при написанні рекурсивних функцій важливо переконатися, що існує коректний базовий випадок, щоб уникнути незкінченної рекурсії, і обмежити глибину рекурсії, щоб уникнути переповнення стеку.

Таким чином, стек викликів відіграє важливу роль у керуванні викликами функцій, включаючи рекурсивні виклики. Він відстежує послідовність викликів функцій і гарантує, що програма знає, куди повернутися після завершення кожного виклику функції. Розуміння стеку викликів є необхідним для розуміння роботи рекурсії і для написання ефективних і безпомилкових рекурсивних функцій.

Роз'яснити концепцію нескінченної рекурсії та способи її уникнення

Тепер давайте прояснимо концепцію нескінченної рекурсії та обговоримо, як її уникнути.

Нескінченна рекурсія:

• Нескінченна рекурсія відбувається, коли рекурсивна функція викликає саму себе нескінченно, не досягаючи базового випадку, який би її зупинив.

• Іншими словами, функція продовжує робити рекурсивні виклики, не просуваючись до базового випадку, що призводить до нескінченного циклу викликів функції.

• Нескінченна рекурсія може швидко спожити всі доступні системні ресурси і викликати аварійне завершення програми або її зависання на невизначений час.

Як це відбувається:

• Нескінченна рекурсія зазвичай виникає, коли в рекурсивній функції відсутній або неправильно вказаний базовий випадок.

• Без базового випадку або з базовим випадком, який ніколи не досягається через неправильну логіку, функція буде викликати саму себе нескінченно.

Приклад:

Давайте розглянемо простий приклад рекурсивної функції для зворотного відліку від заданого числа:

def countDown(n):
  # Виведення поточного числа
  print(n)
  # Виклик функції countDown з на 1 меншим аргументом
  countDown(n - 1)

# Приклад використання:
countDown(5)  # Виведення чисел з 5 до мінус нескінченності

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

Як уникнути нескінченної рекурсії:

• Щоб уникнути нескінченної рекурсії, важливо переконатися, що кожна рекурсивна функція має правильний базовий випадок.

• Базовий випадок повинен представляти собою умову, при якій функція припиняє подальші рекурсивні виклики і повертає результат.

• Під час написання рекурсивної функції завжди запитуйте себе: "Яка умова повинна змусити функцію зупинитися та повернути результат?"

• Переконайтеся, що базовий випадок досяжний та що рекурсивні виклики ведуть до нього.

Виправлений приклад:

• Давайте виправимо попередній приклад, додавши базовий випадок для зупинки рекурсії, коли $n$ досягає $0$:

def countDown(n):
  # Базовий випадок
  if n == 0: return
  # Виведення поточного числа
  print(n)
  # Виклик функції countDown з на 1 меншим аргументом
  countDown(n - 1)

# Приклад використання:
countDown(5)  # Виведення чисел з 5 до 1

• Тепер функція припинить викликати саму себе, коли $n$ стане рівним $0$. Це і стане запобіжником нескінченної рекурсії.

Отже, нескінченна рекурсія відбувається, коли рекурсивна функція викликає саму себе нескінченно, не досягаючи базового випадку. Щоб цього уникнути, завжди переконуйтесь, що ваші рекурсивні функції мають правильний базовий випадок, який зупиняє рекурсію та повертає результат. Тестування рекурсивних функцій з різними вхідними значеннями може допомогти виявити потенційні випадки нескінченної рекурсії під час розробки.

Реалізація рекурсивних алгоритмів

Представимо серію задач з програмування, придатних для рекурсії

Давайте обговоримо деякі відомі рекурсивні алгоритми.

Задачу можна розв'язати зі складністю $O(n)$. Для цього достатньо написати наївний цикл for:

# Читаємо вхідні дані
x, n, m = map(int,input().split())

# Ініціюємо змінну res значенням 1.
# У цій змінній будемо обчислювати результат x^n mod m
res = 1

# Обчислюємо значення x^n mod m використовуючи n операцій множення 
# 1 * x * x * ... * x
for i in range(1,n+1):
  res = (res * x) % m

# Виводимо відповідь
print(res)

Така реалізація алгоритму перевищує Time Limit. Оскільки $n\le 10^9$, а часовий ліміт для цієї задачі становить лише $1$ секунду, то ви не зможете виконати $10^9$ операцій за $1$ секунду, навіть використовуючи сучасні комп'ютери.

Як ми можемо прискорити процес множення? Наприклад, якщо ми хочемо обчислити $x^{100}$, то можемо представити цей вираз у вигляді $(x^2{)}^{50}$. Використовуючи лише одне множення для обчислення $x^2$, ми можемо ефективно зменшити степінь удвічі: з $100$ до $50$.

Наприклад, замість використання $16$ множень для знаходження $x^{16}$, ми можемо переписати вираз наступним чином: $x^{16}=(((x^2{)}^2{)}^2{)}^2$, таким чином виконуючи всього $4$ множення. Аналогічно можна стверджувати, що для обчислення $x^{1024}$ достатньо виконати лише $10$ множень.

Якщо показник степеня непарний, наприклад, $n=99$, то значення $x^{99}$ обчислюємо як $x\cdot x^{98}$.

Наприклад, $x^{15}=((x^2\cdot x{)}^2\cdot x{)}^2\cdot x$.

Ми підійшли до методу бінарного піднесення до степеня, техніки, яка використовується для ефективного обчислення великих степенів числа. Він заснований на принципі, що будь-яке число, піднесене до степеня, можна виразити як послідовність степенів двійки.

По заданим основі $x$ та показнику степеня $n$, ми виражаємо $n$ як суму степенів двійки. Наприклад, якщо $n=13$, ми можемо записати це як $13=8+4+1$. Потім ми обчислюємо $x^n$, перемножаючи разом значення $x$, піднесені до кожної степені двійки, і об'єднуємо результати.

Припустимо, ми хочемо обчислити $x^{13}$.

• Виразимо $13$ у двійковій системі: $13=1101$ у двійковому представленні.

• Потім обчислимо $x^1$, $x^4$ і $x^8$ (що відповідають встановленим бітам у двійковому представленні $13$).

• Нарешті, перемножимо ці значення: $x^{13}=x^1\cdot x^4\cdot x^8$.

Переваги. Бінарне піднесення до степеня скорочує кількість необхідних множень порівняно з наївним піднесенням до степеня. Воно особливо ефективне для великих степенів, оскільки вимагає всього $O({\log }_{2}n)$ множень замість $O(n)$ множень.

Щоб знайти значення $x^{n}modm$, ми будемо використовувати формулу:

# Функція myPow обчислює значення x^n mod m
def myPow(x, n, m):
  if (n == 0): return 1
  if (n % 2 == 0): return myPow((x * x) % m, n / 2, m)
  return (x * myPow(x, n - 1, m)) % m

# Основна частина програми. Читаємо вхідні дані
x, n, m = map(int, input().split())

# Обчислюємо та виводимо відповідь
print(myPow(x, n, m))

Python має вмонтовану функцію $pow(x,n,m)$, яка обчислює $x^{n}modm$. Попередній код можна переписати наступним чином:

# Читаємо вхідні дані
x, n, m = map(int, input().split())

# Обчислюємо та виводимо відповідь
print(pow(x, n, m))

Найбільший спільний дільник (НСД) двох цілих чисел $a$ і $b$ — це найбільше додатне число, яке ділить і $a$, і $b$ без залишку.

Приклад:

• Розглянемо два числа $a=12$ та $b=18$.

• Дільниками числа $12$ будуть $1,2,3,4,6$ і $12$.

• Дільниками числа $18$ будуть $1,2,3,6,9$ і $18$.

• Спільними дільниками чисел $12$ та $18$ будуть $1,2,3$ і $6$.

• З цих дільників найбільшим буде $6$.

• Тому $НСД(12,18)=6$.

Властивості:

• НСД є завжди невід'ємним цілим числом.

• Якщо $a$ та $b$ обидва нулі, то $НСД(a,b)=0$.

• Якщо $a$ або $b$ (або обидва) від'ємні, то $НСД(a,b)$ дорівнює НСД їх абсолютних значень.

• Якщо $a$ або $b$ дорівнює нулю, то $НСД(a,b)$ дорівнює абсолютному значенню ненульового цілого числа.

• НСД будь-якого числа та $0$ дорівнює абсолютному значенню цього числа.

Застосування:

• НСД використовується в різних математичних обчисленнях, включаючи спрощення дробів та знаходження найменшого спільного знаменника.

• НСД використовується в криптографічних алгоритмах, таких як RSA, для генерації ключів і шифрування.

• НСД також використовується в алгоритмах інформатики, таких як алгоритм Евкліда для ефективного обчислення.

Алгоритм Евкліда — це ефективний метод знаходження НСД двох цілих чисел. Він заснований на принципі, що НСД двох чисел залишається незмінним, якщо ми будемо віднімати менше число від більшого до тих пір, поки одне з них не стане рівним нулю.

Якщо замість операції "мінус" використовувати операцію "mod", то обчислення будуть проходити швидше.

Наприклад, щоб обчислити $НCД(1,10^9)$ за допомогою віднімання, знадобиться виконати $10^9$ операцій. Однак при використанні операції взяття остачі достатньо лише однієї дії.

Для двох цілих чисел $a$ та $b$, де $a\ge b$, ми повторюємо наступні кроки:

• Якщо $b$ дорівнює нулю, то НСД дорівнює $a$.

• У протилежному випадку ми замінюємо $a$ на $b$, а $b$ на залишок від ділення $a$ на $b$. Це можна виразити як $a\leftarrow b$ та $b\leftarrow amodb$.

• Ми продовжуємо цей процес, доки $b$ не стане рівним нулю.

НСД $a$ та $b$ — це значення $a$, коли $b$ стає рівним нулю.

Алгоритм Євкліда є ефективним, з часовою складністю $O(lo{g}_{2}min(a,b))$. Він завжди завершується, оскільки значення $b$ зменшується з кожною ітерацією і в кінці стає рівним нулю.

НСД двох чисел можна обчислити за допомогою наступної формули:

def gcd(a, b):
  if a == 0: return b
  if b == 0: return a
  if a > b: return gcd(a % b, b)
  return gcd(a, b % a)

# Основна частина програми. Читаємо вхідні дані.
a, b = map(int, input().split())

# Обчислюємо та виводимо НСД двох чисел.
print(gcd(a, b))

Дану формулу можна виразити в іншій формі:

def gcd(a, b):
  if b == 0: return a
  return gcd(b, a % b)

# Основна частина програми. Читаємо вхідні дані.
a, b = map(int, input().split())

# Обчислюємо та виводимо НСД двох чисел.
print(gcd(a, b))

Python має вбудовану функцію $gcd(a,b)$, яка обчислює найбільший спільний дільник двох чисел. Попередній код можна переписати наступним чином:

import math

# Читаємо вхідні дані.
a, b = map(int, input().split())

# Обчислюємо та виводимо НСД двох чисел.
print(math.gcd(a, b))

Список задач

Рекурсивні програми:

• 1603. Сума цифр числа

• 1658. Факторіал (використано в лекції)

• 2999. Функція - 10

• 8609. Рекурсія - 1

• 11249. Рекурсія - 2

Числа Фібоначчі:

• 3258. Послідовність Фібоначчі (використано в лекції)

• 8295. Генерація рядків Фібоначчі

НСД / НСК:

• 136. Відрізок

• 1601. НСД двох чисел (використано в лекції)

• 1602. НСК двох чисел

• 2214. Функція 9

• 7363. Сума дробів

Біноміальний коефіцієнт:

• 3260. Скільки?

Піднесення до степеня:

• 273. Піднесення до степеня

• 5198. Піднесення до степеня (використано в лекції)

• 9644. Сума степеней

• 9646. Сума степеней 2