完善程序训练

1、专题训练1、【问题描述】 集合A中的元素有以下特征： (1)数1是A中的元素； (2)如果X是A中的元素，则2X+1，3X+1也是A中的元素； (3)除了条件（1），（2）以外的所有元素均不是A中的元素； 给定数N，请求出集合中的第N个元素(元素按由小到大排列)。 例如 N=5， A（5）=9 5个元素分别是1、3、4、7、9 var n,Long,x:longint;function init(x:longint):boolean; begin if x=1 then init:=true else if( (x-1)mod 2=0)and( init(x-1)div 2) or _then

2、 init:=true else_ ; end;begin readln(n); x:=0; Long:=0; while Long<n do begin x:=_ ; if init(x) then _ ; end; writeln(_ );end.2、求N个数中的第K小的数。程序利用快排（递归、分治算法），当找到第N个小的数时候就停止。样例：输入：5 N 5 6 4 1 8 N个数 2 第2小的数 输出：4 第2小的数是4var i,j,k,n:integer; a:array1.100 of integer; procedure search(b,e:integer); var i

3、,m,t:integer; begin if b=e then _; i:=b; j:=e; m:=ak; repeat while _do inc(i); while _ do dec(j); if _ then begin t:=ai;ai:=aj;aj:=t end; until i>=j; if i=k then exit; if i>k then _else _; end; begin readln(n); for i:=1 to n do read(ai); readln(k); search(1,n); writeln(ak); end.3、根据二叉树的前序遍历和中序

4、遍历，求出树的后序遍历。样例输入：abdec （前序） 输出：debca（后序）dbeac （中序）var s1, s2 : string;procedure try(L1, r1, L2, r2 : integer); var m : integer; begin m := pos(s1L1, s2); if m >L2 then try(_); if m < r2 then try(_); write(s1L1) end;begin readln(s1); readln(s2); try(1, length(s1), 1, length(s2);end.4、（选排列）下面程序的

5、功能是利用递归方法生成从1到n(n<10)的n个数中取k(1<=k<=n)个数的全部可能的排列（不一定按升序输出）。例如，当n=3，k=2时，应该输出（每行输出5个排列）： 12 13 21 23 32 31 程序： Var i,n,k:integer; a:array1.10 of integer; count:longint; Procedure perm2(j:integer); var i,p,t:integer; begin if then begin for i:=k to n do begin inc(count); t:=ak; ak:=ai; ai:=t;

6、for do write(ap:1); write(' '); t:=ak;ak:=ai;ai:=t; if (count mod 5=0) then writeln; end; exit; end; for i:=j to n do begin t:=aj;aj:=ai;ai:=t; ; t:=aj; ; end end; begin writeln('Entry n,k (k<=n):'); read(n,k); count:=0; for i:=1 to n do ai:=i; ; end.5、（大整数开方）输入一个正整数n（1n10100），试用二

7、分法计算它的平方根的整数部分。NOIP2011题Const size = 200;type hugeint = record len : integer; num : array1.size of integer;end; /len表示大整数的位数;num1表示个位、num2表示十位,以此类推var s : string; i : integer; target, left, middle, right : hugeint;function times(a, b : hugeint) : hugeint; / 计算大整数 a 和 b 的乘积var i, j : integer; ans : h

8、ugeint; begin fillchar(ans, sizeof(ans), 0); for i := 1 to a.len do for j := 1 to b.len do := ans.numi + j - 1 + a.numi * b.numj; for i := 1 to a.len + b.len do begin ans.numi + 1 := ans.numi + 1 + ans.numi div 10; ; if ans.numa.len + b.len > 0 then ans.len := a.len + b.len else ans.len := a.len

9、+ b.len - 1; end; times := ans; end;function add(a, b : hugeint) : hugeint; / 计算大整数 a 和 b 的和var i : integer; ans : hugeint; begin fillchar(ans.num, sizeof(ans.num), 0); if a.len > b.len then ans.len := a.len else ans.len := b.len; for i := 1 to ans.len do begin ans.numi := ; ans.numi + 1 := ans.n

10、umi + 1 + ans.numi div 10; ans.numi := ans.numi mod 10; end; if ans.numans.len + 1 > 0 then inc(ans.len); add := ans;end;function average(a, b : hugeint) : hugeint; / 计算大整数 a 和 b 的平均数的整数部分var i : integer; ans : hugeint; begin ans := add(a, b); for i := ans.len downto 2 do begin ans.numi - 1 := an

11、s.numi - 1 + ( ) * 10; ans.numi := ans.numi div 2; end; ans.num1 := ans.num1 div 2;if ans.numans.len = 0 then dec(ans.len); average := ans; end;function plustwo(a : hugeint) : hugeint; / 计算大整数 a 加 2 后的结果var i : integer; ans : hugeint; begin ans := a; ans.num1 := ans.num1 + 2; i := 1; while (i <=

12、ans.len) and (ans.numi >= 10) do begin ans.numi + 1 := ans.numi + 1 + ans.numi div 10; ans.numi := ans.numi mod 10; inc(i); end;if ans.numans.len + 1 > 0 then ; plustwo := ans; end;function over(a, b : hugeint) : boolean; / 若大整数 a > b 则返回 1, 否则返回 0var i : integer; begin if ( ) then begin ov

13、er := false; exit; end; if a.len > b.len then begin over := true; exit; end; for i := a.len downto 1 do begin if a.numi < b.numi then begin over := false; exit; end; if a.numi > b.numi then begin over := true; exit; end; end; over := false; end;begin readln(s); fillchar(target.num, sizeof(t

14、arget.num), 0); target.len := length(s); for i := 1 to target.len do target.numi := ord(starget.len - i + 1) - ; fillchar(left.num, sizeof(left.num), 0); left.len := 1; left.num1 := 1; right := target; repeat middle := average(left, right); if over( ) then right := middle else left := middle; until

15、over(plustwo(left), right); for i := left.len downto 1 do write(left.numi); writeln;end. 6、（过河问题NOIP2010）在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸。在这伸手不见五指的黑夜里，过桥时必须借助灯光来照明，不幸的是，他们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则将会坍塌。每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入n(2<=n<100

16、)和这n个人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。例如，有3个人甲、乙、丙，他们单独过桥的时间分别为1、2、4，则总共最少需要的时间为7。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然后甲、丙再一起过桥到河的左岸，总时间为2+1+47。const size=100; infinity=10000; left=true; right=false; left_to_right=true; right_to_left=false;var n,i:integer; time:array 1.size of integer; pos:array

17、 1.size of boolean;function max(a,b:integer):integer;begin if a>b thenmax:=a elsemax:=b;end;function go(stage:boolean):integer;var I,j,num,tmp,ans:integer;begin if (stage=right_to_lefft) thenbegin num:=0; ans:=0; for i:=1 to n do if posi=right then begin inc(num); if timei>ans then ans:=timei;

18、 end; if then begin go:=ans; exit; end; ans:=infinity; for i:=1 to n-1 do if posi=right then for j:=i+1 to n do if posj=right then begin posi:=left; posj:=left; tmp:=max(timei,timej)+ ; if tmp<ans then ans:=tmp; posi:=right; posj:=right; end; go:=ans; else if (stage=left_to_right) then begin ans:

19、=infinity; for i:=1 to n do if then begin posi:=right; tmp:= ; if tmp<ans then ans:=tmp; ; end; go:=ans;endelse go:=0; end;begin readln(n); for i:=1 to n dobegin read(timei); posi:=right;end; writeln(go(right_to_left);end.  7、2012年奥运会在英国伦敦举行，伦敦新建或改造了许多大型体育馆。为了使观众能够方便地在体育馆之间通行，伦敦政府决定在体育馆之间建一些

20、天桥，以使得其中任意两个体育馆之间都有直接和间接的天桥相连。当然，从经济的角度出发，政府希望所有的修天桥费用之和最小，其中修天桥费用与天桥的长度成正比，所以希望建设的天桥总长度尽量小。输入一个整数n（n100），表示有n个体育馆，然后输入n组x、y，xi、yi分别表示第i个体育馆的坐标。输出只有一个实数，表示天桥的最短长度。var select:array1.100 of boolean; g:array1.100,1.100 of real; x,y,len:array1.100 of real; n:integer; ans:real;function dist(i,j:integer):

21、real;begin dist:=sqrt(sqr(xi-xj)+sqr(yi-yj);end;procedure init;var i,j:integer;begin readln(n); for i:=1 to n do read(xi,yi); for i:=1 to n do for j:=1 to n do _end;procedure main;var i,j,k:integer;min:real;begin for i:=1 to n do leni:=g1,i; for k:=1 to n do begin min:=1e20; for j:=1 to n do if _ th

22、en begin min:=leni; _ end; _ selecti:=true; for j:=1 to n do if not selectj and _ then lenj:=gi,j; end;end;begin init; main; writeln(ans:0:2);end.8、简单的背包问题。设有一个背包，可以放入的重量为S。现有n件物品，重量分别为w1,w2,，wn,均为正整数，从n 件物品中挑选若干件，使得放入背包的重量之和正好为s。样例：输入：5 /共5件物品10 /背包重量是101 4 4 5 7 /5件物品的重量输出：data:1 weight:1data:3 we

23、ight:4data:4 weight:5程序如下：Program lianxi_5 ; const m=10 ; var w : array1.m of integer ; x,y :integer ; f : boolean ; function sng( x:integer ) : integer ; begin sng:=0 ; if x>0 then sng:=1 ; if x<0 then sng:=-1 ; end; Function beibao( s, n : integer ) : boolean ; var k : integer ; begin k:=sng

24、(s-wn) ; case k of 0: begin writeln( data:,n:5, weight: , wn:5) ; beinao:= true ; end; 1: begin if n>1 then if _(2)_ then begin writeln( data:,n:5, weight: , wn:5) ; _(3)_ ; end else beibao:=_(4)_ ; else beibao:=false ; end; -1 : if n>1 then beibao:=_(5)_ else beibao:=false ; end ; case end; b

25、egin write( input data : ); repeat readln(y) ; until y<=m ; write(total weight = ) ;readln( x) ; for I:=1 to y do read(w I ) ; f:=_(1)_; if not(f) then writeln( not find ) ; end.9、对于任意输入的正整数n(n<=50000)，请编程求出具有n个不同因子的最小正整数m。例如：n=4，则m=6，因为6有4个不同整数因子1，2，3，6；而且是最小的有4个因子的整数。由于具有n个不同因子的正整数一定是形如p1i1p

26、2i2pkik，且n=(i1+1)*(i2+1)*(ik+1)，要让p1i1p2i2pkik最小，显然p1p2pk要等于前k个质数。同时i1>=i2>=>=ik。程序中递归过程resolve用来求出n的所有不同的因子分解式，如n=12时，其所有不同的因子分解式有：12、6*2、4*3、3*2*2四种，然后比较相应的数211、25*3、23*32、22*3*5的大小得到最小值为22*3*5=60，由于m的值可能很大，所以比较两数大小时转化为自然对数后再比较，最终结果使用了改良的高精度运算。const maxn=50000; p:array 1.16 of longint=(2,

27、3,5,7,11,13,17,19,23,29,31,37,41,43,47,53);var h,i,j,k,l,n,t,total:longint; mins,s:real; f,c,minc:array 1.500 of longint; m:array 0.20000 of longint;procedure resolve(dep,m,r:longint);var i:longint;begin if r=1 then begin s:=0; for i:=1 to dep-1 do s:=s+ ; if s<mins then begin mins:=s; l:=dep-1;

28、minc:=c end end else begin for i:=m to total do if then begin cdep:=fi; resolve(dep+1, ) end endend;procedure mul(t:longint);begin for k:=0 to h do mk:=mk*t; for k:=0 to h do begin mk+1:=mk+1+mk div 10; mk:=mk mod 10 end; while do begin mh+2:=mh+1 div 10; mh+1:=mh+1 mod 10; h:=h+1 end;end;begin read

29、ln(n); total:=0; for i:=n downto 2 do if n mod i=0 then begin total:=total+1; ftotal:=i end; mins:=maxlongint; resolve(1,1,n); for i:=1 to 15000 do mi:=0; m0:=1; h:=0; t:=1; for i:=1 to l do for j:=1 to minci-1 do if pi<200000000 div t then t:=t*pi else begin mul(t); end; mul(t); for i:=h downto

30、0 do write(mi); writeln;end.10、火车站为了很好地调度车厢，一般在轨道中间设计一个转轨网络的栈。如图，其中右边轨道为输入端，左边轨道为输出端。车厢按顺序经过转轨网络的栈后，在输出端可以形成不同顺序的车厢。请你设计一个程序，当输入端到了n(n<=13)节车厢，在输出端会形成多少种不同的车厢顺序。如输入：3节车厢，输出：形成不同顺序车厢的数目是5。111111INOUT程序如下：program train; type tt=array1.100 of char; var inp,t:tt; k,n:integer;num:longint; procedure push(out,s:tt;it,ot,st:integer); var k:integer; c:tt; begin if it>0 then begin c:=s; cst+1:=inpit; ; end; if st>0 then begin c:=out; ; push(c,s,it,ot+1,st-1) end; if then num:=n