Подразделы

Другие разделы

Дата и время

14/03/2025 17:26:07

Авторизация

Зарегистрироваться
Восстановить пароль

Разбор задачи 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.

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Разбор задачи D. Пизанская башня