Мячик на лесенке

Пусть мячик находится на некоторой ступеньке с номером X. Тогда он может спрыгнуть на ступеньки с номерами X - 1, X - 2 и X - 3. Если мы введем функцию F(X), которая определяет число маршрутов со ступеньки X до земли, то F(X) = F(X – 1) + F(X – 2) + F(X – 3). Остается просчитать вручную граничные значения: F(1) = 1, F(2) = 2 (очевидно), F(3) = 4 (3–2–1–0, 3–2–0, 3-1–0, 3–0). Все остальное уже сделано в предыдущей задаче. Чтобы не загромождать функцию, можно присваивания граничных значений сделать заранее, тогда отсечение произойдет автоматически:

Function F(X : integer) : longint;

begin

if D[X] = 0 then D[X] := F(x-1) + F(x-2) + F(x-3);

{для X = 1..3, D[X] > 0 изначально}

F := D[X]

end;

Написание итеративной формы также труда не представляет.

Робот В исследовательской лаборатории фирмы 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(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). Это становится понятным, если учесть, что в итеративной форме мы подсчитываем количества всевозможных маршрутов, а в рекурсивном делаем только то, что нас просят.

Черепашка На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она может переползать только в клетку справа или снизу и хочет, чтобы сумма всех чисел, оказавшихся у нее на пути, была бы максимальной. Определить эту сумму. Формат входных данных Первая строка — N — размер доски. Далее следует N строк, каждая из которых содержит N целых чисел, представляющие доску. Формат выходных данных Одно число — максимальная сумма.

[посмотреть подсказку]