Рекурсия

Справа от функции просчитан контрольный пример для n=4.

Вычисления по tripas(n) реализуются не более чем за n рекурсивных обращений, при этом общее количество операций сложения не пре

восходит величины

3.10 Задача о Ханойских башнях

Рассмотрим следующую весьма популярную у студентов задачу.

Задача о Ханойских башнях. На одном из трех алмазных шпилей надето 64 круглых золотых диска. Диски имеют разные радиусы и расположены на шпиле в порядке убывания радиусов от основания к вершине. Трудолюбивые буддийские монахи день и ночь переносят диски с первого шпиля на второй, используя при необходимости и третий шпиль. При этом неукоснительно соблюдаются следующие правила.

· за один раз можно перемещать только один диск.

· больший диск нельзя располагать на меньшем.

· снятый диск необходимо надеть на какой-либо шпиль перед тем как будет снят другой диск.

Легенда утверждает, что когда монахи закончат свою работу, наступит конец света. Можно было бы подсчитать, что для решения задачи с 64 дисками потребуется 264 – 1 перемещений (около 1020). Поэтому, что касается конца света, то он произойдет по истечении пяти миллиардов веков, если считать, что один диск перемещается за одну секунду. Впрочем, и задачу и легенду для неё придумал в 1883 году математик Э. Люка. Это дает нам право отложить заботы о конце света в сторону и перейти к решению следующей задачи.

Задача 11. Составить рекурсивную программу-функцию, которая бы решала поставленную выше задачу о Ханойских башнях при количестве дисков, равном n (n = 1, 2, …).

Решение. Введем имена для шпилей: a , b , c. Пусть hanoi(n, a, b, c) искомая функция, возвращающая последовательность перемещений дисков с a на b c использованием c по вышеописанным правилам. При n = 1 решать задачу мы умеем. Необходимо просто произвести операцию “переместить a ® b”. Предположим, что мы умеем решать эту задачу для n – 1 диска. Тогда общая схема рекурсии могла бы выглядеть следующим образом.

Иными словами, переместим n – 1 диск с a на с. Далее, переместим один оставшийся диск с a на b и, наконец, переместим n – 1 диск с c на b. Что нам мешает реализовать эту схему на языке программирования Mathcad? По-видимому то, что в процессе вычисления функции hanoi(n, a, b, c), мы не в состоянии организовать вывод сообщений типа “переместить a ® b”. Остается одно средство. Организовать рекурсивные обращения так, чтобы все подобные ходы-перемещения запоминались в массиве, который и будет возвращаться функцией hanoi(n, a, b, c).

Вот один из возможных вариантов определения функции hanoi():

Функция возвращает матрицу размера k´2, в каждой строчке которой фиксируется перемещение одного диска (откуда, куда). Величина k равна общему количеству перемещений.

Контрольный пример. При трех дисках с именами шпилей 1, 2 и 3 получаем следующее решение:

3.11 Экзотические средние

Теперь решим задачу, связанную с экзотическими средними. Рассмотрим два положительных числа а0 и b0 и составим их среднее арифметическое и среднее геометрическое. Продолжим этот процесс и, если числа an и bn уже построены, то определим an+1 и bn+1 следующим образом:

(3)

Известно, что последовательности {an} и {bn} стремятся к общему пределу и, следуя Гауссу, его называют средним арифметико-геометрическим исходных чисел а0 и b0.

Задача 12. Составить рекурсивную программу-функцию, по которой для неотрицательных чисел a и b можно было бы приближенно вычислять их арифметико-геометрическое среднее.

Решение. Параметрами задачи естественно считать исходные величины a, b и количество итераций n по формулам (3). Рекурсию организуем по n, a решением задачи будем считать матрицу (an, bn). Построить соответствующую функцию несложно и выглядеть она может, например, т

Контрольные примеры.

age(100,30,3)=[59.77675556213139 59.77665550389991],

age(100,30,5)=[59.77670553300519 59.77670553300519].

Снова отправляясь от двух положительных чисел а0 и b0 станем последовательно составлять средние арифметические и средние гармонические:

(4)

Известно, что последовательности {an} и {bn}, строящиеся по рекуррентным формулам (4), стремятся к общему пределу. Его называют средним арифметико-гармоническим исходных чисел а0 и b0. Оказывается, что среднее арифметико-гармоническое двух чисел совпадает с их средним геометрическим.

Задача 13. Составить рекурсивную программу-функцию, по которой для неотрицательных чисел a и b можно было бы приближенно вычислять их арифметико-гармоническое среднее, то есть приближенное значение

Решение. Как и в предыдущем случае, параметрами задачи естественно считать исходные величины a, b и количество итераций n по формулам (4). Рекурсию организуем по n, a решением задачи будем считать матрицу (an, bn). Соответствующая функция может выглядеть так:

Контрольный пример.

aga(100,20,7)=[44.7213595499958 44.7213595499958],

3.12 Итерация функции в точке

Задача 14. Составить программу для нахождения n-ой итерации (n = 0, 1, 2,…) функции F(x) в точке a.

Решение. В соответствии с условиями задачи программа должна вычислять значение выражения вида F(F(F…F(a)…)) при n-кратном использовании операции F. Функция iter(F,a,n) решает поставленную задачу.

Контрольный пример.

3.13 Вещественный корень f(x)

Задача 15. Пусть функция f(x) вещественной переменной x непрерывна на отрезке [a, b] и f(a)×f(b) £ 0. Составить программу нахождения на [a, b] какого-либо вещественного корня f(x).

Решение. Во первых, при перечисленных выше условиях по крайней мере один корень f(x) на [a, b] существует. Во вторых, договоримся о том, как понимать слова “найти корень”? Будем считать, что корень ищется с точностью e > 0, то есть должен быть найден отрезок [a, b] (b – a < 2×e), на котором корень имеется. Тогда в качестве приближенного значения корня может быть взята точка x0 = (b + a)/2.

 Скачать реферат