Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


Динамическое программирование

Поиск:

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

Вычислить N чисел в последовательности Фибоначчи, — 1, 1, 2, 3, 5, 8, … — в которой первые два члена равны единице, а все остальные представляют собой сумму двух предыдущих. N меньше 100.

Самый очевидный способ 'решения' задачи состоит в написании рекурсивной функции примерно следующего вида:

Код

    Function F(X:integer):longint;
    Begin
          if (X=1) or (X=2) then F:=1 else F := F(X-1) + F(X-2)
    end;



При этом на шестом-седьмом десятке программа 'подвесит' самый быстрый компьютер. Попробуем разобраться, почему так происходит?

Для вычисления F(40) мы сперва вычисляем F(39) и F(38). Причем F(38) мы считаем “по новой”, “забывая”, что уже вычислили его, когда считали F(39).

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

Var D : Array [1..100] of LongInt;

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

Функция принимает следующий вид (не верьте, пожалуйста, книгам, утверждающим, что искать числа Фибоначчи рекурсивно нельзя в принципе — можно, если отсечение делать с умом):

 
Код

   Function F(X : integer) : LongInt;
    Begin
      if D[X] = 0 then
            if (X=1) or (X=2)
            then D[X] := 1
            else D[X] := F(x-1) + F(x-2);
      F := D[X]
    End;


Этот подход динамического программирования называется подходом 'сверху вниз'. Он запоминает решенные задачи, но очередность решения задач все равно контролирует рекурсия.

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


        D[1] := 1; D[2] := 1;
        For i := 3 to X do
                  D[i] := D[i-1] + D[i-2];


Здесь использован подход 'снизу вверх'. Чаще всего такой способ раза в три быстрее. Однако, в ряде случаев такой метод приводит к необходимости решать большее количество подзадач, нежели при рекурсии.

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

Общий совет таков: ишите и тестируйте рекурсивную форму, а переделыванием занимайтесь, если ваша программа превышает отведенное ей время на 'больших' тестах.
Сайт: manual.ru






Просмотров: 4046

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную