跳馬問題:
如圖,在半張中國象棋的棋盤上(8X4),一只馬從左下角跳到右上角,只允許往右跳,不允許往左跳,問能有多少種跳的方案。
分析:此題可以采取遞歸的方法。站在固定的一個點上,最多可以有4個方向可以跳,設所在點坐標為x,y,則,dx=(1,2,2,1),dy=(2,1,-1,-2)(如圖)。遞歸的邊界是到達目標坐標點(8,4)。
Code
1//跳馬01
2program tiaoma01;
3const
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);
7var
8 num:integer; //可以跳的方案數
9
10procedure jump(x,y:integer);
11var k,x1,y1:integer;
12 t1,t2,t3:boolean;
13begin
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;
25end;
26
27begin
28 num:=0;
29 jump(0,0);
30 writeln(num);
31 readln;
32end.
33
摘自:crcr的專欄