Динамическое программирование сверху и снизу
HTML-код
- Опубликовано: 12 авг 2018
- Скорость рекуррентного вычисления чисел Фибоначчи.
Проблема повторных вычислений.
Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений
Динамическое программирование сверху и снизу.
Курс молодого бойца по информатике (Язык Си).
cs.mipt.ru/c_intro
Красавчик! Всем б таких преподов в школы/универы.
очень круто! спасибо вам! много полезного узнал. а про кеширование результатов рекурсивной функции - вообще огонь! толи еще будет))
Это нечто! Лучшее, что я видел
Полностью поддерживаю!)
талантливо и просто объяснено то, до чего сам доходил очень долго. не зная как это называется:):) Спасибо.
Пожалуй лучшее объяснение, и даже не важно что не на родном С
Я таксист, но очень интересно)).
еще не поздно стать программистом
@@vip51000 уже)))
@@user-dl3zo8xf7g история с хорошим окончанием :)))
в каком возрасте вы решили быть программистом?
Потрясное объяснение, вы лучший
очень круто, очень красиво...
Лучшее объяснение ДП 👍
human resource machine был такой уровень только там примерно такой код должен быть.
int f[2] = { 0,1 };
for (int i = 0; i < 40; i++)
{
f[i % 2] = f[0] + f[1];
printf(" %d
", f[i % 2]);
}
Метод снизу кажется логически более простым для осознания так сказать... но блин тот который сверху, с рекурсией, очень красиво получилось, я долго сидел осознавал) Вот для питона что у меня получилось:
#динамический метод с рекурсией(сверху)
F=[0]*100
def fib(n):
if n
cache = {}
def fib(n):
try:
return cache[n]
except KeyError:
if n
def fib(n):
fibs=[0, 1]
for i in range(2, n+1):
fibs.append(fibs[i-1] + fibs[i-2])
return fibs[n]
сразу видно челы даже про декораторы никогда не слышали
ого как здорово. Спасибо
Спасибо!
восторг.
Круто👍
Желаю всем такого препода
👍👍👍
Добрый вечер. Вы можете помочь по питону?
Плохо что термин "динамическое программирование" придуманный в 1940 годах совсем не соответствует значению слова "динамический".
По сути здесь ключевым является термин "Кеширование". Используя различные вариации Кеша, сверху снизу.. получаем то что получаем.
Далее можем развивать Кеш, добавляя к нему уровни вложенности и ограничивая время хранения Кеша на разных уровнях.
меня, в свое время, воодушевил этот пример, что так лихо можно кэшировать и настолько ускорять производительность кода. Смущала только затраченная память, потом дошел до того, что не обязательно кэшировать в память, можно просто переменными передавать нужные параметры. А сегодня увидел такое:
Python3
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return n + fib(n-1)
Вопрос: зачем нужно было вызывать функцию два раза в примере из видео?
Шутка, код выше - это модификация нахождения факториала и она работает не правильно 😂
Но можно сделать так:
def fib(n):
if n
А почему компилятор не выдает ошибку, связанную с int Fib[n+1] ? Массив же статический, значит, n должно быть известно
В новом стандарте можно так делать. Но только для локальных переменных.
Я тоже удивлен. У меня С11 тож в сборке mingw, и мой компилятор такое не пропускает.
Поправочка, компилятор не пропускает, если попытаться в той же строке инициализировать все элементы в нули. Если просто объявить массив, то можно :\
Начиная со стандарта С99 можно делать такие определения внутри функции. Память в этом случае выделяется на стеке, в отличие от malloc, который выделяет в куче.
Я в этом ничего не понимаю, решил просто так послушать и на 3:02 не понятно, почему 1+0 возвращает 0?
Бывает, оговорка. Сказал одно, а на доске другое.
Чёта я не догнал, чем второй (последний) метод лучше рекурсии с кешированием, когда у него производительность хуже, цикл в цикле, плюс массив создаётся в каждом вызове fib_dynamic
@@saltylungs о каком вложенном цикле идёт речь - функция fib_dynamic() содержащая цикл в строке 19 выполняется в цикле в строке 26
Ну с кешированием однозначно быстрее, там на тот же самый fib_dynamic(500) цикл прогонится 498 раз, а на верхнюю функцию, если до этого вызывались fib 499, то и вычислиться с 2 вызовыми. fib(500) = fib (499) и fib(498).
По ощущением fin_dynamic это вообще не относится к динамическому программированию, конкретно под термин "решить каждую подзадачу только один раз". Либо я чего-то не понимаю. Но сложность функции find_dynamic получается O(n-2), даже если были известны до этого вычисления.
хммм... А если такое дерево? )
int Fib(int n)
{
while (n>0)
{
Fib(--n);
}
return n;
}
кроме того еще и стек переполниться может в первом варианте программы.
А разве cache[n] = fib(n-1) + fib(n-2) нельзя заменить на cache[n] = fib(n-1) + cache[n-2]?
да, можно. Так будет более оптимизированно.
Забавно, но в данной задаче мне бы и в голову не пришла мысль о рекурсии, а вот второй вариант решения, по-моему, очевиден... Честно говоря, не могу себе даже представить задачу, которую можно было бы решить только с помощью рекурсии, потому вообще считаю это бесполезной побочкой логики работы выислительных систем просто.
Інколи завдяки рекурсії зручно "дочекатися" (встановлюючи інтервали очікування) "чогось", на що не зручно повісити listener чи observer. На практиці це виручає наприклад в JavaScript, коли використовуються кілька різних бібліотек і динамічно додаються елементи в DOM. Такий собі спосіб async await))
What
10:08 "глубина погружения все равно большая" - неправда, глубина всего одного вызова
нет, макс. глубина вызова ~n, см. на доску
Имелся ввиду пример с fib(1=>50), всё в кеше
@@NewMrCricket при чем кэш, если речь шла о стэке? И глубина более одного вызова.
@@ukravenger3924
Строка 17: вызываем fib(1) => fib(50), значит при n==40 (например), мы имеем в кеше результаты всех предыдущих n => fib(1-39)
То есть при вызове, например, fib(40), мы
а) в строке 9 не находим значение для n==40 в кеше, затем
б) в строке 10 вызываем fib(39) => то есть уходим на один вызов в стеке глубже => находим значение для n==39 в кеше (строка 11), и возвращаемся в fib(40)
в) в строке 10 вызываем fib(38) => то есть уходим на один вызов в стеке глубже => находим значение для n==38 в кеше (строка 11), и возвращаемся в fib(40)
Значит, при вызове fib(40) мы дважды спустились по стеку на глубину == 1 и вернулись.
А в начале 11й минуты автор говорит "с кешированием или без, память мы не экономим, глубина погружения все равно большая", но ведь в его примере глубина погружения == 1? (Ну, или 2, смотря как считать)
@@NewMrCricket в этом случае повезло с предыдущими вызовами, но так везет далеко не всегда ) Тимофей, скорее всего, имел в виду общий случай.
Почему мне это попало в рекомендации? Что это за убогий подход вообще.. Всего нужно 2 кеш числа, потому что каждая N итерация будет затрагивать только лишь N-1 и N-2, и при следующем витке происходит смещение итератора и замена N-2 на N, оставляя уже для следующей суммы опять N-1(бывшая N), и N-2(бывшая N-1).