四维博客-ʩ

四维博客-ʩ

一直被超越,从未被模仿。

题解 P1057 【传球游戏】

posted on 2017-12-24 11:15:57 | under 题解 |

原题

该题有多种算法,此处贴上Pascal代码,以及一些说明。

深度优先搜索:
var
  n,m,tot:longint;
procedure try(p{position,位置},t{times,次数}:longint);
var
  pp{新位置},tt{新次数}:longint;
begin
  if t=m then
    if p=1 then begin inc(tot); exit; end
           else exit;
  pp:=p-1;
  if pp=0 then pp:=n;
  tt:=t+1;
  try(pp,tt); //本行与前3行的作用是:向左边的人继续搜索。
  pp:=p+1;
  if pp=n then pp:=0;
  tt:=t+1;
  try(pp,tt); //本行与前3行的作用是:向右边的人继续搜索。
end;
begin
  readln(n,m);
  try(1,0);
  writeln(tot);
end.
递归算法:
var
  n,m:longint;
function try(p{position,位置},t{times,次数}:longint):longint;
begin
  if t=0 then
    if p=1 then exit(1)
           else exit(0);
  if p=1 then try:=try(n,t-1)+try(2,t-1)
         else if p=n then try:=try(n-1,t-1)+try(1,t-1)
                     else try:=try(p-1,t-1)+try(p+1,t-1);
end;
begin
  readln(n,m);
  writeln(try(1,m))
end.

以上两种算法并不能得满分,因为会搜索很长时间。

而用递推算法可以用空间代替时间

递推算法:
var
  n,m,p{position,位置},t{times,次数}:longint;
  f:array[0..30,0..30]of longint;
begin
  readln(n,m);
  for p:=0 to n do
    for t:=0 to m do
      f[p,t]:=0;
  f[1,0]:=1; //本行与前3行都是初始化递推边界。
  for t:=1 to m do
  begin
    f[1,t]:=f[n,t-1]+f[2,t-1];
    for p:=2 to n-1 do
      f[p,t]:=f[p-1,t-1]+f[p+1,t-1];
    f[n,t]:=f[n-1,t-1]+f[1,t-1];
  end;
  writeln(f[1,m]);
end.