|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
29.01.2014, 21:35 | #1 |
Пользователь
Регистрация: 23.04.2012
Сообщений: 82
|
Задача на динамическое программирование
Как решать такого рода задачи?
В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку. Формат входных данных Вводятся два числа N и M - размеры таблицы (1<=N<=10, 1<=M<=10). Формат выходных данных Выведите искомое количество способов. |
29.01.2014, 22:19 | #2 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,291
|
Чуток подумав, приходим к выводу, что количество способов попасть в клетку равно сумме способов попасть в верхнюю и левую клетки от данной. 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 |