信息学奥赛基础知识讲解.ppt

《信息学奥赛基础知识讲解.ppt》由会员分享，可在线阅读，更多相关《信息学奥赛基础知识讲解.ppt（113页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息学奥赛基础知识讲解现在学习的是第1页，共113页精心备课，突破疑点难点，追求直观高效。精心备课，突破疑点难点，追求直观高效。现在学习的是第2页，共113页 分析：分析：将十进数转换成二进制数将十进数转换成二进制数, ,一般采用除二取余法。如果用一般采用除二取余法。如果用一个数组一个数组b b来存放二进制数来存放二进制数, ,可以依次把所得的余数存入可以依次把所得的余数存入b0b0、b1b1、bn,bn,最后按最后按bnbn、bn-1bn-1、b1b1、b0b0的顺序输出这些余的顺序输出这些余数数, ,就得到了所求的二进制数。就得到了所求的二进制数。 1 1、读入一个十进制自然数，将其转换成

2、二进制数后输出。、读入一个十进制自然数，将其转换成二进制数后输出。现在学习的是第3页，共113页例如：例如：余数：余数：25252 212122 26 62 23 32 21 12 20 0输出结果为：输出结果为：11001110010 01 10 01 11 10123456现在学习的是第4页，共113页var var i,j,n: i,j,n:longintlongint; ; b:array 0.31 of 0.1; b:array 0.31 of 0.1;beginbegin readln(n); readln(n); write(n,=(); write(n,=(); i:=0; i

3、:=0; while while（ ）dodo begin begin （ ）; ; i:=i+1; i:=i+1; 指定下一个余数的存放位置指定下一个余数的存放位置 n:=n div 2 n:=n div 2 产生的商将作为新的被除数产生的商将作为新的被除数 end;end; for j:= for j:=（ ）do write(bj);do write(bj); writeln()2) writeln()2)end.end.n0n0 bi:=n mod 2bi:=n mod 2 i-1 downto 0i-1 downto 0 后进先出后进先出现在学习的是第5页，共113页Str1=321

4、0Str2=98765a 0 1 2 3b 5 6 7 8 95791101j对位对位相加相加进位进位2、高精度加法、高精度加法现在学习的是第6页，共113页var str1,str2:string; a,b:array1.100 of 0.9; l1,l2,i,j,k:integer;begin readln(str1); readln(str2); 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

5、)-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+1=0 then j:=j-1; for i:=j+1 downto 1 do write(ai); writeln;end.处理进位处理进位从低位到高位依次将各从低位到高位依次将各位数相加位数相加用字符串形式输入用字符串形式输入加数和被加数加数和被

6、加数ai-10ai+1+1现在学习的是第7页，共113页 分析：分析：类似加法，可以用竖式求乘法。在做乘法运算时，同样类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进行乘法运算时，必须进行错位相加。也有进位，同时对每一位进行乘法运算时，必须进行错位相加。8 4 8 2 3 2 5 4 4 1 6 9 61 9 5 0 43*8+0+0=24 c1=4x= aix= ai* *bj+ x div 10+ ci+j-1bj+ x div 10+ ci+j-1 ci+j-1= x mod 10ci+j-1= x mod 103*4+2+0=14 c2=43*8+1+0=25

7、c3=5 c4=22*8+0+4=20 c2=02*4+2+5=15 c3=52*8+1+2=19 c4=9 c5=13、高精度乘法、高精度乘法现在学习的是第8页，共113页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

8、ala-i+1:=ord(s1i)-ord(0); for i:=lb downto 1 do blb-i+1:=ord(s2i)-ord(0); 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

9、:=lc-1; for i:=lc downto 1 do write(ci); writeln;end.现在学习的是第9页，共113页varvar yh:array1.5,1.5of integer; yh:array1.5,1.5of integer; i,j:integer; i,j:integer;beginbegin yh1,1:=1; yh1,1:=1; for i:=2 to 5 do for i:=2 to 5 do begin begin yhi,1:=1;yhi,i:=1; yhi,1:=1;yhi,i:=1; for j:= for j:=2 to i-12 to i-1

