2.3 典型例题

　　例3 梵塔问题

　　如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子

　　从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上

　　不能出现大盘压小盘.找出移动次数最小的方案.

　　程序如下:

　　program fanta;

　　var

　　n:integer;

　　procedure move(n,a,b,c:integer);

　　begin

　　if n=1 then writeln(a,'--->',c)

　　else begin

　　move(n-1,a,c,b);

　　writeln(a,'--->',c);

　　move(n-1,b,a,c);

　　end;

　　end;

　　begin

　　write('Enter n=');

　　read(n);

　　move(n,1,2,3);

　　end.

　　例4 快速排序

　　快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.

　　程序如下:

　　program kspv;

　　const n=7;

　　type

　　arr=array[1..n] of integer;

　　var

　　a:arr;

　　i:integer;

　　procedure quicksort(var b:arr; s,t:integer);

　　var i,j,x,t1:integer;

　　begin

　　i:=s;j:=t;x:=b[i];

　　repeat

　　while (b[j]>=x) and (j>i) do j:=j-1;

　　if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;

　　while (b[i]<=x) and (i<j) do i:=i+1;

　　if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end

　　until i=j;

　　b[i]:=x;

　　i:=i+1;j:=j-1;

　　if s<j then quicksort(b,s,j);

　　if i<t then quicksort(b,i,t);

　　end;

　　begin

　　write('input data:');

　　for i:=1 to n do read(a[i]);

　　writeln;

　　quicksort(a,1,n);

　　write('output data:');

　　for i:=1 to n do write(a[i]:6);

　　writeln;

　　end.

　　练习:

　　1.计算ackerman函数值:

　　n+1                  m=0

　　ack(m,n)={ ack(m-1,1)           m<>0 ,n=0

　　ack(m-1,ack(m,n-1))  m<>0,n<>0

　　求ack(5,4)

　　关于合肥市青少年信息学竞赛更多的信息，请关注合肥奥数网“青少年信息学竞赛”频道。　　

　　相关阅读

　　信息学竞赛常用算法与策略：算法的概念

　　青少年信息学竞赛Pascal语言：程序调试（十一）

　　青少年信息学竞赛Pascal语言：指针（十）

　　信息学竞赛Pascal语言：记录与文件类型（九）

　　更多精彩内容推荐>>