Паскаль составить программу вычисления. Все 3 задания

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("Enter N value: "))

M = int(input("Enter M value: "))

print(calculate_max_way_price(0, 0, N, M))