Исправлен рекурсивный алгоритм упражнений

Следующие исправленные упражнения касаются принципа рекурсивного алгоритма, например Фибоначчи, Ханойских башен и многих других случаев. математика. Упражнения включают простую рекурсию, хвостовую рекурсию, кросс-рекурсию или взаимную рекурсию, а также принцип запоминания (подробнее об этом последнем пункте см. динамическое программирование).

рекурсивный алгоритм

Упражнение 1

Перепишите следующие алгоритмы в рекурсивной форме в терминальной форме, когда это возможно.

рекурсивный алгоритм исправлены упражнения рекурсивный терминал дерево вызовов множественной рекурсии

рекурсивный алгоритм

рекурсивный алгоритм

Последний в дорогу. На этот раз вы должны понять, что он делает, прежде чем сделать его терминально-рекурсивным!

алгоритм НОД

Мы считаем, что n — целое положительное число или нуль.

терминальный рекурсивный алгоритм

терминальный рекурсивный алгоритм

algo3 уже рекурсивен, но не терминален. Поскольку алгоритм возвращает 2^нет, мы изменим его структуру, чтобы сделать его терминальным.

терминальный рекурсивный алгоритм

Для последней алгоритм, мы должны сначала понять, что он вычисляет gcd между a и b. Сделайте тест вручную, вы поймете, что первая ветка бесполезна, поэтому мы удалим ее для рекурсии. Переменная r не используется для замены значений a и b, поэтому она не подходит для рекурсии.

алгоритм НОД

Упражнение 2

Задача Фибоначчи (1170 – 1250):

«Изначально имея пару кроликов, сколько пар вы получите за двенадцать месяцев, если каждая пара будет порождать новую пару каждый месяц, начиная со второго месяца своего существования? Кролики никогда не умирают».

Итак, если мы возьмем пример первых 7 месяцев.

Месяц

1

2

3

4

5

6

7

Пара

1

1

2

3

5

8

13

a – Выразите совокупность пар месяца n как функцию предыдущих месяцев.

б – Напишите итерационный алгоритм, вычисляющий количество пар через 12 месяцев.

c – Модифицируйте итерационный алгоритм, чтобы вычислить количество месяцев, после которых популяция пар кроликов превысит 300.

d – Напишите рекурсивный алгоритм для подсчета количества пар кроликов через n месяцев.

имеет -

Количество пар кроликов в месяце n равно сумме существующих пар в предыдущем месяце (в месяце n - 1) и новых пар в месяце n.

Однако в тексте указывается, что все пары, существовавшие двумя месяцами ранее (в месяце n - 2), размножаются.

Следовательно, в месяц n ≥ 2 количество кроликов равно сумме месяцев n-1 и n-2. В месяце 0 и месяце 1 есть только одна пара.

б-

Исправлены упражнения рекурсивного алгоритма рекурсивного алгоритма

против -

Исправлены упражнения рекурсивного алгоритма рекурсивного алгоритма

д-

рекурсивный алгоритм Фибоначчи

Мы не будем вычислять сложность выше. Для тех, кто хочет потерять голову, я приглашаю вас сюда: https://miashs-www.u-ga.fr/prevert/Prog/Complexite/nombresFibonacci.html

Упражнение 3

а – Напишите алгоритм, вычисляющий максимум 2 действительных числа. 

б – Напишите рекурсивный алгоритм, который вычисляет максимум 3 действительных числа, используя алгоритм а. Показать дерево вызовов.

c – Напишите рекурсивный алгоритм, который вычисляет максимум 4 действительных числа, используя алгоритм a. Показать дерево вызовов.

г – Является ли алгоритм рекурсивным?

имеет -

максимально рекурсивный алгоритм

б-

максимально рекурсивный алгоритм

Здесь Maximum2 действует как терминальное условие рекурсивного алгоритма. Стек вызовов выглядит следующим образом:

максимально рекурсивный алгоритм

против -

максимально рекурсивный алгоритм

Стек вызовов выглядит следующим образом:

максимально рекурсивный алгоритм

d — Хотя это выглядит как рекурсия, это скорее перегрузка функции или вызов функции для уменьшения размера проблемы. Это не рекурсивный алгоритм как таковой.

Упражнение 4

а – Являются ли алгоритмы ниже рекурсивными алгоритмами? 

б – являются ли они конечными?

в - Они заканчиваются?

лог-рекурсивный алгоритм

степенной рекурсивный алгоритм

суммирующий рекурсивный алгоритм

имеет -

Алгоритмы журнала и суммы рекурсивны: каждый содержит хотя бы один вызов самого себя, с другой стороны, мощность не является: он вызывает алгоритм тогда. Надо тогда властью заменить.

б- 

log является терминальным, мощность и сумма - нет, потому что они требуют вычислений во время рекурсии.

против -

log завершается для любого целого числа x. Итерация целочисленного деления на 2 приводит к 0, а базовый случай 0 заканчивается выполнением return. 

Для мощного алгоритма (исправленного) базовый случай 0 заканчивается выполнением возврата. Если алгоритм завершается для значения n−1, то он также завершается для значения n, выполняющего возврат. Не забывайте, что пользователь может ввести что-нибудь вроде power(2, – 5), так что вы должны проверить его прекращение.

сумма не заканчивается, когда n строго положителен. Действительно, алгоритм для n завершается, только если алгоритм завершается для n+1. Однако не существует строго положительного целого числа, при котором алгоритм останавливается.

Упражнение 5

а — Мы хотим написать рекурсивную функцию, которая вычисляет квадрат целого числа. Для этого нам нужно будет использовать отношение между квадратом (n) и квадратом (n-1), зная, что квадрат (1) = 1. Представляет стек вызовов для carre(5).

б – Комбинации – это математическое понятие, описывающее различные способы выбора заданного количества объектов из множества заданного размера. Например, сколько можно вытянуть 6 лотерейных шаров из 60 на барабане. Или вытяните 3 карты из колоды Таро. Комбинация выбора p элементов из n элементов обозначается как C(p,n)=(n/p)*C(p-1, n-1). Мы получили C(0,n)=1 и C(n,n)=1. 

Напишите нетерминальную рекурсивную функцию, затем терминальную рекурсивную функцию и покажите стек вызовов для C(3,7). Через терминальную функцию выведите итеративную функцию.

c – Для комбинаций мы обычно предпочитаем избегать метода b, потому что деление может создать проблемы с округлением. Вместо этого мы будем использовать следующее соотношение: C(p,n)=C(p,n-1)+C(p-1,n-1). Напишите рекурсивную функцию и стек или дерево вызывает C (2,4).

a - Чтобы найти связь между квадратом (n) и квадратом (n-1), мы используем формулу: (n + 1)² = n² + 2n+ 1. Запишем это как функцию от n до n-1: n² = (n−1)²+2(n−1)+1, следовательно, квадрат(n)=квадрат(n-1)+2*n-1. Вот и все !

квадратно-рекурсивный алгоритм

Стек вызовов:

квадратно-рекурсивный алгоритм

б – Все сказано в заявлении, остается только записать.

комбинированный рекурсивный алгоритм

Вот список вызовов C(3,7):

комбинированный рекурсивный алгоритм

А теперь для терминальной версии это немного сложнее, потому что вам нужно задаться вопросом, что вы должны хранить в памяти для рекурсии. На каждой итерации мы делали n/p раз предыдущую, поэтому n/p * (n-1)/(p-1). Мы могли бы записать это как n(n-1)/p(p-1). Таким образом, мы могли бы сохранить умножение уменьшения n с одной стороны и уменьшения p с другой.

комбинированный рекурсивный алгоритм

Вот стек вызовов для C(3,7,1,1):

комбинированный рекурсивный алгоритм

Выведем итеративную функцию из терминальной функции. Просто выполните До тех пор, пока не будет достигнуто условие остановки.

комбинированный рекурсивный алгоритм

c - У нас уже есть рекурсивное отношение в операторе.

комбинированный рекурсивный алгоритм

Вот дерево вызовов для C(2,4):

комбинированный рекурсивный алгоритм

Упражнение 6

Определим функцию Маккарти следующим образом:

Алгоритм Маккарти

Что делает функция при n>100? для n=98, 99, 100? Вообще для n<=100?

Мы собираемся немного посчитать... Если n > 100, у нас будет n-10. Проблема возникает, когда мы начинаем с n<=100. Посчитайте для 98, 99 и 100. Проведем прямую демонстрацию.

Для n между 90 и 100 включительно, т. е. 11 последовательных значений, это пригодится позже. Мы сделаем Carthy(Carthy(n+11)) так что мы превысим значение 100. Так что в конце у нас будет Carthy(n+1). Если n+1 по-прежнему не больше 100, ставим крышку обратно. Итак, мы останавливаемся, когда переходим от 100 к 101, или Carthy(101)=101-10=91.

В резюме то, что мы оставили в начале предыдущего пункта. Для последних 11 последовательных значений у нас будет результат 91. Обратите внимание, что любое число от 0 до 89, к которому мы добавляем 11, если оно меньше 90, будет иметь конечное значение от 90 до 100 включительно.

Мы делаем вывод, что Carthy при значении 100 или меньше даст значение 91.

Потребовалось немного математики. Информатика — это просто еще один синтаксический способ заниматься математикой!

Упражнение 7

Мы говорим о рекурсия cross, когда две функции вызывают друг друга рекурсивно.

Мы проверим перекрестную рекурсию, чтобы узнать, является ли число четным (истина) или нечетным (ложь). Вот предложение:

кросс-рекурсивный алгоритм

Проверка на четность(2), нечетность(3), четность(3) и нечетность(2). Верен ли алгоритм? В противном случае измените его, чтобы проверить исправление ← PS: если учитель спрашивает об этом, это потому, что в алгоритме есть проблема CQFD

Очевидно, что алгоритм неверен. Возьмите четное (3) → нечетное (2) → четное (1) → нечетное (0) → четное (-1) → нечетное (-2) → и т. д. Это связано с тем, что условия остановки работают только в том случае, если номер четного метода четный, а нечетный метод нечетный. Мы изменим только нечетный метод.

четно-нечетная перекрестная рекурсия

Это зависит от вас, чтобы проверить, правильно ли это сейчас!

Упражнение 8

Невозможно завершить рекурсию, не упомянув знаменитые Ханойские башни (одержимость студентов, а иногда и лекторов и преподавателей!). Так что будем действовать медленно.

ханойские башни

Имеется n лотков разного размера и 3 стержня, пронумерованных от 0 до 2.

Изначально все лотки располагаются на стволе i. Цель состоит в том, чтобы передать их в стержень j, соблюдая следующие правила:

- Вы можете перемещать только одну доску за раз.

– Лотки всегда должны располагаться на стержне в порядке убывания (самый большой внизу, затем в порядке убывания вверх по стержню).

1 — Решить задачу вручную, если n = 2, i = 0 и j = 2 (итак, 2 лотка, все они основаны на стержне 0, и мы хотим поставить их на стержень 2).

2 – Решите задачу вручную, если n = 3, i = 0 и j = 2 (то есть 3 лотка, все они основаны на стержне 0, и мы хотим поставить их на стержень 2).

3 – Допустим, ваш друг знает, как решить задачу для некоторого n и любого что я и j. Вам предлагается решить задачу на n + 1. Вы имеете право воспользоваться помощью друга. Как ты сделал это?

