跳马问题: 如图,在半张中国象棋的棋盘上(8X4),一只马从左下角跳到右上角,只允许往右跳,不允许往左跳,问能有多少种跳的方案。
分析:此题可以采取递归的方法。站在固定的一个点上,最多可以有4个方向可以跳,设所在点坐标为x,y,则,dx=(1,2,2,1),dy=(2,1,-1,-2)(如图)。递归的边界是到达目标坐标点(8,4)。
Code 1 //跳马01 2 program tiaoma01; 3 const 4 mbx=8; mby=4; //目标点所在的坐标 5 dx:array[1..4]of integer=(1,2,2,1); //可以移动的坐标位移 6 dy:array[1..4]of integer=(2,1,-1,-2); 7 var 8 num:integer; //可以跳的方案数 9 10 procedure jump(x,y:integer); 11 var k,x1,y1:integer; 12 t1,t2,t3:boolean; 13 begin 14 for k:=1 to 4 do 15 begin 16 x1:=x+dx[k]; 17 y1:=y+dy[k]; 18 t1:=(x1>=0)and(x1<=mbx); 19 t2:=(y1>=0)and(y1<=mby); 20 t3:=(x1=mbx)and(y1=mby); 21 if(t1 and t2) then 22 if t3 then inc(num) 23 else jump(x1,y1); //递归 24 end; 25 end; 26 27 begin 28 num:=0; 29 jump(0,0); 30 writeln(num); 31 readln; 32 end. 33
|