Начало
Соревнования
Разбор задачи D. Пизанская башня
Тема: динамическое программированиеСложность: ниже среднего
1 способ: вывод рекуррентной формулы
Вручную для `n` от 1 до 5 находим минимальное количество перекладываний.
| n | 1 | 2 | 3 | 4 | 5 |
| кол-во ходов `m` | 1 | 3 | 5 | 9 | 15 |
Далее, видим, что зависимость можно описать формулой `m_i\ =\ m_{i-2}+m_{i-1}+1`.
var n,i:integer;
m:array[1..40]of int64;
begin
read(n);
m[1]:=1;
m[2]:=3;
for i:=1 to n do
m[i]:=m[i-2]+m[i-1]+1;
writeln(m[n]);
end.
2 способ: запоминающая функция
Чтобы переложить `n` дисков со столбика `a` на столбик `b`, нужно сначала переложить `n-1` диск на столбик `6-a-b`, затем переложить `n`-й диск на столбик `b`, затем все диски со столбика `6-a-b` на столбик `b`. Чтобы повторно не вычислять результат функции количества перекладываний для некоторого набора аргументов (`n`, `a`, `b`), функция должна запоминать в массиве результаты предыдущих вычислений. Размерность массива для запоминания должна совпадать с количеством аргументов функции и областью определения аргументов.
var n:integer;
_nmoves:array[1..40,1..3,1..3] of int64; { для запоминания результата }
function nmoves(n,a,b:integer):int64;
begin
if _nmoves[n,a,b]=0 then
if (n=1) or (a=2) then
_nmoves[n,a,b]:=1
else
_nmoves[n,a,b]:=nmoves(n-1,a,6-a-b)+1+nmoves(n-1,6-a-b,b);
nmoves:=_nmoves[n,a,b]
end;
begin
read(n);
writeln(nmoves(n,1,3));
end.
