В этой задаче мы впервые сталкиваемся с функцией трех переменных: F(X, Y, Z) - показывает количество маршрутов длины Z, приводящих в клетку (X, Y). К сожалению, такая структура данных как
Array [-16..16, -16..16, 0..16] of LongInt;в память не помещается. Забудем пока об этой трудности и напишем рекурсивную часть. Для ответа на поставленный в задаче вопрос можно посчитать число маршрутов длины Z - 1 в четыре клетки, смежных с заданной, а результаты сложить, не забывая случаи клеток на границе. Граничными условиями будут F(X, Y, 0) = 0, если хотя бы одна из координат X или Y отлична от нуля, и F(0, 0, 0) = 1. Действительно, если робота не двигать, то он может оказаться только в начале координат. Теперь вспомним о проблеме хранения данных. Выхода существует два. Первый, чисто программистский, заключается в разбиении большой структуры на несколько меньших и размещении их в динамической памяти. Сделать это можно, например, так
Type T1 = array[-16..16, -16..16] of LongInt; T2 = array [0..16] of ^T1; Var D : T2;
Тогда наша функция будет записана так (предполагается, что память выделена, граничные условия введены, а для не вычисленных значений функции в массиве хранится "-1"):
Function F(X, Y, Z : integer) : longint; var s : longint; begin if D[Z]^[X, Y] = -1 then begin s := 0; if X <> -16 then s := s + F(X - 1, Y, Z - 1); if X <> 16 then s := s + F(X + 1, Y, Z - 1); if Y <> -16 then s := s + F(X, Y - 1, Z - 1); if Y <> 16 then s := s + F(X, Y + 1, Z - 1); D[Z]^[X, Y] := s end; F := D[Z]^[X, Y] end;
Это, конечно, решение, но оно далеко не оптимальное (с точки зрения расходования памяти). Действительно, для вычислений в некий момент времени необходимы данные только за предыдущий, что же происходило ранее, нас не интересует - с этим мы уже справились. Значит, достаточно хранить только 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;
Интересно, что итеративное решение на некоторых тестах работает несколько дольше рекурсивного (правда это заметно только на слабых машинах, примерно до 486SX). Это становится понятным, если учесть, что в итеративной форме мы подсчитываем количества всевозможных маршрутов, а в рекурсивном делаем только то, что нас просят.