题解 P1057 【传球游戏】

0__o

2017-12-24 11:15:57

Solution

[原题](https://www.luogu.org/problemnew/show/1057) ###该题有多种算法,此处贴上Pascal代码,以及一些说明。 ##### 深度优先搜索: ```cpp 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. ``` ##### 递归算法: ```cpp 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. ``` 以上两种算法并不能得满分,因为会搜索很长时间。 而用递推算法可以**用空间代替时间**。 ##### 递推算法: ```cpp 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. ```