Слово
«fib»впервые сказано пользователем
ramzai 18.03.2008 в 09:20,
и с тех пор употреблялось
35 раз.
Сообщения со словом
«fib»
Запрос выполнился за
0.0043 сек.
- 18.03.2008, 09:20. ramzai в теме
«Неделя 6. Динамическое программирование»
... числа фибоначчи была бы рекурсивная функция код int fib int n if n 1 return n else return fib n 1 fib n 2 при вызове скажем fib 5 происходит следующее 1 fib 5 2 fib 4 fib 3 3 fib 3 fib 2 fib 2 fib 1 4 fib 2 fib 1 fib 1 fib 0 fib 1 fib 0 fib 1 5 fib 1 fib 0 fib 1 fib 1 fib 0 fib 1 fib 0 fib 1 одна и та же функция вызывается много раз хотя было бы достаточно рассчитать ее лишь однажды так если составить небольшую программу для подсчета количества вызова функции код long long cnt int fib int n cnt if n 1 return n else return fib n 1 fib n 2 int main cnt 0 cout fib 40 endl cout cnt endl return 0 то для fib 40 мы получаем 331160281 вызовов функции fib что работает примерно 3 секунды на моем компьютере помним что 10 8 операций обрабатываются примерно за 1 секунду попробуем уменьшить это число динамическое программирование метод решения задач состоящих из перекрывающихся подзадач позволяющий избежать многократного вычисления одних и тех же подзадач первым используемым приемом является запоминание memoization будем хранить массив вычисленных значений изначально проинициализированный значениями которых не может быть в последовательности например -1 теперь при вызове функции будем проверять не было ли рассчитано ее значение для данного аргумента если было то мы его просто возвращаем не порождая новых вызовов иначе рассчитываем и сохраняем код int a 50 long long cnt int fib int n cnt if a n -1 if n 1 a n n else a n fib n 1 fib n 2 return a n int main cnt 0 memset a -1 sizeof a cout fib 40 endl cout cnt endl return 0 здесь каждая функция...