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

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

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

Таблица 3.1. Схематическое изображение последовательности рекур-

сивных обращений и формирования полной рекурсивной траектории

В оставшейся части данного пункта рассматривается серия простых учебных демонстрационных задач, решения которых получаются с помощью рекурсивно определенных алгоритмов. Во многих случаях детально обсуждаются описанные выше схематические приемы поиска этих алгоритмов. В основном все программы-функции написаны на языке программирования вычислительной среды Mathcad. Часть программ написана на языке Object Pascal 5.0 системы объектного визуального программирования Delphi 5. Для некоторых задач предлагается несколько вариантов программ. Приводятся контрольные примеры. Заметим, что, ввиду разноплановости предложенных задач, многие из них могут служить отдельными темами, собирающими вокруг себя родственный содержательный материал по рекурсии для отработки техники рекурсивного программирования в рамках конкретного направления.

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

1. Факториал

Задача 1. Составить программу-функцию вычисления факториала целого неотрицательного числа n.

Решение. Для целых неотрицательных чисел n факториал n обозначается через n! и определяется так:

В данном случае параметризация задачи осуществлена в её постановке. Остается лишь ввести более приемлемое для нас обозначение искомой функции. Пусть это будет facto(n). Тривиальные случаи, для которых задача решается без рекурсивных вызовов, также очевидны: facto(0)=1, facto(1)=1. Они и составляют базу рекурсии. Декомпозиция по параметру n реализуется по формуле: facto(n) = nfacto(n–1) (n = 1, 2, …). Поэтому вычисления facto(n) можно организовать так:

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

Понять процесс реализации рекурсивных вызовов, то есть декомпозицию, и возвратов управления при организации отложенных вычислений facto(n) можно из схемы рис. 3.1 (n = 3). Там около стрелок в круглых скобках жирными цифрами указаны номера последовательных шагов вычислений: (1), (2), (3) декомпозиция; (4), (5), (6) отложенные вычисления.

Рис. 3.1. Схематическое изображение рекурсивных вызовов и

отложенных вычислений при нахождении facto(3) = 3!.

Замечание. С помощью встроенной функции if() предложенный алгоритм удается записать еще короче. Это же касается и многих других примеров.

Для решения конкретной задачи иногда удается построить несколько различных рекурсивных алгоритмов. Например, функцию facto(n) можно было бы определить и так.

По сравнению с прежней реализацией facto() здесь количество рекурсивных вызовов уменьшается практически в 2 раза. В реальных ситуациях подобный фактор может оказаться решающим при выборе того или иного алгоритма.

Используем теперь для вычисления n! cформулированную выше схему 3 (обобщить). Если вместо исходной функции facto(n)=n!, ввести в рассмотрение функцию двух переменных fa(n, )=n! (n=0,1,…), то получим равенства:

fa(n, )=n(n1)…1=(n)(n1)!=fa(n)(n1)!,

fa(1, )= , fa(n,1)=n!.

Первое из этих соотношений может служить правилом декомпозиции, второе определять рекурсивную базу, а третье показывает, как вычислять n!. Соответствующая рекурсивная программа-функция могла бы выглядеть так:

В чем же отличие этой функции от первого варианта функции facto(n)? Дело в том, в facto(n) формирование n! реализуется при проведении отложенных вычислений, в то же время нахождение fa(n, ) проводится вообще без отложенных вычислений. Особенно наглядно это видно на рисунках 3.1 и 3.2. На шагах 4, 5 и 6, отмеченных на рис. 3.2 жирными цифрами в круглых скобках, происходит лишь передача значений. Иными словами здесь мы имеем повторительную рекурсию.

Рис. 3.2. Схематическое изображение рекурсивных вызовов

при нахождении fa(3,) = 3!.

Еще один вариант вычисления n! можно реализовать с помощью рассмотренной ниже в задаче 20 функции Кадью.

1. Сложный процент

Задача 2. Вкладчик положил в сбербанк сумму в sum единиц под p процентов за один период времени (год, месяц, неделя и т.д.). Составить программу-функцию возвращающую величину вклада по истечении n периодов времени (n = 1, 2,).

Решение. Пусть invest(sum,p,n) искомая функция. Для данной задачи вычисления значений invest() можно проводить по формуле

invest(sum,p,n) = sum(1+p/100)ⁿ .

Однако, в учебных целях, нас интересует рекурсивный вариант алгоритма решения задачи. Рекурсию будем осуществлять по параметру n. Тривиальный случай очевиден. Если вклад положен на хранение и взят сразу, то есть до истечения первого периода времени начисления процентов, то возврату подлежит начальная сумма вклада sum. Далее, декомпозиция может быть реализована исходя из следующего факта. Положить некоторую сумму в банк на n периодов – это то же самое, что положить эту сумму на n – 1 периодов и затем полученную сумму положить на 1 период. Соответствующий вариант программы-функции решения задачи выглядит так:

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

Схема рекурсивных вызовов здесь такая же, как при вычислении значений функции facto(n). Нетрудно видеть, что общее количество рекурсивных вызовов при вычислении invest(sum,p,n) равно n. При необходимости можно было бы уменьшить это значение до log₂(n).

1. Степень числа

Задача 3. Пусть a вещественное число отличное от нуля и n целое неотрицательное число. Составить программу-функцию возвращающую величину aⁿ.

Решение. Приведенная ниже функция power(a,n) дает решение задачи за n рекурсивных вызовов:

Уменьшить количество вызовов можно так. Организуем декомпозицию иначе, представив величину aⁿ в виде:

Отсюда сразу же получаем алгоритм вычисления aⁿ, требующий не более log₂(n) рекурсивных вызовов. Реализуется он функцией pow(a,n):

Сумма элементов массива

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

Решение. Определение суммы n слагаемых в виде:

S= a₀+a₁+…+a_n1=(a₀ +a₁+…+a_n2)+a_n1

рекурсивно по своей сути. Сумма n слагаемых есть сумма первых (n1)-го слагаемого плюс сумма последнего слагаемого. Этот факт и положен в основу определения функции summa(v), где v=(a₀,a₁,…,a_n1)^T.

1. Произведение элементов массива

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

Решение. Определение произведения n сомножителей в виде:

P= a₀a₁…a_n1= (a₀a₁…a_n2)a_n1 ,

как и соответствующее определение суммы, рекурсивно по своей сути. Произведение n сомножителей есть произведение первых (n1)-го сомножителей умноженное на последний сомножитель. Отсюда и определение функции product(v), где v=(a₀,a₁,…,a_n1)^T.

1. Числа Фибоначчи

Задача 6. Составить программу-функцию вычисления nго числа Фибоначчи, исходя из рекуррентного определения этих чисел:

f(0)=f(1)=1, f(n)=f(n1)+f(n2) (n=2,3,…).(1)

Решение. Наличие рекуррентного соотношения вида (1) сразу же определяет и базу рекурсии, и способ декомпозиции. Программа-функция fib(n) написана строго в соответствии с определением (1).

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

Функция fib(n) вряд ли подходит для вычисления чисел Фибоначчи при больших n. И происходит это потому, что в данном случае с ростом n дерево рекурсивных вызовов очень быстро разрастается. На рис. 3.3 представлена схема рекурсивных вызовов для fib(5) (имя функции обозначено через f).

Рис. 3.3. Схематическое изображение рекурсивных вызовов при

нахождении f(5)

Для ускорения вычислений можно было бы учесть, что

Это приводит к следующей рекурсивной программе функции:

Отметим, что теперь количество рекурсивных вызовов для fiboo(n) имеет порядок равный log₂(n) и, скажем, fiboo(200) в символьной форме вычисляется практически мгновенно.

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

fiboo(0)=1 fiboo(1)=1 fiboo(10)=89

fiboo(200) 453973694165307953197296969697410619233826

1. Алгоритм Ламберта вычисления e

Задача 7. Составить программу вычисления приближения к основанию натуральных логарифмов, то есть к числу е, используя следующий алгоритм Ламберта:

Решение. Указанный алгоритм предложен Ламбертом в 1766 году [6, с.70]. Организовать по нему рекурсивные вычисления труда не составляет. Здесь величины a(k) и b(k) задаются рекуррентными соотношениями, похожими на определение чисел Фибоначчи, но нелинейными. Однако это обстоятельство не привносит каких-либо дополнительных затруднений в программную реализацию соответствующих функций. Дело в том, что задание последовательности любыми рекуррентными соотношениями сразу решает проблему триады: осуществлена параметризация задачи, выделена база и задана декомпозиция.

Программа e(k) приближенно вычисляет e, обращаясь к рекурсивным функциям-подпрограммам a(k) и b(k):

Учитывая, что последовательности a(k) и b(k) (k=0,1,2, …) определяются весьма схожим образом, можно построить одну общую функцию двух переменных для вычисления их членов. Отсюда ещё один вариант решения поставленной задачи:

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

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