ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98716
Тема:    [ Динамическое программирование: классические задачи ]
Сложность: 3-
Классы:
Название задачи: Робот.
В корзину
Прислать комментарий

Условие

В исследовательской лаборатории фирмы Robots&Co разработали новую модель робота. Главной особенностью данной модели робота является то, что он работает по заранее заданной программе, в которой могут присутствовать команды: сделать шаг на Юг, на Север, на Восток или на Запад. Робот исполняет программу строго последовательно и, дойдя до конца программы, останавливается. Специалисты из Robots&Co заинтересовались вопросом, сколько существует различных программ, состоящих из K инструкций, таких, что робот, выйдя из начала координат, придет в точку с координатами (X, Y). Оси координат располагаются параллельно сторонам света, и единица измерения, соответствует одному шагу робота. Напишите программу, которая дает ответ на этот вопрос.
Формат входных данных
Во входном файле находятся три числа K, X и Y (0 <= K <= 16, |X|, |Y| <= 16), разделенные пробелами.
Формат выходных данных
В выходной файл ваша программа должна поместить одно число — количество программ для робота.

Решение

В этой задаче мы сталкиваемся с функцией трех переменных: F(X, Y, Z) - показывает количество маршрутов длины Z, приводящих в клетку (X, Y). К сожалению, такая структура данных как

	Array [-16..16, -16..16, 0..16] of LongInt;
требует много памяти. Забудем пока об этой трудности и напишем рекурсивную часть. Для ответа на поставленный в задаче вопрос можно посчитать число маршрутов длины Z - 1 в четыре клетки, смежных с заданной, а результаты сложить, не забывая случаи клеток на границе. Граничными условиями будут F(XY, 0) = 0, если хотя бы одна из координат X или Y отлична от нуля, и F(0, 0, 0) = 1. Действительно, если робота не двигать, то он может оказаться только в начале координат. Теперь вспомним о проблеме хранения данных. Использованное нами решение, конечно, далеко не оптимальное (с точки зрения расходования памяти). Действительно, для вычислений в некий момент времени необходимы данные только за предыдущий, что же происходило ранее, нас не интересует - с этим мы уже справились. Значит, достаточно хранить только 2 квадратные матрицы размером 31, - одна несет данные в предыдущий момент времени, а вторая вычисляется для текущего с использованием первой матрицы. После окончания расчета данные первой уже не нужны, ей присваиваем значение второй матрицы, увеличиваем счетчик времени и т.д. Ясно, что такую идею можно реализовать только итеративно.

for z := 1 to k do
  begin
   Way2 := Way1;
   for i := -16 to 16 do
    for j := -16 to 16 do
	begin
		s := 0;
		if i <> -16 then s := s + Way2[i - 1, j];
		if i <> 16 then  s := s + Way2[i + 1, j];
		if j <> -16 then s := s + Way2[i, j - 1];
		if j <> 16 then  s := s + Way2[i, j + 1];
		Way1[i, j] := s
	end
  end;

Интересно, что итеративное решение в некоторых случаях работает несколько дольше рекурсивного. Это становится понятным, если учесть, что в итеративной форме мы подсчитываем количества всевозможных маршрутов, а в рекурсивном делаем только то, что нас просят.

Источники и прецеденты использования

веб-сайт
предмет информатика
Название Дидактические материалы по математике и информатике
URL http://comp-science.narod.ru
занятие
Номер 2
Название Динамическое программирование
Автор Е.В.Брызгалов
задача
Номер 3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .