Я в таких случаях начальнику всегда напоминаю один анекдот: Василий Иванович и Петька терпят крушение, и тут начинается диалог: -Петька приборы? - Двести - Что двести? - А что приборы? Так что умейте добиваться информации от кого либо.... в том числе и постановки задач по SMART.
Можно начать с заказа сырья у поставщика: дох3я килограммов самого чистого них3я. Можно даже сказать, что поставщик готов подождать с оплатой суммы в дох3я рублей, пока кладовщик примет заказ. Думаю на этом всё и закончится.
@@РупорК А потом сказать что поставщик оказался липовый, или банкротство объявил, в результате чего мы получим то самое нихЗя и как следствие дохЗя проблем. Задание выполнено))
мне кажется что проще подойти к задаче с точки зрения вероятностей, любой путь будет содержать (n -1) шагов направо и (m-1) шагов вверх, тогда надо просто посчитать количество их возможных комбинаций, для n=5 и m=4, тогда решением будет (4 + 3)!/(4!*3!) = 35 вариантов. сложность такого алгоритма O(1). Пояснения: (4 + 3)! это количество возможных уникальных вариантов если каждый шаг уникален, но у нас есть есть однотипные неуникальные серии шагов которые сокращают это количество, 4 одинаковых шага сокращают количество комбинаций в 4! раза, и другие 3 одинаковых шага сокращают в 3! раза.
Все так, только сложность условно константная, все-таки, т.к. факториал не считается за константу, если нет заранее просчитанной таблицы готовых значений. А так получается О(n+m).
это всё хорошо в самом простом идеальном случае, который описан в видео. давайте выберем несколько клеток посреди поля и запретим через них ходить. или добавим условия, что из некоторых клеток можно ходить только вверх, а из некоторых - только вправо. или добавим веса при прохождении через клетки. алгоритм, описанный в видео, продолжит работать, с минимальными доработками.
Стоит еще упомянуть, что в первом случае затраты памяти - O(1), а вот во 2 случае - O(n*m) (в конце алгоритма у нас в памяти будет вся матрица), и это в обоих случаях без учета затрат памяти на рекурсивные вызовы. Притом, можно улучшить затраты памяти до n: 1) Пишем итеративный цикл с проходом по строкам слева направо. 2) Не трудно заметить, что для вычисления очередной клетки, весь массив нам не нужен, а нужна только предыдущая строка, которую мы вычисляем на предыдущем шаге итерации, и клетка слева, которая также уже вычислена.
@@alexeys1789после чего на собеседовании идём лесом, ибо затраты на рекурсию тоже всегда надо учитывать, иначе это ошибка. Стек растет пропорционально глубине рекурсии
Завтра на всех галерах страны за 200$ в месяц будут спрашивать о Динамическом Программировании. Мне особенно нравится, когда сидит "Байкер" часный предпрениматель и спрашивает "Что вы знаете о культуре нашей компании". Автору спасибо за видео.
@Руслан Грищук Могу сказать тоже про наши компании - только лох не нанимает скиловых людей за копейки а ищут нинзь и фей, а потом собирают команду сказочных дол№оебов и такие - раньше мы брали с опытом 7 лет надо повысить планку хотябы в трое. А потом ХРМ пишет тебе нам нужен чел с опытом Вью не менее 20 лет - браво!
Выучи язык, а эти задачи можно только запоминать и выписывать. Подход, сейчас решу сам за часок из головы, тут только сломает тебя. Просто найди готовое решение , пойми его, запомни и иди на новую задачу.
А тк надо посчитать побыстрее, то воспользуемся асимптотикой сочетаний через экспоненту - это и будет примерный ответ, который можно посчитать аж за lon (n + m))
Сначала посчитал рекурсией (правда, немного другой), потом подумал - а почему нельзя аналитически решить? Получил тот же ответ, что и вы: Выборка из (m+n-2) по (m-1). Или, что то же самое, выборка из (m+n-2) по (n-1). Или, ответ = (m+n-2)!/{(m-1)!*(n-1)!}
Видео как бы "обосновывает" применение сильных сторон компьютера, а вы поднимаете вопрос силы человеческого мозга. Ну да, если кончится бензин кругом - те кто быстрее и дольше могут бегать будут в выигрыше, но как правило человек (и даже дедуля и даже ребёнок) используя машину становится сразу быстрее бегуна, причём (и это самое главное!) НЕ заморачиваясь на проблеме, а решая задачу. Это видео ценно как раз тем, что показано как использовать силу (преимущество) компьютера, который может и не оптимально (как человек оптимально - аналитически) решит задачу, но целый _класс_ задач зато где надо "быстро смоделировать" (рекурсией - тут силён комп конечно) не заморачиваясь.
очень доходчивое и наглядное объяснение, спасибо! с меня подписка! (пришел с гугл рекламы). Так же стоило упомянуть комбинаторное решение. Нужно будет посчитать количество перестановок вверх (их m-1, если m - высота поля), и вправо (аналогично n-1).
@@sashalukin, не перегружать видео и поэтому там 8 мин абстракных размышлени, не самый очевидный алгорим, и избыточная реализация решения.. На работу звяли?
Нашёл его же, загнал в код. Получил не ожидаемую мной особенность: при больших значениях m и n факториалы легко вылетают даже за границы лонг инта, т.е. требуется правильно выделять память. А вот метод с вспомогательной таблицей менее требователен в этом конкретном аспекте. P.S. А проще и элегантнее всего задача кодится заполнением аналогичного массива из исходного угла в конченый. Можно заполнять "полосками". В первой колонке все единички, в первой полоске тоже единички, а в каждой клетке потом - сумма соседей снизу и слева. Так полоска за полоской и заполняем. И кодить просто (рекурсии-то нет), и цифирки не большие. И особенно пикантно то, что если вычисления большие и их надо "на паузу" ставить, то запоминать надо самый минимум: текущее состояние массива и координаты последней заполненной клетки.
После твоего душевного рассказа на нашем собеседовании, я бы перевернул твой рисунок на 180 градусов, увидел твои округлившиеся глаза и сказал - спасибо, что пришел, пригласи пожалуйста следующего!
Динамическое программирование - это не только запоминание промежуточных результатов, но также и само рекурсивное решение. Также как при вычислении числа Фибоначчи, данную задачу можно решить как простым циклом, так и рекурсивно. И именно рекурсивное решение с запоминанием промежуточных результатов является динамическим программированием для обоих задач.
Есть видео, (Тимофей Хирьянов "Динамическое программирование сверху и снизу"). Смотрел его через пару дней после этого видео. Обычно можно переделать рекурсию на цикл и это улучшает производительность.
Спасибо большое! Стопнул на 1:02 и решил самостоятельно, после чего сверился. Советую всем так делать, хотя бы устно, в уме. Можно, кстати, оптимизировать использование ОЗУ чуть меньше, чем в 2 раза. Это задача на внимательность, на нахождение треугольника паскаля в ней. А прелестное свойство треугольника паскаля - его симметричность, нам достаточно хранить его половину вместе с главной диагональю (для реализации подсказка: arr[n][m] считается как обычно, arr[n-1][m]+arr[n][m-1], а главная диагональ - arr[n][n] = arr[n][n-1] * 2).
Я не смог досмотреть это видео, просто потому, что у меня начались "вьетнамские флэшбэки" с сотен собеседований, где задавали крайне полезные и актуальные вопросы, которые я точно должен уметь решать. "Где Вы видите себя через 5 лет?" да в вашем офисе буду бумажки перебирать, где ж ещё?!
Я ща на старости флешбеки как фильмы смотрю, сьэкономил на кинотеатрах и купил клей момент и ласты, перед сном надеваю на всякий случай и наслаждаюсь 5Д без искуственного интелекта, последних технологий, промисов и блокчейнов. Замомните - То что нас не убивает, н№XeRa не делает нас сильнее, просто убивает потом.
Как уже упомянуло несколько людей в комментариях задача действительно может решаться просто по формуле, но если использовать рекурсию как в видео, то более простым вариантом пожалуй будет это: int paths(int n, int m) { if(n == 1 || m ==1) return 1; return paths(n-1,m) + paths(n, m-1); } Если точка находится на одной линии с роботом, то очевидно только один путь к ней, поэтому возвращает единицу, таким образом выход за рамки поля невозможен, и считать его не надо, такая рекурсия как по мне выглядит намного проще, да и для прямого пути в 5 клеток не надо будет вызывать 5 функций пока они не дойдут до робота, а сразу возвращает единицу.
Саша, здравствуйте! А вы будете продолжать вести канал? Сейчас очень актуальны ваши ролики с задачами и теорией (если она планируется), все очень доходчиво и понятно, спасибо!
Хороший ролик, хорошее объяснение. Мы задачи подобного рода аналитически решали на уроках информатики в 6-7 классах (не спец школа), на Basic. Сижу и думаю, то ли учитель хороший был, то ли что-то в мире поменялось. :)
Если я не ошибаюсь, то можно без рекурсии намного проще. Нужно в каждой клетке (i,j) просчитать к-во вариантов. Начинаем с нижнего ряда слева направо - все единицы (т.к. снизу клеток нет, а слева все время 1). Начитая со второго ряда снизу значение К(i,j) = значение клетки слева К(i-1, j) (для клетки К(1,j) будет 1) + K(i,j-1). И так, пока не дойдем до точки К(n,m)
Путь однозначно задается как n - 1 стрелка вправо и m - 1 стрелка вверх, выпишем стрелки в ряд в произвольном порядке (всего в ряду n + m - 2 стрелок). Тогда число способов расставить здесь n - 1 стрелку вправо равно количеству сочетаний из n + m - 2 по n - 1 (или по m - 1, что тоже самое). Ответ: (n+m-2)! / (m - 1)! / (n-1)!
Контент супер! _Динамическое программирование_ - способ решения сложных задач путём разбиения их на более простые подзадачи. Вся наша жизнь немножно динамическое программирование :-) Видео как бы намекает зачем компьютеру надо столько много памяти (на стек вызовов рекурсии, на массив для мемоизации) :-) Тут много людей пишет в комментариях, что можно решить оптимальнее и аналитически вообще (сведя к формуле), но если хорошенько подумать, то показана то не конкретная задача, а _класс_ задач. Ну и опять же, компьютер изобрели чтобы НЕ заморачиваться. Да, можно интеграл красиво аналитически посчитать, а можно методом трапеций численно. Аналитически это конечно же красиво и "интеллектуально элитно", но в суровой реальной жизни когда заказчику надо "вчера!" и результат нужен "прям щас и один раз!" и "уже всё!" и у директора дёргается от этого глаз от нервов всех этих - математика-аналитика-теоретика раньше уволят нафиг (и заводу может кирдык придёт), ну или премию дадут "Петровичу" который методом трапеций за 5 минут прикинул и сказал "ах**но! материала хватит! вот смета!" :-))))
@@akiiaev математик-теоретик - товар штучный, а решения надо принимать много где, и тут на помощь придёт "числодробилка" которая сделает даже дурачка "великим математиком" ;-) в мире много рукожопов - поэтому изобрели санчала трафареты, а потом и ЧПУ станки, в мире много тугодумов - поэтому изобрели компы и численные методы и методы мат.моделирования. и это дало возможность даже дурачкам кормиться и размножаться, алилуйя! :-D но конечно же "для любителей помучаться" (мазохистов) остались ручные дрели, лобзики, логарифмические линейки, кульманы для чертежей вручную и прочие "орудия пыток" :-D но мне как-то нравится в 3D принтер или ЧПУ загружать чертёж, который я могу поправить в САПР если что не переделывая полностью. видимо я не дошёл до "дзена", мне результат как-то важнее процесса.
Примерно в этом и заключается талант грамотного технического менеджера: отличать задачи, которые нужно решать быстро и в лоб, от тех, которые нужно решать долго и красиво. И в промышленной разработке, конечно, первых гораздо больше, но всё же не 100 %.
Можно увидеть в этом треугольник Паскаля. Номер ряда L = n + m - 2. Искомый член ряда P = Min(m, n) - 1 Результат L! / (P! * (L - P)!), то есть число сочетаний из элементов по Ну и всё, не нужно так заморачиваться. Дабы не мучить компьютер лишний раз, число сочетаний высчитываем как "Произведение P последних из L делить на P!" И тогда сложность из O(m+n) становится O(min(n, m)). Как бы сделать ещё красивее?
@@АндрейБочарников-х5ъ Для компа перемножить тысячи чисел - десятая доля секунды. Надо, конечно, позаботиться об избежании переполнения, но всё равно это будет гораздо быстрее в сравнении с оббеганием 4 000 000 ячеек. К тому же у нас не растёт потребление по памяти, чего не скажешь про код автора.
@@YevhenDiulin так а астмптотику подсчёта факториала вы знаете? Плюс следить за переполнением легко, но что делать если оно будет?(а оно будет) Длинная арифметика или варианты получше?) Все это красиво только на листочке, а на практике чёт не очень
@@freedomtv2295 Можно взять тип с плавающей точкой и не считать факториалы отдельно, а сразу считать число сочетаний: умножил на один член чеслителя, разделил на один член знаменателя, потом на другой член чеслителя и на другой член знаменателя. Есть пути в обход.
@@YevhenDiulin идея с поочередным умножением это хорошо, но типы с плавающей точкой сразу нет. Это гора проблем, там от ответа не останется даже и следа
Если в задании нельзя использавать комбинаторику (хотя этот способ самый лучший) можносделать программу ещё проше, На языке паскаль: for i:=1 to n do a[i,1]:=i; for i:=1 to m do a[1,i]:=i; for i:=2 to n do for j:=2 to m do a[i,j]:=a[i,j-1]+a[i-1,j]; write(a[n,m]); Да уж, уже подзабыл программирование со школьных лет не занимался
Рекурсия почти всегда красивое решение. Хотя и трудно для понимания иногда. Да и цена алгоритма очень высока. Если у нас задача просто посчитать пути, тогда предлагаю такой вариант: Если ручкой провести все пути, то можно заметить следующее- есть 2 экстремальных пути, когда робот пойдет по периметру, а также пути внутри периметра. Если посмотреть на все пути, то в поле справа от каждого остается на один квадрат больше, и фигура, образуемая этими квадратами будет расти равномерно, как выпуклая геометрическая фигура. Говоря проще, количество путей будет равно сумме (m*n) - (m+n-1) +1, где (m*n) -это количество всех квадратов, (m+n-1) - это сумма квадратов в случае, если робот пошел экстремально вверх до конца и направо до конца, а +1 - это путь, который он прошел экстремально вправо до конца, а потом вверх до конца Но данное условие не подойдет в случае, если имзенится поведение робота. Надеюсь хоть чтото понятно, если будет интересно - приложу рисунок
@@АнтонФролов-о1с блин) я уже не помню че там было)) Ну в целом я к тому, что не всегда нужно решать задачу, чтобы она решала любые вариации впоследующем. Если есть возможность сделать тупо и просто, потратив меньше часов и энергии, то, возможно, это лучшее решение. А если вдруг потом понадобится расширение - тогда уже подумать над алгоритмом. Опять же, зависит от котекста
Эту задачу можно решить ещё быстрее увидев, что это треугольник паскаля, правда надо ещё знать формулу его. Тогда апроксимация времени работы алгоритма будет = О(n+m).
Эту задачу можно решить и за константное время,, используя формулу количества сочетаний. Только для конкретно этого варианта задачи нужно уменьшить и ширину, и высоту сетки на 1.
@@кикислав Вы написали, и я задумался. Раз уж так, можем считать факториал с конца, то есть a*(a-1)*(a-2)*...*(a-i), где а=n+m в нашем случае, а i=min(n,m); попутно же будем считать количество перестановок (i факториал); поделим одно на другое и получим искомое количество сочетаний. Выходит что сложность алгоритма и того меньше - О(min(n,m)).
@@АкрилГуашев На самом деле апроксимация вычисляется более сложным путём, так-как апроксимация умножение двух чисел длиной n и m равна O(max(m, n)) Вы можете сами проверить, написав программу, потому что компьютер умножает числа примерно как мы, в столбик.
изначально не понимал с какой стороны подойти к решению) В итоге пришел к решению с комбинаторикой. Но решение автора мне очень понравилось. Правда что рекурсия уже не подойдет на очень больших m и n
Это на самом деле задача из комбинаторики для 7-8 класса. Здесь можно даже увидеть треугольник Паскаля, который разворачивается направо-вверх: ... 1 ... 1 4 ... 1 3 6 ... 1 2 3 4 ... 1 1 1 1 1 ... Число в каждой клетке равно количеству маршрутов, ведущих в неё из начальной клетки. Ну и одновременно с этим, числа, из которых состоит треугольник Паскаля представляют собой кол-во сочетаний, поэтому ответ C из n по m.
Фишка в том что посчитать биномиальный коэффициент всё равно не просто, а если на машине умножение долгая операция то и без дополнительной памяти не обойтись
с чего-то вдруг было принято, что если квадрат 1 на 1, то у робота 1 путь, хотя на самом деле пути нет, а не он пустой, т.к. робот никуда не движется. Дальше можно не смотреть, как уже написали в комментах, задача решается гораздо проще исходя из логики и без рекурсии
вот легче решение для понимания. Если идем вправо на одну клетку тогда это приравниваем к 1 а если вверх то 0. Тогда получается бинарное число из 1 и 0. Нам надо что бы в этом бинарном числе было 4 единицы в любом порядке. Всего 7 цифр в нем. В первой задече получается бинарное число из 3х цифр в котором должен длжно быть одна единица в любом порядке. Таким образом можно решить эту задачу с любым колличеством клеток. Следовательно нам просто надо найти сколько бинарных числел с 7 знаками содержит 4 единицы. Код элементарный так же: def decimalToBinary(n): return bin(n).replace("0b", "") N=0 for i in range(int('1111111', 2)): if str(decimalToBinary(i)).count("1")==4: N+=1 print(N) 35 для последней задачи получаем и 3 для первой итд
n, m = int(input()), int(input()) b = [] for i in range(n): b.append([0] * m) for i in range(m): b[0][i] = 1 for i in range(n): b[i][0] = 1 for i in range(1, n): for j in range(1, m): b[i][j] = b[i - 1][j] + b[i][j - 1] for i in b: print(i) Аналогичный алгоритм на питоне
Это просто разложение первого хода. Ты можешь пойти вверх и тогда высота оставшегося поля уменьшится на 1. Или ты можешь пойти вправо и тогда ширина поля уменьшиться на 1. Соответственно общее кол-во путей - это просто сумма путей для обоих вариантов.
Все проще. Это треугольник паскаля. Время работы О(2*(m + n)) В случае если n>=2 и m >=2 ответ записывается формулой (n + m - 2)!/((m - 1)! * (n - 1)!) //просто найти факториалы отдельно и посчитать Иначе ответ 1
У нас эта и подобные ей задачи были в 8 классе на уроках информатики. В Паскале писали всякие алгоритмы для роботов. Всегда ненавидел это дело. По сути, весь 8й и 9й класс были посвящены тому, чтобы робот бегал по карте с препятствиями и искал выход наиболее оптимальным образом. Вечно ошибался и либо написанная прога не работала, либо робот шёл не туда, куда надо, либо шел куда надо, но не оптимальным способом, либо учителю не нравился сам код... В общем, с программированием не сложилось :)
у нас была "черепашка" и "робот-пылесос". робот нужно было программировать на русском. это был 6й класс и я обожал это дело, тогда и влюбился в программирование окончательно :)
Решила в голове за пять секунд. Решение: ```cpp unsigned long long coolfunc(int a, int b) { int n = a+b-2; int k = (n+1)/2; return binomial(n,k); } ``` Для решения нужно будет округление и факториалы и биномиальные коэффициенты, их можете взять из библиотеки или сами написать: ```cpp #include #include void reduceFraction(int &numerator, int &denominator) { int greatestCommonDivisor = std::gcd(numerator, denominator); numerator /= greatestCommonDivisor; denominator /= greatestCommonDivisor; } int factorial(int num, int k=1) { if (num
@Mike я не считал максимальный грид для моего решения, но для решения на литкоде мне хватило трёх переменных long long и небольшой оптимизации. В итоге самый быстрый результат на сайте.
@@avshukan ты не совсем прав, фактически нам нужна петля для подсчёта факториала, но при минимальном упрощении мы считаем только то колличество итераций, которое будет меньше (k!-1 Или (n-k)! -1)
Вот кстати из-за таких педагогов и таких фанатиков в комментах дети в школах и боятся математики) Я не пытаюсь никого обидеть, но здесь сухое построение функций очень сбивает. Та же фигня была и на курсах программирования. А проблема решалась очень просто - давайте нормальные и понятные названия переменным! И тогда человек которому вы что-то объясняете лучше усваивает инфу. Сами учите как использовать поменьше памяти, а забываете что мозг человека работает примерно также с новой информацией. И вот когда парень на видео увлеченно ушел вперед и рассказывает о формулах вычисления, человек судорожно пытается построить какую-то цельную картинку в мозгу и вспомнить а что там за m, а буква n это что там было? Понимаю что это звучит наивно и для профессионалов это очевидные вещи, но всё же это образовательный ролик на ютубце. И направлен он на людей которые хотят научится, а не на тех кто уже всё это знает.
самое главное в подобных задачах - уметь применять знания полученные при решении. а то приходят литкодовцы и кроме алго и систем дизайн интервью ничего пройти не могут. да и на практике говнокод лютейший генерируют. идея которая была заложена в алго интервью уже изжила себя и это абузят все кому не лень.
Добрый день. Можно ли решить задачу следующим способом? Робот может двигаться только вправо и вверх, т.е. каждая клетка из которой можно двинуться вправо или вверх является развилкой и дает +1 путь - это не крайние правые и не крайние верхние клетки. При поле размером 1 клетка в ширину или 1 клетка в высоту у робота только один путь. Т.о. получаем алгоритм: h=5; n=4; ways_count=1; hi=1; ni=1; for(hi=1;hi++;hi
Развилка даёт не +1 путь, а +к путей , где к - количество путей до этой клетки. Проверьте сами себя: посчитайте для квадрата 4*5 "руками" (должно получиться 35) и своим алгоритмом
Можно свести задачу к графу, построить матрицу смежности и возвести в степень k, где k - расстояние между вершинами. Это будет где-то (m*n)^2.5 сложность, зато потенциально найдет решение в общем лучае. + Будет задел на применение прочих графовских алгоритмов
@@alexanderpalagin4662на больших m и n устанешь, эти факториалы не влезут в размер переменной, нужно будет с бубнами плясать, лучше загрузить процессор и точно знать, что оно выполнится, а не упадёт, потому что комп не сможет оперировать в формуле факториалом от миллиарда)
матрица NxM число ходов вправо n=N-1, число ходов вверх m=M-1 нужно найти кол-во сочетаний n ходов вправо и m ходов вверх всего ходов s=n+m paths = s! / (n! * m!) = (s*s-1*s-2*...*s-n)/(1*2*3*...*n) = ИЛИ = (s*s-1*s-2*...*s-m)/(1*2*3*...*m) то есть выбираем меньшее из k=min(n, m) и вычисляем paths = s-i/(1+i), i=0..k-1
рекурсия это - зло (в большинстве случаев) всегда нужно быть ОЧЕНЬ осторожным с рекурсией (а лучше избегать ее), т.к. очень часто неизвестна глубина рекурсии и размер стека, а отсюда и до переполнения стека недалеко (если конечно современным прогерам известно что это такое :) )
@@MultiOpachki противники рекурсии любят писать переносимый код, который не зависит от платформы, компилятора, настроек, ... :() кстати даже не хочу знать что такое ленивые вычисления, хотя догадываюсь зато хорошо знаю как сложно найти переполнение стека, которое происходит раз в 5 лет у одного юзера из 1000
Пробовал данное решение использовать на leetcode, получил перерасход времени. Вот более быстрое решение на JS: var uniquePaths = function(m, n) { let row = new Array(m).fill(1); for (let i = n -2 ; i>=0; i--) { const newRow = new Array(m).fill(1); for (let i =m-2; i>=0;i--){ newRow[i] = newRow[i+1]+row[i] } row = newRow; } return row[0] };
Хорошее решение, только для чего используешь два массива? да и проверку всё же лучше делать, чтобы код ошибок не выдавал ;) function uniquePaths(m, n) { if (m < 1 || n < 1 || (m === 1 && n === 1)) return 0; //считаю, что поле [1;1] также не имеет решения if (m === 1 || n === 1) return 1; let arr = new Array(m).fill(1); for (let i = n - 2 ; i >= 0; i--){ for (let j = m - 2; j >= 0; j--){ //для лучше читаемости кода лучше всё же переменные называть по разному arr[j] = arr[j+1]+arr[j] } } return arr[0] };
Динамическое программирование здесь понадобилось бы, если бы были случайно разбросаны острова, которые бы случайно вырезали часть маршрутов. А в задаче именно в таком виде тут будет чисто комбинаторное решение в виде функции от m,n, равной числу сочетаний из (n + m - 2) по (n - 1) или (m - 1), без разницы
@@zugzug90 Оно не выводится, оно по смыслу есть) У тебя путь длиной n + m - 2 в котором ты делаешь (m -1) шагов вниз и (n - 1) шагов в сторону. Ну то есть условно можно представить путь как последовательность из 0 и 1 длиной (n + m - 2) в которой будет(n - 1) нулей и (m - 1) единиц, располагающихся в случайном порядке. Тогда совсем очевидно что количество таких перестановок будет числом сочетаний кол-ва нулей или единиц из всей длины
@@matanmaster "ты делаешь (m -1) шагов вниз" - но ведь вниз ходить нельзя.. Все таки непонятно, как получается (n-m-2).. Мб (n + m - 2) ? Там и выше у вас такое число кстати. Комбинаторику уже совсем не помню, пока что утверждение для меня неочевидно, но вероятно если освежить в голове пару глав - станет понятно лично мне. В любом случае спасибо за разъяснения.
Программирование попросту немного не про то, там недостаточно один раз вычислить по формуле и забыть. Что если, отныне нужно считать наикратчайший из этих путей? Или у ячеек вдруг появились веса (ходить по одним "дороже", чем по другим)? Гораздо проще ввести небольшие изменения в текущий алгоритм, чем выводить новые формулы. А если этот алгоритм работает в рамках какого нибудь приложения и с этим кодом взаимодействуют другие разработчики? Тогда для его понимания проще и быстрее пару раз прогнать этот кусок кода с разными значениями, нежели разбираться что такое биномиальный коэффициент. Так что, этот вариант имеет место быть, но в мире программистов - это очень плохая практика
У вас явно не было серьёзного опыта в продакшне. Написать программу это лишь небольшая часть работы, гораздо бОльшая - её поддержка. Грош цена коду, если нельзя с ходу понять что и как он делает, а в последствии адаптировать его под меняющиеся условия. Поэтому важнее оптимизировать процессы в команде и сэкономить человекочасы, нежели подобные мелочи, а современные вычислительные мощности всё равно нивилируют разницу до минимума. Конечно, если мы запускаем аппарат в космос, математика сразу выглядит в разы выигрышнее. Условия всё равно концептуально не меняются, а сложность вычисления минимальная. Однако, с IT это уже имеет мало общего
Уважаемый автор, на 5.52 сек клетка 31, говорит что там количество ходов 1 шт. А как же последовательность 11 - 12 - 22 - 21 - 31 ? Может условие чуть иное в задаче? получается что мах количество ходов для n=3 m=2 равно не 3 а 4. Спасибо
Мне одному кажется странным код, который он приводит? Во первых нигде нет суммирования значений рекурсивных ступеней(Везде только ретёрны), во вторых функция должна возвращать инт, а возвращает массив. 8:12
1) а. С массивом будет вызываться функция повторно для тех клеток, которые равны нулю; б. Массив должен быть заранее известного размера либо динамически перераспределяться - будет развесистый спагетти-код. Поэтому надо функцию вызывать из экземпляра класса, добавить поле с мапой и в начале функции ифчик с проверкой на присутствие в мапе, а в конце добавить вхождение в мапу. 2) a. рекурсия сама по себе ограничивает глубину вызова и стоит это как-то учесть, например, выбрасывать исключение при слишком больших (m, n); б. Ддя больших значений m и n, которые не позволят массиву/мапе поместиться в кэш процессора, будет производится вычитка из памяти. Операция эта долгая, и прежде чем добавлять такую реализацию, стоит проверить на бенчмарках выигрыш от нее - вполне возможно, что повторное вычисление будет быстрее
По сути массив вы используете как мапу, где индекс == ключу элемента. Согласен, для оптимизации это хорошо иногда работает, массив очень полезная штука, но тут и мапа будет хорошо работать, а читаемость существенно вырастет, поэтому она и должна быть в коде как минимум до того момента, пока на бенчмарках не будет доказана эффективность замены
@@user-uvk в цифрах О большого и то, и то О(1). Понятно, что будут накладные расходы на высчитывание хэша и сравнение объектов, а также на плохо распределяемые объекты, но и в таком случае, например, в джаве, все под капотом достаточно хорошо оптимизируется до O(log N) для сравнимых элементов. И при этом по памяти мы независим от непрерывного участка памяти. В общем, непонятно, откуда взялось "на порядок медленнее", можете пояснить? И в каких компаниях попросили бы писать такой код без мапы (чтобы туда не попасть случайно), если, конечно, там не какую-нибудь встроенную систему реального времени управления атомным реактором внутри него же самого на жестко ограниченном железе пишут
@@hro688 Мапа работает гораздо дольше по следующим причинам: 1) при вставке очередного элемента под него надо выделить память. Это значит, пройтись по спискам свободной памяти, найти там подходящий участок, разделить его на выделяемую и оставляемую в свободной памяти части, организовать необходимые служебные структуры и т.п. 2) из-за наличия служебных полей (от списков памяти) размер выделяемой под элемент памяти больше размера элемента данных. Если элемент данных маленький (как в данной задаче 4 байта), то эти накладные расходы (минимум 2 указателя по 8 байт) в разы больше полезной памяти - это повышает нагрузку на кеш процессора (точнее, снижает вероятность найти данные в нём). 3) при выборке надо посчитать хеш-код, использовать его как индекс в обычном линейном массиве или для поиска по дереву (зависит от реализации мапы) - это требует много машинных команд да ещё с условными переходами (которые имеют свои накладные расходы для процессора), а получение int из простого массива - одна машинная команда. 4) работа с мапой, обычно, это вызовы встроенных функций из библиотеки, а с массивом - прямой код в программе. Это означает лишние обращения к памяти для передачи аргументов подпрограмме через стек, которых нет в работе с массивом. Мапа имеет огромное преимущество, когда только малая часть возможных ключей (которые могли бы быть индексами в массиве) будет использована. Тут она экономит память, что при больших размерах массива может быть важно. И в случае, когда ключ поиска не может быть напрямую использован как индекс массива, массив отдыхает.
Иначе некому в гугле будет работать. Вы же не думаете, что таланты из Стэнфорда пойдут в Гугл работать? Такие идут работать в более важные стратегические структуры.
Спасибо. Решение очень красивое и простое, но если вы ищите путь, то где препятствия? Если есть препятствия, то путь будет с шагами назад и вниз, а это может привести к циклам, которые можно исключить если на карте ставить метки, где идёт текущий прогон. Вы передаёте в рекурсивной функции параметр - таблицу, то есть таблица должна остаться в стеке при каждом вызове, но это при росте размера карты приведёт к ошибке Stack Overflow? Избежать ошибки можно если сделать "прямое" решение с поиском путей от первой точки, заменив рекурсию на цикл, а таблицу из параметров сделать переменной.
Решение автора ролика не самое простое и далеко не самое красивое! ;) И ещё вы не внимательно слушали условие задачи - робот может ходить вверх или вправо, но он НЕ МОЖЕТ ходить вниз или влево!
@@ukrainekiev3990, вы серьёзно? Просто привычки программиста, ТЗ меняется на ХЗ в любой момент. В общем, можете рассказать пользователям чего робот "НЕ МОЖЕТ".
@@Aimilomim, при чём здесь "можете рассказать пользователям"? Речь идёт о том, что вы НЕВНИМАТЕЛЬНЫЙ и невнимательно слушали условие задачи! Невнимательность это не привычка программиста, это привычка раздолбая, от сюда ваши кривые коды со всеми вытекающими ))
@@ukrainekiev3990, в хорошей программе должна быть возможность модификации. А у пользователей всегда есть новые требования. Вы считаете, что рекурсия лучше циклов? Параметры рекурсии не имеют значения?
Добрый день! Возможно, я чего-то не понимаю, но я вижу здесь классическую рекурсию. Да, есть двумерный массив состояний, но заполняется он в рекурсивной функции. Вся прелесть ДП, на мой взгляд, как раз в том, что рекуррентное соотношение обрабатывается в цикле без применения рекурсии.Я могу предложить свой вариант. Если я неправ, то прошу дать разъяснения.
У меня только один вопрос: зачем решать перебором то, что считается аналитически? Роботу нужно сделать n движений вверх и m движений вправо. Вполне очевидно, что количество путей равно числу сочетаний из n+m по n.
эту задачу можно решить гораздо проще и красивее, без циклов, условий и прочего. можно составить формулу числа возможных путей от N и M ) вот как это можно сделать: с каждым ходом робот продвигается либо вверх либо вправо, следовательно все маршруты имеют одинаковую длину и отличаются только последовательностью ходов вверх и вправо, количество ходов вверх = N-1 количество ходов вправо = M-1. наша задача - найти, сколько есть вариантов расставить N "вещей" в (N+M-2) позициях ("вещи" не уникальны). для этого есть формула в комбинаторике. помогите мне её вспомнить))))
по моему задача решается легче математически. всего шагов n+m-2 и надо выбрать лишь номер шагов вверх или вправо, тоесть ответ С из n-1 по n+m-2 или C из m-1 по n+m-2 тут как удобнее, т.к. числа эти будут равны
Случайно, не воспользовалась ли майкрософт данной задачей для отбора программистов для написания windows 10 с критерием - кто решил данную задачу данным способом, берём, а кто другим способом - забраковали. Из чего такая аналогия? Когда комьютеры всё мощнее и мощнее, а работают всё медленнее и менее отзывчиво. По сути: функция О(...) не покрывает всех критериев затрат времени. Ещё есть затраты на вызов стека, дополнительное пространство памяти на хранениние результатов, пустые сравнения и копирование просчитанного значения в память и из памяти. Я вижу лучший путь, чем доп массив. Представленный автором 2й метод несколько быстрее первого, но не отличается принципиально. Спасибо за видео
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
Это простая задача, вот у нас на заводе, начальник цеха ставит задачу
- Сделать дох3я из них3я и еще премии лишает если не выйдет. О как!
Cрочно пришлите нам его телефон! (Директор Гугля)
Когда начальник требует "дох3я из них3я" очень важно убедить что "нах3й нужно" и таки получить премию! Вам просто не хватает навыков убеждения! :-D
Я в таких случаях начальнику всегда напоминаю один анекдот:
Василий Иванович и Петька терпят крушение, и тут начинается диалог:
-Петька приборы?
- Двести
- Что двести?
- А что приборы?
Так что умейте добиваться информации от кого либо.... в том числе и постановки задач по SMART.
Можно начать с заказа сырья у поставщика: дох3я килограммов самого чистого них3я. Можно даже сказать, что поставщик готов подождать с оплатой суммы в дох3я рублей, пока кладовщик примет заказ. Думаю на этом всё и закончится.
@@РупорК А потом сказать что поставщик оказался липовый, или банкротство объявил, в результате чего мы получим то самое нихЗя и как следствие дохЗя проблем. Задание выполнено))
мне кажется что проще подойти к задаче с точки зрения вероятностей, любой путь будет содержать (n -1) шагов направо и (m-1) шагов вверх, тогда надо просто посчитать количество их возможных комбинаций, для n=5 и m=4, тогда решением будет (4 + 3)!/(4!*3!) = 35 вариантов. сложность такого алгоритма O(1).
Пояснения: (4 + 3)! это количество возможных уникальных вариантов если каждый шаг уникален, но у нас есть есть однотипные неуникальные серии шагов которые сокращают это количество, 4 одинаковых шага сокращают количество комбинаций в 4! раза, и другие 3 одинаковых шага сокращают в 3! раза.
Вы написали мои мысли :)
быть может с точки зрения комбинаторики?
@@Maksim_C ну да скорее комбинаторика, есл угодно
Все так, только сложность условно константная, все-таки, т.к. факториал не считается за константу, если нет заранее просчитанной таблицы готовых значений. А так получается О(n+m).
это всё хорошо в самом простом идеальном случае, который описан в видео. давайте выберем несколько клеток посреди поля и запретим через них ходить. или добавим условия, что из некоторых клеток можно ходить только вверх, а из некоторых - только вправо. или добавим веса при прохождении через клетки. алгоритм, описанный в видео, продолжит работать, с минимальными доработками.
Стоит еще упомянуть, что в первом случае затраты памяти - O(1), а вот во 2 случае - O(n*m) (в конце алгоритма у нас в памяти будет вся матрица), и это в обоих случаях без учета затрат памяти на рекурсивные вызовы. Притом, можно улучшить затраты памяти до n:
1) Пишем итеративный цикл с проходом по строкам слева направо.
2) Не трудно заметить, что для вычисления очередной клетки, весь массив нам не нужен, а нужна только предыдущая строка, которую мы вычисляем на предыдущем шаге итерации, и клетка слева, которая также уже вычислена.
В первом случае сложность для памяти не O(1), каждый вызов ф-ии это новый элемент в памяти
@@GatherOwsen внимательно читаем сообщение еще раз и что мы видим??? "это в обоих случаях без учета затрат памяти на рекурсивные вызовы"
@@alexeys1789после чего на собеседовании идём лесом, ибо затраты на рекурсию тоже всегда надо учитывать, иначе это ошибка. Стек растет пропорционально глубине рекурсии
@@volervagashim ахахахах, если это рофл, то харош))0
@@alexeys1789 поясни, плз, видимо я не понимаю чего-то
Завтра на всех галерах страны за 200$ в месяц будут спрашивать о Динамическом Программировании. Мне особенно нравится, когда сидит "Байкер" часный предпрениматель и спрашивает "Что вы знаете о культуре нашей компании". Автору спасибо за видео.
@DaXz на самом деле видел тех кто пол года бесплатно работал, ради того чтоб начать и получить хоть какоето резюме.
@DaXz стажеры каторые работают 8 часов в сутки. Нет это джуны. Там были реальные работы и реальные требования.
@Руслан Грищук пол украины так работает, от дизайнеров до фулстакеров. Я рад что вы в розовой зоне и у вас все хорошо.
@Руслан Грищук Могу сказать тоже про наши компании - только лох не нанимает скиловых людей за копейки а ищут нинзь и фей, а потом собирают команду сказочных дол№оебов и такие - раньше мы брали с опытом 7 лет надо повысить планку хотябы в трое. А потом ХРМ пишет тебе нам нужен чел с опытом Вью не менее 20 лет - браво!
@@AWoh51EIbvd половина компаній України, які працюють на ринок України. Але у нас 90% айті - це аутсорс, або стабільні продуктові компанії.
Тот случай, когда только начал учиться программированию и понимаешь, что скоро обучение закончится
Ну че там, как дела?
@@ИмяФамилия-э4ф7в, видимо закончил
Выучи язык, а эти задачи можно только запоминать и выписывать. Подход, сейчас решу сам за часок из головы, тут только сломает тебя. Просто найди готовое решение , пойми его, запомни
и иди на новую задачу.
@@axiswait5339можешь подробнее расписать свою точку зрения?
🤣 Мужик, я не знаю учишь до сих пор программирование или нет, но с юмором у тебя однозначно все в полном порядке 😅
Отличный ролик!
6:55 мемоизация , спасибо )
Можно комбинаторикой: пусть a - количество ходов вверх ИЛИ вправо (неважно), b - общее количество ходов. Тогда ответ на задачу равен C из b по a
Воот! Думал ровно про то же самое. Тут хватит одной формулы без циклов.
Звучит логично, но не совсем понятно)
А тк надо посчитать побыстрее, то воспользуемся асимптотикой сочетаний через экспоненту - это и будет примерный ответ, который можно посчитать аж за lon (n + m))
Сначала посчитал рекурсией (правда, немного другой), потом подумал - а почему нельзя аналитически решить?
Получил тот же ответ, что и вы: Выборка из (m+n-2) по (m-1). Или, что то же самое, выборка из (m+n-2) по (n-1).
Или, ответ = (m+n-2)!/{(m-1)!*(n-1)!}
Видео как бы "обосновывает" применение сильных сторон компьютера, а вы поднимаете вопрос силы человеческого мозга.
Ну да, если кончится бензин кругом - те кто быстрее и дольше могут бегать будут в выигрыше, но как правило человек (и даже дедуля и даже ребёнок) используя машину становится сразу быстрее бегуна, причём (и это самое главное!) НЕ заморачиваясь на проблеме, а решая задачу.
Это видео ценно как раз тем, что показано как использовать силу (преимущество) компьютера, который может и не оптимально (как человек оптимально - аналитически) решит задачу, но целый _класс_ задач зато где надо "быстро смоделировать" (рекурсией - тут силён комп конечно) не заморачиваясь.
очень доходчивое и наглядное объяснение, спасибо! с меня подписка! (пришел с гугл рекламы). Так же стоило упомянуть комбинаторное решение. Нужно будет посчитать количество перестановок вверх (их m-1, если m - высота поля), и вправо (аналогично n-1).
Спасибо! Действительно, так можно и это очень красивое решение. Но решил не перегружать это видео.
@@sashalukin очень зря, это наиболее простое и красивые решение)
@@sashalukin, не перегружать видео и поэтому там 8 мин абстракных размышлени, не самый очевидный алгорим, и избыточная реализация решения.. На работу звяли?
@@sashalukin а ответ в большой таблице равен 35?
Нашёл его же, загнал в код.
Получил не ожидаемую мной особенность: при больших значениях m и n факториалы легко вылетают даже за границы лонг инта, т.е. требуется правильно выделять память. А вот метод с вспомогательной таблицей менее требователен в этом конкретном аспекте.
P.S. А проще и элегантнее всего задача кодится заполнением аналогичного массива из исходного угла в конченый. Можно заполнять "полосками". В первой колонке все единички, в первой полоске тоже единички, а в каждой клетке потом - сумма соседей снизу и слева. Так полоска за полоской и заполняем. И кодить просто (рекурсии-то нет), и цифирки не большие. И особенно пикантно то, что если вычисления большие и их надо "на паузу" ставить, то запоминать надо самый минимум: текущее состояние массива и координаты последней заполненной клетки.
Спасибо, полезно. Мне очень помогает знать простую идею, стоящую за алгоритмом. Потом очень легко распространить её на более сложные варианты.
После твоего душевного рассказа на нашем собеседовании, я бы перевернул твой рисунок на 180 градусов, увидел твои округлившиеся глаза и сказал - спасибо, что пришел, пригласи пожалуйста следующего!
Динамическое программирование - это не только запоминание промежуточных результатов, но также и само рекурсивное решение. Также как при вычислении числа Фибоначчи, данную задачу можно решить как простым циклом, так и рекурсивно. И именно рекурсивное решение с запоминанием промежуточных результатов является динамическим программированием для обоих задач.
Есть видео, (Тимофей Хирьянов "Динамическое программирование сверху и снизу"). Смотрел его через пару дней после этого видео.
Обычно можно переделать рекурсию на цикл и это улучшает производительность.
Для обЕих задач
Спасибо большое! Стопнул на 1:02 и решил самостоятельно, после чего сверился. Советую всем так делать, хотя бы устно, в уме.
Можно, кстати, оптимизировать использование ОЗУ чуть меньше, чем в 2 раза. Это задача на внимательность, на нахождение треугольника паскаля в ней. А прелестное свойство треугольника паскаля - его симметричность, нам достаточно хранить его половину вместе с главной диагональю (для реализации подсказка: arr[n][m] считается как обычно, arr[n-1][m]+arr[n][m-1], а главная диагональ - arr[n][n] = arr[n][n-1] * 2).
Я не смог досмотреть это видео, просто потому, что у меня начались "вьетнамские флэшбэки" с сотен собеседований, где задавали крайне полезные и актуальные вопросы, которые я точно должен уметь решать.
"Где Вы видите себя через 5 лет?" да в вашем офисе буду бумажки перебирать, где ж ещё?!
Я ща на старости флешбеки как фильмы смотрю, сьэкономил на кинотеатрах и купил клей момент и ласты, перед сном надеваю на всякий случай и наслаждаюсь 5Д без искуственного интелекта, последних технологий, промисов и блокчейнов. Замомните - То что нас не убивает, н№XeRa не делает нас сильнее, просто убивает потом.
хз как я сюда попал, но в принципе не обязательно уходить за границы матрицы - можно упростить дно рекурсии `if (n == 1 || m == 1) return 1;`
а если n уже равно 1, а m ещё нет? У нас же остаются еще куча вариантов развития событий
@@cleverabbit нет, не остаются - возможен только один путь по прямой вдоль "стеночки"
@@firejvlz ох, спасибо, вы конечно правы
Как уже упомянуло несколько людей в комментариях задача действительно может решаться просто по формуле, но если использовать рекурсию как в видео, то более простым вариантом пожалуй будет это:
int paths(int n, int m) {
if(n == 1 || m ==1)
return 1;
return paths(n-1,m) + paths(n, m-1);
}
Если точка находится на одной линии с роботом, то очевидно только один путь к ней, поэтому возвращает единицу, таким образом выход за рамки поля невозможен, и считать его не надо, такая рекурсия как по мне выглядит намного проще, да и для прямого пути в 5 клеток не надо будет вызывать 5 функций пока они не дойдут до робота, а сразу возвращает единицу.
Спасибо! Интересный разбор задачи!
Спасибо большое за объяснение!
Очень круто объясняешь! Посмотрел не отрываясь, спасибо!!!
Саша, здравствуйте! А вы будете продолжать вести канал? Сейчас очень актуальны ваши ролики с задачами и теорией (если она планируется), все очень доходчиво и понятно, спасибо!
Александр, прекрасно объясняете, спасибо!
Хороший ролик, хорошее объяснение. Мы задачи подобного рода аналитически решали на уроках информатики в 6-7 классах (не спец школа), на Basic. Сижу и думаю, то ли учитель хороший был, то ли что-то в мире поменялось. :)
Сейчас аналогичная задача даётся в ЕГЭ, причём это не самая сложная
Если я не ошибаюсь, то можно без рекурсии намного проще. Нужно в каждой клетке (i,j) просчитать к-во вариантов. Начинаем с нижнего ряда слева направо - все единицы (т.к. снизу клеток нет, а слева все время 1). Начитая со второго ряда снизу значение К(i,j) = значение клетки слева К(i-1, j) (для клетки К(1,j) будет 1) + K(i,j-1). И так, пока не дойдем до точки К(n,m)
Да, можно прежде и левый столбец заполнить единицами. Однако это не динамическое программирование.
Плюсую
Почему у тебя так мало подписчиков я считаю то-что ты хороший блогер жилаю удачи и дальше
Спасибо!
Знаешь иногда я завидую таким как вы Веть у меня нет даже канала не то что подписчиков а ты можешь помочь нам
@@АуАУауАнрп Ютуб - это развлекаловка, людям нужны котики и похабные анекдотики, никто не будет после работы динамическое программирование смотреть.
@@zelmanfeig5404 и что?
@@zelmanfeig5404 Я просто выразил свои мысли
Путь однозначно задается как n - 1 стрелка вправо и m - 1 стрелка вверх, выпишем стрелки в ряд в произвольном порядке (всего в ряду n + m - 2 стрелок). Тогда число способов расставить здесь n - 1 стрелку вправо равно количеству сочетаний из n + m - 2 по n - 1 (или по m - 1, что тоже самое). Ответ: (n+m-2)! / (m - 1)! / (n-1)!
А вариант "змейкой" не учитывается? Или нужен кратчайший путь?
0:25 . Робот не может ходить вниз, то есть вариант змейки не возможен в принципе
@@surekt4780 , да, я уже понял, просто не внимательно послушал условия.
Контент супер!
_Динамическое программирование_ - способ решения сложных задач путём разбиения их на более простые подзадачи.
Вся наша жизнь немножно динамическое программирование :-)
Видео как бы намекает зачем компьютеру надо столько много памяти (на стек вызовов рекурсии, на массив для мемоизации) :-)
Тут много людей пишет в комментариях, что можно решить оптимальнее и аналитически вообще (сведя к формуле), но если хорошенько подумать, то показана то не конкретная задача, а _класс_ задач.
Ну и опять же, компьютер изобрели чтобы НЕ заморачиваться. Да, можно интеграл красиво аналитически посчитать, а можно методом трапеций численно.
Аналитически это конечно же красиво и "интеллектуально элитно", но в суровой реальной жизни когда заказчику надо "вчера!" и результат нужен "прям щас и один раз!" и "уже всё!" и у директора дёргается от этого глаз от нервов всех этих - математика-аналитика-теоретика раньше уволят нафиг (и заводу может кирдык придёт), ну или премию дадут "Петровичу" который методом трапеций за 5 минут прикинул и сказал "ах**но! материала хватит! вот смета!" :-))))
Разве математик-теоретик не посчитает интеграл по красоте сейчас 5минут?
@@akiiaev математик-теоретик - товар штучный, а решения надо принимать много где, и тут на помощь придёт "числодробилка" которая сделает даже дурачка "великим математиком" ;-)
в мире много рукожопов - поэтому изобрели санчала трафареты, а потом и ЧПУ станки, в мире много тугодумов - поэтому изобрели компы и численные методы и методы мат.моделирования. и это дало возможность даже дурачкам кормиться и размножаться, алилуйя! :-D
но конечно же "для любителей помучаться" (мазохистов) остались ручные дрели, лобзики, логарифмические линейки, кульманы для чертежей вручную и прочие "орудия пыток" :-D
но мне как-то нравится в 3D принтер или ЧПУ загружать чертёж, который я могу поправить в САПР если что не переделывая полностью. видимо я не дошёл до "дзена", мне результат как-то важнее процесса.
Примерно в этом и заключается талант грамотного технического менеджера: отличать задачи, которые нужно решать быстро и в лоб, от тех, которые нужно решать долго и красиво. И в промышленной разработке, конечно, первых гораздо больше, но всё же не 100 %.
Можно увидеть в этом треугольник Паскаля.
Номер ряда L = n + m - 2.
Искомый член ряда P = Min(m, n) - 1
Результат L! / (P! * (L - P)!), то есть число сочетаний из элементов по Ну и всё, не нужно так заморачиваться.
Дабы не мучить компьютер лишний раз, число сочетаний высчитываем как "Произведение P последних из L делить на P!"
И тогда сложность из O(m+n) становится O(min(n, m)).
Как бы сделать ещё красивее?
поле размером 2000 х 2000, с факториалом не мучать компьютер лишний раз не получится
@@АндрейБочарников-х5ъ Для компа перемножить тысячи чисел - десятая доля секунды. Надо, конечно, позаботиться об избежании переполнения, но всё равно это будет гораздо быстрее в сравнении с оббеганием 4 000 000 ячеек.
К тому же у нас не растёт потребление по памяти, чего не скажешь про код автора.
@@YevhenDiulin так а астмптотику подсчёта факториала вы знаете?
Плюс следить за переполнением легко, но что делать если оно будет?(а оно будет)
Длинная арифметика или варианты получше?)
Все это красиво только на листочке, а на практике чёт не очень
@@freedomtv2295 Можно взять тип с плавающей точкой и не считать факториалы отдельно, а сразу считать число сочетаний: умножил на один член чеслителя, разделил на один член знаменателя, потом на другой член чеслителя и на другой член знаменателя. Есть пути в обход.
@@YevhenDiulin идея с поочередным умножением это хорошо, но типы с плавающей точкой сразу нет. Это гора проблем, там от ответа не останется даже и следа
Грамотно объяснил, спасибо!
Александр. Спасибо. Наткнулся случайно. Прекрасный материал и его подача. Не останавливайтесь!
Это ж простейшая комбинаторика :)
Спасибо. Окончательно убедился что да ну его нафиг.
Если в задании нельзя использавать комбинаторику (хотя этот способ самый лучший) можносделать программу ещё проше,
На языке паскаль:
for i:=1 to n do a[i,1]:=i;
for i:=1 to m do a[1,i]:=i;
for i:=2 to n do
for j:=2 to m do
a[i,j]:=a[i,j-1]+a[i-1,j];
write(a[n,m]);
Да уж, уже подзабыл программирование со школьных лет не занимался
Для первой задачи ответ 4, но это так, придирка. Видос отличный!
4 - это если он вниз ходить умеет
@@rizhiy87, вы правы, я упустил исходные требования, да, три варианта.
Ох, ребята. Снимаю шляпу перед вами! Эта область для меня темный лес. Всегда вами восхищался!
А почему ответ на задачу из гугла 3 , а не 4 ?
Понял,прослушал, что он в низ не может ходить.
И че я сюда зашел? Почуствовал себя тупым и пошел дальше 🤓
вспомнил basic и fortran 4
и пошел дальше играть в видеоигры? )))
@@ovsyannikovo а чего добился ты 😅, я вот много игр прошел - дибильных
@@GrAlUnrealEngine ну для начала я смог завязать с играми 🙂
@@ovsyannikovo жаль тебя 😂 (рофлю), а меня в их разработку затянуло.
Рекурсия почти всегда красивое решение. Хотя и трудно для понимания иногда. Да и цена алгоритма очень высока.
Если у нас задача просто посчитать пути, тогда предлагаю такой вариант:
Если ручкой провести все пути, то можно заметить следующее- есть 2 экстремальных пути, когда робот пойдет по периметру, а также пути внутри периметра. Если посмотреть на все пути, то в поле справа от каждого остается на один квадрат больше, и фигура, образуемая этими квадратами будет расти равномерно, как выпуклая геометрическая фигура.
Говоря проще, количество путей будет равно сумме (m*n) - (m+n-1) +1,
где (m*n) -это количество всех квадратов, (m+n-1) - это сумма квадратов в случае, если робот пошел экстремально вверх до конца и направо до конца, а +1 - это путь, который он прошел экстремально вправо до конца, а потом вверх до конца
Но данное условие не подойдет в случае, если имзенится поведение робота. Надеюсь хоть чтото понятно, если будет интересно - приложу рисунок
Почему цена алгоритма высока? Рекурсию необязательно реализовывать через вызов той же функции. В этой конкретной задачи решается массивом 2*M или 2*N.
@@airn587 да гдето читал, что рекурсивные функции норм так жрут
А как делать не через функцию? через цикл с ветвлением?
Для m = 3, n = 3 проверь. По твоей формуле 5, по факту 6
@@airn587 ну и недавно посмотрел про рекурсии. Если они довольно большие - просто ловишь stackOverflow
@@АнтонФролов-о1с блин) я уже не помню че там было))
Ну в целом я к тому, что не всегда нужно решать задачу, чтобы она решала любые вариации впоследующем. Если есть возможность сделать тупо и просто, потратив меньше часов и энергии, то, возможно, это лучшее решение.
А если вдруг потом понадобится расширение - тогда уже подумать над алгоритмом. Опять же, зависит от котекста
Эту задачу можно решить ещё быстрее увидев, что это треугольник паскаля, правда надо ещё знать формулу его. Тогда апроксимация времени работы алгоритма будет = О(n+m).
Эту задачу можно решить и за константное время,, используя формулу количества сочетаний. Только для конкретно этого варианта задачи нужно уменьшить и ширину, и высоту сетки на 1.
@@ДенисСитник-й8б Для количества сочетаний придётся считать факториалы, каждый из них считается за время O(n). Тогда для этой задачи О(max(n,m)).
@@АкрилГуашев Там факториал от n+m
@@кикислав Вы написали, и я задумался. Раз уж так, можем считать факториал с конца, то есть a*(a-1)*(a-2)*...*(a-i), где а=n+m в нашем случае, а i=min(n,m); попутно же будем считать количество перестановок (i факториал); поделим одно на другое и получим искомое количество сочетаний. Выходит что сложность алгоритма и того меньше - О(min(n,m)).
@@АкрилГуашев На самом деле апроксимация вычисляется более сложным путём, так-как апроксимация умножение двух чисел длиной n и m равна O(max(m, n)) Вы можете сами проверить, написав программу, потому что компьютер умножает числа примерно как мы, в столбик.
изначально не понимал с какой стороны подойти к решению)
В итоге пришел к решению с комбинаторикой.
Но решение автора мне очень понравилось. Правда что рекурсия уже не подойдет на очень больших m и n
Можешь написать как это комбинаторикой решить?
Интересно кто это применил это на практике больше одного раза?
Это на самом деле задача из комбинаторики для 7-8 класса. Здесь можно даже увидеть треугольник Паскаля, который разворачивается направо-вверх:
...
1 ...
1 4 ...
1 3 6 ...
1 2 3 4 ...
1 1 1 1 1 ...
Число в каждой клетке равно количеству маршрутов, ведущих в неё из начальной клетки.
Ну и одновременно с этим, числа, из которых состоит треугольник Паскаля представляют собой кол-во сочетаний, поэтому ответ C из n по m.
Фишка в том что посчитать биномиальный коэффициент всё равно не просто, а если на машине умножение долгая операция то и без дополнительной памяти не обойтись
интересная задачка, своеобразное комбо матрицы и дерева)
с чего-то вдруг было принято, что если квадрат 1 на 1, то у робота 1 путь, хотя на самом деле пути нет, а не он пустой, т.к. робот никуда не движется. Дальше можно не смотреть, как уже написали в комментах, задача решается гораздо проще исходя из логики и без рекурсии
вот легче решение для понимания. Если идем вправо на одну клетку тогда это приравниваем к 1 а если вверх то 0. Тогда получается бинарное число из 1 и 0. Нам надо что бы в этом бинарном числе было 4 единицы в любом порядке. Всего 7 цифр в нем. В первой задече получается бинарное число из 3х цифр в котором должен длжно быть одна единица в любом порядке. Таким образом можно решить эту задачу с любым колличеством клеток. Следовательно нам просто надо найти сколько бинарных числел с 7 знаками содержит 4 единицы. Код элементарный так же:
def decimalToBinary(n):
return bin(n).replace("0b", "")
N=0
for i in range(int('1111111', 2)):
if str(decimalToBinary(i)).count("1")==4:
N+=1
print(N)
35 для последней задачи получаем и 3 для первой итд
спасибо за видео, очень помогло!
хм, почему путь 21 22 12 13 до двери не рассматривается? Почему учитывается только самый короткий путь?
А почему массив выделяется m+1 на n+1 а не просто m на n?
Саша , отлично объясняешь! Хоть я и вообще не хочу быть программистом )) Я пилот, но умение рассказывать у вас однозначно есть!
Ну так, пілоти то раза 2 більше, в середньому, отримують)
@@denisdragomirik не в деньгах счастье
@@pilotjenya тоді давай до нас ;)
@@denisdragomirik нi. Спасибо :)) мэнi и тут дуже гарно
@@pilotjenya 😁😁
n, m = int(input()), int(input())
b = []
for i in range(n):
b.append([0] * m)
for i in range(m):
b[0][i] = 1
for i in range(n):
b[i][0] = 1
for i in range(1, n):
for j in range(1, m):
b[i][j] = b[i - 1][j] + b[i][j - 1]
for i in b:
print(i)
Аналогичный алгоритм на питоне
У тех, кто не ищет лёгких путей, может быть ещё один путь: вверх, вправо, вниз, вправо, вверх.
Вообще не понял, как прийти к выводу что: paths(n, m) = paths(n - 1, m) + paths(n, m - 1)
мне кажется это потому что мы считаем число путей (комбинаций как прийти) к точке А и к точке В. Которые находятся либо слева либо снизу.
Это просто разложение первого хода. Ты можешь пойти вверх и тогда высота оставшегося поля уменьшится на 1. Или ты можешь пойти вправо и тогда ширина поля уменьшиться на 1. Соответственно общее кол-во путей - это просто сумма путей для обоих вариантов.
Все проще. Это треугольник паскаля.
Время работы О(2*(m + n))
В случае если n>=2 и m >=2 ответ записывается формулой
(n + m - 2)!/((m - 1)! * (n - 1)!) //просто найти факториалы отдельно и посчитать
Иначе ответ 1
Хорошо объясняешь. Но почему так мало видео?
Пашет человек на гугл/амазон/фейсбук, некогда
Половина комментаторов пропустили важную часть условия и умничают. Всё, что нужно знать о комментаторах
У нас эта и подобные ей задачи были в 8 классе на уроках информатики. В Паскале писали всякие алгоритмы для роботов.
Всегда ненавидел это дело. По сути, весь 8й и 9й класс были посвящены тому, чтобы робот бегал по карте с препятствиями и искал выход наиболее оптимальным образом. Вечно ошибался и либо написанная прога не работала, либо робот шёл не туда, куда надо, либо шел куда надо, но не оптимальным способом, либо учителю не нравился сам код...
В общем, с программированием не сложилось :)
у нас была "черепашка" и "робот-пылесос". робот нужно было программировать на русском. это был 6й класс и я обожал это дело, тогда и влюбился в программирование окончательно :)
А у нас вообще не было компьютеров.
Решила в голове за пять секунд.
Решение:
```cpp
unsigned long long coolfunc(int a, int b) {
int n = a+b-2;
int k = (n+1)/2;
return binomial(n,k);
}
```
Для решения нужно будет округление и факториалы и биномиальные коэффициенты, их можете взять из библиотеки или сами написать:
```cpp
#include
#include
void reduceFraction(int &numerator, int &denominator) {
int greatestCommonDivisor = std::gcd(numerator, denominator);
numerator /= greatestCommonDivisor;
denominator /= greatestCommonDivisor;
}
int factorial(int num, int k=1) {
if (num
Для относительно небольших размеров грида самым быстрым решением будет формула биномиальных коэффициентов, так по использованию памяти мы получим O(1)
там формула еще проще
@Mike я не считал максимальный грид для моего решения, но для решения на литкоде мне хватило трёх переменных long long и небольшой оптимизации. В итоге самый быстрый результат на сайте.
Разве формула биноминальных коэффициентов даёт О(1).
Там же, кажется, О(n)
@@avshukan ты не совсем прав, фактически нам нужна петля для подсчёта факториала, но при минимальном упрощении мы считаем только то колличество итераций, которое будет меньше (k!-1 Или (n-k)! -1)
@@adventurer_v
ну, то есть O( min(k, n-k) )
в худшем случае, это О(n/2)
так?
Разве функция хелпер типа может вернуть массив инт?
Можно обратить внимание, что это просто повернутый треугольник паскаля и решить задачу просто фомулой C из n по k, нет? Или я чего-то не догоняю?
Вот кстати из-за таких педагогов и таких фанатиков в комментах дети в школах и боятся математики) Я не пытаюсь никого обидеть, но здесь сухое построение функций очень сбивает. Та же фигня была и на курсах программирования. А проблема решалась очень просто - давайте нормальные и понятные названия переменным! И тогда человек которому вы что-то объясняете лучше усваивает инфу.
Сами учите как использовать поменьше памяти, а забываете что мозг человека работает примерно также с новой информацией. И вот когда парень на видео увлеченно ушел вперед и рассказывает о формулах вычисления, человек судорожно пытается построить какую-то цельную картинку в мозгу и вспомнить а что там за m, а буква n это что там было?
Понимаю что это звучит наивно и для профессионалов это очевидные вещи, но всё же это образовательный ролик на ютубце. И направлен он на людей которые хотят научится, а не на тех кто уже всё это знает.
самое главное в подобных задачах - уметь применять знания полученные при решении. а то приходят литкодовцы и кроме алго и систем дизайн интервью ничего пройти не могут. да и на практике говнокод лютейший генерируют. идея которая была заложена в алго интервью уже изжила себя и это абузят все кому не лень.
Добрый день. Можно ли решить задачу следующим способом? Робот может двигаться только вправо и вверх, т.е. каждая клетка из которой можно двинуться вправо или вверх является развилкой и дает +1 путь - это не крайние правые и не крайние верхние клетки. При поле размером 1 клетка в ширину или 1 клетка в высоту у робота только один путь. Т.о. получаем алгоритм: h=5; n=4; ways_count=1; hi=1; ni=1; for(hi=1;hi++;hi
Развилка даёт не +1 путь, а +к путей , где к - количество путей до этой клетки.
Проверьте сами себя: посчитайте для квадрата 4*5 "руками" (должно получиться 35) и своим алгоритмом
Можно свести задачу к графу, построить матрицу смежности и возвести в степень k, где k - расстояние между вершинами. Это будет где-то (m*n)^2.5 сложность, зато потенциально найдет решение в общем лучае. + Будет задел на применение прочих графовских алгоритмов
Можно решить задачу через комбинаторику и найти ответ в одну строчку вычислений)
@@alexanderpalagin4662на больших m и n устанешь, эти факториалы не влезут в размер переменной, нужно будет с бубнами плясать, лучше загрузить процессор и точно знать, что оно выполнится, а не упадёт, потому что комп не сможет оперировать в формуле факториалом от миллиарда)
матрица NxM
число ходов вправо n=N-1, число ходов вверх m=M-1
нужно найти кол-во сочетаний n ходов вправо и m ходов вверх
всего ходов s=n+m
paths = s! / (n! * m!) = (s*s-1*s-2*...*s-n)/(1*2*3*...*n) = ИЛИ = (s*s-1*s-2*...*s-m)/(1*2*3*...*m)
то есть выбираем меньшее из k=min(n, m) и вычисляем
paths = s-i/(1+i), i=0..k-1
рекурсия это - зло (в большинстве случаев)
всегда нужно быть ОЧЕНЬ осторожным с рекурсией (а лучше избегать ее), т.к. очень часто неизвестна глубина рекурсии и размер стека, а отсюда и до переполнения стека недалеко (если конечно современным прогерам известно что это такое :) )
Это утверждение верно, если язык не поддерживает TCO и ленивые вычисления (если, конечно, противникам рекурсии известно что это такое :) )
@@MultiOpachki
противники рекурсии любят писать переносимый код, который не зависит от платформы, компилятора, настроек, ... :()
кстати даже не хочу знать что такое ленивые вычисления, хотя догадываюсь
зато хорошо знаю как сложно найти переполнение стека, которое происходит раз в 5 лет у одного юзера из 1000
@@alexeyivanov3222 Настолко переносимые, что эти программы запускаются еще и на AVR, например? Чтож, похвально.
Пробовал данное решение использовать на leetcode, получил перерасход времени. Вот более быстрое решение на JS:
var uniquePaths = function(m, n) {
let row = new Array(m).fill(1);
for (let i = n -2 ; i>=0; i--)
{
const newRow = new Array(m).fill(1);
for (let i =m-2; i>=0;i--){
newRow[i] = newRow[i+1]+row[i]
}
row = newRow;
}
return row[0]
};
Хорошее решение, только для чего используешь два массива? да и проверку всё же лучше делать, чтобы код ошибок не выдавал ;)
function uniquePaths(m, n) {
if (m < 1 || n < 1 || (m === 1 && n === 1)) return 0; //считаю, что поле [1;1] также не имеет решения
if (m === 1 || n === 1) return 1;
let arr = new Array(m).fill(1);
for (let i = n - 2 ; i >= 0; i--){
for (let j = m - 2; j >= 0; j--){ //для лучше читаемости кода лучше всё же переменные называть по разному
arr[j] = arr[j+1]+arr[j]
}
}
return arr[0]
};
Динамическое программирование здесь понадобилось бы, если бы были случайно разбросаны острова, которые бы случайно вырезали часть маршрутов. А в задаче именно в таком виде тут будет чисто комбинаторное решение в виде функции от m,n, равной числу сочетаний из (n + m - 2) по (n - 1) или (m - 1), без разницы
Подскажите пожалуйста, как выводится такая формула и почему для данной задачи? Заранее спасибо.
@@zugzug90 Оно не выводится, оно по смыслу есть) У тебя путь длиной n + m - 2 в котором ты делаешь (m -1) шагов вниз и (n - 1) шагов в сторону. Ну то есть условно можно представить путь как последовательность из 0 и 1 длиной (n + m - 2) в которой будет(n - 1) нулей и (m - 1) единиц, располагающихся в случайном порядке. Тогда совсем очевидно что количество таких перестановок будет числом сочетаний кол-ва нулей или единиц из всей длины
@@matanmaster "ты делаешь (m -1) шагов вниз" - но ведь вниз ходить нельзя.. Все таки непонятно, как получается (n-m-2).. Мб (n + m - 2) ? Там и выше у вас такое число кстати. Комбинаторику уже совсем не помню, пока что утверждение для меня неочевидно, но вероятно если освежить в голове пару глав - станет понятно лично мне. В любом случае спасибо за разъяснения.
@@zugzug90 Ну в данном ролике вверх, обычно в этой задаче идут из верхнего левого в нижний правый. (n - m - 2) и нет нигде, там сумма.
А почему мы не можем в первой задачи пойти так ( 2,1; 2,2; 1,2; 1,3 м следующий ход уже в дверь ) это был бы 4 вариант
Вроде все понятно и просто ,но если самостоятельно сделать ,я бы прикурил )
Только функция 2^(m*n) - показательная, а не экспонента.
Спасибо за видео!
Я похоже что-то не понимаю в этих ваших программированиях, но зачем считать биномиальный коэффициент раскрывая его через рекуррентную формулу?
Да, можно решить просто через число сочетаний С_(n+m - 2)^(n - 1), но автор показывает более понятный для программиста итеративный рекуррентный способ
Программирование попросту немного не про то, там недостаточно один раз вычислить по формуле и забыть.
Что если, отныне нужно считать наикратчайший из этих путей? Или у ячеек вдруг появились веса (ходить по одним "дороже", чем по другим)? Гораздо проще ввести небольшие изменения в текущий алгоритм, чем выводить новые формулы.
А если этот алгоритм работает в рамках какого нибудь приложения и с этим кодом взаимодействуют другие разработчики? Тогда для его понимания проще и быстрее пару раз прогнать этот кусок кода с разными значениями, нежели разбираться что такое биномиальный коэффициент.
Так что, этот вариант имеет место быть, но в мире программистов - это очень плохая практика
@@easy_smoke плохая практика не использовать математику для уменшения усилий на вычисление
У вас явно не было серьёзного опыта в продакшне.
Написать программу это лишь небольшая часть работы, гораздо бОльшая - её поддержка. Грош цена коду, если нельзя с ходу понять что и как он делает, а в последствии адаптировать его под меняющиеся условия. Поэтому важнее оптимизировать процессы в команде и сэкономить человекочасы, нежели подобные мелочи, а современные вычислительные мощности всё равно нивилируют разницу до минимума.
Конечно, если мы запускаем аппарат в космос, математика сразу выглядит в разы выигрышнее. Условия всё равно концептуально не меняются, а сложность вычисления минимальная. Однако, с IT это уже имеет мало общего
@@easy_smoke видимо у вас его еще меньше, особенно в высоконагруженных😅
Как не программист сломал себе мозг пока додумался почему массив на единицу больше
Странный алгоритм - показывает 3 пути когда их 4 в последнем примере. Через центр идут 2 пути один вверх, другой вниз
Интересно почему мало кто обратил на это внимание.
Как это вниз? 0:17 Условия задачи гласят, что робот не может так ходить.
@@MuKeXa ясно. странный алгоритм для странного робота)
мне кажется или просто return n+m-2?
А можна на нормальній мові?
2001 год. У нас тогда появился компьютерный класс в школе и на информатике мы писали программу с похожим решением. Только там был не робот, а кенгуру.
Если кенгуру - тогда m-n заменяем на k-z . Только так и не как иначе!
@@maksimr3175 а для черепашки x-y
@@A1bertG шуточки шутим?! Какие "ХУ"? Ну какие ху? Какие ху. Это элементарно ! Если черепашка значит n-z !
Шучу. Всех благ! Кидаю краба. Присел на корточки. Семечки плюю в кулёчек .
Уважаемый автор, на 5.52 сек клетка 31, говорит что там количество ходов 1 шт. А как же последовательность 11 - 12 - 22 - 21 - 31 ? Может условие чуть иное в задаче? получается что мах количество ходов для n=3 m=2 равно не 3 а 4. Спасибо
Кудой, кудою? По ТЗ робот может ходить лишь вправо и вверх.
Мне одному кажется странным код, который он приводит? Во первых нигде нет суммирования значений рекурсивных ступеней(Везде только ретёрны), во вторых функция должна возвращать инт, а возвращает массив. 8:12
1) а. С массивом будет вызываться функция повторно для тех клеток, которые равны нулю; б. Массив должен быть заранее известного размера либо динамически перераспределяться - будет развесистый спагетти-код. Поэтому надо функцию вызывать из экземпляра класса, добавить поле с мапой и в начале функции ифчик с проверкой на присутствие в мапе, а в конце добавить вхождение в мапу. 2) a. рекурсия сама по себе ограничивает глубину вызова и стоит это как-то учесть, например, выбрасывать исключение при слишком больших (m, n); б. Ддя больших значений m и n, которые не позволят массиву/мапе поместиться в кэш процессора, будет производится вычитка из памяти. Операция эта долгая, и прежде чем добавлять такую реализацию, стоит проверить на бенчмарках выигрыш от нее - вполне возможно, что повторное вычисление будет быстрее
По сути массив вы используете как мапу, где индекс == ключу элемента. Согласен, для оптимизации это хорошо иногда работает, массив очень полезная штука, но тут и мапа будет хорошо работать, а читаемость существенно вырастет, поэтому она и должна быть в коде как минимум до того момента, пока на бенчмарках не будет доказана эффективность замены
@@hro688 обычно мапа на порядки медленнее массива...
@@user-uvk в цифрах О большого и то, и то О(1). Понятно, что будут накладные расходы на высчитывание хэша и сравнение объектов, а также на плохо распределяемые объекты, но и в таком случае, например, в джаве, все под капотом достаточно хорошо оптимизируется до O(log N) для сравнимых элементов. И при этом по памяти мы независим от непрерывного участка памяти. В общем, непонятно, откуда взялось "на порядок медленнее", можете пояснить? И в каких компаниях попросили бы писать такой код без мапы (чтобы туда не попасть случайно), если, конечно, там не какую-нибудь встроенную систему реального времени управления атомным реактором внутри него же самого на жестко ограниченном железе пишут
@@hro688 Мапа работает гораздо дольше по следующим причинам: 1) при вставке очередного элемента под него надо выделить память. Это значит, пройтись по спискам свободной памяти, найти там подходящий участок, разделить его на выделяемую и оставляемую в свободной памяти части, организовать необходимые служебные структуры и т.п. 2) из-за наличия служебных полей (от списков памяти) размер выделяемой под элемент памяти больше размера элемента данных. Если элемент данных маленький (как в данной задаче 4 байта), то эти накладные расходы (минимум 2 указателя по 8 байт) в разы больше полезной памяти - это повышает нагрузку на кеш процессора (точнее, снижает вероятность найти данные в нём). 3) при выборке надо посчитать хеш-код, использовать его как индекс в обычном линейном массиве или для поиска по дереву (зависит от реализации мапы) - это требует много машинных команд да ещё с условными переходами (которые имеют свои накладные расходы для процессора), а получение int из простого массива - одна машинная команда. 4) работа с мапой, обычно, это вызовы встроенных функций из библиотеки, а с массивом - прямой код в программе. Это означает лишние обращения к памяти для передачи аргументов подпрограмме через стек, которых нет в работе с массивом.
Мапа имеет огромное преимущество, когда только малая часть возможных ключей (которые могли бы быть индексами в массиве) будет использована. Тут она экономит память, что при больших размерах массива может быть важно. И в случае, когда ключ поиска не может быть напрямую использован как индекс массива, массив отдыхает.
Пока такие задачи задают на собеседованиях в гугл и амазон - у нас их добавляют в ЕГЭ по информатике))
Иначе некому в гугле будет работать. Вы же не думаете, что таланты из Стэнфорда пойдут в Гугл работать? Такие идут работать в более важные стратегические структуры.
Можно сразу дать ответ: С из n+m по n.
Ну так надо это ещё посчитать. Можно O(n*m), а можно O(n)
Можно еще оптимизировать вдвое, если учесть, что paths(n, m) === paths(m, n)
Спасибо. Решение очень красивое и простое, но если вы ищите путь, то где препятствия? Если есть препятствия, то путь будет с шагами назад и вниз, а это может привести к циклам, которые можно исключить если на карте ставить метки, где идёт текущий прогон. Вы передаёте в рекурсивной функции параметр - таблицу, то есть таблица должна остаться в стеке при каждом вызове, но это при росте размера карты приведёт к ошибке Stack Overflow? Избежать ошибки можно если сделать "прямое" решение с поиском путей от первой точки, заменив рекурсию на цикл, а таблицу из параметров сделать переменной.
Решение автора ролика не самое простое и далеко не самое красивое! ;)
И ещё вы не внимательно слушали условие задачи - робот может ходить вверх или вправо, но он НЕ МОЖЕТ ходить вниз или влево!
@@ukrainekiev3990, вы серьёзно?
Просто привычки программиста, ТЗ меняется на ХЗ в любой момент.
В общем, можете рассказать пользователям чего робот "НЕ МОЖЕТ".
@@Aimilomim, при чём здесь "можете рассказать пользователям"? Речь идёт о том, что вы НЕВНИМАТЕЛЬНЫЙ и невнимательно слушали условие задачи! Невнимательность это не привычка программиста, это привычка раздолбая, от сюда ваши кривые коды со всеми вытекающими ))
@@ukrainekiev3990, в хорошей программе должна быть возможность модификации. А у пользователей всегда есть новые требования.
Вы считаете, что рекурсия лучше циклов? Параметры рекурсии не имеют значения?
@@Aimilomim забей. Он не поймёт
Добрый день! Возможно, я чего-то не понимаю, но я вижу здесь классическую рекурсию. Да, есть двумерный массив состояний, но заполняется он в рекурсивной функции. Вся прелесть ДП, на мой взгляд, как раз в том, что рекуррентное соотношение обрабатывается в цикле без применения рекурсии.Я могу предложить свой вариант. Если я неправ, то прошу дать разъяснения.
Добрый день. Опишите пожалуйста свой вариант с заполнением массивов. Я учусь и интересно как это относительно данной задачи
У меня только один вопрос: зачем решать перебором то, что считается аналитически?
Роботу нужно сделать n движений вверх и m движений вправо. Вполне очевидно, что количество путей равно числу сочетаний из n+m по n.
реально интересная задача!
Решал такую задачу много лет назад на позицию джуна
Я может что то не понял, но в примере где n=3, m=2, 4 правильных ответа, а не 3
Посчитай ручным образом возможные пути. Просто на примере рисунка. Так будет понятнее. Путей действительно 3, соответственно ответ аналогичен.
робот не умеет ходить вниз
вверх вправо вправо
вправо вверх вправо
вправо вправо вверх
@@chaosvk13 А как же маршрут "вверх вправо вниз вправо вверх"?
@@Djonni47 3 комментария вверх
эту задачу можно решить гораздо проще и красивее, без циклов, условий и прочего. можно составить формулу числа возможных путей от N и M ) вот как это можно сделать: с каждым ходом робот продвигается либо вверх либо вправо, следовательно все маршруты имеют одинаковую длину и отличаются только последовательностью ходов вверх и вправо, количество ходов вверх = N-1 количество ходов вправо = M-1. наша задача - найти, сколько есть вариантов расставить N "вещей" в (N+M-2) позициях ("вещи" не уникальны). для этого есть формула в комбинаторике. помогите мне её вспомнить))))
опять же, это красивее, но дольше обрабатывать, так как вычисление условного поля 2000х2000 это затратнее
А сколько даётся времени на её решение?
Вот решение в три строки:
factorial = lambda n: 1 if n == 0 else n * factorial(n-1)
def calculate(m, n):
return factorial(m+n-2) // factorial(m-1)
Вот она деградация программистов - писать целую программу для элементарной задачки по комбинаторике
Не все изучали комбинаторику
@@A1bertG Может еще арифметику тоже не обязательно программисту знать?
@@A1bertG Это школьная программа. Что этот программист вообще изучал?
Кликбейтное видео, вот и всё. Даже если и спрашивали в гуглах такое, то только из-за нехватки программистов
Сам автор тоже алгоритмы нифига не знает. o(2^(n+m)) это же ужасно. Не сложно додуматься до o(1), просто выводя формулу
по моему задача решается легче математически. всего шагов n+m-2 и надо выбрать лишь номер шагов вверх или вправо, тоесть ответ С из n-1 по n+m-2 или C из m-1 по n+m-2 тут как удобнее, т.к. числа эти будут равны
Саша, в итоге устроился куда-нибудь на работу?
Я долго думал, что же мне напоминает ДП. Это как кэширование данных, чтобы не приходилось каждый раз обращаться к базе
Проблемы с условием? Робот может выбрать не кратчайший путь и идти змейкой, что поломает логику
спасибо за разьяснение
А через комбинаторику?
Случайно, не воспользовалась ли майкрософт данной задачей для отбора программистов для написания windows 10 с критерием - кто решил данную задачу данным способом, берём, а кто другим способом - забраковали. Из чего такая аналогия? Когда комьютеры всё мощнее и мощнее, а работают всё медленнее и менее отзывчиво. По сути: функция О(...) не покрывает всех критериев затрат времени. Ещё есть затраты на вызов стека, дополнительное пространство памяти на хранениние результатов, пустые сравнения и копирование просчитанного значения в память и из памяти. Я вижу лучший путь, чем доп массив. Представленный автором 2й метод несколько быстрее первого, но не отличается принципиально. Спасибо за видео