4 – Напишите рекурсивную функцию, которая решает эту проблему для всех n, i, j (Если вы можете сделать это без обмана, поздравляем! В противном случае это нормально, мы почти все прошли через этот великий момент непонимания и сомнения в ее карьере…)

1 – 

Маленькая табличка переведена с 0 на 1. 

Большая доска переведена с 0 на 2. 

Переносим малый лоток с 1 на 2.

2 –

Маленькая доска переведена с 0 на 2. 

Переводим среднее плато с 0 на 1.

Переносим маленькую доску с 2 на 1. (мы переместили 2 доски с 0 на 1). 

Большая доска переведена с 0 на 2. 

Маленькая табличка переведена с 1 на 0. 

Переносим среднюю доску с 1 на 2. 

Переносим маленькую доску с 0 на 2. (мы переместили 2 доски с 1 на 2).

3 –

Перемещаем n подносов из i в позицию, которая не является ни i, ни j (серией из трех манипуляций пункта 2). Затем мы перемещаем последнюю доску (самую большую) из i в j. Мы призываем друга передвинуть n подносов на j. 

4 –

Если вы найдете это… шампанское! Переименуем для простоты стебли в d для стартового, a для прибытия и r для оставшегося.

ханойские башни

Упражнение 9

Напишите программу, которая находит НОД двух чисел с помощью рекурсии.

Вот идея алгоритма:

алгоритм НОД

алгоритм НОД

Упражнение 10

Напишите программу для преобразования десятичного числа в двоичное с помощью рекурсии.

Вот идея алгоритма:

бинарный алгоритм

бинарный рекурсивный алгоритм

Упражнение 11

Напишите программу для нахождения НОК двух чисел с помощью рекурсии.

MCL

Вот алгоритм:

MCL

Упражнение 12

Напишите программу, которая проверяет, является ли заданная строка палиндромом или нет.

Упражнение 13

Число Пи можно рассчитать по следующей формуле:

пи рекурсивный

Напишите рекурсивный алгоритм для вычисления значения Pi, рассматривая последовательность до ранга n.

Сделайте то же самое со следующими приближениями числа Пи.

Серия Грегори-Лейбница:

Исправлены упражнения рекурсивного алгоритма рекурсивного алгоритма

И более старая серия Мадхавы, Рамануджана, Давида и Чудновского (факториал сам по себе будет рекурсивным вызовом):

пи рекурсивный

 

Вот рекурсивный алгоритм:

пи рекурсивный

