МОДУЛЬ1.Рекуррентное соотношение, рекурсия

Параметры задачи. понятие задачи и подзадачи. рекуррентное соотношение.

ПРИМЕР1

При формулировке любой задачи необходимо определить исходные данные, которые мы будем называть параметрами задачи.

Например, если мы решаем задачу нахождения корней квадратного уравнения ax² + bx + c = 0, то эта задача определяется тремя параметрами - коэффициентами a, b и c.

Если же мы хотим решить задачу нахождения среднего арифметического некоторого набора чисел, то параметрами задачи будут количество чисел и их значения.

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

Здесь и далее в качестве параметров будут рассматриваться целые неотрицательные числа.

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

После того, как задача формализована (представлена) в виде функции с некоторыми аргументами, определим понятие подзадачи.

Под «подзадачей» мы будем понимать ту же задачу, но с меньшим числом параметров или задачу с тем же числом параметров, но при этом хотя бы один из параметров имеет меньшее значение.

Найти самую тяжелую монету из 10 монет.

Для формализации задачи определим функцию "Самая тяжелая монета", аргументами которой являются количество монет (10) и масса каждой из монет. Пока нас не интересует конкретный вид этой функции, для нас важнейшим фактором является факт, что она дает правильное решение. Для данной задачи можно рассмотреть 9 подзадач, которые имеют меньшее значение аргументов:

"Самая тяжелая монета" из 1 монеты,

"Самая тяжелая монета" из 2 первых монет,

"Самая тяжелая монета" из 3 первых монет,

...

"Самая тяжелая монета" из 9 первых монет.

Данную задачу можно свести к различным наборам подзадач, например:

найти самую тяжелую из 9 монет, а затем найти самую тяжелую из 2 монет (найденной из 9 и оставшейся)

или найти самую тяжелую из 5 монет, затем самую тяжелую из других 5 монет, а затем самую тяжелую из 2 монет, найденных на предыдущих шагах.

Возможны и другие наборы, но нетрудно заметить, что все они основываются на одной подзадаче: найти самую тяжелую из 2 монет.

В приведенном примере исходная задача сводится к подзадачам с меньшим числом параметров, в данном случае — с меньшим количеством монет.

Text Box: Одним из основных способов решения задач является их сведение к решению такого набора подзадач, чтобы, исходя из решений подзадач, было возможно получить решение исходной задачи.

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

—

МЕТОД РЕШЕНИЯ ЗАДАЧИ С ПОМОЩЬЮ РАЗБИЕНИЯ ЕЕ НА ПОДЗАДАЧИ

Пример2

Найти наибольший общий делитель (НОД) двух натуральных чисел N и M.

Подзадачи:

1. НОД(X,Y) =X, если Y=0 .

2. НОД(X,Y) = НОД(Y, X mod Y) при Y≠0.

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

A{i}=a{i-1}+d

Формулы, выражающие очередной член последовательности через один или несколько предыдущих членов, называют рекуррентными соотношениями.

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

2. Составить программу-функцию возвращающую величину aⁿ.

3. Составить программу—функцию вычисления последовательности Фибоначчи

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

5. Треугольник Паскаля

6. Количество делителей. Составить программу-функцию подсчета для натурального числа n количества всех его делителей.

7. Составить программу-функцию проверяющую, является ли заданное натурально число n простым?

8. Составить программу-функцию подсчета количества x(m) разбиений натурального числа m, то есть его представления в виде суммы натуральных чисел.

9. Последовательность из латинских букв строится следующим образом. На нулевом шаге она пуста. На каждом последующем шаге последовательность удваивается, то есть приписывается сама к себе, и к ней слева добавляется очередная буква алфавита (a,b,c,…). По заданному числу n определить символ, который стоит на n-ом месте последовательности, получившейся после шага 26.

Задачи, решения, код программы PASCAL

рекуррентное соотношение

Соотношения, связывающие одни и те же функции, но с различными аргументами, называются рекуррентными соотношениями или рекуррентными уравнениями.

Правильными рекуррентными соотношениями (уравнениями) будем называть такие рекуррентные соотношения, у которых количество или значения аргументов у функций в правой части соотношения меньше количества или, соответственно, значений аргументов функции в левой части соотношения. Если аргументов несколько, то достаточно уменьшения одного из аргументов.

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

Суть метода решения задач с помощью рекуррентных соотношений заключается в том, чтобы:

· Установить факт возможности решения задачи данным методом, то есть убедиться, что реккурентное соотношение существует и есть смысл тратить время на его поиски и вывод;

· Ввести рекуррентную величину от одного, двух и более параметров;

· Определить, как найти результат решения задачи при вычислении рекуррентной величины;

· Установить начальные значения рекуррентной величины;

· Исходя из специфики задачи, ввести корректное рекуррентное соотношение;

· Проверить правильность рекуррентного соотношения для значений, просчитанных вручную или вспомогательными программами; в этот момент можно реализовать саму программу, вычисляющую рекуррентную величину;

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

Пример 1 Задача нахождения суммы N элементов таблицы A.

Пример 3. Вычислить значение суммы S = 1/1! + 1/2! + ... + 1/k!

Упражнение для самостоятельной работы

Нахождения произведения N элементов таблицы A, используя рекуррентную формулу

Нахождения максимума N элементов таблицы A.

Вычислить Σ(-1)ⁱxⁱ/i! Для i=1,...,n;

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

Написать рекуррентную формулу для подсчета количества различных укладок плитками размера 1х2 коридора размера 2хN.