Рекурсия (стр. 5 из 12)
Решение. Обозначим через nok(a0,a1,…,an-1) – наименьшее общее кратное чисел ap (p=0..n-1). Известно, что
и
Поэтому соответствующую программу-функцию можно было бы записать так:
где nod(x,y) - функция нахождения наибольшего общего делителя натуральных x и y.
Контрольный пример.
Функцию nok() можно записать в следующей более компактной форме:
3.9 Биномиальные коэффициенты
Задача 10. Составить программу-функцию вычисления биномиальных коэффициентов С(n,m), где nm- целые и 0£m£n.
Решение. Известно, что
Отсюда и вытекает справедливость следующего рекурсивного определения С(n,m):
Обратите внимание на то, что здесь мы имеем рекурсию сразу по двум аргументам.
Опираясь на функцию C(n,m) как на подпрограмму, построим функцию binom(n,k), возвращающую для целого n³0 вектор из k последовательных биномиальных коэффициентов: С(n,0), C(n,1),…,C(n,k) (k£n).
Решение данной задачи можно записать так:
Контрольные примеры.
Замечание. Для отыскания всех биномиальных коэффициентов при заданном n не обязательно вычислять binom(n,n). Учитывая, что C(n,k)=C(n,n-k), достаточно вычислить binom(n,(n-mod(n/2))/2).
И еще один способ вычисления биномиальных коэффициентов. Рекурсивная программа-функция tripas(n) вычисляет треугольник Паскаля, то есть значения величин C(i,j) для (0£i£n , 0£j£i), исходя из формул непосредственно определяющих и декомпозицию и базу:
Справа от функции просчитан контрольный пример для 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.
Для отыскания решения многих задач часто используется метод дихотомии, называемый также методом последовательного деления пополам, бисекции или вилки. В некоторых ранее рассмотренных задачах мы уже сталкивались с этим методом. В нашем случае, когда ищется корень уравнения, суть его в следующем. Пусть e > 0 задано. Делим отрезок [a, b] точкой с=(b+a)/2 на две равные части и в качестве нового отрезка [a, b] берем ту из его половин, для которой снова f(a)×f(b) £ 0 и т.д. Ясно, что на некотором шаге будем иметь отрезок [a, b] такой, что b – a < 2×e и f(a)×f(b) £ 0. Следовательно, приближенное решение найдено и оно равно (b + a)/2.