Остальные формулы работают по тому же принципу, нет необходимости все детализировать. Будьте все же осторожны, чтобы использовать правильный расчет в рекурсии! (алгоритмы будет легче писать в нетерминальной рекурсии.

Упражнение 14

В 1920-х годах Вильгельм Акерманн и Габриэль Судан, в то время ученики Дэвида Гильберта, изучали основы вычислимости. Судан первым привел пример примитивно-рекурсивной, но нерекурсивной функции, названной тогда функцией Судана. Вскоре после этого и независимо, в 1928 году, Акерман опубликовал свой собственный пример примитивно-рекурсивной, но нерекурсивной функции. Первоначально Аккерман рассматривает функцию ϕ(m, n, p), зависящую от трех переменных.

Функция только двух переменных дана позже Розой Петер и Рафаэлем Робинсоном; именно последняя известна сегодня как функция Аккермана.

Функция Аккермана-Петера определяется рекурсивно следующим образом:

Аккерман

Функция растет настолько быстро, что быстро записать ее классическим числом невозможно и приходится использовать нотацию Кнута!

Аккерман

Решение очень простое, но запускать алгоритм на ПК не рекомендую.

рекурсивный Аккерманн

Упражнение 15

Вот функция Судана, еще одного ученика Давида Гильберта. Эта функция была разработана в 1927 году, то есть на год раньше, чем функция Аккермана.

рекурсивный судан

Здесь, чем больше значение n растет, тем больше взрывается результат функции функции. Вот пример для F_1(14,14).

рекурсивный судан

Ничего особо сложного, просто скопируйте математическую формулу в виде рекурсии.

рекурсивный судан

Упражнение 16

Функция Такэути, сокращенно так или иногда тараи, представляет собой рекурсивное представление функции, названной в честь Икуо Такеучи (竹内郁雄). Представление функции, которая к тому же допускает достаточно простое нерекурсивное определение, может потребовать очень длительных вычислений, если реализующий ее компилятор неэффективен. По этой причине его часто используют для проверки производительности реализации рекурсивных функций компилятором языка программирования.

Такеучи

Первоначальное определение Такеучи было таким:

Такеучи

tarai — это аббревиатура от «раздавать» на японском языке. Джон Маккарти назвал эту функцию tak() в честь Такеучи.

Рекурсия была улучшена благодаря кросс-рекурсии:

Такеучи

Упражнение 17

Последовательность Хофштадтера мужчина-женщина определяется:

F(0)=1, M(0)=0 и

Хофштадтер

Напишите рекурсивный алгоритм для вычисления последовательности Хофштадтера.

Это перекрестно-рекурсивный алгоритм (также называемый совершенным взаимно-рекурсивным алгоритмом).

взаимная рекурсия Хофштадтера

Упражнение 18

Некоторые языки программирования допускают мемоизацию. Это кеширование возвращаемых значений функции в соответствии с ее входными значениями. Цель этого метода оптимизации кода — сократить время выполнения компьютерной программы за счет запоминания значений, возвращаемых функцией.

Таким образом, выполняя последовательность Фибоначчи, можно запоминать уже вычисленные значения во избежание насыщения памяти значениями, уже полученными в другой ветке дерева вызовов.

На самом деле всякий раз, когда мы вычисляем fib(i), мы можем просто кэшировать этот результат и использовать его позже. Поэтому, когда мы вызываем fib(n), нам не нужно делать намного больше, чем 0(n) вызовов, потому что есть только O(n) возможных значений, которые мы можем привести к fib(n).

Мемоизация Фибоначчи

Упражнение 19

Некоторые языки программирования допускают мемоизацию. Это кеширование возвращаемых значений функции в соответствии с ее входными значениями. Цель этого метода оптимизации кода — сократить время выполнения компьютерной программы за счет запоминания значений, возвращаемых функцией.

Напишите алгоритм вычисления факториала n (n!), используя принцип мемоизации.

Мы будем хранить каждое значение факториала в массиве:

факториал запоминания

Второе решение более техническое, поскольку требует доступа к кэш-памяти, например, для импорта lru_cache. Таким образом, вычисление факториала большого числа становится быстрым и не прожорливым в памяти.

Упражнение 20

А вот небольшое упражнение, объединяющее все, что вы видели, рекурсию, кроссовер и мемоизацию.

На кухне есть апельсины, и вы решили съедать несколько таких апельсинов каждый день следующим образом:

  • Съешьте апельсин.
  • Если количество оставшихся апельсинов n делится на 2, то вы можете съесть n/2 апельсинов.
  • Если количество оставшихся апельсинов n делится на 3, то вы можете съесть 2*(n/3) апельсинов.

Вы можете выбрать только одно из действий в день.

Учитывая целое число n, возвращает минимальное количество дней, в течение которых можно есть n апельсинов.

Вход: n = 10
Выход: 4

Пояснение: У вас есть 10 апельсинов.

День 1: съешьте 1 апельсин, 10 – 1 = 9.
День 2: съешьте 6 апельсинов, 9 – 2*(9/3) = 9 – 6 = 3. (Поскольку 9 делится на 3)
День 3: съешьте 2 апельсина, 3 – 2*(3/3) = 3 – 2 = 1.
День 4: Съесть последний апельсин 1 – 1 = 0.

Чтобы съесть все 10 апельсинов, нужно как минимум 4 дня.

Делиться
ru_RURU