Написание рекурсивного алгоритма
Тест разработан в качестве цифрового домашнего задания к уроку по теме "Написание рекурсивного алгоритма".
Задание 1
Приведите примеры рекурсии
Задание 2
Рекурсия кроется в идее "картины в картине". Примеры рекурсии, знакомые вам: рисующие друг друга руки, рукотражения в зеркалах, стихотворение "У попа была собака", наша Галактика, морские раковины и т.п. Рекурсивным называется объект, который через самого себя. Почти во всех языках программирования можно задать подпрограмму (процедуру или функцию) и при необходимости вызвать ее. Если подпрограмма в процессе выполнения , то такой прием называется рекурсией. Рекурсией называется ситуация, когда подпрограмма вызывает сама себя либо непосредственно, либо через другие подпрограммы. По сути это означает, что некоторую подзадачу свели к точно такой же, но с другими . Такое сведение является одной из базисных схем обработки информации и также называется рекурсией.
Задание 3
Достоинства и недостатки рекурсии
Задание 4
Сравнение рекурсивных и итеративных алгоритмов
Задание 5
Ханойские башни - пример рекурсии (ход решения головоломки с 4 дисками) Согласно легенде в Великом храме , под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времен монахи этого монастыря провинились перед богом Брамой. Разгневанный, Брама воздвиг три высоких стержня и на один из них поместил 64 диска из чистого золота, причем так, что каждый меньший диск . Как только все 64 диска будут переложены со стержня, на который Бог Брама сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты . В процессе требуется, чтобы больший диск ни разу . Монахи в затруднении, в какой же последовательности стоит делать перекладывания? Требуется снабдить их софтом для расчета этой последовательности. Независимо от Брамы данную головоломку в конце XIX века предложил Эдуард Люка. В продаваемом варианте обычно использовалось 7-8 дисков.
Задание 6
Веберите вариант внутри текста Вернемся к вопросу о Ханойской башне. Время, необходимое программе для переноса башни, состоящей из n дисков, приблизительно пропорционально 2n. Можно сказать, что этот алгоритм имеет в смысле временных затрат. Алгоритмы этого типа применять нежелательно, т.к. даже для вполне разумных значений входных данных время выполнения может становиться . Допустим, что ЭВМ может вычислить одну переменную за 1/1000000 долю секунды. Даже при такой скорости расчета переноса башни из 64 дисков потребуется около .
Задание 7
Алгоритм вычисления факториала неотрицательного натурального числа. Функцию n! = 1·2·3·…·n Program factorial; var n: integer; function fact (i: integer): longint; begin If i=1 then fact := 1 else . . . end; begin write ('n='); readln(n); writeln ('факториал = ',fact(n)); end. Выберите из предложенных вариантов пропущенный оператор:
Задание 8
Понятия рекурсии
Задание 9
Рекурсия - это вызов функции из самой себя Рекурсия - это вызов функции (процедуры) из самой себя. Рекурсию можно воспринимать, как трюк, который позволяет программисту . Как у каждого трюка у рекурсии есть свои достоинства и недостатки. К достоинствам относится способность создавать . К недостаткам: . Идеи рекурсии известны людям издавна. Рекурсивные определения как мощный аналитический аппарат используется во многих областях науки, особенно.
Задание 10
Алгоритм вычисления чисел Фибоначчи (каждое последующее число равно сумме двух предыдущих). program m;{Числа Фибоначчи} var i: Integer; function Fib(t: Integer): integer; begin if (t=1) or (t=2) then Fib:=1 else Fib: = . . . ; end; begin for i := 1 to 10 do Writeln(i, ' ', Fib(i)); end. Выберите из предложенных вариантов пропущенный оператор: