Задача на динамическое программирование - Помощь студентам

makskovalko · 29.01.2014, 21:35

Как решать такого рода задачи?
В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку.
Формат входных данных
Вводятся два числа N и M - размеры таблицы (1<=N<=10, 1<=M<=10).
Формат выходных данных
Выведите искомое количество способов.

BDA · 29.01.2014, 22:19

Чуток подумав, приходим к выводу, что количество способов попасть в клетку равно сумме способов попасть в верхнюю и левую клетки от данной. a[i, j] = a[i - 1, j] + a[i, j - 1], причем, если клетки с такими координатам нет, то подставляем 0, а в самой левой верхней клетке стоит число 1.

Аватар · 29.01.2014, 22:25

И решение таким способом называется динамическим программированием

29.01.2014, 21:35	#1
makskovalko Пользователь Регистрация: 23.04.2012 Сообщений: 82	Задача на динамическое программирование Как решать такого рода задачи? В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку. Формат входных данных Вводятся два числа N и M - размеры таблицы (1<=N<=10, 1<=M<=10). Формат выходных данных Выведите искомое количество способов.

29.01.2014, 22:19	#2
BDA МегаМодератор СуперМодератор Регистрация: 09.11.2010 Сообщений: 7,429	Чуток подумав, приходим к выводу, что количество способов попасть в клетку равно сумме способов попасть в верхнюю и левую клетки от данной. a[i, j] = a[i - 1, j] + a[i, j - 1], причем, если клетки с такими координатам нет, то подставляем 0, а в самой левой верхней клетке стоит число 1. Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись ) Последний раз редактировалось BDA; 30.01.2014 в 06:37.

29.01.2014, 22:25	#3
Аватар Старожил Регистрация: 17.11.2010 Сообщений: 18,922	И решение таким способом называется динамическим программированием Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Динамическое программирование, Visual C#/C++, задача о рюкзаке	fanpilot	Помощь студентам	0	21.12.2011 23:13
Динамическое программирование.	IllidanStormrage	Помощь студентам	0	06.11.2011 19:03
Задача на динамическое программирование)	Андрей1010	Паскаль, Turbo Pascal, PascalABC.NET	4	11.10.2011 13:56
Динамическое программирование	joey_ramone	Паскаль, Turbo Pascal, PascalABC.NET	0	23.04.2010 13:51
Задача на динамическое программирование	Римма1990	Помощь студентам	2	02.04.2009 23:11