@Itvanya

Проект Эйлера. Задача #15. Как решить правильно?

Ребята, начал решать задачи по проекту Эйлера. Решил уже примерно 75 штук, но осталось несколько задачек, которые мне не совсем даются на пути окончания первой сотни задач. Я неплохо знаю математику, анализ, но совсем не учил ни комбинаторику, ни теорию вероятности, ни, тем более, что-то связанное с подобным поиском. Тут решения два : использовать динамическое программирование, либо комбинаторику. Брут тут реален, но это займет ну очень много времени.
Своим умом допер, что :
При N=20(кол-во исходов в одну сторону):
x = 2N! / (N! * N!)
x = 2*20! / (20! * 20!)
x = 137846528820(ответ верный)
Но, опять же, я не совсем понимаю механику работы поиска : количество исходов для любой клетки - максимум 40 вариантов(20 вниз и 20 вправо), но каким образом тут нам помогает факториал? И как это можно решить другим способом? Какие формулы нужно использовать, а также какую область математики, чтобы находить подобные решения без танцев с бубном?
P.S. решал на Python

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
p015.gif
How many such routes are there through a 20×20 grid?

P.S.S. Вариант в переводе - euler.jakumo.org/problems/view/15.html
Спасибо!
  • Вопрос задан
  • 4392 просмотра
Пригласить эксперта
Ответы на вопрос 5
@Seradasrad
Я понимаю, что вопрос был задан 3 года назад, но решать Проект Эйлера я начал только сейчас и может у кого-то ещё будут вопросы по этой задаче. Сам код я писать не буду, читайте коммент от Владимира Мартьянова. Чтобы решить задачу "правильно" необходимо знание алгоритмов. Вот тут часть теории (с 2:48 найден рекуррентный случай) https://www.youtube.com/watch?v=m4HOkVeN4Mo&list=P...
А ещё одна часть теории здесь (построение матрицы) https://silvertests.ru/GuideView.aspx?id=34372
На основе этой информации вы сможете сами составить достаточно быстрый код.
Ответ написан
Комментировать
@SilentFl
Факториалы - потому что количество путей описываются треугольником Паскаля, а их можно вычислить и через биномиальные коэффициенты. Можете посмотреть логику решения тут
Ответ написан
Комментировать
Тут что то с формулой не так
x = 2N! / (N! * N!)
При N = 2 , ответ будет 1
При N = 3 , ответ будет (2*(1*2*3))/((1*2*3)*(1*2*3)) = 12/36 = 1/3
Как у Вас с такой формулой в обще получилось число больше единицы, если знаменатель всегда будет больше числителя
Ответ написан
@Stiknkfist
Количество шагов в каждом возможном пути 20 на 20 клеток(21 на 21, так как шаги происходят между клеток) из верхнего левого угла в нижний правый будет 40. так как у нас только 2 варианта шага - вниз и вправо, их можно обозначить как 0 и 1.
По сути это количество возможных комбинаций для длины в 40 знаков состоящей строго поровну из 20 единиц и 20 нулей. Например для 2 на 2 (3 на 3) длина пути - 6 шагов, для 4 на 4 (5 на 5) - 8. для 20 на 20 (21 на 21) - 40. И все бы хорошо, но itertools уводит систему в нокаут рассчитывая все возможные последовательности из 0 и 1 длиной 40 ...
Ответ написан
Комментировать
@Duh_py
64adac8e814c0014227070.png
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы