pascal体会.ppt

1、辅导信息学奥赛的几点体会,精心备课，突破疑点难点，追求直观高效。,分析：将十进数转换成二进制数,一般采用除二取余法。如果用一个数组b来存放二进制数,可以依次把所得的余数存入b0、b1、bn,最后按bn、bn-1、b1、b0的顺序输出这些余数,就得到了所求的二进制数。,1、读入一个十进制自然数，将其转换成二进制数后输出。,例如：,余数：,0,输出结果为：11001,0,1,0,1,1,0,1,2,3,4,5,6,var i,j,n:longint; b:array 0.31 of 0.1; begin readln(n); write(n,=(); i:=0; while（ ）do begin

2、（ ）; i:=i+1; 指定下一个余数的存放位置 n:=n div 2 产生的商将作为新的被除数 end; for j:=（ ）do write(bj); writeln()2) end.,n0,bi:=n mod 2,i-1 downto 0,后进先出,Str1=3210 Str2=98765,a,0 1 2 3,b,5 6 7 8 9,5,7,9,1,1,0,1,对位 相加 进位,2、高精度加法,var str1,str2:string; a,b:array1.100 of 0.9; l1,l2,i,j,k:integer; begin readln(str1); readln(str2

3、); l1:=length(str1); l2:=length(str2); if l1l2 then j:=l1 else j:=l2; k:=0; for i:=l1 downto 1 do begin k:=k+1; ak:=ord(str1i)-ord(0); end;,k:=0; for i:=l2 downto 1 do begin k:=k+1; bk:=ord(str2i)-ord(0); end; for i:=1 to j do begin ai:=ai+bi; if ai=10 then begin ai:=（ ）; ai+1:=（ ）; end; end; if ai+

4、1=0 then j:=j-1; for i:=j+1 downto 1 do write(ai); writeln; end.,处理进位,从低位到高位依次将各位数相加,用字符串形式输入加数和被加数,ai-10,ai+1+1,分析：类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进行乘法运算时，必须进行错位相加。,8 4 8 2 3,2 5 4 4 1 6 9 6,1 9 5 0 4,3*8+0+0=24 c1=4,3*4+2+0=14 c2=4,3*8+1+0=25 c3=5,c4=2,2*8+0+4=20 c2=0,2*4+2+5=15 c3=5,2*8+1+2=19

5、 c4=9,c5=1,3、高精度乘法,var s1,s2:string; a,b:array1.100of 0.9; c:array1.200of 0.9; la,lb,lc, i,j,x,y,z,w:integer; begin readln(s1); readln(s2); la:=length(s1); lb:=length(s2); lc:=la+lb; 积的位数为la+lb-1或者la+lb； for i:=la downto 1 do ala-i+1:=ord(s1i)-ord(0); for i:=lb downto 1 do blb-i+1:=ord(s2i)-ord(0);

6、for i:=lc downto 1 do ci:=0; for i:=1 to la do begin x:=0; 上次乘积进位初始化 for j:=1 to lb do 对乘数的每一位进行处理 begin x:=ai*bj+x div 10+ci+j-1; ci+j-1:= x mod 10; end; ci+j:= x div 10; end; while (clc=0) and (lc1) do lc:=lc-1; for i:=lc downto 1 do write(ci); writeln; end.,var yh:array1.5,1.5of integer; i,j:inte

7、ger; begin yh1,1:=1; for i:=2 to 5 do begin yhi,1:=1;yhi,i:=1; for j:=2 to i-1 do yhi,j:=yhi-1,j-1 + yhi-1,j; end; for i:=1 to 5 do begin for j:=1 to i do write(yhi,j:3); writeln; end; end.,1,1,1,1,1,2,1,1,3,3,1,1,4,6,4,4、阅读程序，写出运行结果。,5、2001年普及组、提高组初赛试题（穷举法） 在A、B两个城市之间设有N个路站(如下图中的S1，且N100)，城市与路站之间、路

8、站和路站之间各有若干条路段(各路段数=20，且每条路段上的距离均为一个整数)。 A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，最后到达B。通路上路段距离之和称为通路距离(最大距离=1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。 例如：下图所示是当N=1时的情况：,从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。 数据结构： N记录A，B间路站的个数；数组Di，0记录第i-1个到第i个路站间路段的个数; Di，1，Di，2，记录每个路段的距离;数组G记录可取到的距离。,0 1 1

9、 1 8+4+3=15 g15=1,0 1 1 2 8+4+4=16 g16=1,0 1 2 1 8+5+3=16 g16=1,0 1 2 2 8+5+4=17 g17=1,0 1 3 1 8+7+3=18 g18=1,0 1 3 2 8+7+4=19 g19=1,0 2 1 1 6+4+3=13 g13=1,0 2 1 2 6+4+4=14 g14=1,0 2 2 1 6+5+3=14 g14=1,0 2 2 2 6+5+4=15 g15=1,0 2 3 1 6+7+3=16 g16=1,0 2 3 2 6+7+4=17 g17=1,b0 b1 b2 b3,1 1 1 1 穷举结束,D1，0

10、=2, D1，1=8, D1，2=6 D2，0=3, D2，1=4, D2，2=5， D2，3=7 D3，0=2, D3，1=3, D3，2=4,var i,j,n,s:integer; b:array0.100 of integer; d:array0.100,0.20 of integer; g:array0.1000 of 0.1;begin readln(n); for i:=1 to n+1 do begin readln(di,0); for j:=1 to di,0 do read(di,j); end; d0,0:=1; for i:=1 to n+1 do bi:=1; b0

11、:=0; for i:=1 to 1000 do gi:=0;,while( )do begin s:=0; for i:=1 to n+1 do s:=( ); gs:=1; j:=n+1; while( )do j:=j-1; bj:=bj+1; for i:=j+1 to n+1 do bi:=1; end; s:=0; for i:=1 to 1000 do( ); writeln(s); readln;end.,b01,s+d i , bi ,bj=dj,0,s:=s+gi,穷举用,循环开关,求当前通路的距离,统计不同的通路条数,作记录,产生一种新的方案,要求在国际象棋棋盘上放置八个

12、皇后，使她们不能互相攻击，即任何两个皇后不能处在同一行、同一列、同一条线上。请找出所有的摆法。,分析： 如果我们把8*8的棋盘看成是一个平面直角坐标系，那么任意两个皇后在平面上的坐标应同时满足以下三个条件： 两个皇后的横坐标不相等。 两个皇后的纵坐标不相等。 两个皇后的横坐标之差的绝对值不等于纵坐标之差的绝对值。 我们用数组xi来描述八个皇后在棋盘上的状态， xi =j表示在第i行的第j列放置了一个皇后。,IK,当IK时，XI XK,当IK时，|I-K|XI-XK|,6、八皇后问题（回溯法）,const n=8;var i,j,k:integer;x:array1.n of integer;f

13、unction place(k:integer):boolean; var i:integer; begin place:=true; for i:=1 to k-1 do if ( ) or (abs(xi-xk)=abs(i-k) then( ) ; end;procedure print; var i:integer; begin for i:=1 to n do write(xi:4); writeln; end;,procedure try(k:integer); var i:integer; begin if( )then begin print; exit end; for i:

14、= 1 to n do begin ( ); if( )then try(k+1); end; end ;begin try(1);end.,xi=xk,k=n+1,place:=false,xk:=i,place(k),如下图所示为一个数字三角形，请编程计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。（只要求输出总和） 规定： 一步可沿左斜线向下或右斜线向下走； 图形行数小于等于100； 三角形中的数字为0，1，99; 测试数据通过键盘逐行输入，如下图数据应以如下所示格式输入： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出：30,7、数字三角形（动态规划）

15、,逆推法: 按三角形的行划分阶段，若行数为n，则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的最大和，再依次求出第n-2阶段、第n-3阶段第1阶段(起始点)各决策点至第n行的最大和。 设fi,j为从第i阶段中的点j至第n行的最大的数字和； 则fn,j=an,j（1=j=n） fi,j= max ai,j+fi+1,j , ai,j+fi+1,j+1 （1=j=i） f1,1即为所求。,const maxn=100; var n,i,j:integer; a:array1.maxn,1.maxn of integer; f:array1.maxn,1.m

16、axn of integer; begin readln(n); for i:=1 to n do for j:=1 to i do read(ai,j); for i:=1 to n do fn,i:=an,i; for i:=n-1 downto 1 do for j:=1 to i do if fi+1,jfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j; writeln(f1,1); end.,阶段,状态,决策,状态转移方程,4,5,2,6,5,7,12,10,10,20,13,10,23,21,30,8、深度优先遍历,基

17、本思想： 第一步，从图中某个顶点V0出发，首先访问V0； 第二步，找出刚访问过的顶点Vi的第一个未被访问的邻接点，然后访问该顶点。以该顶点为新顶点，重复本步骤，直到当前的顶点没有未被访问的邻接点为止； 第三步，返回前一个访问过的且仍有未被访问的邻接点的顶点，找出并访问该顶点的下一个未被访问的邻接点，然后执行第二步步骤； 若此时图中尚有顶点未访问，则另选图中一个未被访问的顶点作起始点，重复第一步至第三步，直至图中所有顶点都被访问到为止。,1,2,3,7,5,4,6,8,9,该图的深度优先搜索的输出序列为： ABCFEGDHI,以F作为起始点，该图的深度优先搜索的输出序列为： FCBADGEHI

18、或 FCBADGHIE 或 FCBAEGDHI 或 FCBAEGHID 或 FCBEADGHI 或 FCBEGHIDA 或 FCBEGDAHI,任取一个顶点加入生成树，然后对那些一个端点在生成树中，而另一个端点不在生成树中的边进行排序，取权值最小的边，将它和另一个端点加进生成树中。重复上述步骤直到所有顶点都进入了生成树为止。,9、构造最小生成树的prim算法,1,2,16,3,5,第一步，U1，VU2,3,4,5,6，TE ,第二步，U1,2，VU3,4,5,6，TE(1,2),第三步，U1,2,3，VU4,5,6，TE(1,2)，(2,3),第四步，U1,2,3,4，VU5,6，TE(1,2

19、)，(2,3)，(2,4),第五步，U1,2,3,4,6，VU5，TE(1,2)，(2,3)，(2,4)，(2,6),第六步，U1,2,3,4,6,5，VU ，TE(1,2)，(2,3)，(2,4)，(2,6)，(4,5),4,6,6,11,5,18,说明： 最小生成树也不是唯一的,所谓后缀表达式是指这样的一种表达式：式中不再引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行，不再考虑运算符的优先规则。例如5*（7-3）+9对应的后缀表达式为5 7 3 -*9 +，其中每个操作数后都有一个空格。 输入：后缀表达式a 输出：表达式的值,10、计算后缀表达式的值,

20、分析： 设后缀表达式串为a，操作数、中间结果和最终结果都存放在栈S中，S的元素类型为实型。 计算过程如下：由左向右处理a中的每一个字符。若遇到一个操作数，就送入栈S中保存；遇到一个操作符，就从栈中取出栈顶的两个操作数进行计算，然后将计算结果重新压入栈中。依次类推，直至表达式最后一个操作符处理完毕，这时的栈顶元素值即为最终计算结果。,表达式：5 7 3 - * 9 +,top,表达式：5 7 3 - * 9 +,top,5,表达式：5 7 3 - * 9 +,top,5,7,表达式：5 7 3 - * 9 +,top,5,7,3,表达式：5 7 3 - * 9 +,top,5,7,3,表达式：5

21、 7 3 - * 9 +,top,5,7,3,-,=4,表达式：5 7 3 - * 9 +,top,5,4,表达式：5 7 3 - * 9 +,top,5,4,表达式：5 7 3 - * 9 +,top,5,4,*,=20,表达式：5 7 3 - * 9 +,top,20,表达式：5 7 3 - * 9 +,top,20,9,表达式：5 7 3 - * 9 +,top,20,9,表达式：5 7 3 - * 9 +,top,20,9,+,=29,表达式：5 7 3 - * 9 +,top,29,type stack=record data:array1.100of real; top:0.100

22、; end; var s:stack; i:integer; x:real; a:string; ch:char; function pop (var s:stack):real; 出栈 begin pop:=s.datas.top; s.top:=s.top-1; end; procedure push (var s:stack;x:real); 入栈 begin s.top:=s.top+1; s.datas.top:=x; end; begin 主程序 readln(a); s.top:=0; 置空栈,i:=1; ch:=ai; while （ ）do begin case ch of

23、0.9: begin 取出操作数 x:=0; while（ ） do begin x:=x*10+ord(ch)-ord(0); i:=i+1; ch:=ai; end; end; + : x:=pop(s)+pop(s); - : begin x:=pop(s); x:=pop(s)-x; end; * : x:=pop(s)*pop(s); / : begin x:=pop(s); x:=pop(s)/x; end; end; （ ）; i:=i+1; ch:=ai; 继续扫描字符串a end; writeln( :0:0); end.,i=length(a),ch ,push(s,x),

24、pop(s),现有1g、2g、3g、5g、10g、20g的砝码各若干枚，问用这些砝码可以称出多少种不同的重量。（设砝码的总重不超过1000g，且砝码只能放在天平的一端） 输入：a1 a2 a3 a4 a5 a6 （表示1g砝码有a1个，2g砝码有a2个，20g砝码有a6个） 输出：total=n （ n表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况） 如输入：1 1 0 0 0 0 则输出：total=3（表示可以称出1g，2g，3g三种不同的重量）,由一个砝码也不取开始扩展结点，当扩展出的某一个结点所对应的质量数在前面已经出现过时，则不再从该结点扩展下去，并删掉该结点；如

25、此重复，直到没有结点可扩展为止。统计扩展的结点总数，就可得到可以称出的质量总数。,11、砝码称重：,const w:array1.6 of integer=(1,2,3,5,10,20);每种砝码的单位质量 maxweight=1000; 队列的最大长度 type tlist=array0.maxweight of record we:integer; 当前结点所对应砝码组合的总质量 sn: array1.6 of integer; 各砝码个数 end; var a:tlist; 队列 s: array1.6 of integer; 存放每种砝码的数量 b:array1.1000 of boo

26、lean; 标记某个质量是否可被称出 i,head,tail:integer; cw:integer; begin for i:=1 to 6 do read(si);readln; 读入每种砝码的数量 fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0);,1 2 2 0 0 0,331 332,23321,head:=0; tail:=0; 置队空 while（ ）do 还有结点可扩展,则执行循环体 begin for i:=1 to 6 do 试探每种砝码 if （ ）新组合可以得到 then begin cw:=ahead.we+wi; cw

27、为新组合的总质量 if（ ）then begin 入队 tail:=tail+1;（ ） bcw:=true;标记 atail.sn:=ahead.sn; （ ） end; end; （ ）; 出队 end; writeln(total=,tail); end.,head=tail,ahead.snisi,not bcw,atail.we:=cw;,inc(atail.sni),head:=head+1,多做老题，立足基本算法，引导一题多解。,穷举法、回溯法、动态规划,【问题描述】 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说

28、：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为： vj1*wj1+vj2*wj2+ +vjk*wjk 请你帮助金明设计一个满足要求的购物单。,开心的金明(2006年普及组复赛),【输

29、入文件】 输入文件happy.in 的第1行，为两个正整数，用一个空格隔开： N m（其中N（30000）表示总钱数，m（25）为希望购买物品的个数。） 从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数v p（其中v表示该物品的价格(v=10000)，p表示该物品的重要度(15)） 【输出文件】 输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（100000000）。 【输入样例】 1000 5 800 2 400 5 300 5 400 3 200 2 【输出样例】 3900,var v,p:array1.25

30、of integer; b:array0.25 of 0.1; n,m,i,j,max,s,yu,l:longint; begin readln(n,m); for i:=1 to m do readln(vi,pi); for i:=0 to m do bi:=0; while b0=0 do begin j:=m; while bj=1 do j:=j-1; bj:=1; for l:= j+1 to m do bl:=0;,s:=0; yu:=0; for i:=1 to m do if (bi=1) then begin yu:=yu+vi; s:=s+vi*pi; end; if (

31、yumax) then max:=s; end; writeln(max); end.,可以通过8个测试点,1、用穷举法解,2001年普及组、提高组初赛试题 在A、B两个城市之间设有N个路站(如下图中的S1，且N100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数=20，且每条路段上的距离均为一个整数)。 A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，最后到达B。通路上路段距离之和称为通路距离(最大距离=1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。 例如：下图所示是当N=1时的情况：,从A到B的通路条数为

32、6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。 数据结构： N记录A，B间路站的个数；数组Di，0记录第i-1个到第i个路站间路段的个数; Di，1，Di，2，记录每个路段的距离;数组G记录可取到的距离。,var i,j,n,s:integer; b:array0.100 of integer; d:array0.100,0.20 of integer; g:array0.1000 of 0.1;begin readln(n); for i:=1 to n+1 do begin readln(di,0); for j:=1 to di,0 do read(di,j);

33、end; d0,0:=1; for i:=1 to n+1 do bi:=1; b0:=0; for i:=1 to 1000 do gi:=0;,while( )do begin s:=0; for i:=1 to n+1 do s:=( ); gs:=1; j:=n+1; while( )do j:=j-1; bj:=bj+1; for i:=j+1 to n+1 do bi:=1; end; s:=0; for i:=1 to 1000 do( ); writeln(s); readln;end.,b01,s+d i , bi ,bj=dj,0,s:=s+gi,将2n个0和2n个1，排成

34、一圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的2n+1个二进制数都不相同。例如，当n=2时，即22个0和22个1排成如下一圈：,比如，从A位置开始，逆时针方向取三个数000，然后再从B位置上开始取三个数001，接着从C开始取三个数010，.可以得到000，001，010，101，011，111，110，100共8个二进制数且都不相同。 程序说明： 以n=4为例，即有16个0，16个1，数组a用以记录32个0，1的排法，数组b统计二进制数出现的可能性。,2000年提高组初赛试题,var a:array1.36 of 0.1;

35、 b:array0.31 of integer; i,j,k,s,p:integer;begin for i:=1 to 36 do ai:=0; for i:=28 to 32 do ai:=1; p:=1; a6:=1; for i:=1 to 32 do for j:=i to i+4 do write(aj); writeln end.,while ( p=1 ) do begin j:=27 while aj=1 do j:=j-1; ( ) for i:=j+1 to 27 do ( ) for i:=0 to 31 do bi:=0; for i:=1 to 32 do begi

36、n( )for k:=i to i+4 do s:=s*2+ak; ( )end; s:=0; for i:=0 to 31 do s:=s+bi; if ( ) then p:=0 end;,aj:=1,ai:=0,s:=0,bs:=1,s=32,将n个整数分成k组(kn,要求每组不能为空),显然这k个部分均可得到一个各自的和s1,s2,sk,定义整数P为: P=(S1-S2)2+(S1一S3)2+(S1-Sk)2+(s2-s3)2+(Sk-1-Sk)2 问题求解: 求出一种分法,使P为最小(若有多种方案仅记一种。 程序说明: 数组:a1,a2,.an存放原数 s1,s2,.,sk存放每个部

37、分的和 b1,b2,.,bn穷举用临时空间 d1,d2,.,dn存放最佳方案,2002年普及组初赛试题,var i,j,n,k : integer; a :array 1.100 of integer; b,d:array 0.100 of integer; s :array1.30 of integer; begin readln(n,k); for i:=1 to n do read(ai); for i:=0 to n do bi:=1; cmin:=1000000; while (b0=1) do begin for i:=1 to k do ( ); for i:=1 to n do

38、( ); sum:=0; for i:=1 to k-1 do for j:=( ) sum:=sum+(si-sj)*(si-sj);,if( )then begin cmin:=sum; for i:=1 to n do di:=bi; end; j:=n; while( )j:=j-1; bj:=bj+1; for i:=j+1 to n do( ) end; writeln(cmin); for i:=1 to n write(di:40); end.,si:=0,sbi:=sbi+ai,i+1 to k do,cminsum,bj=k,bi:=1,有n种基本物质(n10),分别记为P

39、1,P2,Pn,用n种基本物质构造物品,这些物品使用在k个不同地区(k20),每个地区对物品提出自己的要求,这些要求用一个n位的数表示:12n,其中: i =1表示所需物质中必须有第i种基本物质 =-1表示所需物质中必须不能有第i种基本物质 =0无所谓 问题求解: 当k个不同地区要求给出之后,给出一种方案,指出哪些物质被使用,哪些物质不被使用。 程序说明: 数组b1,b2,.,bnJ表示某种物品 a1.k,1.n记录k个地区对物品的要求,其中: ai,j=1表示第i个地区对第j种物品是需要的 ai,j=0表示第i个地区对第j种物品是无所谓的 ai,j=-1表示第i个地区对第j种物品是不需要的,

40、2002年提高组初赛试题,var i, j ,k, n :integer; p:boolean; b :array 0.20 of 0.1; a :array1.20,1.10d integer; begin readln(n,k); for i:=1 to k do begin for j:=1 to n do read(ai,j); readln; end; for i:=0 to n do bi:=0; p:=true;,while( )do begin j:=n; while bj=1 do j:=j-1; ( ); for i:=j+1 to n do bi:=0; ( ); for

41、 i:=1 to k do for j :=1 to n do if(ai,j=1)and(bj=0)or( ) then p:=true; end; if( )then writeln(找不到!) else for i:=1 to n do if (bi=1) then writeln(物质,i,需要) else writeln(物质,i,不需要); end.,p and (b0=0),bj:=1,p:=false,(ai,j=-1)and(bj=1),p,一个正整数（非素数）可以表示成它的因子（1与其本身除外）的乘积。例如：12有因子2，2，3，4，6，所以可表示为：12=2*2*3=4*

42、3=2*6 给出任一个整数n，求出它所有的因子乘积表达式（交换律得出的不同式子算同一种）。 算法说明：读入一个整数n，首先求出它的所有的因子以及每个因子可能的次数。 例如：整数48 因子：2 3 4 6 8 12 16 24 次数：4 1 2 1 1 1 1 1 将上面的结果存入二维数组a中，其中：ai，1表示因子；ai，2表示次数。然后用穷举法求出所有可能的表示： 数组b记录取数情况； 数组c工作单元。,1997年普及组、提高组初赛试题,var a:array0.20,1.2 of integer; c,b:array0.20 of integer; n,m,i,j,s,k,l:intege

43、r; begin readln(n); for i:=1 to 20 do ai,1:=0; j:=0; for i:=2 to n-1 do begin s:=0; m:=n; while(m0) and (m mod i=0) do begin m:=m div i;（ ）; end; if（ ）then begin j:=j+1; （ ）; aj,2:=（ ）; end end;,s:=s+1,s0,aj,1:=i,s,for i:=0 to j do bi:=0; while b0=0 do begin k:=j; while（ ）do k:=k-1; bk:=bk+1; for l:

44、=（ ） do bl:=0; s:=1; for i:=1 to j do if bi0 then for l:=1 to bi do （ ）; if s=n then begin end end end.,for i:=1 to j do ci:=bi; write(); m:=1; for i:=1 to j do while (ci0) and (mn) do begin m:=m*ai,1; if m=n then write(ai,1) else begin write(ai,1,*）; ci:=ci-1; end; end; writeln();,bk=ak,2,k+1 to j,

45、s:=s*ai,1,输出表达式,有一个箱子容量为V（正整数，0V20000），同时有n个物品（0n30），每个物品的体积值为正整数。 要求从n个物品中，任取若干个装入箱内，使箱子的剩余空间最小。 输入：一行整数，第一个数表示箱子的容量，第二个数表示有n个物品，后面n个数分别表示这n个物品各自的体积。 输出：一个整数，表示箱子的剩余空间。 样例： 输入：24 6 8 3 12 7 9 7 输出：0,装箱问题（2001年普及组复赛第4题）,选数（2002年普及组复赛第2题） 已知n（1=n=20）个整数x1,x2,xn（1=xi=5000000），以及一个整数k（kn）。从n个整数中任选k个整数相

46、加，可分别得到一系列的和。 例如当n=4，k=3，4个整数分别为3，7，12，19时，可得到的全部组合及它们的和为3+7+12=22，3+7+19=29，7+12+19=38，3+12+19=34。 现在，要求你计算出和为素数的组合共有多少种。如上例中，只有一种组合的和为素数：3+7+19=29。 输入： n , k x1，x2，xn 输出： 一个整数(满足条件的组合个数) 样例 输入： 4 3 3 7 12 19 输出： 1,问题描述： 辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都

47、是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？ 输入文件medic.in：第一行有两个整数T（1 = T = 1000）和M（1 = M = 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。 输出文件medic.out：包括一行，这一行只包含一个

48、整数，表示在规定的时间内，可以采到的草药的最大总价值。 样例输入： 70 3 71 100 69 1 1 2 样例输出： 3,采药(2005年普及组第3题),var w,v,a,s:array0.100 of longint; i,m,n,max:longint; procedure try(k,use,now:longint); K为待选购物品的序号，use是已用去的钱，now是现有的价值和 begin if k=m+1 then begin if nowmax then max:=now; exit; end; if use+wk=n then try(k+1,use+wk,now+ak)

49、; 钱还够，就买入此物品，待选下一物品 try(k+1,use,now);不买此物品,待选下一物品 end;,2、用回溯法解,begin readln(n,m); 总钱数和物品数 for i:=1 to m do begin read(wi,vi); ai:=wi*vi; end; max:=0; try(1,0,0); writeln(max); end.,下面程序的功能是利用递归方法生成从1到n(n10)的n个数的全部可能的排列（不一定按升序输出）。例如，输入3，则应该输出（每行输出5个排列）： 123 132 213 231 321 312,求全排列（2006年普及组初赛）,var i,

50、n,k:integer; a:array1.10 of integer; count:longint; procedure perm(k:integer); var j,p,t:integer; begin if then begin ; for p:=1 to k do write(ap:1); write( ); if then writeln; exit; end;,for j:=k to n do begin t:=ak; ak:=aj; aj:=t; perm(k+1) ; t:=ak; ; end end; begin read(n); count:=0; for i:=1 to

51、n do ai:=i; ; end.,k=n inc(count) count mod 5=0 ak:=aj; aj:=t perm(1),设有一个n*m的棋盘（2n20，2m20），如下图，在棋盘上左下角有一个中国象棋马。 （n,m） (1,1) 马走的规则为：马走日字；马只能向右走； 即如下图如示： 问题：当n，m输入之后，找出一条从左下角到右上角的路径。若不存在路径，则输出 NO。 样例 输入：4 4 输出：（1，1）-(2,3) -(4,4),马,骑士游历问题(1997年高中组第三题),问题描述: 将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。 例如：n=7，k

52、=3，下面三种分法被认为是相同的： 1，1，5; 1，5，1; 5，1，1; 问有多少种不同的分法。 输入：n，k (6n=200，2=k=6) 输出：一个整数，即不同的分法。 样例： 输入： 7 3 输出： 4 四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;,数的划分（2001年提高组复赛第2题）,【问题描述】 棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)

53、，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。 【输入】一行四个数据，分别表示B点坐标和马的坐标。 【输出】 一个数据，表示所有的路径条数。 【样例】 输入:6 6 3 3 输出:6,马拦过河卒（2002年普及组第4题）,问题描述： 已知n（1=n=20）个整数x1,x2,xn（1=xi=5000000），以及一个整数k（kn）。从n个整数中任选k个整数相加，可分别得到一系列的和。 例如当n=4，k=3,4个整数分别为3,7,12,19时，可得到的全部组合及它们的和为3+7+12=22,3+7+19=29,7

54、+12+19=38,3+12+19=34。 现在，要求你计算出和为素数的组合共有多少种。如上例中，只有一种的和为素数：3+7+19=29。 输入：n , k (1=n=20, kn) x1,x2,xn（1=xi=5000000） 输出：一个整数(满足条件的组合个数) 输入输出样例 输入： 4 3 3 7 12 19 输出： 1,选数（2002年普及组复赛第2题）,单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和aston

55、ish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。 输入:输入的第一行为一个单独的整数n (n=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。 输出:只需输出以此字母开头的最长的“龙”的长度。 样例： 输入 5 at touch cheat choose tact a 输出 （连成的“龙”为atoucheatactactouchoose）,单词接龙（2000年普及组、提高组复赛题）,问题描述： 现有一个操作数序列，从1，2，一直到n，栈A的深度大于n。 现在可以进行以下两种操作： 将一个数，从操作数序列的头端移到栈的头端。 将一个数，从栈的头端移到输出序列的尾端。,栈（2003年普及组复赛第3题）,使用这两种操作，由一个操作数序列就可以得