Динамическое программирование: траектории кузнечика

Рет қаралды 76,836

5 жыл бұрын

Задача из ЕГЭ про граф дорог.
Количество различных траекторий кузнечика из 1 в N.
Реализация динамическим программированием.
Курс молодого бойца по информатике (Язык Си).
cs.mipt.ru/c_intro

Пікірлер: 69

@LIMESLYME 5 жыл бұрын

Спасибо огромное за все то, что вы делаете!

@aswonder5569 5 жыл бұрын

Эх, мне бы ваши лекции лет 15 назад... Я тогда рисовал сайт города и надо было на карте для некоторой точки в городе найти кратчайший маршрут, используя известные маршруты общественного транспорта. Ох, пришлось попотеть, до всего доходя своими мыслями и поиском алгоритмов в Интернете!

@crappydog7747 4 жыл бұрын

Кузнечик получился очень реалистичный

@tema_skakun 3 жыл бұрын

только коленки д.б. в другую сторону)

@niklkislshin9125 3 жыл бұрын

Вы замечательный преподаватель!

@olexandrchernov7697 Жыл бұрын

Это просто лучшее объяснение, спасибо огромное

@alexuspro26 Жыл бұрын

Более правильный ответ, конечно: if (n < 2) { return n; } else { return numberof(n - 1) + numberof(n - 2); } Но можно и через массив. С удовольствием послушал, спасибо.

@LebbLebb Жыл бұрын

Спасибо вам за курсы - постоянно открываю

@risesduckness 3 жыл бұрын

Благодарю за хороший урок!

@MrMitror 4 жыл бұрын

«Некоторые школьники думают 0» -не только школьники, скажу я вам)

@recreationreally4382 4 жыл бұрын

И скорее всего правы.

@padla6304 2 жыл бұрын

@@recreationreally4382 у прав столько же прав сколько у неправ

@andrey7530 4 жыл бұрын

спасибо за науку!!

@mar_kha Жыл бұрын

Потрясающее объяснение!)

@saitaro 5 жыл бұрын

Я в здоровой части YT, спасибо вам за это, Тимофей!

@recreationreally4382 4 жыл бұрын

Если у Вас в А - одна траектория, тогда во всех других будет +1, В, С по 2 траектории и т.д. Добавляя ребро (А,А) Вы усложняете задачу лишней информацией. В А - 0 траекторий, ибо нет ни одного входящего ребра и это признак начальной вершины Вашего графа. В J есть только входящие ребра: (G,J), (H,J), (I,J) и это признак конечной вершины.

@user-zp1rl4pi2i Жыл бұрын

я в программировании почти ноль) просто зашел к вам в гости

@user-ht1be5it7r 4 жыл бұрын

на 9:06 непоняточка: "формула для К равного 2 даёт 1" хотя корректнее было бы сказать "K при n равным 2 формула даёт 1"

@mihrankhachatryan3693 3 жыл бұрын

Он назвал меня школьником))

@Andrew_Petrovich_Zykov 11 ай бұрын

тут все школьники

@andrey7530 4 жыл бұрын

6:06 Тимофей, видимо, обратился к помощи калькулятора :), шутка )))

@user-iq5wx7qq4v 3 жыл бұрын

Х))

@sergen5298 2 жыл бұрын

По условию задачи кузнечик прыгает только на +1 или + 2! На 0 (т.е. "не прыгать") он не может. Значит попасть в город 1 из города 1 он не может. Просто считать это единицей удобно.

@user-gi7yg7yx4f Жыл бұрын

просто "удобно" подогнать под формулу. ведь 0! =1.

@hackerpro6073 Жыл бұрын

Можно ли это использовать для нахождения уникальных комбинаций из не минимизированых функций?

@user-fu9ix6xh7x 4 жыл бұрын

спасибо

@DiamondSane 4 жыл бұрын

4:48 Из города А в город А может быть 1 либо 0 траекторий, если мы договорились описывать траектории рёбрами ориентированного графа. На момент задания вопроса у вас не было нарисовано стрелки из А в А, что можно трактовать двояко: либо этой траектории нет, либо её не нарисовали чтобы не загромождать и такая траектория подразумевается существующей для каждого города. В ряде случаев такие умалчивания могут смущать учащихся.

@mihaitimofti9789 3 жыл бұрын

кстати а почему не считается циклом траектория из А в А?

@DiamondSane 3 жыл бұрын

@@mihaitimofti9789 по договорённости, как и всегда

@arrov1980 2 жыл бұрын

@@DiamondSane а почему он обсчитался? У него получилось 14, а всего вроде путей до J 12, но почему?

@igorsavelev9013 Жыл бұрын

А не планируется практики или алгоритмов и структур данных на си курса?

@II-is4ft Жыл бұрын

Спасибо

@nemounas2127 4 жыл бұрын

Интересный алгоритм. Правильно ли я понимаю, что если бы кузнечик мог прыгать еще и на +3 клетки нужно было бы просто в цикле прибавить еще K[i-3] ? Получается для n=5 такой массив [0, 1, 1, 2, 4, 7] И количество возможных вариантов попасть в 5 увеличиться до 7 ? Как можно получить 4 : 1-2-4 1-3-4 1-2-3-4 и добавляется еще четвертый вариант с прыжком +3: 1-4. Вроде бы работает верно?

@nemounas2127 4 жыл бұрын

Но это все как то теоретически. Для решения какой задачи его можно применить?

@iwansea6040 4 жыл бұрын

Тут объяснение куда понятнее чем в лекции)))

@onemiller5002 4 жыл бұрын

Так я все время решал через рекурсию, даже не зная этого))

@user-cg2fw3kw9d 3 жыл бұрын

Скажите пожалуйста, а при составлении расписаний, используется динамическое программирование?

@TheSanSanch 2 жыл бұрын

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

@jeen9984 4 жыл бұрын

10:08 Могу ошибаться, но статические массивы так создавать нельзя, т.к. размер должен быть константой. То что оно работает - это ub.

@siborgium9022 4 жыл бұрын

Начиная со стандарта C99 (Если использовать gcc-расширения стандарта, то с C90) такой код корректен. Обращу внимание, С, не С++.

@jeen9984 4 жыл бұрын

@@siborgium9022 Да, все верно. Почему-то не заметил, что на C пишут, а не на плюсах.

@TheKirk1989 Ай бұрын

Итак подытожим , что я сегодня узнал.. 1. из пункта "А" в пункт "А" оказывается есть один путь (учитывая что вариаций путей два это либо 1 прыжок, либо 2) 2. grasshopper - кузнечик (англ.)

@Drampam 3 жыл бұрын

Я может что-то совсем не понял? Но почему при формуле Kn = Kn-1 + Kn-2 в задаче маршрутов из 1 в 5 получается ответ 5??? n = 5, значит ответо должен быть Kn=5 = 4+3 = 7. Вариантов прыжков кузнечика при этом вообще 8: 1) 1->5; 2) 1->2->5; 3) 1->3->5; 4) 1->4->5; 5) 1->2->3->5; 6) 1->2->4->5; 7) 1->2->3->4->5; 8) 1->3->4->5 . Пожалуйста, объясните, я в панике :)))

@user-hx9zx1in9v 3 жыл бұрын

K5=K4+K3, K4=K3+K2, K3=K2+K1, K1=1, K2=1, следовательно K3=2, K4=3 и K5=5. Кузнечик прыгает на 1 или 2 шага, он не может прыгнуть из 1 в 5 или из 1 в 4 и т.д., поэтому вариантов не 8, а 5ть.

@entarossa 2 жыл бұрын

@@user-hx9zx1in9v Это числа Фибоначчи. Вариантов действительно 8 (варианты прыжков кузнечика для 5-ти): 1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 2 1 + 1 + 2 + 1 1 + 2 + 1 + 1 2 + 1 + 1 + 1 2 + 1 + 2 2 + 2 + 1 1 + 2 + 2

@llBARSll 2 жыл бұрын

@@entarossa у Вас рассчёт для 6-ти. На 5-ти он прыгает 4 раза, потому что в первой клетке он уже стоит по умолчанию. фиб: 1, 1, 2, 3, 5,

@AB-ex4iu Жыл бұрын

1:34-1:36 magic

@Lorienl2master 3 жыл бұрын

в начале вроде Ка-з = Ка-у + Ка-х + 2 (4.20 время)

@thepantelemon 4 жыл бұрын

Сорри, но я не понял 14 было правильно или нет?

@lGambit 4 жыл бұрын

Да.

@kirillshvedov8417 3 жыл бұрын

Да, когда уже школу закончил - это уж точно знаешь.Тут как бы не обсуждается.

@art4259 3 ай бұрын

Массив-то зачем? ;)

@Jax16432 2 жыл бұрын

Куплинов?

@topsy9818 10 ай бұрын

Объяснение топ, все круто, но когда включили демку с компа, я был в шоке... Почему такая древняя винда, такой древний софт... Вроде МФТИ, а как будто самая задрипанная школа...

@surname_name 4 жыл бұрын

В коника лапи не в ту сторону згинаються.

@rosalyrdw 6 ай бұрын

Я сначала подумала, что вы с Борисом Трушиным связаны, но нет Изменено: Так я путешествую, просто моя траектория это лежать на кровати

@sobakabasquerwilly1263 5 жыл бұрын

Вот если бы я увидел это когда сдавал ЕГЭ 4 года назад)))

@malyshevslava4664 4 жыл бұрын

я не понимаю этих ЕГЭ. Если там такие алгоритмы, которые требуют университетских знаний, зачем тогда потом университет?

@torcher5023 3 жыл бұрын

это не университетский алгоритм, такие задачи разбирают в 9 классе.

@user-ze7bo6jn1s 2 жыл бұрын

сложно даа

@zimniyhodok4622 4 жыл бұрын

О, животик уже виднеется

@kirillshvedov8417 3 жыл бұрын

Назвал бы функцию как function() ---> как-то ближе к народу русскому было бы. А так какие-то тражекторис какие-то...аж слух режет

@linterrupt 3 жыл бұрын

В программировании называть переменные и функции русскими названиями считается плохим тоном. Надо учить английский и привыкать писать на английском.

@kirillshvedov8417 3 жыл бұрын

@@linterrupt @Саша Коваленко да лол.я английский получше препода средненького универа знаю)))считаю для первичного понимния можно было бы фунцию как-то попроще назвать: типа myfunct/functAlloc и.т.д.) ну или в данном случае заменить tRaJEctory на path или ways) ну grasshoper - это вообще смех)))

@kirillshvedov8417 3 жыл бұрын

А так вообще по материалу вопросов нет)) спасибо за лекции)) очень помогаете при изучении С

@linterrupt 3 жыл бұрын

@@kirillshvedov8417 Вы ошиблись, поблагодарив меня, я простой комментатор. Лучше сразу формировать привычку писать на английском. На понимании это никак не отражается, поэтому не вижу смысла откладывать на потом.

@romaboy1052 4 жыл бұрын

калькулятор это не в духе динамического программирования. он в ВШЭ сбегал пнул дверь, те - набибулину,она-МВФ, те - ротшильдов с постели подняли .А почему все так быстро? А потому- CASH был, батенька...