рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Рекурсия и динамическое программирование

Рекурсия и динамическое программирование - раздел Транспорт, От автора В Этом И Всех Последующих Разделах Речь Пойдет Уже Не О Языке Программировани...

В этом и всех последующих разделах речь пойдет уже не о языке программирования Паскаль, а о задачах, которые вы можете решать с помощью этого языка, о наиболее интересных и полезных алгоритмах и приемах программирования. Сначала рассмотрим две несложные задачи, которые можно решить с помощью рекурсивного алгоритма. Первая из них состоит в вычислении n-го числа Фибоначчи. Мы знаем, что F0=0, F1=1 и Fn=Fn-1+Fn-2 для всех n³2. Запрограммируем эту рекуррентную формулу в виде рекурсивной функции

 

Function Fibonacci_Recursive(n:Word):LongInt;

Begin

If n<2 Then Fibonacci_Recursive:=n

Else Fibonacci_Recursive:=Fibonacci_Recursive(n-1) +Fibonacci_Recursive(n-2);

End;

 

Это правильная функция, но хорошая ли она? Вообще в каком смысле следует понимать этот критерий, какой алгоритм мы будем называть хорошим, а какой - плохим? Давайте начнем тестирование нашей функции, будем передавать ей n=1, n=2, ..., n=46 (для n, больших чем 46, число Фибоначчи уже не умещается в тип LongInt и программа завершится аварийно) и будем засекать время t(n), которое потребуется для выполнения алгоритма. Для n<20 время настолько мало, что засечь его не удается, но затем оно начинает довольно быстро расти, и примерно при n=25 мы почувствуем некоторый дискомфорт : t(25)=1,05 секунды, t(26)=1,65 секунды, ... t(30)=11,25 секунд, t(31)=18,25 секунды, t(32)=29,5 секунды ... t(35)=125 секунд ... t(40)=1385 секунд. Здесь наше терпение кончилось, и мы прервали программу, так как все уже ясно - время работы алгоритма обладает тем же свойством, что и сами числа Фибоначчи: t(n)=t(n-1)+t(n-2). Теперь можно приблизительно оценить время, необходимое программе для вычисления F46, оно примерно равно 414 минутам, или почти 7 часам. Автор полагает, что даже очень далекий от математики человек справится с этой задачей гораздо раньше, имея лишь лист бумаги и карандаш. Почему наша функция работает так медленно, ведь она правильная? Это определяется сложностью алгоритма. Сложность - это одно из наиболее фундаментальных понятий теории алгоритмов; говорят, что алгоритм имеет сложность f(n), если количество операций, которые необходимо выполнить для вычисления некоторого значения, равно C×f(n), где C - константа, не зависящая от n. Наш алгоритм, очевидно, имеет сложность Fn. Известно, что Fn³an-2, где a=(Ö5+1)/2, следовательно, сложность нашего алгоритма не меньше, чем an. В этом случае говорят, что алгоритм имеет степенную сложность. Хороши или плохи такие алгоритмы? Очевидный ответ “такие алгоритмы плохие” не совсем верен. Качество алгоритма определяется не только его сложностью, но и тем кругом задач, в котором его предполагается использовать. Если мы уверены, что нам потребуются лишь числа Фибоначчи с небольшими номерами, и их будет не очень много, то рекурсивный алгоритм вполне приемлем, в противном случае он не годится. Запишем теперь алгоритм вычисления числа Фибоначчи, имеющий сложность n:

 

Function Fibonacci_Dynamical(n:Word):LongInt;

Var

a0,a1,a2: LongInt;

k : Word;

Begin

If n<2 Then Begin

Fibonacci_Dynamical:=n;

Exit;

End;

a0:=0;

a1:=1;

For k:=2 To n Do Begin

a2:=a0+a1; a0:=a1; a1:=a2;

End;

Fibonacci_Dynamical:=a2;

End;

 

Эта функция пользуется той же самой рекуррентной формулой, что и первая, но вычисляет числа Фибоначчи в другой последовательности: F0,F1, ..., Fn. Для вычисления каждого очередного Fk необходимо выполнить некоторое фиксированное число операций C, следовательно, всего потребуется C×n действий и алгоритм имеет сложность n. В этом алгоритме мы использовали метод, который называется динамическое программирование. И это уже не первый раз - вспомните, как мы вычисляли n!. В общем случае динамическим программированием называют метод вычисления некоторой величины, заданной рекуррентными формулами, в последовательности “снизу вверх”: пусть требуется вычислить Q(n) и известно, что Q(n)=F(Q(n-1),Q(n-2),...,Q(n-k)). Вычислим сначала Q(1), затем Q(2), Q(3) и так далее, пока не дойдем до нужного нам значения Q(n). Алгоритмы динамического программирования, как правило, являются наиболее эффективными из всех известных алгоритмов решения данной задачи. Существуют ли алгоритмы вычисления числа Фибоначчи со сложностью, меньшей чем n? Да, известен алгоритм сложности log2(n), но мы не станем рассматривать его здесь.

Теперь решим еще одну задачу: найти C(n,m) - число сочетаний по m из n элементов. Конечно, мы знаем, что биномиальный коэффициент C(n,m) можно вычислить по прямой формуле C(n,m)=n!/m!/(n-m)!, но здесь мы не будем использовать эту возможность (отметим, что для больших n, m эта формула в компьютерных вычислениях непригодна). Известна рекуррентная формула C(n,m) = C(n-1,m-1) + C(n-1,m), C(n,n) = C(n,0) = 1, примем ее за основу нашего алгоритма. Запишем сначала рекурсивный алгоритм

 

Function Cnm_Recursive(n,m:Byte):LongInt;

Begin

If(n=m)Or(m=0) Then Cnm_Recursive:=1

Else Cnm_Recursive:=Cnm_Recursive(n-1,m-1)+Cnm_Recursive(n-1,m);

End;

 

Оценим его сложность. Так же, как в случае с числами Фибоначчи, функция будет углубляться в рекурсию (уменьшая n и m), пока не встретит биномиальный коэффициент, равный единице; таким образом, вычисляемое значение фактически есть сумма нужного количества единиц. Следовательно, сложность этого алгоритма равна C(n,m). Заменяя факториалы их приближенными значениями по формуле Стирлинга, получим nn/mm/(n-m)n-m - это степенная сложность (пусть для простоты m=n/2, тогда сложность равна 2n). Мы уже убедились, что алгоритмы со степенной сложностью не годятся при больших n, это справедливо и для данной функции. Запишем более эффективный алгоритм, используя известный как “треугольник Паскаля” способ вычисления биномиальных коэффициентов (к языку Паскаль данный термин имеет лишь косвенное отношение). Треугольник Паскаля - это треугольная таблица вида

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

..................

В этой таблице значение C(n,m) находится в m-м столбце n-й строки (строки и столбцы нумеруются, начиная с нуля). Будем последовательно вычислять первую, вторую, третью и так далее строку, пока не вычислим строку с номером n. Очевидно, что это тоже алгоритм динамического программирования. Оценим сложность алгоритма. Нам необходимо вычислить полностью n строк треугольника и, возможно, неполную еще одну строку. Для вычисления k-й строки необходимо C(k+1) операция; итак, потребуется всего C+2C+...+nC+ (m+1)C операций, используя формулу для суммы арифметической прогрессии, запишем это число в более простом виде: C((n+1)n/2+m+1)=C/2(n2+n+2m+2). Пренебрегая малыми слагаемыми и приняв C/2 за новую константу C, получим C×n2 - алгоритм имеет сложность n2. Запишем соответствующую функцию, обратите внимание, что в программе нет никакой необходимости хранить всю таблицу, достаточно лишь помнить две строки - предыдущую и текущую.

 

Function Cnm_Dynamical(n,m:Byte):LongInt;

Var

C0,C : Array[0..100] Of LongInt;

k,j : Byte;

Begin

k:=1; C[0]:=1; C[1]:=1;

While k<n Do Begin

C0:=C;

Inc(k);

C[0]:=1;

For j:=1 To k-1 Do C[j]:=C0[j-1]+C0[j];

C[k]:=1;

End;

Cnm_Dynamical:=C[m];

End;

– Конец работы –

Эта тема принадлежит разделу:

От автора

B r... Теперь мы можем присвоить переменным их значения...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Рекурсия и динамическое программирование

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

От автора
Первое издание этой книги вышло в свет в 1997 году и довольно быстро стало библиографической редкостью. Автор несколько неожиданно для себя обнаружил, что книга пользуется черезвычайно высоким спро

Round(x) - округленное до целого вещественное число, преобразованное к типуLongInt
6. Sqr(x) - квадрат числа 7. Sqrt(x) - квадратный корень 8. Exp(x) - экспонента 9. Ln

Символьный тип данных
Для хранения символьной информации в Паскале предусмотрен специальный тип данных Char. Допустимы переменные, нетипизированные и типизированные константы такого типа. Данные типа

Caseвыражение Of
список значений : оператор/блок .................................. список значений: оператор/блок

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

Открытые массивы и нетипизированные параметры
Из предыдущего раздела мы узнали, что параметры подпрограмм описываются как [Var] имя : имя типа , это правда, но не вся правда - существует еще два

Множества
Понятие множества в Паскале очень близко к математическому определению: множество - это совокупность однотипных неиндексированных объектов. Множества

Графические средства языка Паскаль
Монитор персонального компьютера может работать в двух режимах - текстовом и графическом. Все, что мы делали до сих пор, мы делали в текстовом режиме. Текстовый экран содержит 2000 знако

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

Case тип Of
константа 1 : (описание поля); константа 2 : (описание поля); .....................

Модуль Crt
Crt - еще один стандартный модуль Паскаля, в котором содержатся разнообразные средства консольного ввода-вывода (то есть ввода с клавиатуры и вывода на текстовый экран). Процедуры

Var TextAttr : Byte
В ней содержится текущий цвет фона и цвет символов, используемые при выводе на экран процедурами Write иWriteLn. Изменив эту переменную, вы задаете новый

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

Type SearchRec=Record
Fill : Array[1..21] of Byte; Attr : Byte; Time : LongInt; Size : LongInt; Name : Stri

Процедурные типы
Язык Паскаль позволяет использовать в программе данные типа “процедура” или типа “функция”. Такие данные можно передавать как аргументы подпрограмм, можно описывать и использовать массивы процедур

Указатели и динамическая память
Указателями называются переменные и константы, значениями которых являются адреса. Различаются два вида указателей - обобщенные указатели и

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

Открытые строки
  Открытыми строками, или длинными строками, или C-строками, называются символьные последовательности длиной до 65535 символов, ограниченные справа нуль-символ

Использование командной строки и вызов внешних программ
Паскаль позволяет передавать информацию в программу при ее запуске через командную строку. Для этого служат две стандартные функции -ParamCount и ParamStr.

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

Объекты
Объектом в языке Паскаль называется совокупность данных и подпрограмм, обрабатывающих эти данные. Программирование с использованием объектов называется объектно-о

Type имя типа=Object
описание полей описание методов End; Поля объектов описываются так же, как поля записей, а описание метода - это заголовок процедуры или функции. Сами методы распол

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

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

Комбинаторные алгоритмы
В этом разделе мы рассмотрим три наиболее важные задачи комбинаторики: нахождение всех подмножеств множества из n элементов; нахождение всех выборок по m элементов из n элементов и нахождение всех

Бинарные деревья
В этом разделе мы рассмотрим различные алгоритмы обхода бинарного дерева. К алгоритмам создания бинарного дерева мы обратимся несколько позже, а пока будем считать, что дере

Упорядоченные бинарные деревья и приоритетные очереди
Упорядоченным бинарным деревом, или бинарным деревом поиска, называют дерево, в любой части которого элементы левого поддерева меньше корневого элеме

Алгоритмы сортировки
В этом разделе мы рассмотрим различные алгоритмы решения задачи сортировки. Задача сортировки ставится следующим образом: дана последовательность записей R1,R

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги