Динамическое программирование: траектории кузнечика
Вставка
- Опубліковано 12 сер 2018
- Задача из ЕГЭ про граф дорог.
Количество различных траекторий кузнечика из 1 в N.
Реализация динамическим программированием.
Курс молодого бойца по информатике (Язык Си).
cs.mipt.ru/c_intro
Спасибо огромное за все то, что вы делаете!
Эх, мне бы ваши лекции лет 15 назад... Я тогда рисовал сайт города и надо было на карте для некоторой точки в городе найти кратчайший маршрут, используя известные маршруты общественного транспорта. Ох, пришлось попотеть, до всего доходя своими мыслями и поиском алгоритмов в Интернете!
Вы замечательный преподаватель!
Кузнечик получился очень реалистичный
только коленки д.б. в другую сторону)
Это просто лучшее объяснение, спасибо огромное
Спасибо вам за курсы - постоянно открываю
Благодарю за хороший урок!
«Некоторые школьники думают 0»
-не только школьники, скажу я вам)
И скорее всего правы.
@@recreationreally4382 у прав столько же прав
сколько у неправ
спасибо за науку!!
Потрясающее объяснение!)
Я в здоровой части YT, спасибо вам за это, Тимофей!
Более правильный ответ, конечно:
if (n < 2) { return n; } else { return numberof(n - 1) + numberof(n - 2); }
Но можно и через массив. С удовольствием послушал, спасибо.
на 9:06 непоняточка: "формула для К равного 2 даёт 1" хотя корректнее было бы сказать "K при n равным 2 формула даёт 1"
Можно ли это использовать для нахождения уникальных комбинаций из не минимизированых функций?
6:06 Тимофей, видимо, обратился к помощи калькулятора :), шутка )))
Х))
Если у Вас в А - одна траектория, тогда во всех других будет +1, В, С по 2 траектории и т.д. Добавляя ребро (А,А) Вы усложняете задачу лишней информацией. В А - 0 траекторий, ибо нет ни одного входящего ребра и это признак начальной вершины Вашего графа. В J есть только входящие ребра: (G,J), (H,J), (I,J) и это признак конечной вершины.
спасибо
Он назвал меня школьником))
тут все школьники
Спасибо
я в программировании почти ноль) просто зашел к вам в гости
А не планируется практики или алгоритмов и структур данных на си курса?
По условию задачи кузнечик прыгает только на +1 или + 2! На 0 (т.е. "не прыгать") он не может. Значит попасть в город 1 из города 1 он не может. Просто считать это единицей удобно.
просто "удобно" подогнать под формулу. ведь 0! =1.
Интересный алгоритм. Правильно ли я понимаю, что если бы кузнечик мог прыгать еще и на +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. Вроде бы работает верно?
Но это все как то теоретически. Для решения какой задачи его можно применить?
4:48 Из города А в город А может быть 1 либо 0 траекторий, если мы договорились описывать траектории рёбрами ориентированного графа. На момент задания вопроса у вас не было нарисовано стрелки из А в А, что можно трактовать двояко: либо этой траектории нет, либо её не нарисовали чтобы не загромождать и такая траектория подразумевается существующей для каждого города. В ряде случаев такие умалчивания могут смущать учащихся.
кстати а почему не считается циклом траектория из А в А?
@@mihaitimofti9789 по договорённости, как и всегда
@@DiamondSane а почему он обсчитался? У него получилось 14, а всего вроде путей до J 12, но почему?
Так я все время решал через рекурсию, даже не зная этого))
Скажите пожалуйста, а при составлении расписаний, используется динамическое программирование?
динамическим программированием можно назвать любой итерационный процесс, где сохраняется информация с текущей итерации и используется в последующих. так что да, если расписание составляют итерационно, используя информацию с предыдущих итераций - это динамическое программирование) а если просто ставят первый попавшийся предмет первому попавшемуся учителю - это уже жадный алгоритм)
Тут объяснение куда понятнее чем в лекции)))
Объяснение топ, все круто, но когда включили демку с компа, я был в шоке... Почему такая древняя винда, такой древний софт... Вроде МФТИ, а как будто самая задрипанная школа...
Я может что-то совсем не понял? Но почему при формуле 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 . Пожалуйста, объясните, я в панике :)))
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ть.
@@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
@@entarossa у Вас рассчёт для 6-ти. На 5-ти он прыгает 4 раза, потому что в первой клетке он уже стоит по умолчанию.
фиб: 1, 1, 2, 3, 5,
1:34-1:36 magic
10:08 Могу ошибаться, но статические массивы так создавать нельзя, т.к. размер должен быть константой. То что оно работает - это ub.
Начиная со стандарта C99 (Если использовать gcc-расширения стандарта, то с C90) такой код корректен. Обращу внимание, С, не С++.
@@siborgium9022 Да, все верно. Почему-то не заметил, что на C пишут, а не на плюсах.
в начале вроде Ка-з = Ка-у + Ка-х + 2 (4.20 время)
Да, когда уже школу закончил - это уж точно знаешь.Тут как бы не обсуждается.
Вот если бы я увидел это когда сдавал ЕГЭ 4 года назад)))
Сорри, но я не понял 14 было правильно или нет?
Да.
Я сначала подумала, что вы с Борисом Трушиным связаны, но нет
Изменено: Так я путешествую, просто моя траектория это лежать на кровати
Массив-то зачем? ;)
Куплинов?
В коника лапи не в ту сторону згинаються.
сложно даа
я не понимаю этих ЕГЭ. Если там такие алгоритмы, которые требуют университетских знаний, зачем тогда потом университет?
это не университетский алгоритм, такие задачи разбирают в 9 классе.
О, животик уже виднеется
калькулятор это не в духе динамического программирования. он в ВШЭ сбегал пнул дверь, те - набибулину,она-МВФ, те - ротшильдов с постели подняли .А почему все так быстро? А потому- CASH был, батенька...
Назвал бы функцию как function() ---> как-то ближе к народу русскому было бы. А так какие-то тражекторис какие-то...аж слух режет
В программировании называть переменные и функции русскими названиями считается плохим тоном.
Надо учить английский и привыкать писать на английском.
@@linterrupt @Саша Коваленко да лол.я английский получше препода средненького универа знаю)))считаю для первичного понимния можно было бы фунцию как-то попроще назвать: типа myfunct/functAlloc и.т.д.) ну или в данном случае заменить tRaJEctory на path или ways) ну grasshoper - это вообще смех)))
А так вообще по материалу вопросов нет)) спасибо за лекции)) очень помогаете при изучении С
@@kirillshvedov8417 Вы ошиблись, поблагодарив меня, я простой комментатор.
Лучше сразу формировать привычку писать на английском. На понимании это никак не отражается, поэтому не вижу смысла откладывать на потом.
Какого ето у меня у рекомендациях..
Пойду лучше смотреть лайфхаки
Диванный Интеллектуал так тут и есть лайфхак