0.04.2020
Сообщений: 6
1
Количество маршрутов в прямоугольной таблице
10.05.2020, 18:11. Просмотров 6573. ответов 4
Метки нет (Все метки)
приветствую вас, участники форума!
очень нуждаюсь в вашей в решении задачи на сайте Сириус.
Задание
В прямоугольной таблице N×M вначале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть у игрока попасть в правую нижнюю клетку.
Входные данные
Вводятся два числа N и M — размеры таблицы 1≤N≤10,1≤M≤10.
Выходные данные
Выведите искомое количество .
Пример
Ввод
1 10
Вывод
1
Решения, которые работают, но на сколько верно и сайт (Сириус) их не принимает.
№1
PythonВыделить код
1
2
3
4
5
6
7
n, m = map(int,input().split())
F = [[0]*(m+1) for i in range (n+1)]
F[1][1] = 1
for i in range (2, n+1):
for j in range (2, m+1):
F[i][j] = F[i-1][j-2]+[i-2][j-1]
print (F[n][m])
№2
PythonВыделить код
1
2
3
4
5
from math import factorial
N = int(input())-1
M = int(input())-1
res = factorial(N+M)//(factorial(N)*factorial(M))
print(res)
Так как речь идет о таблице, то лучше перебрать рекурсивно. Логично, что количество путей для клетки (i,j) - это количество путей для правой соседней клетки + количество путей для нижней соседней клетки.
При таком условии мы будем посещать те же клетки слишком часто, однако значение для них меняться не будет. Имеет смысл вычислить их единожды и запомнить для последующих использований. (На самом деле, достаточно иметь буфер вместимостью всего в 6 элементов, но мы сделаем полное запоминание).
(Иллюстрация 3 - таблица кэша)
Иллюстрации кода и возможного вывода прикреплены в дополнительных материалах.
========================
Ваши оценки и отзывы позволяют лучше оценить качество ответа.
Если ответ удовлетворил, не забудь отметить его как "Лучший".
Успехов в учёбе!
========================
Код:
cache = {}
def calculate_max_way_price(x: int, y: int, m:int, n:int):
if (x, y) in cache:
return cache[(x, y)]
x_way, y_way = 0, 0
if x < m - 1:
x_way = calculate_max_way_price(x + 1, y, m, n)
if y < n - 1:
y_way = calculate_max_way_price(x, y + 1, m, n)
if x == m - 1 and y == n - 1:
cache[(x, y)] = 1
return 1
cache[(x, y)] = x_way + y_way
return x_way + y_way
N = int(input())
M = int(input())
print(calculate_max_way_price(0, 0, N, M))