10、 do do yhi,j:=yhi-1,j-1 + yhi-1,j;yhi,j:=yhi-1,j-1 + yhi-1,j; end; end; for i:=1 to 5 do for i:=1 to 5 do begin begin for j:=1 to i do write(yhi,j:3); for j:=1 to i do write(yhi,j:3); writeln;writeln; end; end;end.end.1111121133114644 4、阅读程序，写出运行结果。、阅读程序，写出运行结果。现在学习的是第10页，共113页 5、20012001年普及组、提高组初赛试

11、题（穷举法）年普及组、提高组初赛试题（穷举法） 在在A、B两个城市之间设有两个城市之间设有N个路站个路站(如下图中的如下图中的S1，且且N100)，城市与路站之间、城市与路站之间、路站和路站之间各有若干条路段路站和路站之间各有若干条路段(各路段数各路段数=20，且每条路段上的距离均为一个整数，且每条路段上的距离均为一个整数)。 A，B的一条通路是指：从的一条通路是指：从A出发，可经过任一路段到达出发，可经过任一路段到达S1，再从再从S1出发经过任一路段出发经过任一路段，最后到达最后到达B。通路上路段距离之和称为通路距离通路上路段距离之和称为通路距离(最大距离最大距离=1000)。当所有的路段距

12、离。当所有的路段距离给出之后，求出所有不同距离的通路个数给出之后，求出所有不同距离的通路个数(相同距离仅记一次相同距离仅记一次)。 例如：下图所示是当例如：下图所示是当N=1时的情况：时的情况： 从从A到到B的通路条数为的通路条数为6，但因其中通路，但因其中通路5+5=4+6，所以满足条件的不同距离的通，所以满足条件的不同距离的通路条数为路条数为5。 数据结构：数据结构： N记录记录A，B间路站的个数；间路站的个数； 数组数组Di，0记录第记录第i-1个到第个到第i个路站间路段的个数个路站间路段的个数; Di，1，Di，2，记录每个路段的距离记录每个路段的距离; 数组数组G记录可取到的距离。记

13、录可取到的距离。现在学习的是第11页，共113页8645374 0 1 1 1 8+4+3=15 g15=10 1 1 2 8+4+4=16 g16=10 1 2 1 8+5+3=16 g16=10 1 2 2 8+5+4=17 g17=10 1 3 1 8+7+3=18 g18=10 1 3 2 8+7+4=19 g19=10 2 1 1 6+4+3=13 g13=10 2 1 2 6+4+4=14 g14=10 2 2 1 6+5+3=14 g14=10 2 2 2 6+5+4=15 g15=10 2 3 1 6+7+3=16 g16=10 2 3 2 6+7+4=17 g17=1b0 b

14、1 b2 b31 1 1 1 穷举结束穷举结束D1，0=2, D1，1=8, D1，2=6D2，0=3, D2，1=4, D2，2=5， D2，3=7D3，0=2, D3，1=3, D3，2=4现在学习的是第12页，共113页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); en

15、d; 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.b01s+d i , bi bj=dj,0s:=s+gi穷举用穷举用循环开关循环开关求当前通路求

16、当前通路的距离的距离统计不同的通路统计不同的通路条数条数作记录作记录产生一种产生一种新的方案新的方案现在学习的是第13页，共113页 要求在国际象棋棋盘上放置八个皇后，使她们不能互相攻击，即任何要求在国际象棋棋盘上放置八个皇后，使她们不能互相攻击，即任何两个皇后不能处在同一行、同一列、同一条线上。请找出所有的摆法。两个皇后不能处在同一行、同一列、同一条线上。请找出所有的摆法。 分析：分析： 如果我们把如果我们把8*8的棋盘看成是一个平面直角坐标系，那么任意两个的棋盘看成是一个平面直角坐标系，那么任意两个皇后在平面上的坐标应同时满足以下三个条件：皇后在平面上的坐标应同时满足以下三个条件：两个皇后

17、的横坐标不相等。两个皇后的横坐标不相等。两个皇后的纵坐标不相等。两个皇后的纵坐标不相等。两个皇后的横坐标之差的绝对值不等于纵坐标之差的绝对值。两个皇后的横坐标之差的绝对值不等于纵坐标之差的绝对值。 我们用数组我们用数组xixi来描述八个皇后在棋盘上的状态，来描述八个皇后在棋盘上的状态， xixi =j=j表示在第表示在第i i行的第行的第j j列放置了一个皇后。列放置了一个皇后。IKIK当当IKIK时，时，XI XKXI XK当当IKIK时，时，| |I-K|XI-XK|I-K|XI-XK|6、八皇后问题八皇后问题（回溯法）（回溯法）现在学习的是第14页，共113页const n=8;var

18、i,j,k:integer; x:array1.n of integer;function 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

19、( )then begin print; exit end; for i:= 1 to n do begin ( ); if( )then try(k+1); end; end ;begin try(1);end.xi=xkk=n+1place:=falsexk:=iplace(k)现在学习的是第15页，共113页 如下图所示为一个数字三角形，请编程计算从顶到底的某处的一如下图所示为一个数字三角形，请编程计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。（只要求输出总和）条路径，使该路径所经过的数字总和最大。（只要求输出总和） 规定：规定： 一步可沿左斜线向下或右斜线向下走；一步可沿

20、左斜线向下或右斜线向下走； 图形行数小于等于图形行数小于等于100100； 三角形中的数字为三角形中的数字为0 0，1 1，99;99; 测试数据通过键盘逐行输入，如下图数据应以如下所示格式输入测试数据通过键盘逐行输入，如下图数据应以如下所示格式输入：5 57 73 83 88 1 08 1 02 7 4 42 7 4 4 4 5 2 6 5 4 5 2 6 5 输出：输出：30307 7、数字三角形（动态规划）、数字三角形（动态规划）现在学习的是第16页，共113页 逆推法逆推法: : 按三角形的行划分阶段，若行数为按三角形的行划分阶段，若行数为n n，则可把问题看做一个则可把问题看做一个n

21、-1n-1个阶段个阶段的决策问题。先求出第的决策问题。先求出第n-1n-1阶段阶段( (第第n-1n-1行上各点行上各点) )到第到第n n行的最大和，再行的最大和，再依次求出第依次求出第n-2n-2阶段、第阶段、第n-3n-3阶段阶段第第1 1阶段阶段( (起始点起始点) )各决策点至第各决策点至第n n行的最行的最大和。大和。 设设fi,jfi,j为从第为从第i i阶段中的点阶段中的点j j至第至第n n行的最大的数字和；行的最大的数字和； 则则fn,j=an,jfn,j=an,j（1=j=n1=j=n） fi,j= fi,j= maxmax ai,j+fi+1,j ai,j+fi+1,j

22、 , , ai,j+fi+1,j+1 ai,j+fi+1,j+1 （1=j=i1=jfi+1,j+1 then fi,j:=fi+1,j+ai,j if fi+1,jfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j; else fi,j:=fi+1,j+1+ai,j; writeln(f1,1); writeln(f1,1);end.end.阶段阶段状状态态决策决策状态转移方程状态转移方程452657121010201310232130现在学习的是第18页，共113页8 8、深度优先遍历、深度优先遍历 基本思想：基本思想：n第一步

23、，从图中某个顶点第一步，从图中某个顶点V0出发，首先访问出发，首先访问V0；n第二步，找出刚访问过的顶点第二步，找出刚访问过的顶点Vi的第一个未被访问的邻接点，的第一个未被访问的邻接点，然后访问该顶点。以该顶点为新顶点，重复本步骤，直到当前的然后访问该顶点。以该顶点为新顶点，重复本步骤，直到当前的顶点没有未被访问的邻接点为止；顶点没有未被访问的邻接点为止；n第三步，返回前一个访问过的且仍有未被访问的邻接点的顶点，找第三步，返回前一个访问过的且仍有未被访问的邻接点的顶点，找出并访问该顶点的下一个未被访问的邻接点，然后执行第二步步骤；出并访问该顶点的下一个未被访问的邻接点，然后执行第二步步骤；n若

24、此时图中尚有顶点未访问，则另选图中一个未被访问的顶点作起若此时图中尚有顶点未访问，则另选图中一个未被访问的顶点作起始点，重复第一步至第三步，直至图中所有顶点都被访问到为止。始点，重复第一步至第三步，直至图中所有顶点都被访问到为止。现在学习的是第19页，共113页123754689ABDCEFGHI该图的深度优先搜索的输出序列为：该图的深度优先搜索的输出序列为：ABCFEGDHI以以F作为起始点，该图的深度作为起始点，该图的深度优先搜索的输出序列为：优先搜索的输出序列为：FCBADGEHI 或或FCBADGHIE 或或FCBAEGDHI 或或FCBAEGHID 或或FCBEADGHI 或或FCB

25、EGHIDA 或或FCBEGDAHI现在学习的是第20页，共113页 任取一个顶点加入生成树，然后对那些一个端点在生成任取一个顶点加入生成树，然后对那些一个端点在生成树中，而另一个端点不在生成树中的边进行排序，取权值最树中，而另一个端点不在生成树中的边进行排序，取权值最小的边，将它和另一个端点加进生成树中。重复上述步骤直小的边，将它和另一个端点加进生成树中。重复上述步骤直到所有顶点都进入了生成树为止。到所有顶点都进入了生成树为止。9、构造最小生成树的、构造最小生成树的prim算法算法现在学习的是第21页，共113页12345616192133111418656121635第一步，第一步，U1，

26、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)，(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)46611518现在学习的是第22页，共113页第一步，第一步，U1，VU2,3,4,5,6，TE 第二步，第二步，U1,2，VU3,4,5,6，

27、TE(1,2)第三步，第三步，U1,2,3，VU4,5,6，TE(1,2)，(2,3)第四步，第四步，U1,2,3,4，VU5,6，TE(1,2)，(2,3)，(3,4)第五步，第五步，U1,2,3,4,6，VU5，TE(1,2)，(2,3)，(3,4)，(2,6)第六步，第六步，U1,2,3,4,6,5，VU ，TE(1,2)，(2,3)，(3,4)，(2,6)，(4,5)12163546115186说明：说明：最小生成树也不是唯一的最小生成树也不是唯一的12345616192133111418656现在学习的是第23页，共113页 所谓后缀表达式是指这样的一种表达式：式中不再引入括号，所谓

28、后缀表达式是指这样的一种表达式：式中不再引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行，不再考虑运算符的优先规则。例如格地由左而右进行，不再考虑运算符的优先规则。例如5 5* *（7-37-3）+9+9对应的后缀表达式为对应的后缀表达式为5 7 3 -5 7 3 -* *9 +9 +，其中每个操作数后都有一个空格，其中每个操作数后都有一个空格。 输入：后缀表达式输入：后缀表达式a a 输出：表达式的值输出：表达式的值 1010、计算后缀表达式的值、计算后缀表达式的值现在学习的是第24页，共113页分

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

30、，这时的栈顶元素值即为最终计算结果。的栈顶元素值即为最终计算结果。 现在学习的是第25页，共113页表达式：表达式：5 7 3 - * 9 + top现在学习的是第26页，共113页表达式：表达式：5 7 3 - * 9 + top5现在学习的是第27页，共113页表达式：表达式：5 7 3 - * 9 + top57现在学习的是第28页，共113页表达式：表达式：5 7 3 - * 9 + top573现在学习的是第29页，共113页表达式：表达式：5 7 3 - * 9 + top573现在学习的是第30页，共113页表达式：表达式：5 7 3 - * 9 + top573-=4现在学习的

31、是第31页，共113页表达式：表达式：5 7 3 - * 9 + top54现在学习的是第32页，共113页表达式：表达式：5 7 3 - * 9 + top54现在学习的是第33页，共113页表达式：表达式：5 7 3 - * 9 + top54*=20现在学习的是第34页，共113页表达式：表达式：5 7 3 - * 9 + top20现在学习的是第35页，共113页表达式：表达式：5 7 3 - * 9 + top209现在学习的是第36页，共113页表达式：表达式：5 7 3 - * 9 + top209现在学习的是第37页，共113页表达式：表达式：5 7 3 - * 9 + top

32、209+=29现在学习的是第38页，共113页表达式：表达式：5 7 3 - * 9 + top29现在学习的是第39页，共113页type stack=record data:array1.100of real; top:0.100; 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); 入栈入栈 beg

33、in s.top:=s.top+1; s.datas.top:=x; end;begin 主程序主程序 readln(a); s.top:=0; 置空栈置空栈现在学习的是第40页，共113页 i:=1; ch:=ai; while （ ）do begin case ch of 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; * :

34、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)pop(s)现在学习的是第41页，共113页 现有现有1 1g g、2g2g、3g3g、5g5g、10g10g、20g20g的砝码各若干枚，问用这些砝码可以称出多少种不同的的砝码各若干枚，问用这些砝码可以称出多少种不同的重量。（设砝码的总重不超过重量。（设砝码的总重不超过10001000g g，且砝码只能放

35、在天平的一端）且砝码只能放在天平的一端） 输入：输入：a1 a2 a3 a4 a5 a6a1 a2 a3 a4 a5 a6 （表示表示1 1g g砝码有砝码有a1a1个，个，2 2g g砝码有砝码有a2a2个，个，2020g g砝码有砝码有a6a6个）个） 输出：输出：total=ntotal=n （ n n表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况） 如输入：如输入：1 1 0 0 0 01 1 0 0 0 0 则输出：则输出：total=3total=3（表示可以称出表示可以称出1 1g g，2g2g

36、，3g3g三种不同的重量）三种不同的重量） 由一个砝码也不取开始扩展结点，当扩展出的某一个结点所对应的质量数在前面已经出由一个砝码也不取开始扩展结点，当扩展出的某一个结点所对应的质量数在前面已经出现过时，则不再从该结点扩展下去，并删掉该结点；如此重复，直到没有结点可扩展为止。现过时，则不再从该结点扩展下去，并删掉该结点；如此重复，直到没有结点可扩展为止。统计扩展的结点总数，就可得到可以称出的质量总数。统计扩展的结点总数，就可得到可以称出的质量总数。1111、砝码称重：、砝码称重：现在学习的是第42页，共113页constconst w:array1.6 of integer=(1,2,3,5,

37、10,20); w:array1.6 of integer=(1,2,3,5,10,20);每种砝码的单位质量每种砝码的单位质量 maxweight=1000; maxweight=1000; 队列的最大长度队列的最大长度 type type tlist=array0.maxweight of record tlist=array0.maxweight of record we:integer;we:integer; 当前结点所对应砝码组合的总质量当前结点所对应砝码组合的总质量 sn: array1.6 of integer;sn: array1.6 of integer; 各砝码个数各砝码个

38、数 end;end;var a:tlist; var a:tlist; 队列队列 s: array1.6 of integer; s: array1.6 of integer; 存放每种砝码的数量存放每种砝码的数量 b:array1.1000 of boolean; b:array1.1000 of boolean; 标记某个质量是否可被称出标记某个质量是否可被称出 i,i,head,tailhead,tail:integer; :integer; cw:integer; cw:integer;beginbegin for i:=1 to 6 do read(si);readln; for i

39、:=1 to 6 do read(si);readln; 读入每种砝码的数量读入每种砝码的数量 fillchar(a,sizeof(a),0);fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); fillchar(b,sizeof(b),0); 1 2 2 0 0 01 2 3 12 13 21 22 23 31 32 33 132 133 231 232 233331 33213322331 2332 1332223321现在学习的是第43页，共113页 head:=0; tail:=0; head:=0; tail:=0; 置队空置队空 wh

40、ilewhile（ ）do do 还有结点可扩展还有结点可扩展, ,则执行循环体则执行循环体 begin begin for i:=1 to 6 do for i:=1 to 6 do 试探每种砝码试探每种砝码 if if （ ） 新组合可以得到新组合可以得到 then beginthen begin cw:=ahead.we+wi; cw cw:=ahead.we+wi; cw为新组合的总质量为新组合的总质量 ifif（ ）then begin then begin 入队入队 tail:=tail+1;tail:=tail+1;（ ） bcw:=true; bcw:=true;标记标记 at

41、ail.sn:=ahead.sn;atail.sn:=ahead.sn; （ ） end; end; end; end; （ ）; ; 出队出队 end;end; writeln(total=,tail); writeln(total=,tail); end.end.head=tailhead=tailahead.snisiahead.snisinot bcwnot bcwatail.we:=cw;atail.we:=cw;inc(atail.sni)inc(atail.sni)head:=head+1head:=head+1现在学习的是第44页，共113页多做老题，立足基本算法，引导一题多解

42、多做老题，立足基本算法，引导一题多解。穷举法、回溯法、动态规划穷举法、回溯法、动态规划现在学习的是第45页，共113页【问题描述】【问题描述】 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过，怎么布置，你说了算，只要不超过N元钱就行元钱就行”。今天一早金明就开始做预算。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限

43、定的，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规元。于是，他把每件物品规定了一个重要度，分为定了一个重要度，分为5等：用整数等：用整数15表示，第表示，第5等最重要。他还从因特网上查到了每件物等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过品的价格（都是整数元）。他希望在不超过N元（可以等于元（可以等于N元）的前提下，使每件物品元）的前提下，使每件物品的价格与重要度的乘积的总和最大。的价格与重要度的乘积的总和最大。 设第设第j件物品的价格为件物品的价格为vj，重要度为重要度为wj，共选中了共选中了k件物品，编号依次为件物品，编号依次为j1，

44、j2，jk，则所求的总和为：则所求的总和为： vj1*wj1+vj2*wj2+ +vjk*wjk 请你帮助金明设计一个满足要求的购物单。请你帮助金明设计一个满足要求的购物单。开心的金明开心的金明(2006年普及组复赛年普及组复赛)现在学习的是第46页，共113页【输入文件输入文件】 输入文件输入文件happy.in 的第的第1行，为两个正整数，用一个空格隔开：行，为两个正整数，用一个空格隔开：N m（其中其中N（30000）表示总钱数，表示总钱数，m（25）为希望购买物品的个数。）为希望购买物品的个数。） 从第从第2行到第行到第m+1行，第行，第j行给出了编号为行给出了编号为j-1的物品的基本

45、数据，每行有的物品的基本数据，每行有2个非负整数个非负整数v p（其中其中v表示该物品的价格表示该物品的价格(v=10000)，p表示该物品的重要度表示该物品的重要度(15)）【输出文件输出文件】 输出文件输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（和的最大值（100000000）。）。【输入样例输入样例】 1000 5 1000 5 800 2 800 2 400 5 400 5 300 5 300 5 400 3 400 3 200 2 200 2【输出样例输出样例】 3900现在

46、学习的是第47页，共113页var v,p:array1.25 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 y

47、u:=yu+vi; s:=s+vi*pi; end; if (yumax) then max:=s; end; writeln(max);end.可以通过可以通过8个测试点个测试点1、用穷举法解、用穷举法解现在学习的是第48页，共113页 20012001年普及组、提高组初赛试题年普及组、提高组初赛试题 在在A、B两个城市之间设有两个城市之间设有N个路站个路站(如下图中的如下图中的S1，且且N100)，城市与路站之间、路城市与路站之间、路站和路站之间各有若干条路段站和路站之间各有若干条路段(各路段数各路段数=20，且每条路段上的距离均为一个整数，且每条路段上的距离均为一个整数)。 A，B的一条

48、通路是指：从的一条通路是指：从A出发，可经过任一路段到达出发，可经过任一路段到达S1，再从再从S1出发经过任一路段出发经过任一路段，最后到达最后到达B。通路上路段距离之和称为通路距离通路上路段距离之和称为通路距离(最大距离最大距离=1000)。当所有的路段距。当所有的路段距离给出之后，求出所有不同距离的通路个数离给出之后，求出所有不同距离的通路个数(相同距离仅记一次相同距离仅记一次)。 例如：下图所示是当例如：下图所示是当N=1时的情况：时的情况： 从从A到到B的通路条数为的通路条数为6，但因其中通路，但因其中通路5+5=4+6，所以满足条件的不同距离的通，所以满足条件的不同距离的通路条数为路

49、条数为5。 数据结构：数据结构： N记录记录A，B间路站的个数；间路站的个数； 数组数组Di，0记录第记录第i-1个到第个到第i个路站间路段的个数个路站间路段的个数; Di，1，Di，2，记录每个路段的距离记录每个路段的距离; 数组数组G记录可取到的距离。记录可取到的距离。现在学习的是第49页，共113页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(d

50、i,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:=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.b01s+d i