183648 (596697), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

Мы видим, что уже е(5) e с точностью до 9 знаков после десятичной точки, а начиная с e(8) уже все 15 знаков после точки верные. Если была бы необходимость вычислять по алгоритму Ламберта число e с большей точностью, то пришлось бы программно реализовывать арифметику длинных чисел.

Замечание. Предложенные варианты вычисления e можно было бы сделать существенно более эффективными, организовав в них динамические базы, пополняемые в процессе вычислений уже найденными значениями. Тем самым, исключив повторные вычисления элементов последовательностей, можно было бы вычислять a(k), b(k) и d(k,t) за k рекурсивных обращений.

1. Наибольший общий делитель

Задача 8. Составить программу-функцию возвращающую наибольший общий делитель двух натуральных чисел x и y.

Решение. Обозначим через nod(x,y) – наибольший общий делитель x и y. Известно, что

(2)

На этих утверждениях базируется известный итеративный алгоритм Евклида, нахождения наибольшего общего делителя двух целых чисел. Внимательный взгляд на соотношения (2) приводит нас к убеждению, что фактически мы имеем рекурсивное определение функции nod(x,y). На языке Mathcad это надо было бы записать так.

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

Обобщим решенную задачу, составив программу-функцию, возвращающую наибольший общий делитель нескольких натуральных чисел a_p (p=0..n1, n1), являющихся компонентами вектора v=(a₀,a₁,…,a_n1)^T.

Обозначим через nodd(a₀,a₁,…,a_n1) – наибольший общий делитель чисел a_p (p=0..n1). Поскольку

nodd(a₀,a₁,…,a_n1)=nod(nodd(a₀,a₁,…,a_n2),a_n1) ,

то соответствующая программа-функция, вычисляющая nodd(v) будет выглядеть так:

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

1. Наименьшее общее кратное

Задача 9. Составить программу-функцию, возвращающую наименьшее общее кратное натуральных чисел a_p (p=0..n1, n2), являющихся компонентами вектора v=(a₀,a₁,…,a_n1)^T.

Решение. Обозначим через nok(a₀,a₁,…,a_n1) – наименьшее общее кратное чисел a_p (p=0..n1). Известно, что

и

Поэтому соответствующую программу-функцию можно было бы записать так:

где nod(x,y) функция нахождения наибольшего общего делителя натуральных x и y.

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

Функцию nok() можно записать в следующей более компактной форме:

1. Биномиальные коэффициенты

Задача 10. Составить программу-функцию вычисления биномиальных коэффициентов С(n,m), где n m целые и 0mn.

Решение. Известно, что

Отсюда и вытекает справедливость следующего рекурсивного определения С(n,m):

Обратите внимание на то, что здесь мы имеем рекурсию сразу по двум аргументам.

Опираясь на функцию C(n,m) как на подпрограмму, построим функцию binom(n,k), возвращающую для целого n0 вектор из k последовательных биномиальных коэффициентов: С(n,0), C(n,1),…,C(n,k) (kn).

Решение данной задачи можно записать так:

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

Замечание. Для отыскания всех биномиальных коэффициентов при заданном n не обязательно вычислять binom(n,n). Учитывая, что C(n,k)=C(n,nk), достаточно вычислить binom(n,(nmod(n/2))/2).

И еще один способ вычисления биномиальных коэффициентов. Рекурсивная программа-функция tripas(n) вычисляет треугольник Паскаля, то есть значения величин C(i,j) для (0in , 0ji), исходя из формул непосредственно определяющих и декомпозицию и базу:

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

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

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

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

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

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

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

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

Легенда утверждает, что когда монахи закончат свою работу, наступит конец света. Можно было бы подсчитать, что для решения задачи с 64 дисками потребуется 2⁶⁴ – 1 перемещений (около 10²⁰). Поэтому, что касается конца света, то он произойдет по истечении пяти миллиардов веков, если считать, что один диск перемещается за одну секунду. Впрочем, и задачу и легенду для неё придумал в 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():

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

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

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

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

(3)

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

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

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

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

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

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

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

(4)

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

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

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

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

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

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

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

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

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

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

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

Характеристики

Список файлов ВКР