Метод снизу кажется логически более простым для осознания так сказать... но блин тот который сверху, с рекурсией, очень красиво получилось, я долго сидел осознавал) Вот для питона что у меня получилось: #динамический метод с рекурсией(сверху) F=[0]*100 def fib(n): if n
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]); }
меня, в свое время, воодушевил этот пример, что так лихо можно кэшировать и настолько ускорять производительность кода. Смущала только затраченная память, потом дошел до того, что не обязательно кэшировать в память, можно просто переменными передавать нужные параметры. А сегодня увидел такое: 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
Плохо что термин "динамическое программирование" придуманный в 1940 годах совсем не соответствует значению слова "динамический". По сути здесь ключевым является термин "Кеширование". Используя различные вариации Кеша, сверху снизу.. получаем то что получаем. Далее можем развивать Кеш, добавляя к нему уровни вложенности и ограничивая время хранения Кеша на разных уровнях.
Я тоже удивлен. У меня С11 тож в сборке mingw, и мой компилятор такое не пропускает. Поправочка, компилятор не пропускает, если попытаться в той же строке инициализировать все элементы в нули. Если просто объявить массив, то можно :\
Начиная со стандарта С99 можно делать такие определения внутри функции. Память в этом случае выделяется на стеке, в отличие от malloc, который выделяет в куче.
Забавно, но в данной задаче мне бы и в голову не пришла мысль о рекурсии, а вот второй вариант решения, по-моему, очевиден... Честно говоря, не могу себе даже представить задачу, которую можно было бы решить только с помощью рекурсии, потому вообще считаю это бесполезной побочкой логики работы выислительных систем просто.
Інколи завдяки рекурсії зручно "дочекатися" (встановлюючи інтервали очікування) "чогось", на що не зручно повісити listener чи observer. На практиці це виручає наприклад в JavaScript, коли використовуються кілька різних бібліотек і динамічно додаються елементи в DOM. Такий собі спосіб async await))
Чёта я не догнал, чем второй (последний) метод лучше рекурсии с кешированием, когда у него производительность хуже, цикл в цикле, плюс массив создаётся в каждом вызове fib_dynamic
Ну с кешированием однозначно быстрее, там на тот же самый fib_dynamic(500) цикл прогонится 498 раз, а на верхнюю функцию, если до этого вызывались fib 499, то и вычислиться с 2 вызовыми. fib(500) = fib (499) и fib(498). По ощущением fin_dynamic это вообще не относится к динамическому программированию, конкретно под термин "решить каждую подзадачу только один раз". Либо я чего-то не понимаю. Но сложность функции find_dynamic получается O(n-2), даже если были известны до этого вычисления.
@@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, смотря как считать)
Почему мне это попало в рекомендации? Что это за убогий подход вообще.. Всего нужно 2 кеш числа, потому что каждая N итерация будет затрагивать только лишь N-1 и N-2, и при следующем витке происходит смещение итератора и замена N-2 на N, оставляя уже для следующей суммы опять N-1(бывшая N), и N-2(бывшая N-1).
Пожалуй лучшее объяснение, и даже не важно что не на родном С
Красавчик! Всем б таких преподов в школы/универы.
очень круто! спасибо вам! много полезного узнал. а про кеширование результатов рекурсивной функции - вообще огонь! толи еще будет))
Это нечто! Лучшее, что я видел
Полностью поддерживаю!)
талантливо и просто объяснено то, до чего сам доходил очень долго. не зная как это называется:):) Спасибо.
Я таксист, но очень интересно)).
еще не поздно стать программистом
@@vip51000 уже)))
@@АлександрИванов-п4и9ь история с хорошим окончанием :)))
в каком возрасте вы решили быть программистом?
Потрясное объяснение, вы лучший
Лучшее объяснение ДП 👍
Желаю всем такого препода
Метод снизу кажется логически более простым для осознания так сказать... но блин тот который сверху, с рекурсией, очень красиво получилось, я долго сидел осознавал) Вот для питона что у меня получилось:
#динамический метод с рекурсией(сверху)
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]
сразу видно челы даже про декораторы никогда не слышали
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]);
}
очень круто, очень красиво...
ого как здорово. Спасибо
меня, в свое время, воодушевил этот пример, что так лихо можно кэшировать и настолько ускорять производительность кода. Смущала только затраченная память, потом дошел до того, что не обязательно кэшировать в память, можно просто переменными передавать нужные параметры. А сегодня увидел такое:
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
Спасибо!
Круто👍
Плохо что термин "динамическое программирование" придуманный в 1940 годах совсем не соответствует значению слова "динамический".
По сути здесь ключевым является термин "Кеширование". Используя различные вариации Кеша, сверху снизу.. получаем то что получаем.
Далее можем развивать Кеш, добавляя к нему уровни вложенности и ограничивая время хранения Кеша на разных уровнях.
В чём может быть проблема, если и с кешем, и без кеша время выполнения одинаково (первые два рассматриваемых случая)?
Windows, MinGW, gcc
восторг.
А почему компилятор не выдает ошибку, связанную с int Fib[n+1] ? Массив же статический, значит, n должно быть известно
В новом стандарте можно так делать. Но только для локальных переменных.
Я тоже удивлен. У меня С11 тож в сборке mingw, и мой компилятор такое не пропускает.
Поправочка, компилятор не пропускает, если попытаться в той же строке инициализировать все элементы в нули. Если просто объявить массив, то можно :\
Начиная со стандарта С99 можно делать такие определения внутри функции. Память в этом случае выделяется на стеке, в отличие от malloc, который выделяет в куче.
👍👍👍
А разве cache[n] = fib(n-1) + fib(n-2) нельзя заменить на cache[n] = fib(n-1) + cache[n-2]?
да, можно. Так будет более оптимизированно.
Я в этом ничего не понимаю, решил просто так послушать и на 3:02 не понятно, почему 1+0 возвращает 0?
Бывает, оговорка. Сказал одно, а на доске другое.
Добрый вечер. Вы можете помочь по питону?
Забавно, но в данной задаче мне бы и в голову не пришла мысль о рекурсии, а вот второй вариант решения, по-моему, очевиден... Честно говоря, не могу себе даже представить задачу, которую можно было бы решить только с помощью рекурсии, потому вообще считаю это бесполезной побочкой логики работы выислительных систем просто.
Інколи завдяки рекурсії зручно "дочекатися" (встановлюючи інтервали очікування) "чогось", на що не зручно повісити listener чи observer. На практиці це виручає наприклад в JavaScript, коли використовуються кілька різних бібліотек і динамічно додаються елементи в DOM. Такий собі спосіб async await))
хммм... А если такое дерево? )
int Fib(int n)
{
while (n>0)
{
Fib(--n);
}
return n;
}
кроме того еще и стек переполниться может в первом варианте программы.
Чёта я не догнал, чем второй (последний) метод лучше рекурсии с кешированием, когда у него производительность хуже, цикл в цикле, плюс массив создаётся в каждом вызове 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), даже если были известны до этого вычисления.
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 в этом случае повезло с предыдущими вызовами, но так везет далеко не всегда ) Тимофей, скорее всего, имел в виду общий случай.
What
Почему мне это попало в рекомендации? Что это за убогий подход вообще.. Всего нужно 2 кеш числа, потому что каждая N итерация будет затрагивать только лишь N-1 и N-2, и при следующем витке происходит смещение итератора и замена N-2 на N, оставляя уже для следующей суммы опять N-1(бывшая N), и N-2(бывшая N-1).