当前位置:首页 >> 学科竞赛 >> 暑假信息学奥赛辅导教案

暑假信息学奥赛辅导教案


暑假信息学奥赛辅导教案
复习初中内容
(halt:退出程序。 exit:退出过程、函数。如果在主程序,则效果和 halt 一样。 break:跳出循环。 continue 也是用在循环里面,但它并不是跳出,而是跳过这一次循环,直接进入下一个循环。 ) 一、分治算法: 例 1:快速排序 (1)基本思想 在当前无序区 R[1..H]中任取一个数据元素作为比较的&q

uot;基准"(不妨记为 X),用此基准将当前无序区 划分为左右两个较小的无序区:R[1..I-1]和 R[I+1..H],且左边的无序子区中数据元素均小于等于基准元 素,右边的无序子区中数据元素均大于等于基准元素,而基准 X 则位于最终排序的位置上,即 R[1..I-1] ≤X.Key≤R[I+1..H](1≤I≤H),当 R[1..I-1]和 R[I+1..H]均非空时,分别对它们进行上述的划分过程, 直至所有无序子区中的数据元素均已排序为止。 (2)排序过程【示例】 初 始 关键字 [ 49 38 65 97 76 13 27 49] 第一次交换后 [27 38 65 97 76 13 49 49] 第二次交换后 [27 38 49 97 76 13 65 49] J 向左扫描,位置不变,第三次交换后 [27 38 13 97 76 49 65 49] I 向右扫描,位置不变,第四次交换后 [27 38 13 49 76 97 65 49] J 向左扫描 [27 38 13 49 76 97 65 49] (一次划分过程) 初 始 关键字 [49 38 65 97 76 13 27 49] 一趟排序之后 [27 38 13]49[76 97 65 49] 二趟排序之后 [13]27[38]49[49 65]76[97] 三趟排序之后 13 27 38 49 49[65]76 97 最后的排序结果 13 27 38 49 49 65 76 97 各趟排序之后的状态 快速排序算法 Const n=10; Var a:array [1..n] of integer; i,k:integer; procedure qsort(low,high:integer); var i,j:integer;x:integer; begin if low<high then begin i:=low;j:=high;x:=a[i]; repeat while (a[j]>=x) and (i<j)do j:=j-1; {把大于基准的数留在右面} if (a[j]<x) and (i<j) then begin a[i]:=a[j];i:=i+1;end; {把小于基准的数交换到左面} while (a[i]<=x) and (i<j) do i:=i+1; {把小于基准的数交换到左面} if (a[i]>x) and (i<j) then begin a[j]:=a[i];j:=j-1; end; {把大于基准的数交换到右面} until i=j; {直到 I 与 j 重叠,完成一次分组过程}

a[i]:=x; {把基准数插入相应的位置,以后不再参与排序} qsort(low,i-1); {小于基准的数重复分组} qsort(i+1,high); {大于基准的数重复分组} end; end; begin for i:=1 to n do read(a[i]); qsort(1,n); for i:=1 to n do write(a[i]:6); writeln; end. 算法改进: procedure qsort(l,r:integer); var i,j,mid:integer; begin i:=l;j:=r; mid:=a[(l+r) div 2]; {将当前序列在中间位置的数定义为中间数} repeat while a[i]<mid do inc(i); {在左半部分寻找比中间数大的数} while a[j]>mid do dec(j); {在右半部分寻找比中间数小的数} if i<=j then begin {若找到一组与排序目标不一致的数对则交换它们} swap(a[i],a[j]); inc(i);dec(j); {继续找} end; until i>j; if l<j then qsort(l,j); {若未到两个数的边界,则递归搜索左右区间} if i<r then qsort(i,r); end;{sort} 从输出的数据可以发现,对较坏的初始数据如第一组输入数据,快速排序在交换数据的次数方面已给出了 相当好的结果。时间的复杂性是 O(nlog2n),速度快,但它也是不稳定的排序方法。 例2:循环比赛 设有N个选手进行循环比赛,其中N=2^M,要求每名选手要与其他N-1名选手比赛一次,每名选手每天 比赛一次,循环赛共进行N-1天,要求每天没有选手轮空。 输入:M 输出:表格形式的比赛安排表 【样例输入】3 【样例输出】 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1

这样,对8个队的赛事排列就逐步减化为对4个队的排列,然后又进一步减化为对2个队的排列,最 后就成为1个队的排列。因此,这一问题可以采用分治法的思想来解决。 在设计程序时,采用由小到大的方法进行扩展,而数组下标的处理是解决该问题的关键。 【算法过程】 program xhbs; var m,n,k,p,s,t,i,j:integer; a:array[1..1000,1..1000]of integer; Begin read(m); k:=trunc(exp(m*ln(2))); n:=k; for i:=1 to k do a[1,i]:=i; p:=1; for s:=1 to m do begin n:=n div 2; for t:=1 to n do begin for i:=p+1 to 2*p do for j:=p+1 to 2*p do begin a[i,j+(t-1)*p*2]:=a[i-p,j+(t-1)*p*2-p]; a[i,j+(t-1)*p*2-p]:=a[i-p,j+(t-1)*p*2]; end; end; p:=p*2; end; for i:=1 to k do begin for j:=1 to k do begin write(a[i,j]:3); end;

writeln; end; end. 二、回溯算法 例 1:马的遍历

【算法分析】 如图4(b),马最多有四个方向,若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为: 1: (i,j)→(i+2,j+1); (i<3,j<8) 2: (i,j)→(i+1,j+2); (i<4,j<7) 3: (i,j)→(i-1,j+2); (i>0,j<7) 4: (i,j)→(i-2,j+1); (i>1,j<8) 搜索策略: S1:A[1]:=(0,0); S2:从A[1]出发,按移动规则依次选定某个方向,如果达到的是(4,8)则转向S3,否则继续搜索下 一个到达的顶点; S3:打印路径。 【算法设计】 procedure try(i:integer); {搜索} var j:integer; begin for j:=1 to 4 do {试遍4个方向} if 新坐标满足条件 then begin 记录新坐标; if 到达目的地 then print {统计方案,输出结果} else try(i+1); {试探下一步} 退回到上一个坐标,即回溯; end; end; 【参考程序】 program exam2;

const x:array[1..4,1..2] of integer=((2,1),(1,2),(-1,2),(-2,1)); var t:integer; a:array[1..9,1..2] of integer; procedure print(ii:integer); var i:integer; begin inc(t); for i:=1 to ii-1 do write(a[i,1],',',a[i,2],'-->'); writeln('4,8',t:5); readln; end; procedure try(i:integer); var j:integer; begin a[1,1]:=0;a[1,2]:=0; for j:=1 to 4 do if (a[i-1,1]+x[j,1]>=0) and (a[i-1,1]+x[j,1]<=4) and (a[i-1,2]+x[j,2]>=0) and (a[i-1,2]+x[j,2]<=8) then begin a[i,1]:=a[i-1,1]+x[j,1]; a[i,2]:=a[i-1,2]+x[j,2]; if (a[i,1]=4) and (a[i,2]=8) then print(i) else try(i+1); a[i,1]:=0;a[i,2]:=0 end; end; begin try(2); end. 例 2:选书

【算法分析】

可用穷举法,先不考虑“每人都满意” 这一条件,这样只剩“每人选一本且只能选一本”这一条件。 在这个条件下,可行解就是五本书的所有全排列,一共有5!=120种。然后在120种可行解中一一删去不 符合“每人都满意”的解,留下的就是本题的解答。 为了编程方便,设1,2,3,4,5分别表示这五本书。这五个数的一种全排列就是五本书的一种分发。 例如54321就表示第5本书(即E)分给张,第4本书(即D)分给王,??,第1本书(即A)分给李。 “喜爱书表”可以用二维数组来表示,1表示喜爱,0表示不喜爱。 【算法设计】 S1:产生5个数字的一个全排列; S2:检查是否符合“喜爱书表”的条件,如果符合就打印出来; S3:检查是否所有的排列都产生了,如果没有产生完,则返回S1; S4:结束。 上述算法有可以改进的地方。比如产生了一个全排列12345,从表中可以看出,选第一本书即给张同 学的书,1 是不可能的,因为张只喜欢第3、4 本书。这就是说,1××××一类的分法都不符合条件。由 此想到,如果选定第一本书后,就立即检查一下是否符合条件,发现1是不符合的,后面的四个数字就不 必选了,这样就减少了运算量。换句话说,第一个数字只在3、4中选择,这样就可以减少3/5的运算量。 同理,选定了第一个数字后,也不应该把其他4个数字一次选定,而是选择了第二个数字后,就立即检查 是否符合条件。例如,第一个数选3,第二个数选4后,立即检查,发现不符合条件,就应另选第二个数。 这样就把34×××一类的分法在产生前就删去了。又减少了一部分运算量。 综上所述,改进后的算法应该是:在产生排列时,每增加一个数,就检查该数是否符合条件,不符合, 就立刻换一个,符合条件后,再产生下一个数。因为从第I本书到第I+1本书的寻找过程是相同的,所以 可以用递归方法。算法设计如下: procedure try(i); begin for j:=1 to 5 do begin if 第i 个同学分给第j本书符合条件 then begin 记录第i 个数 if i =5 then 打印一个解 else try(i+1); 删去第i 个数字 end; end; end; 【参考程序】 program exam3; const like:array[1..5,1..5] of 0..1=((0,0,1,1,0),(1,1,0,0,1), (0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1)); name:array[1..5] of string[6]=('zhang','wang','liu','sun','li'); var book:array[1..5] of 0..5; flag:set of 1..5; c:integer; procedure print; var i:integer; begin inc(c);writeln('answer',c,':');

for i:=1 to 5 do writeln(name[i]:10,':',chr(64+book[i])); end; procedure try(i:integer); var j:integer; begin for j:=1 to 5 do if not(j in flag) and (like[i,j]>0) then begin flag:=flag+[j];book[i]:=j; if i=5 then print else try(i+1); flag:=flag-[j];book[i]:=0; end; end; begin flag:=[]; c:=0; try(1); readln end. 输出结果: zhang: C wang: A liu: B sun: D li: E 例 3:八皇后问题 〖问题描述〗 在一个8× 8的棋盘里放置8个皇后,要求每个皇后两两之间不相"冲"(在每一横列竖列斜列只有一个皇 后) 。 〖问题分析〗 这道题可以用递归循环来做,分别一一测试每一种摆法,直到得出正确的答案。主要解决以下几个问题: 1、冲突。包括行、列、两条对角线: (1)列:规定每一列放一个皇后,不会造成列上的冲突; (2)行:当第 I 行被某个皇后占领后,则同一行上的所有空格都不能再放皇后,要把以 I 为下标的标记置 为被占领状态; (3)对角线:对角线有两个方向。在同一对角线上的所有点(设下标为(i,j)) ,要么(i+j)是常数,要么(i-j) 是常数。因此,当第 I 个皇后占领了第 J 列后,要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。 2、数据结构。 (1)解数组 A。A[I]表示第 I 个皇后放置的列;范围:1..8 (2)行冲突标记数组 B。B[I]=0 表示第 I 行空闲;B[I]=1 表示第 I 行被占领;范围:1..8 (3)对角线冲突标记数组 C、D。 C[I-J]=0 表示第(I-J)条对角线空闲;C[I-J]=1 表示第(I-J)条对角线被占领;范围:-7..7 D[I+J]=0 表示第(I+J)条对角线空闲;D[I+J]=1 表示第(I+J)条对角线被占领;范围:2..16

〖算法流程〗 1、数据初始化。 2、从 n 列开始摆放第 n 个皇后(因为这样便可以符合每一竖列一个皇后的要求),先测试当前位置(n,m) 是否等于0(未被占领): 如果是,摆放第 n 个皇后,并宣布占领(记得要横列竖列斜列一起来哦),接着进行递归; 如果不是,测试下一个位置(n,m+1),但是如果当 n<=8,m=8 时,却发现此时已经无法摆放时,便要进行回 溯。 3、当 n>8 时,便一一打印出结果。 〖优点〗逐一测试标准答案,不会有漏网之鱼。 〖参考程序〗 program tt; var a:array [1..8] of integer; b,c,d:array [-7..16] of integer; t,i,j,k:integer; procedure print; begin t:=t+1; write(t,' '); for k:=1 to 8 do write(a[k],' writeln; end;

');

procedure try(i:integer); var j:integer; begin for j:=1 to 8 do {每个皇后都有 8 种可能位置} if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判断位置是否冲突} begin a[i]:=j; {摆放皇后} b[j]:=1; {宣布占领第 J 行} c[i+j]:=1; {占领两个对角线} d[i-j]:=1; if i<8 then try(i+1) {8 个皇后没有摆完,递归摆放下一皇后} else print; {完成任务,打印结果} b[j]:=0; {回溯} c[i+j]:=0; d[i-j]:=0; end; end; begin for k:=-7 to 16 do {数据初始化} begin b[k]:=0; c[k]:=0;

d[k]:=0; end; try(1);{从第 1 个皇后开始放置} end.

三、查找算法 例 1、现在有 N 位同学要参加表彰大会,请将这 N 位同学按姓名(姓名第一个字母大写)的字典顺序由小到 大分别安排在 1-N 号的位置上,并且要求输入一个学生的姓名后,输出该学生相应的座号,如果找不到该 学生的姓名,则输出“NO FOUND” 。 输入格式: 5 Tom Jenny Yang Zhang Kate Tom 输出格式: Tom 3 参考程序: program biaozh; var n,i,j:integer; a:array[1..1000]of string; temp,b:string; found:boolean; begin readln(n); for i:=1 to n do readln(a[i]); for i:=1 to n-1 do for j:=i+1 to n do if a[i]>a[j] then begin temp:=a[i]; a[i]:=a[j]; a[j]:=temp; end; for i:=1 to n do writeln(a[i]); read(b); found:=true; for i:=1 to n do if a[i]=b then begin found:=false;

writeln(a[i],' ',i); break; end; if found then writeln('no found'); end. 例 2: 二分查找的基本思想:首先将结点按关键字排序,其次将查找值与中间位置的值比较,相等,查找成功; 不等,则中间数据大于或小于查找值,无论怎样查找将在一半的数据中查找。 参考程序 1: program lx6; const n=15; var a:array[1..n] of integer; min,mid,top,bot,x,I:integer; find:Boolean; begin for I:=1 to n do read(a[i]); readln; writeln('input x to look for:');readln(x); top:=1;bot:=n;find:=false; repeat mid:=(top+bot) div 2; if (x=a[mid]) then begin writeln('find:',x:3,',it position is: ',mid:2); find:=true end else if (x<a[mid]) then bot:=mid-1 else if (x>a[mid]) then top:=mid+1 until ((bot<top)or find); if (not find )then writeln(x:3,'not been found.') end. 例 3:查找第 k 小元素 查找第 k 小元素即在 n 个元素中(未排序)找到第 k 小的元素。方法同快速排序,采用递归方式。 程序如下: program kspv; const n=7; type arr=array[1..n] of integer; var b:arr; i,k:integer; function p(s,t:integer):integer; var i,j,t1,x: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; p:=i; end; function find(s,t,k:integer):integer; var p1,q:integer; begin if s=t then find:=b[s] else begin p1:=p(s,t); q:=p1-s+1; if k<=q then find:=find(s,p1,k) else find:=find(p1+1,t,k-q); end; end; begin write('input data:'); for i:=1 to n do read(b[i]);readln; write('input k:');read(k); write('output data:'); writeln('kthsmall:=',find(1,n,k)); end. 四、字符串处理 例 1:乒乓球比赛
【题目描述】 华华通过以下方式进行分析,首先将比赛每个球的胜负列成一张表,然后分别计算在 11 分制和 21 分制下, 双方的比赛结果(截至记录末尾)。 比如现在有这么一份记录,(其中 W 表示华华获得一分,L 表示华华对手获得一分): WWWWWWWWWWWWWWWWWWWWWWLW 在 11 分制下,此时比赛的结果是华华第一局 11 比 0 获胜,第二局 11 比 0 获胜,正在进行第三局,当前比 分 1 比 1。而在 21 分制下,此时比赛结果是华华第一局 21 比 0 获胜,正在进行第二局,比分 2 比 1。如果一局 比赛刚开始,则此时比分为 0 比 0。 你的程序就是要对于一系列比赛信息的输入(WL 形式),输出正确的结果。 【输入格式】 每个输入文件包含若干行字符串(每行至多 20 个字母),字符串有大写的 W、L 和 E 组成,也许中间有若干个空 格。其中 E 表示比赛信息结束,程序应该忽略 E 之后的所有内容,E 后面可能有干扰文字。

【输出格式】 输出由两部分组成,每部分有若干行,每一行对应一局比赛的比分(按比赛信息输入顺序)。其中第一部分是 11 分制下的结果,第二部分是 21 分制下的结果,两部分之间由一个空行分隔。

【输入样例】 WWWWWWWWWWWWWWWWWWWW WWLWE

【输出样例】 11:0 11:0 1:1 21:0 2:1

program ssy; const name='table'; var top:longint; a:array[1..1000000]of char; procedure init; var ch:char; begin read(ch); begin if (ch='W')or(ch='L')then begin inc(top);a[top]:=ch;end; read(ch); end; end; procedure main(n:longint); var i,x,y:longint; begin x:=0;y:=0; for i:=1 to top do begin if a[i]='W'then inc(x) else inc(y); if (abs(x-y)>=2)and((x>=n)or(y>=n))then begin top:=0; while ch<>'E'do

writeln(x,':',y); x:=0;y:=0; end; end; writeln(x,':',y); end; begin assign(input,name+'.in');reset(input); assign(output,name+'.out');rewrite(output); init; main(11); writeln; main(21); close(input); close(output); end. 例 2:球星 【题目描述】 在 1000000000 年,足球在世界上依然很流行,在足球史上,曾经有过很多球星,人们想知道在 某个时期里最顶尖的 11 个足球运动员。现在给你一个足球运动员的名单,让你去完成这份工作,每个运 动员(年份,名字,能力)来表示。 【输入格式】 第一行包括一个整数 N(1<=N<=50000),表示运动员的总数,紧跟着的 N 行,每行描述一位球员。 0<=年份<=1000000000,名字的长度少于 15 个字母,0<=能力<=1000000000。输入保证没有两个名字是一 样。然后一行有一个整数 R,表示询问数(1<=R<=100000)。紧跟着的 R 行,每行包括两个整数 x 和 y(0<=x<=y<=1000000000),表示查询的时期的年份范围为[x,y]。 【输出格式】 对于每个询问,输出 11 个球员的名字,按球员的 ability 从高到低排序,如果一样,按年份从 低到高排序,如果还是一样,按姓名的字典序排序,如果查询的年份范围内的球员少于 11,则剩下的每行 都输出“XXX” 。在每个询问后输出一个空行。 【输入样例】 5 1 a 1

2 2 5 5 2 1 5

b c e d 2 5

2 6 50 50

【输出样例】 c b a XXX XXX XXX XXX XXX XXX XXX XXX d e XXX XXX XXX XXX XXX XXX XXX XXX XXX program football; type data=record aa:longint; ss:string; cc:longint; end; per=array[1..50000]of data; var p,q:per; temp:data; i,l,k,j,m,f:integer; s1:string; x,y,r,n:longint; procedure ygw(x,y:longint);

begin m:=0; for i:=1 to n do for j:=x to y do if p[i].aa=j then begin m:=m+1;q[m]:=p[i]; end; for i:=1 to m-1 do for j:=i+1 to m do begin if q[i].cc<q[j].cc then begin temp:=q[i];q[i]:=q[j];q[j]:=temp;end; if q[i].cc=q[j].cc then begin if q[i].aa<q[j].aa then begin temp:=q[i];q[i]:=q[j];q[j]:=temp;end; if q[i].aa=q[j].aa then begin if q[i].ss>q[j].ss then begin temp:=q[i];q[i]:=q[j];q[j]:=temp;end; end; end; end; for i:=1 to 11 do if q[i].ss='' then writeln(output,'XXX') else writeln(output,q[i].ss); fillchar(q,sizeof(q),0); writeln(output); end; begin assign(input,'foot.in'); assign(output,'foot.out'); reset(input); rewrite(output); readln(n); for i:=1 to n do begin readln(s1); l:=length(s1); k:=pos(' ',s1); val(copy(s1,1,k-1),p[i].aa); s1:=copy(s1,k+1,l); k:=pos(' ',s1); p[i].ss:=copy(s1,1,k-1); val(copy(s1,k+1,l),p[i].cc); end; readln(r); for f:=1 to r do begin readln(x,y); ygw(x,y); end;

close(input); close(output); end. 例 3:笨小猴 笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用 这种方法去选择选项的时候选对的几率非常大!这种方法的具体描述如下:假设 maxn 是单词中出现次数 最多的字母的出现次数,minn 是单词中出现次数最少的字母的出现次数,如果 maxn-minn 是一个质数,那 么笨小猴就认为这是个 Lucky Word,这样的单词很可能就是正确的答案。 输入说明:输入只有一行,是一个单词,其中只可能出现小写字母,并且长度小于 100。 输出说明: 输出共两行, 第一行是一个字符串, 假设输入的的单词是 Lucky Word, 那么输出“Lucky Word”, 否则输出“No Answer”;第二行是一个整数,如果输入单词是 Lucky Word,输出 maxn-minn 的值,否则 输出 0。 范例输入:范例 1:error;范例 2:Olymipic 范例输出 :范例 1:Lucky Word (换行)2 范例 2:No Answer(换行)0 解题思路:建立一个数组 m,用于存储 a 至 z 的 26 个字母在这个单词中的出现次数,然后用“打擂台”的 方法找出最大与最小的数 (皆不可以为 0) 然后调用函数, , 判断这俩个数的差是否为质数, 是则返回 true, 不是则返回 false,根据返回的的值,最后输出。 参考程序 1: program cx1; var s:string; b:array['a'..'z']of integer; i,max,min,l:integer; j:char; function zhishu(a:integer):boolean; var i:integer; begin zhishu:=true; if (a=0)or(a=1) then zhishu:=false; for i:=2 to trunc(sqrt(a)) do if a mod i=0 then zhishu:=false; end; begin readln(s); l:=length(s); fillchar(b,sizeof(b),0); for i:=1 to l do inc(b[s[i]]); max:=0; min:=maxint; for j:='a' to 'z' do if b[j]>0 then begin if b[j]>max then max:=b[j]; if b[j]<min then min:=b[j]; end;

if zhishu(max-min) then begin writeln('Lucky Word');writeln(max-min); end else begin writeln('No Answer');writeln('0'); end; readln; end. 参考程序 2: program cx2; var a:string; b:array[1..10000]of integer; i,j,max,min,l:integer; function zhishu(a:integer):boolean; var i:integer; begin zhishu:=true; if (a=0)or(a=1) then zhishu:=false; for i:=2 to trunc(sqrt(a)) do if a mod i=0 then zhishu:=false; end; begin readln(a); l:=length(a); for i:=1 to l do for j:=1 to l do if a[i]=a[j] then b[i]:=b[i]+1; max:=0; for i:=1 to l do if b[i]>max then max:=b[i]; min:=max; for i:=1 to l do if b[i]<min then min:=b[i]; if zhishu(max-min) then begin writeln('Lucky Word');writeln(max-min); end else begin writeln('No Answer');writeln('0'); end; readln; end. 五、搜索算法 例 1:八皇后问题

〖问题描述〗 在一个8×8的棋盘里放置8个皇后,要求每个皇后两两之间不相"冲"(在每一横列竖列斜列只有一个皇 后) 。 〖问题分析〗 这道题可以用递归循环来做,分别一一测试每一种摆法,直到得出正确的答案。主要解决以下几个问题: 1、冲突。包括行、列、两条对角线: (1)列:规定每一列放一个皇后,不会造成列上的冲突; (2)行:当第 I 行被某个皇后占领后,则同一行上的所有空格都不能再放皇后,要把以 I 为下标的标记 置为被占领状态; (3)对角线:对角线有两个方向。在同一对角线上的所有点(设下标为(i,j)) ,要么(i+j)是常数,要么 (i-j)是常数。因此,当第 I 个皇后占领了第 J 列后,要同时把以(i+j)、(i-j)为下标的标记置为被占领 状态。 2、数据结构。 (1)解数组 A。A[I]表示第 I 个皇后放置的列;范围:1..8 (2)行冲突标记数组 B。B[I]=0 表示第 I 行空闲;B[I]=1 表示第 I 行被占领;范围:1..8 (3)对角线冲突标记数组 C、D。 C[I-J]=0 表示第(I-J)条对角线空闲;C[I-J]=1 表示第(I-J)条对角线被占领;范围:-7..7 D[I+J]=0 表示第(I+J)条对角线空闲;D[I+J]=1 表示第(I+J)条对角线被占领;范围:2..16 〖算法流程〗 1、数据初始化。 2、从 n 列开始摆放第 n 个皇后(因为这样便可以符合每一竖列一个皇后的要求) ,先测试当前位置(n,m) 是否等于0(未被占领): 如果是,摆放第 n 个皇后,并宣布占领(记得要横列竖列斜列一起来哦),接着进行递归; 如果不是,测试下一个位置(n,m+1),但是如果当 n<=8,m=8 时,却发现此时已经无法摆放时,便要进行回 溯。 3、当 n>8 时,便一一打印出结果。 〖优点〗逐一测试标准答案,不会有漏网之鱼。 〖参考程序〗queen.pas ---------------------------------------------------------------------------program tt; var a:array [1..8] of integer; b,c,d:array [-7..16] of integer; t,i,j,k:integer; procedure print; begin t:=t+1; write(t,' '); for k:=1 to 8 do write(a[k],' '); writeln; end; procedure try(i:integer); var j:integer;

begin for j:=1 to 8 do {每个皇后都有 8 种可能位置} if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判断位置是否冲突} begin a[i]:=j; {摆放皇后} b[j]:=1; {宣布占领第 J 行} c[i+j]:=1; {占领两个对角线} d[i-j]:=1; if i<8 then try(i+1) {8 个皇后没有摆完,递归摆放下一皇后} else print; {完成任务,打印结果} b[j]:=0; {回溯} c[i+j]:=0; d[i-j]:=0; end; end; begin for k:=-7 to 16 do {数据初始化} begin b[k]:=0; c[k]:=0; d[k]:=0; end; try(1);{从第 1 个皇后开始放置} end. N 皇后问题: PROGRAM nqueen(input,output); CONST nmax=100; VAR x:ARRAY[1..nmax] OF integer; a:ARRAY[1..nmax] OF boolean; b:ARRAY[2..nmax*2] OF boolean; c:ARRAY[-nmax..nmax] OF boolean; count,n:integer; PROCEDURE print; VAR k:integer; BEGIN count:=count+1; FOR k:= 1 TO n DO write(x[k]:4); writeln; END; PROCEDURE try(i:integer); VAR

{存放每个皇后位置的数组} {用于表示该列是否可放置的数组} {用于表示正对角线位置是否可放置的数组} {用于表示反对角线位置是否可放置的数组}

j:integer; BEGIN FOR j:= 1 TO n DO IF a[j] AND b[i+j] and c[i-j] THEN BEGIN x[i]:=j; a[j]:=false; b[i+j]:=false; c[i-j]:=false; IF i<n THEN try(i+1) ELSE print; a[j]:=true; b[i+j]:=true; c[i-j]:=true; END{if} END;{try} BEGIN{mian} assign(input,'nqueen.in'); reset(input); assign(output,'nqueen.out'); rewrite(output); readln(n); count:=0; fillchar(a,sizeof(a),true); fillchar(b,sizeof(b),true); fillchar(c,sizeof(c),true); try(1); writeln(count); close(input); close(output); END.

{只有当三个位置都没有冲突时才可放置}

{若 n 个皇后没有放满,则递归放下一个}

{出栈时恢复状态}

例 2:有 N 个硬币(6<=N<=30)正面朝上排成一排,每次将 5 个硬币翻过来放在原位置,直到最后全部
硬币翻成反面朝上为止。 编程让计算机找出步数最少的翻法并把翻币过程及次数打印出来 (用 o 表示正面, *表示反面,?o?和?*?均为小写字母)。 输入: 一行,整数 N 输出: 如果有解,从步骤 0 开始输出各步骤,step 后面的步骤数为长度为两位的整数,如果无解,输出“no solution”。 样例输入 6 样例输出 step 0:oooooo

step 1:o***** step 2:oooo** step 3:ooo*** step 4:oo**** step 5:ooooo* step 6:****** 参考程序: type ss=array[1..5000] of 0..9; var n,m,open,closed,k:integer; a,b:ss;p:array[1..5000] of integer; function check(xx:integer):boolean; var i:integer; begin check:=true; for i:=1 to open do if xx=a[i] then check:=false; end; procedure print; var i,j,o,c,k,s:integer; a1,b1:ss; begin k:=(n div 5)-1; c:=p[open]; s:=0; for i:=1 to c do begin a1[i]:=a[i];b1[i]:=b[i]; end; write('step',s:2,': '); for o:=1 to n do write('o'); writeln; if k>0 then begin for o:=1 to k do begin s:=s+1; write('step',s:2,': '); for j:=1 to n-5*o do write('o'); for j:=1 to o*5 do write('*'); writeln; end; end; for j:=2 to c+1 do begin s:=s+1; write('step',s:2,': ');

for o:=1 to b1[j] do write('o'); for o:=1 to n-b1[j] do write('*'); writeln; end; halt; end; procedure inp; begin write('n='); readln(n); m:=(n mod 5)+5;k:=(n div 5)-1; a[1]:=0; b[1]:=m; p[1]:=0; end; procedure try; var i,x,y,x1,y1:integer; begin closed:=0;open:=1; repeat inc(closed); x:=a[closed]; y:=b[closed];{x 是反面朝上的硬币个数,y 是正面朝上的硬币个数} for i:=1 to 5 do if (i<=y) and (x>=5-i) then{i 是将硬币正面翻成反面的个数} begin y1:=y-i+5-i; x1:=x+i-5+i;{y1 是此次翻币之后正面朝上的硬币个数,x1 是此次翻币之后反面 朝上硬币个数} if check(x1) then{检查翻币之后反面朝上的个数是不是与前面各次翻币之后反面朝上的个数是 否相等,如果相等了,说明不能这样翻动,这样翻动之后会造成循环。} begin inc(open); a[open]:=x1; b[open]:=y1; p[open]:=closed;{a[open]是每一步翻币之后反面 朝上的硬币个数,b[open]是每一步翻币之后正面朝上的硬币个数,p[open]是翻币的次数。} if y1=0 then print;{当 y1=0 之后就说明翻动之后都是反面朝上了} end; end; until closed=open; end; begin inp; try; if closed=open then writeln('no solution'); readln; end. 例 3:分油问题:假设有 3 个油瓶,容量分别为 10,7,3(斤)。开始时 10 斤油瓶是满的,另外两个是空的, 请用这三个油瓶将 10 斤油平分成相等的两部分。 PASCAL 程序: Program lt9_2_2; uses crt;

const max=3000; v:array[1..3] of byte=(10,7,3); type node=record a:array[1..3] of byte; ft:integer; end; var o:array[1..max] of node; h,t,i,j,k:integer; function is_ans(h:integer):boolean; begin with o[h] do if ord(a[1]=5)+ord(a[2]=5)+ord(a[3]=5)=2 then is_ans:=true else is_ans:=false; end; function new_node(t:integer):boolean; var r:integer; begin r:=t; repeat dec(r); with o[t] do if (a[1]=o[r].a[1]) and (a[2]=o[r].a[2]) and (a[3]=o[r].a[3]) then begin new_node:=false;exit;end; until (r=1); new_node:=true; end; procedure print(r:integer); var b:array[1..30] of integer; t,l,p:integer; begin t:=0; while r>0 do begin inc(t);b[t]:=r; r:=o[r].ft; end; gotoxy(1,1); writeln('':5,v[1]:5,v[2]:5,v[3]:5); writeln('--------------------'); for l:=t downto 1 do begin write('[',t-l:2,'] ');

for p:=1 to 3 do write(o[b[l]].a[p]:5); writeln; end; halt; end; begin clrscr; with o[1] do begin a[1]:=10;a[2]:=0;a[3]:=0; end; h:=1;t:=2; repeat if is_ans(h) then print(h); for i:=1 to 3 do if o[h].a[i]>0 then for j:=1 to 3 do if (i<>j) and (o[h].a[j]<v[j]) then begin for k:=1 to 3 do o[t].a[k]:=o[h].a[k]; with o[t] do begin ft:=h; if o[h].a[i]>(v[j]-a[j]) then begin a[i]:=o[h].a[i]+a[j]-v[j];a[j]:=v[j]; end else begin a[j]:=a[j]+o[h].a[i];a[i]:=0; end; end; if new_node(t) then inc(t); end; inc(h); until (h>t); writeln('NO ANSWER!'); end. 参考程序 2: program BFS; const v:array[1..3] of integer= (3,7,10); //三种桶的容量。 type node=record

l:array[1..3] of longint;//三个水桶。 p:longint;//每个结点的父结点。 end; var i,j,head,tail:longint; t:boolean; //找到目标的标志。 a:array[0..100] of node; procedure init; var i,j:longint; begin fillchar(a,sizeof(a),0); t:=false; a[0].l[3]:=10; head:=-1; tail:=0; end; procedure pour(x,y:longint); var i,j:longint; begin if (a[head].l[x]=0) or t then exit; inc(tail); a[tail]:=a[head]; a[tail].p:=head; if a[tail].l[x]>v[y]-a[tail].l[y] then begin dec(a[tail].l[x],v[y]-a[tail].l[y]); a[tail].l[y]:=v[y]; end else begin inc(a[tail].l[y],a[tail].l[x]); a[tail].l[x]:=0; end; for i:=0 to tail-1 do //检查该状态是否出现过,是的话删除。 begin if a[i]=a[tail] then begin dec(tail); exit; end; end; if a[tail].l[3]=5 then t:=true; end; procedure main;

var i,j:longint; begin repeat inc(head); pour(1,2); //pour 函数的作用是尝试把 x 桶里的水倒入 y 桶,看能不能产生新的状态。 pour(2,1); pour(1,3); pour(3,1); pour(2,3); pour(3,2); until (a[tail].l[3]=5) or (tail=100); //当找到目标或者已经超出预定的搜索范围的时候退出。 end; procedure print; var c:array[1..100] of longint; i,j:longint; begin i:=0; while a[tail].p<>0 do begin inc(i); c[i]:=tail; tail:=a[tail].p; end; for j:=i downto 1 do writeln(a[c[j]].l[1],' ',a[c[j]].l[2],' ',a[c[j]].l[3]); end; begin init; main; print; end. 例 4:如图示半个象棋盘,马从 A 跳到 B 再不限步数跳回 A,输出步数。 首先去的最小步数就是回来的最小步数既然是广度优先,那要的必然是最短路径 program asdf; var x:array[1..4,1..2]of integer; a,b,c:array[1..100]of integer; i,j,x1,x2,y1,y2,t,w:integer; p,q:boolean; begin readln(x1,x2,y1,y2); x[1,1]:=1;x[1,2]:=2; x[2,1]:=1;x[2,2]:=-2; x[3,1]:=-1;x[3,2]:=2;

x[4,1]:=-1;x[4,2]:=-2; a[1]:=x1;b[1]:=x2;c[1]:=0; t:=1;w:=1;p:=false; repeat for i:=1 to 4 do if (x[i,1]+a[t]>0)and(x[i,2]+b[t]>0) then begin inc(w); a[w]:=x[i,1]+a[t]; b[w]:=x[i,2]+b[t]; c[w]:=c[t]+1; q:=false; for j:=1 to w-1 do begin if (a[w]=a[j])and(b[w]=b[j]) then q:=true; end; if q then dec(w); if (a[w]=y1)and(b[w]=y2) then begin p:=true;writeln(2*c[w]);break; end; end; inc(t); until p; end. 例 5:【八数码问题】
九宫格中有 8 个数码,其中只有一个空,规则是只能把一个数码移动到空的格子中,要求从一个初始状态 移动到一个目标状态所要花费的最少步数。如下图 初始状态 2 1 7 8 6 3 4 5

目标状态 1 8 7 2 6 5 3 4

【算法分析】 解决此类问题的办法是宽度搜索,深度搜索耗时太大无法接受。当需要移动的步数很多时,普通的宽度搜

索仍旧无法满足需要,需要对其进行优化。 这个问题也可以推广到流行的拼图游戏。

【具体步骤】 一、确定问题规模(考虑搜索的时间代价) 二、确定产生式规则(如果规则太多,则时间代价会很大) 三、套用经典宽度搜索框架写程序

【参考样例】 【输入】8no.in 2 0 3 1 4 6 7 5 8

1 2 3 4 5 6 7 8 0 【输出】8no.out 5 2 0 3 1 4 6 7 5 8 {下面为移动步骤}

0 2 3 1 4 6 7 5 8

1 2 3 0 4 6 7 5 8

1 2 3

4 0 6 7 5 8

1 2 3 4 5 6 7 0 8

1 2 3 4 5 6 7 8 0

参考程序: program eightno_bfs; const dir:array[1..4,1..2] of -1..1=((1,0),(-1,0),(0,1),(0,-1)); {产生式规则:0 向四个方向移动} max=200000; type t8no=array[1..3,1..3] of 0..8; {八数码数据结构,0 表示空格} tlist=record {结点类型} father:longint; dep:byte; x0,y0:byte; state:t8no; end; var source,target:t8no; {初始结点和目标结点} list:array[0..max] of tlist; {扩展出的中间结点序列} head,foot,best,i:longint; answer:longint; found:boolean; procedure init; {初始化过程} var x,y:byte; begin assign(input,'8no.in'); reset(input); assign(output,'8no.out'); rewrite(output); fillchar(list,sizeof(list),0); for x:=1 to 3 do {读入初始结点} begin

for y:=1 to 3 do read(source[x,y]); readln; end; readln; for x:=1 to 3 do {目标结点} begin for y:=1 to 3 do read(target[x,y]); readln; end; found:=false; head:=0; {队列初始化,队首指针 head,队尾指针 foot} foot:=1; with list[1] do {初始结点作为队列第一个结点} begin state:=source; dep:=0; father:=0; for x:=1 to 3 do for y:=1 to 3 do if state[x,y]=0 then begin x0:=x; y0:=y; end; end; end; procedure writea(a:t8no); {输出八数码矩阵过程} var i,j:integer; begin for i:=1 to 3 do begin for j:=1 to 3 do write(a[i,j],' '); writeln; end; writeln; end; function same(a,b:t8no):boolean; {比较八数码是否相同函数} var i,j:byte; begin same:=false; for i:=1 to 3 do for j:= 1 to 3 do

if a[i,j]<>b[i,j] then exit; same:=true; end; function notappear(newv:tlist):boolean; {判断扩展出的结点是否已在队列中的函数} var i:longint; begin notappear:=false; for i:=1 to foot do if same(newv.state,list[i].state) then exit; notappear:=true; end; procedure add(newv:tlist); {往队列中加入新结点过程} begin if notappear(newv) then begin inc(foot); list[foot]:=newv; end; end; procedure expand(index:longint;var n:tlist); {扩展结点过程} var i,x,y:integer; newv:tlist; begin for i:=1 to 4 do begin x:=n.x0+dir[i,1]; {应用规则计算新的 0 的位置} y:=n.y0+dir[i,2]; if (x>0) and (x<4) and (y>0) and (y<4) {判断应用规则后 0 的坐标是否超出范围,超过则 放弃该规则,否则扩展出新结点} then begin newv.state:=n.state; newv.state[x,y]:=0; newv.state[n.x0,n.y0]:=n.state[x,y]; newv.x0:=x; newv.y0:=y; newv.father:=index; newv.dep:=n.dep+1; add(newv); end; end; end; procedure print(index:longint); {递归打印路径}

var i,j:byte; begin if index=0 then exit; print(list[index].father); writea(list[index].state); end; begin{main} init; repeat inc(head); if same(list[head].state,target) {比较是否跟目标相同,相同则找到,否则扩展新结点} then begin found:=true; best:=list[head].dep; answer:=head; break; end; if list[foot].dep>15 {如果搜索树的层数大于 15 层,时间会变得非常慢,出超时提示} then begin writeln('OverTime!'); break; end; expand(head,list[head]); until (head>=foot) or (foot>max) or found; { writeln(head,' ',foot); for i:=1 to foot do writea(list[i].state); 看队列情况} if found then begin writeln(best); print(answer); end else writeln('No Answer'); close(input); close(output); end.

新课教学阶段
一、双向广度优先搜索算法 1.1 广度双向搜索的概念 所谓双向搜索指的是搜索沿两个方向同时进行: 正向搜索:从初始结点向目标结点方向搜索; 逆向搜索:从目标结点向初始结点方向搜索; 当两个方向的搜索生成同一子结点时终止此搜索过程。

1. 2 广度双向搜索算法 广度双向搜索通常有两种方法: 1. 两个方向交替扩展 2. 选择结点个数较少的那个方向先扩展. 方法 2 克服了两方向结点的生成速度不平衡的状态,明显提高了效率。 算法说明: 设置两个队列 c:array[0..1,1..maxn] of jid,分别表示正向和逆向的扩展队列。 设置两个头指针 head:array[0..1] of integer 分别表示正向和逆向当前将扩展结点的头指针。 设置两个尾指针 tail:array[0..1] of integer 分别表示正向和逆向的尾指针。 maxn 表示队列最大长度。 算法描述如下: 1.主程序代码 repeat {选择节点数较少且队列未空、未满的方向先扩展} if (tail[0]<=tail[1]) and not((head[0]>=tail[0])or(tail[0]>=maxn)) then expand(0); if (tail[1]<=tail[0]) and not((head[1]>=tail[1])or(tail[1]>=maxn)) then expand(1); {如果一方搜索终止,继续另一方的搜索,直到两个方向都终止} if not((head[0]>=tail[0])or(tail[0]>=maxn)) then expand(0); if not((head[1]>=tail[1])or(tail[1]>=maxn)) then expand(1); Until ((head[0]>=tail[0])or(tail[0]>=maxn)) And ((head[1]>=tail[1])or(tail[1]>=maxn)) 2.expand(st:0..1)程序代码如下: inc(head[st]; 取出队列当前待扩展的结点 c[st,head[st]] for i:=1 to maxk do begin if tail[st]>=maxn then exit; inc(tail[st]); 产生新结点; check(st);{检查新节点是否重复} end; 3.check(st:0..1)程序代码: for i:=1 to tail[st]-1 do if c[st,tail[st]]^.*=c[st,i]^.* then begin dec(tail[st]);exit end; bool(st);{如果节点不重复,再判断是否到达目标状态} 4.bool(st:0..1)程序代码: for i:=1 to tail[1-st] do if c[st,tail[st]]^.*=c[1-st,i]^.* then print(st,tail[st],i); {如果双向搜索相遇(即得到同一节点),则输出结果} 5.print(st,tail,k)程序代码: if st=0 then begin print0(tail);print1(k) end; else begin print0(k);print1(tail) end; 6.print0(m)程序代码: if m<>0 then begin print(c[0,m]^.f);输出 c[0,m]^.* end; {输出正方向上产生的结点} 7.print1(m)程序代码; n:=c[1,m]^.f

while m<>0 begin 输出 c[1,n]^.*; n:=c[1,n]^.f; end {输出反方向上产生的结点} 1.3 例题与习题 例 1:8 数码难题 : 2 8 3 1 2 3 1 6 4 -> 8 4(用最少的步数) 7 5 7 6 5 程序如下: program num8; const maxn=4000; type jid=record str:string[9]; f:0..maxn; dep:byte; end; bin=0..1; var c:array[0..1,1..maxn] of ^jid; head,tail:array[0..1] of integer; start,goal:string[9]; procedure init; var i,j:integer; begin start:='283164705'; goal:='123804765'; for i:=0 to 1 do for j:=1 to maxn do new(c[i,j]); c[0,1]^.str:=start; c[0,1]^.f:=0; c[0,1]^.dep:=0; c[1,1]^.str:=goal; c[1,1]^.f:=0; c[1,1]^.dep:=0; for i:=0 to 1 do begin head[i]:=0;tail[i]:=1;end; end; procedure print(st:bin;tail,k:integer); procedure print0(m:integer); begin if m<>0 then begin print0(c[0,m]^.f);writeln(c[0,m]^.str) end; end; procedure print1(m:integer); var n:integer; begin n:=c[1,m]^.f;

while n<>0 do begin writeln(c[1,n]^.str); n:=c[1,n]^.f end; end; begin if st=0 then begin writeln('step=',c[0,tail]^.dep+c[1,k]^.dep); print0(tail); print1(k);end else begin writeln('step=',c[0,k]^.dep+c[1,tail]^.dep); print0(k); print1(tail); end ; halt; end; procedure check(st:bin); procedure bool(st:bin); var i:integer; begin for i:=1 to tail[1-st] do if c[st,tail[st]]^.str=c[1-st,i]^.str then print(st,tail[st],i); end; var i:integer; begin for i:=1 to tail[st]-1 do if c[st,tail[st]]^.str=c[st,i]^.str then begin dec(tail[st]);exit end; bool(st); end; procedure expand(st:bin); var i,p0,p1,d:integer; str0,str1:string[9]; begin inc(head[st]); str0:=c[st,head[st]]^.str; d:=c[st,head[st]]^.dep; p0:=pos('0',str0); for i:=1 to 4 do begin if tail[st]>=maxn then exit; p1:=p0+2*i-5; if (p1 in [1..9]) and not ((p0=3) and (p1=4))and not((p0=4)and (p1=3)) and not((p0=6)and(p1=7))and not((p0=7)and(p1=6)) then begin inc(tail[st]); str1:=str0; str1[p0]:=str1[p1]; str1[p1]:='0'; c[st,tail[st]]^.str:=str1;

c[st,tail[st]]^.f:=head[st]; c[st,tail[st]]^.dep:=d+1; check(st); end; end; end; begin init; check(0); repeat if (tail[0]<=tail[1]) and not((head[0]>=tail[0])or(tail[0]>=maxn)) then expand(0); if (tail[1]<=tail[0]) and not((head[1]>=tail[1])or(tail[1]>=maxn)) then expand(1); if not((head[0]>=tail[0])or(tail[0]>=maxn)) then expand(0); if not((head[1]>=tail[1])or(tail[1]>=maxn)) then expand(1); Until((head[0]>=tail[0])or(tail[0]>=maxn))And((head[1]>=tail[1])or(tail[1]>=maxn)); writeln('No answer'); end. 1.4 双向广度优先搜索 广度优先搜索遵循从初始结点开始一层层扩展直到找到目标结点的搜索规则,它只能较好地解决状态不是 太多的情况,承受力很有限。如果扩展结点较多,而目标结点又处在较深层,采用前文叙述的广度搜索解 题,搜索量巨大是可想而知的,往往就会出现内存空间不够用的情况。双向搜索和 A 算法对广度优先的搜 索方式进行了改良或改造,加入了一定的“智能因素” ,使搜索能尽快接近目标结点,减少了在空间和时 间上的复杂度。 (1)搜索过程 有些问题按照广度优先搜索法则扩展结点的规则,既适合顺序,也适合逆序,于是我们考虑在寻找目 标结点或路径的搜索过程中,初始结点向目标结点和目标结点向初始结点同时进行扩展—,直至在两个扩 展方向上出现同一个子结点,搜索结束,这就是双向搜索过程。出现的这个同一子结点,我们称为相交点, 如果确实存在一条从初始结点到目标结点的最佳路径,那么按双向搜索进行搜索必然会在某层出现“相 交” ,即有相交点,初始结点一相交点一目标结点所形成的一条路径即是所求路径。 例如:移动一个只含字母 A 和 B 的字符串中的字母,给定初始状态为(a)表,目标状态为(b)表,给定 移动规则为:只能互相对换相邻字母。请找出一条移动最少步数的办法。 [AABBAA] [BAAAAB] (a) (b) 解题分析:从初始状态和目标状态均按照深度优先搜索扩展结点,当达到以下状态时,出现相交点,如 图 1(a),结点序号表示结点生成顺序。 双向扩展结点: 顺序 逆序 1 1 ___AABBAA___ BAAAAB 2 / \ 3 2 / \ 3 __ABABAA__ AABABA ABAAAB BAAABA 4 / |5 \ 6 7 / \ 8 4 /

ABBAAA BAABAA ABAABA AAABBA AABAAB AABAAB (a) 图1 (b) 顺序扩展的第 8 个子结点与逆序扩展得到的第 4 个子结点就是相交点,问题的最佳路径如图 2。 [AABBAA]—[AABABA]—[AABAAB]—[ABAAAB]—[BAAAAB] 图2 从搜索的结点来看,双向广度要简单得多。假设每一个子结点可以扩展的子结点数是 X,不计约束条 件,以完全 X 叉树计算,那么用广度优先搜索一个长度为 I 的最佳路径的解,共需要扩展结点 X(XL-1)÷ (X-1)。从双向搜索来看,设正个方向的搜索在第 y 层找到向交点,那么正向共搜索了 X(XY-1)÷(X-1), 逆向扩展的结点数为(XL-y-1)÷(X-1),两个方向共搜索了 X(XY+XL-Y-2)÷(X-1)。我们假设 L 为偶数, 则 Y=L/2 , 双 向 搜 索 扩 展 的 结 点 数 约 为 单 向 搜 索 的 2 ÷ (XL/2+1)*100 % , 相 对 减 少 (XL/2-1) ÷ (XL/2+1)*100%。 当然这里只是作个粗略的比较,事实上在其它一般情况下,双向搜索搜索量都要比单向搜索来的少。 (2)结点扩展顺序 双向扩展结点,在两个方向的扩展顺序上,可以轮流交替进行,但由于大部分的解答树并不是棵完全 树,在扩展完一层后,下一层则选择结点个数较少的那个方向先扩展,可以克服两个方向结点生成速度不 平衡的状态,明显提高搜索效率。 (3)数据结构 单向广度优先搜索需建立两个表 OPEN 和 CLOSED,用来存储生成结点和已扩展结点,双向搜索从两个 方向进行扩展,我们建立两个二维表 OPEN,CLOSED,OPEN[1],CLOSED[1], OPEN[2],CLOSED[2]分别存 储两个方向上的生成结点和已扩展结点,OPEN 仍然是具有“先进先出”的队列结构。为编程方便,我们采 用基于广度优先搜索算法的双向,建立三个二维指针:Q1,Q2,Q3 其作用如下: Q1[1],Q1[2]:分别指向两个方向上当前待扩展层的第一个结点。 Q2[1],Q2[2]:分别指两个方向上队尾新产生的结点。 Q3[1],Q3[2]:分别指向两个方向上下一层的第一个结点位置。 为了区分当前搜索方向,设方向标志: t=1 表示处于正向搜索,t=2 表示处于逆向搜索。 Fail—有一个方向搜索失败时,为真,并且结束搜索过程,否则为假。 I—全局变量,指向当前要扩展的结点。 (4)算法描述 Program DOUBFS; 初始化,初始结点,和目标结点分别进入 OPEN[1]和 OPEN[2]表; Q1[1]:=1;Q2[1]:=1;Q1[2]:=1;Q2[2]:=1; repeat if (Q2[1]-Q1[1])<=(Q2[2]-Q1[2]) then t:=1 else t:=2; for I:=Q1[t] to Q2[t] do EXPEND(t);{扩展第 1 个结点} Q1[t]:=Q3[t]; until(Q1[t]>Q2[t]); 其中过程 EXPEND(t)的结构如下:

Procedure expand(t:integer); Var j:integer; begin for j:=1 to n do {n 为最多后继状态数} begin 产生 i 点的第 j 个后继状态,将它加入到队尾(Q2[t]+1); if 新结点未与其上一层以上的所有点重复 then if isans(t) then [输出解;halt;] else else 将新点从队列中去掉;(Q2[t]-1) end; end; 判断是否是相交点的过程 isans(t)如下: function isans(t:integer):Boolean; var j,t1:integer; begin if t=1 then t1:=2 else t1:=1; isans:=false; forj:=Q1[t1] to Q2[t1] do if Q2[t]=j {Q2[t]新结点是相交点} then [isans:=true;exit]; end;(5)例题应用 【例 1】魔方问题 在魔方风靡全球之后,Rubik 先生发明了它的简化版——魔板。魔板由 8 个同样大小的方块组成,每 个方块的颜色均不相同,本题中以数字 1—8 分别表示,可能出现在魔板的任一位置,任一时刻魔板的状 态可以用方块的颜色序列表示:从魔板的左上角开始,按顺时针方向依次写下各方块的颜色代号,得到的 数字序列即可表示此时魔板的状态。 例如,序列(1,2,3,4,5,6,7,8)表示题中魔板的初始状态。 1 2 3 4 8 7 6 5 对于魔板,可以施加三种不同的操作,分别以 A,B,C 标识。 具体操作方法如下: A:上下行互换,如上图可以变换为状态 87654321 B:每行同时循环右移一格,如上图可以变换为 41236785 C:中间 4 个方块顺时针旋转一格,上图可以变换为 17245368。 应用这三种基本操作,可以由任一状态达到任意另一状态。 子任务 A: 请编一程序,对于输入的一个目标状态,寻找一种操作的序列,使得从初始状态开始,经过此操作序 列后使该魔板变为目标状态。 子任务 B: 如果你的程序寻找到的操作序列在 300 步以内,会得到子任务 B 的分数。 输入数据: 文件名 INPUT.TXT,第一行包含 8 个以一个空格相隔的正整数,表示目标状态。 输出数据: 输出文件名为 OUTPUT.TXT,在第一行输出你的程序寻找到的操作序列的步数 L,随后 L 行是相应的 操作序列,每行的行首写一个字符,代表相应的操作。 【算法分析】

A.空间复杂度 如果解的步数为 n,则状态表示空间约占 3n。 B.基本算法 本题是典型的广度优先算法题,很自然的想到能否构造启发算法。但本题不同于八数码,很 难找到一个估价函数。 因为每一种状态的达到都有三种本质不同的方法, 因此在计算某一状态的估价值时, 容易将状态各个数字的最少移动步数重复计算,或忽略计算,不能够构造出一个恰当函数 f*使得 f*< f。 因此不宜采用启发算法得出最优解,而只能得可行解。现在考虑双向广度优先搜索。 双向搜索与单向广度搜索相比的优点在于节省了存储空间, 避免搜索出更多的无用结点, 提高丁搜索速度, 如果采用动态数组存储(655 350Byte)可以做到大约 21~22 步,甚至可以更多。 【参考程序】 Program Rubic; Uses Crt; Const n=8; input = 'input.txt'; Type dar = record f: integer; d: array[1..n] of Integer; End; Var Cab: array[1..2,1..7500] of ^dat; dat1,dat2: dat; Procedure Init; Var f: text; i,i: Integer; Begin assign(f, input); reset(f); new(cab[1,1]); for I:=1 To n do read(f,cab[1,I]^.d[i]); cab[1,1]^.f := 0; readln(f); new(cab[2,1 ] ); for I := 1 tondo read(f,cab[2,1]^.d[i]); readln(f); cab[2,1]^.f := 0; End; Function Check(x,y: Integer) :boolean; Var i,j,k: Integer; ok: Boolean; Begin for i:= 1 to y-1 do Begin

forj := 1 to n do if cab[x,i]^.d[j] < > dat1.d[j] then Begin ok := true; Break; End else Ok:= false; if not ok then break; End; Check := ok; End; Function CheckOut(X,Y: Integer;Var a: Integer): Boolean; Var i,j,k: Integer; ok: Boolean; Begin a:=0; fori := 1 to y do Begin for j := 1 to n do if cab[x,i]A.d[j] < > dat1.d[j] then Begin ok := true; Break; End else Ok: = false; if not ok then Begin a:= i; break; End; End; CheckOut := ok; End; Procedure Print(a,b,c: Integer); Var i,j,k,l: Integer; s1,s2: array[1..30] of Integer; x,y: Integer; Begin fillchar(s1,sizeof(s1), 0); fillchar(s2,sizeof(s2) ,0); if a = 1 then Begin i:=1; j:=2; End else Begin

i:=2; j:=1; End; k:= O; Repeat inc(k); s1[k] := b; b := cab[i,b]^.f; Until b = 0; l:= 0; Repeat inc(l); s2[l] := c; c := cab[j,c]^.f; Until c = 0; if a = 1 then begin for x := k downto 1 do Begin for y := 1 to n do write(cab[1,s1[x]]^.d[y]: 3); if y mod 4 = 0 then writeln; End; writeln('-----'); Readln; End; for x := 2 to l do Begin for y := 1 to n do Begin write(cab[2,s2[x]]^.d[y]: 3); if y mod 4 = 0 then writdn; End; writeln('-----'); Readln; End; End else Begin for x := l downto 1 do Begin for y := 1 to n do write(cah[1,s2[x]]^.d[y]: 3); if y mod 4 = 0 then writdn; End; writeln('-----');

Readln; End; for x := 2 to k do Begin for y:= 1 to n do begin write(cab[2,s1[x]]^.d[y]: 3); if y mod 4 = 0 then writeln; End; writeln('-----'); Readln; End; End; Halt; End; Procedure Double; Var i,j: array[1..2] of Integer; Out: Boolean; k,l,kk,s: Integer; i[1] := 1; i[2] := 1; j[1] := 2; j[2] := 2; Out := false; repeat kk:=2; k:=1; {--1--} dat1.d := Cab[k,i[k]]^.d; for l := 1 to 4 do Begin dat1.d[l] := dat1.d[l+4]; dat1.d[l+4] := cab[k,i[k]]^.d[l]; End; dat1.f := i[k]; if Check(k,j[k]) then Begin new(mb[kd[k]]); mb[kd[k]]^:= dat1; inc(j[k]); if Not CheckOut(kk,j[kk] - 1,s) then Print(k,j[k] - 1 ,s); End; {--2--} dat1.d := Cab[k,i[k]]^.d; dat1.d[3]: = dat1.d[2];

dat1.d[2] := dat1.d[5]; dat1.d[5] := dat1.d[6]; dat1.d[6] := cab[k,i[k]]^.d[3]; dat1.f: = i[k]; if Check(k,j[k]) then Begin new(cab[k,j[k]]); cab[k,j[k]]^ := dat1; inc(j[k]); if NOt CheckOut(kk,j[kk] - 1,s) then Print(k,j[k] - 1,s); End; {--3--} dat1.d:= Cab[k,i[k] ]^.d; dat1.d[4]: = dat1.d[3]; dat1.d[3]: = dat1.dj2]; dat1.d[2] := dat1.d[1]; dat1.dj1] := cab[k,i[k]]^.d[4]; dat1.f := i[k]; if Check(k,j[k]) then Begin new(cab[k,j[k]]); cab[k,j[k]]^:= dat1; inc(j[k]); if Not CheckOut(kk,j[kk]- 1,s) then Print(k,j[k] - 1,s); End; Inc(i[k]); kk:= 1; k:=2; {--1--} dat1.d := Cab[k,i[k]]^.d; for l := 1 to 4 do Begin dat1.d[l] := dat1.d[l+4]; dat1.d[l+4] := cab[k,i[k]]^.d[l]; End; dat1.f:= i[k]; if Check(k,j[k]) then Begin new(cab[k,j[k] ]); cab[k,j[k]]^:= dat1; inc(j[k]); if Not CheckOut(kk,j[kk] - 1 ,s) then Print(k,j[k] - 1 ,s); End; {--2--} dat1.d := Cab[k,i[k]]^.d; daft. d[2] : = dat1. d[3];

dat1.d[3] := dat1.d[6]; dat1.d[6]: = dat1.d[5]; dat1.d[5] := cab[k,i[k]]^.d[2]; dat1.f: = i[k]; if Check(k,j[k]) then Begin new(cab[k,j[k]]); cab[k,j[k]]^:= dat1; ine(j[k]); if Not CheckOut(kk,j[kk] - 1 ,s) then Print(k,j[k] - 1 ,s); End; {---3---} dad.d:= Cab[k,i[k]]^.d; dat1.d[1] := dat1.d[2]; dat1.d[2] := dat1.d[3]; dat1.d[3] := dat1. d[4]; dat1.dj4] := cab[k,i[k] ]^.d[1]; dat1.f := i[k]; if Check(k,j[k]) then Begin new(cab[k,j[k]]); cab[k,j[k]]^ := dat1; inc(j[k]); if Not CheckOut(kk,j[kk] - 1,s) then Prim(k,j[k] - 1,s); End; Inc(i[k]); until Out; End; Begin INit; clrscr; Double; End. 练习 1: 广度搜索虽然可以得到最优解,但是其空间消耗增长太快。但如果从正反两个方向进行广度搜索,理想 情况下可以减少二分之一的搜索量,从而提高搜索速度。 范例:有 N 个黑白棋子排成一派,中间任意两个位置有两个连续的空格。每次空格可以与序列中的某两个 棋子交换位置,且两子的次序不变。要求出入长度为 length 的一个初始状态和一个目标状态,求出最少的 转化步数。 问题分析:该题要求求出最少的转化步数,但如果直接使用广度搜索,很容易产生数据溢出。但如果从初 始状态和目标状态两个方向同时进行扩展,如果两棵解答树在某个节点第一次发生重合,则该节点所连接 的两条路径所拼成的路径就是最优解。 对广度搜索算法的改进: 1。添加一张节点表,作为反向扩展表。 2。在 while 循环体中在正向扩展代码后加入反向扩展代码,其扩展过程不能与 正向过程共享一个 for 循环。

3。在正向扩展出一个节点后,需在反向表中查找是否有重合节点。反向扩展时与之相同。 对双向广度搜索算法的改进: 略微修改一下控制结构,每次 while 循环时只扩展正反两个方向中节点数目较少的一个,可以使两边 的发展速度保持一定的平衡,从而减少总扩展节点的个数,加快搜索速度。 二、拓扑排序
2.1AOV 网 在现代化管理中,人们常用有向图来描述和分析一项工程的计划和实施过程,一个工程常被分为多个小的子工 程,这些子工程被称为活动(Activity),在有向图中若以顶点表示活动,有向边表示活动之间的先后关系,这 样的图简称为 AOV 网。如下图是计算机专业课程之间的先后关系:

基础知识课程应先于其它所有课程,pascal 语言课程应先于数据结构。 2.2 拓扑排序 在 AOV 网中为了更好地完成工程,必须满足活动之间先后关系,需要将各活动排一个先后次序即为拓扑排序。 如上图的拓扑排序 基础知识;Pascal;数据结构;离散数学。或 基础知识;离散数学 Pascal;数据结构。 拓扑排序的方法和步骤: (1)在图中选一个没有前趋的顶点并输出之 (2)删除该顶点及由它发出的各边,直到图中不存在没有前趋的顶点为止。 若图中存在回路,拓扑排序无法进行。 以下是将一 AOV 网进行拓扑排序的算法: 网采用邻接矩阵 A 表示,若 a[i,j]=1,表示活动 i 先于 j,a[i,j]=0,表示活动 i 与 j 不存在先后关系。 (1)计算各顶点的入度 (2)找入度为零的点输出之,删除该点,且与该点关联各点的入度减 1 (3)若所有顶点都输出完毕。 程序如下: program tppv; const maxn=100; var map:array[1..maxn,1..maxn] of byte; into:array[1..maxn] of byte; n,i,j,k:byte; procedure init; var i,j:integer; begin read(n); for i:=1 to n do

for j:=1 to n do begin read(map[i,j]); inc(into[j]); end; end; begin init; for i:=1 to n do begin j:=1; while (j<=n)and(into[j]<>0) do inc(j); write(j,' '); into[j]:=255; for k:=1 to n do if map[j,k]=1 then dec(into[k]); end; end.

2.3 应用举例与练习 例:士兵排队问题: 有 N 个士兵(1<=N<=100),编号依次为 1,2,...,N.队列训练时,指挥官要把士兵从高到矮排成一行,但指挥官 只知道“1 比 2 高,7 比 5 高”这样的比较结果。 输入文件:第一行为数 N(N〈=100);表示士兵的个数。以下若干行每行两个数 A,B 输出文件:给出一个合法的排队序列。 程序如下: program tppv; const maxn=100; var map:array[1..maxn,1..maxn] of byte; into:array[1..maxn] of byte; 表示 A 高于 B。

n,i,j,k:byte; fp:text; procedure init; var i,j:integer; begin assign(fp,'tp.txt'); reset(fp); readln(fp,n); fillchar(map,sizeof(map),0); fillchar(into,sizeof(into),0); while not(seekeof(fp)) do begin readln(fp,i,j); map[i,j]=1 ; inc(into[j]); end; close(fp); end; begin init; for i:=1 to n do begin j:=1; while (j<=n)and(into[j]<>0) do inc(j); write(j,' '); into[j]:=255; for k:=1 to n do if map[j,k]=1 then dec(into[k]); end; end.

三、关键路径(A0E 网)
3.1 AOE 网 在现代化管理中,人们常用有向图来描述和分析一项工程的计划和实施过程,一个工程常被分为多个小的子工 程,这些子工程被称为活动(Activity),在带权有向图中若以顶点表示事件,有向边表示活动,边上的权值表 示该活动持续的时间,这样的图简称为 AOE 网,如下图。

AOE 网具有以下性质: (1)只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始。 (2)只有在进入某点的各有向边所代表的活动都已结束,该顶点所代表的时事件才能发生。 可以将上图假想一个工程有 6 项活动,网中 5 个顶点,分别表示 5 个事件,边上的权值分别表示各项活动所需 要的时间,事件 v1 表示工程开始,事件 v3 表示活动 3 和 4 完成后,活动 5 可以开始,事件 v4 表示活动 2 完成 活动 4 和活动 6 开始,v5 表示活动 1 完成活动 3 开始,事件 v2 表示工程结束。 3. 2 关键路径及其算法 1.关键路径: 在 AOE 网中所关心的问题是完成整个工程至少需要多少时间和哪些活动是影响整个工程进度的关键。 由于 AOE 网中的某些活动能够平行地进行,故完成整个工程所需的时间是从开始顶点到结束顶点的最长路径长 度(路径上的权值和)最长路径叫关键路径。如上述工程的关键路径是 1->4->3->2,关键路径长度为 2+7+6=15, 关键活动是 a2,a4,a5。 2.关键路径算法 1: 1)将网拓扑排序 2)以拓扑序列划分阶段 3)用动态规划求解关键路径 程序如下: program gjlu; const maxn=10; var map:array[1..maxn,1..maxn] of integer; a:array[1..maxn] of 0..maxn; b:array[1..maxn] of integer; c:array[1..maxn] of 0..maxn; n:integer; procedure init; var i,j:integer; begin readln(n); for i:=1 to n do for j:=1 to n do

read(map[i,j]); fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); end; function tporder:boolean; var i,j,k:integer; into:array[1..maxn] of byte; begin tporder:=false; fillchar(into,sizeof(into),0); for i:=1 to n do for j:=1 to n do if map[i,j]>0 then inc(into[j]); for i:=1 to n do begin j:=1; while (j<=n)and(into[j]<>0) do inc(j); if j>n then exit; a[i]:=j; into[j]:=$ff; for k:=1 to n do if map[j,k]>0 then dec(into[k]); end; tporder:=true; end; procedure calc; var i,j:integer; begin b[a[1]]:=0;c[a[1]]:=0; for i:=2 to n do for j:= 1 to i-1 do if b[a[j]]+map[a[j],a[i]]>b[a[i]] then begin b[a[i]]:=b[a[j]]+map[a[j],a[i]];c[a[i]]:=a[j]; end; end; procedure print; var i,j,k:integer; d:array[1..maxn] of 0..maxn; begin writeln('long=',b[a[n]]); k:=c[a[n]];i:=0; while k<>0 do begin i:=i+1;d[i]:=k;k:=c[k] end; for j:=i downto 1 do write(d[j],' writeln(a[n]) ');

end; begin init; if tporder then begin calc; print; end; end. 3.关键路径算法 2: 若结点的排列已经过拓扑排序,即序号前面的结点会影响序号后面结点的活动,如下图。

可使用如下算法: (1)求活动最早可以开始的时间 eet[1]:=0;eet[k]:=max(eet[j]+r[j,k]) (2)求活动最迟应该开始的时间 et[n]:=eet[n];et[k]:=min(et[j]-r[k,j]); (3) 关键路径通过点 J,具有如下的性质:eet[j]=et[j] 程序如下: program gao7_6; var i,j,n,max,min,w,x,y:integer; r:array[1..20,1..20] of integer; eet,et:array[1..20] of integer; begin readln(n); for i:=1 to n do for j:=1 to n do r[i,j]:=-1; readln(x,y,w); while x<>0 do begin r[x,y]:=w; readln(x,y,w); end; eet[1]:=0; for i:=2 to n do begin max:=0; for j:=1 to n do if r[j,i]<>-1 then if r[j,i]+eet[j]>max then max:=r[j,i]+eet[j]; eet[i]:=max;

end; et[n]:=eet[n]; for i:=n-1 downto 1 do begin min:=10000; for j:=1 to n do if r[i,j]<>-1 then if et[j]-r[i,j] <min then min=et[j]-r[i,j]; et[i]:=min; end; for i:=1 to n-1 do if et[i]=eet[i] then write(i,'->'); write(n);readln; end. 3.3练习 1。某工厂发现厂里的机器在生产产品时需要消耗大量的原材料,现在厂里想找出消耗原材料最大的一条生产线 路加以改进以降低成本。 已知厂里的生产线路是一个有向的无环网络, n 个机器分别代表网络中的 n 个结点, 有 弧〈i,j〉(i〈j)表示原材料从机器 i 传到机器 j 的损耗数量。 输入文件:第一行两个整数 n,m(n〈=100,m〈=100)分别表示网络中的结点的个数与弧数,第二行至 m+1 行,每行三个整数 a,b,c,表示弧〈a,b〉的损耗为 c。 输出文件:只一个整数,损耗最大线路的损耗量。

四、动态规划 4.1 数字三角形 【题目描述】 如下所示三角形: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 请编一个程序计算从顶至底的某处的一条路径,使该路径所经过的数字的总和最大。 规则如下: 1.每一步可沿直线向下或右斜线向下走; 2.1<=三角形行数<=200; 3.三角形中的数字为整数 0,1,...,99。 【输入格式】 第一行为一个自然数,表示数字三角形的行数 n,接下来的 n 行表示一个数字三角形。 【输出格式】 仅有一个数,即要求的最大总和。 【输入样例】 5 7

3 8 2 4

8 1 0 7 4 4 5 2 6 5

【输出样例】 30 参考程序: program datasjx; const maxn=100; var fin,fout:text; n,i,j:integer; a:array[1..maxn,1..maxn] of integer; f:array[1..maxn,1..maxn] of integer; begin assign(fin,'f1.in'); assign(fout,'f2.out'); reset (fin); rewrite(fout); readln(fin,n); for i:=1 to n do for j:=1 to i do read(fin,a[i,j]); for i:=1 to n do f[n,i]:=a[n,i]; for i:=n-1 downto 1 do for j:=1 to i do if f[i+1,j]>f[i+1,j+1] then f[i,j]:=a[i,j]+f[i+1,j] else f[i,j]:=a[i,j]+f[i+1,j+1]; writeln(fout,f[1,1]); close(fin); close(fout); end. 4.2 采药 【问题描述】 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为 师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩 子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段 时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价 值最大。” 如果你是辰辰,你能完成这个任务吗? 【输入格式】 输入的第一行有两个整数 T(1 <= T <= 1000)和 M(1 <= M <= 100) ,用一个空格隔开,T 代表总共能 够用来采药的时间,M 代表山洞里的草药的数目。接下来的 M 行每行包括两个在 1 到 100 之间(包括 1

和 100)的整数,分别表示采摘某株草药的时间和这株草药的价值。 【输出格式】 输出包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。 【样例输入】 70 3 71 100 69 1 12 【样例输出】 3 v[i,j]表示在 j 时间内可以采摘 1 到 i 株草药的最大价值: 如果时间允许(j>=a[i])并且可以采摘第 i 株草药时,有 v[i,j]=max{v[i-1,j],v[i-1,j-a[i]]} 如果时间不允许(j<a[i]) ,表示不能采摘第 i 株草药 v[i,j]=v[i-1,j]; 参考程序: var t,m,i,j:integer; a,b:array[ 0..100]of integer; v:array[ 0..100,0..1000]of integer; function max(m,n:integer):integer; begin if m>n then max:=m else max:=n; end; begin readln(t,m); for i:=1 to m do readln(a[i],b[i]); for i:=1 to m do for j:=1 to t do if j>=a[i] then v[i,j]:=max(v[i-1,j],b[i]+v[i-1,j-a[i]]) else v[i,j]:=v[i-1,j]; writeln(v[m,t]); end. 4.3 花瓶插花问题 【题目描述】 你想以最美观的方式布置花店的橱窗。你有 F 束花,每束花的品种都不一样,同时至少有同样数量 的花瓶。它们被按顺序排成一排,花瓶的位置是固定的,并从左到右,从 1 到 V 编号,编号为 V 的花瓶 在最右边。花束可以移动,并且每束花用 1 到 F 的整数唯一标识。标识花束的整数决定了花束在花瓶中的 排列的顺序,如果 i<J,则花束 I 必须放在花束 J 左边的花瓶中。例如,假设杜鹃花的标识数为 1,秋海 棠的标识数为 2,康乃馨的标识数为 3,所有的花束在放入花瓶时必须保持其标识数的顺序,即:杜鹃花 必须放在秋海棠左边的花瓶中。秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目, 则多余的花瓶必须空,即每个花瓶只能放一束花。每一个花瓶的形状和颜色也不同,因此,当各个花瓶中 放入不同的花束时,会产生不同的美学效果,并以美学值(一个整数)来表示,空花瓶的美学值为 0。在 上述例子中,花瓶与花束不同的搭配所具有的美学值,可以用如下的表格表示:

花 瓶 1 2 3 4 5

1 (杜鹃花) 7 23 -5 -24 16

2 (秋海棠) 5 21 -4 10 23

3 (康乃馨) -21 5 -4 -20 20

根据表格,杜鹃花放在花瓶 2 中,会显得非常好看,但若放你在花瓶 4 中则显得很难看。为了取 得最佳美学效果,必须保持花束顺序的条件下,使花的摆放取得最大美学值,如果具有最大美学值的摆放 不止一种,则输出任意一种。 【输入格式】 第一行包含两个数: F, V。(1<=F<=100, F<=V<=100 ) 接下来的 F 行:包含 V 个数,输入 Aij 矩阵。 (-50<=Aij<=50,Aij 为第 i 束花放在第 j 个花瓶中的 美学值) 【输出格式】 第一行输出最大美学值 第二行给出方案 【输入样例】 3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20 【输出样例】 53 2 4 5

【解题指导】 类似 0/1 背包问题。 a[i,j]=花 i 放入瓶 j 的美学价值 s[i,j]=前 i 束花放入前 j 个花瓶内的最大美学价值 决策:花 i 放不放在第 j 个瓶中。 (1)放:s[i,j]=s[i-1,j-1]+a[i,j]

(2)不放:s[i,j]=s[i,j-1] 取 s[i,j]=max{s[i-1,j-1]+a[i,j],s[i,j-1]} 【程序】 var ping,num,i,j,d:integer; a:array[0..100,0..100]of integer; s:array[0..100,0..100]of integer; b:array[1..100]of integer; function max(a1,b1:integer):integer; begin if a1>b1 then max:=a1 else max:=b1; end; begin readln (num,ping); fillchar(a,sizeof(a),0); fillchar(s,sizeof(s),0); for i:=1 to num do for j:=1 to ping do read(a[i,j]); for i:=1 to num do for j:=i to ping do if i=j then s[i,j]:=s[i-1,j-1]+a[i,j] else s[i,j]:=max(s[i-1,j-1]+a[i,j],s[i,j-1]); writeln (s[num,ping]); fillchar(b,sizeof(b),0); i:=num; j:=ping; d:=0; while i>=1 do begin while s[i,j]=s[i,j-1] do begin dec(j); end; inc(d); b[d]:=j; dec(i); dec(j); end; for i:=d downto 1 do write(b[i],' '); end. *4.4 矩阵取数游戏 【问题描述】 帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的 n*m 的矩阵,矩阵中的每个元素 aij,均 为非负整数。游戏规则如下: 1.每次取数时须从每行各取走一个元素,共 n 个。m 次后取完矩阵所有元素; 2.每次取走的各个元素只能是该元素所在行的行首或行尾; 3.每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分=被取走的元素值*2^i,其中 i 表

示第 i 次取数(从 1 开始编号); 4. 游戏结束总得分为 m 次取数得分之和。 帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。 【输入格式】 输入文件 game.in 包括 n+1 行: 第 1 行为两个用空格隔开的整数 n 和 m。 第 2-n+l 行为 n*m 矩阵,其中每行有 m 个用单个空格隔开的非负整数。 【输出格式】 输出文件 game.out 仅包含 1 行,为一个整数,即输入矩阵取数后的最大得分。 【输入输出样例 1】 输入: 2 3 1 2 3 3 4 2 输出: 90 【输入输出样例 l 解释】 第 1 次:第 1 行取行首元素,第 2 行取行尾元素,本次得分为 1+2^1+2*2^1=6 第 2 次:两行均取行首元素,本次得分为 2*2^2+3*2^2=20 第 3 次:得分为 3*2^3+4*2^3=56。总得分为 6+20+56=82 【输入输出样例 2】 输入: 1 4 4 5 0 5 输出: 122 【输入输出样例 3】 输入: 2 10 96 56 54 46 86 12 23 88 80 43 16 95 18 29 30 53 88 83 64 67 输出: 316994 参考程序 1: program game; const maxnum=100; jinwei=1000000000; type arr=array[1..4] of longint; var i,j,k,l:integer; m,n:longint; ans:arr; data:array[1..100,1..100] of integer; f:array[0..maxnum,0..maxnum,1..4] of longint; temp1,temp2:arr; procedure max(a,b:arr);

var k:integer; temp:arr; begin for k:=4 downto 1 do begin if a[k]>b[k] then begin temp:=a;break; end else if a[k]<b[k] then begin temp:=b;break; end; temp:=a; end; for k:=1 to 4 do f[i,j][k]:=temp[k]; end; procedure plus2(a,i,j:integer;var temp:arr); var k:integer; begin fillchar(temp,sizeof(temp),0); temp[1]:=(f[i,j][1]+a) shl 1; for k:=2 to 4 do begin temp[k]:=temp[k-1] div jinwei+f[i,j][k] shl 1; temp[k-1]:=temp[k-1] mod jinwei; end; end; procedure plusans(i,j:integer); var k:integer; begin for k:=1 to 4 do begin ans[k]:=ans[k]+f[i,j][k]; if ans[k]>=jinwei then begin ans[k+1]:=ans[k+1]+ans[k] div jinwei; ans[k]:=ans[k] mod jinwei; end; end; end; procedure writeans; var k,j:integer; maxnum:longint; begin maxnum:=jinwei div 10; for i:=4 downto 1 do if ans[i]<>0 then begin

write(ans[i]);break; end; if (i=1) and (ans[i]=0) then write('0'); for k:=i-1 downto 1 do begin for j:=1 to 8 do begin if ans[k] div maxnum=0 then write('0'); maxnum:=maxnum div 10; end; write(ans[k]); maxnum:=jinwei div 10; end; writeln; end; begin assign(input,'game.in');assign(output,'game.out'); reset(input);rewrite(output); readln(n,m); for i:=1 to n do begin for j:=1 to m do read(data[i,j]); readln; end; fillchar(ans,sizeof(ans),0); for k:=1 to n do begin fillchar(f,sizeof(f),0); for l:=1 to m do for i:=1 to m-l+1 do begin j:=i+l-1; plus2(data[k,i],i+1,j,temp1); plus2(data[k,j],i,j-1,temp2); max(temp1,temp2); { f[i,j]:=max(2*(data[k,i]+f[i+1,j]),2*(data[k,j]+f[i,j-1]));} end; plusans(1,m); end; writeans; close(input);close(output); end. 参考程序 2: program gao; type arr=array[0..80] of longint; var i,j,k,n,m:integer; f:array[-1..82,-1..82] of arr; a:array[0..81,0..81] of integer;

s2:array[0..80] of arr; ss,sum,a1,a2,a3,a4:arr; function max(a,b:arr):arr; var z:integer; begin if a[0]>b[0] then begin max:=a; exit; end; if b[0]>a[0] then begin max:=b; exit; end; for z:=a[0] downto 1 do begin if a[z]>b[z] then begin max:=a; exit; end; if b[z]>a[z] then begin max:=b; exit; end; end; max:=a; end; function jia(a,b:arr):arr; var z,l:integer; begin if a[0]>b[0] then l:=a[0] else l:=b[0]; if l=0 then l:=1; for z:=1 to l do begin a[z+1]:=a[z+1]+(a[z]+b[z]) div 10000; a[z]:=(a[z]+b[z]) mod 10000; end;

jia:=a; if a[l+1]<>0 then jia[0]:=l+1 else jia[0]:=l; end; function cheng(b:integer;a:arr):arr; var l,z:integer; begin l:=a[0]; if l=0 then l:=1; for z:=1 to l do a[z]:=a[z]*b; for z:=1 to l do begin a[z+1]:=a[z+1]+a[z] div 10000; a[z]:=a[z] mod 10000; end; while a[l+1]<>0 do begin inc(l); a[l+1]:=a[l] div 10000; a[l]:=a[l] mod 10000; end; cheng:=a; cheng[0]:=l; end; begin readln(n,m); fillchar(a,sizeof(a),0); for i:=1 to n do begin for j:=1 to m do read(a[i,j]); readln; end; s2[1][1]:=2; s2[1][0]:=1; for i:=2 to m do s2[i]:=cheng(2,s2[i-1]); fillchar(f,sizeof(f),0); fillchar(sum,sizeof(sum),0); for k:=1 to n do begin

for i:=0 to m do for j:=m+1 downto i+1 do begin a1:=cheng(a[k,i],s2[i+m-j+1]); a2:=cheng(a[k,j],s2[i+m-j+1]); a3:=jia(f[i-1,j],a1); a4:=jia(f[i,j+1],a2); f[i,j]:=max(a3,a4); end; ss:=f[0,1]; for i:=1 to m-1 do ss:=max(ss,f[i,i+1]); sum:=jia(sum,ss); end; write(sum[sum[0]]); for i:=sum[0]-1 downto 1 do begin if sum[i]<10 then write('000'); if (sum[i]>=10) and (sum[i]<100) then write('00'); if (sum[i]>=100) and (sum[i]<1000) then write('0'); write(sum[i]); end; writeln; end. 参考程序 3: program game; type st=array[0..30] of longint; var ans:st;f:array[1..80,1..80] of st;a:array[1..80] of longint; m,n:longint; procedure add(var x:st;y,z:st); var temp,i:longint; begin temp:=0; if y[0]>z[0] then x[0]:=y[0] else x[0]:=z[0]; for i:=1 to x[0] do begin temp:=y[i]+z[i]+temp; x[i]:=temp mod 10000; temp:=temp div 10000; end; if temp>0 then begin inc(x[0]); x[x[0]]:=temp;end; end;

procedure mul(var x:st); var temp,i:longint; begin temp:=0; for i:=1 to x[0] do begin temp:=x[i]*2+temp; x[i]:=temp mod 10000; temp:=temp div 10000; end; while temp>0 do begin inc(x[0]);x[x[0]]:=temp mod 10000;temp:=temp div 10000;end; end; procedure plus(var x:st;y:st;z:longint); var i:longint; begin x:=y;inc(x[1],z);i:=1; while x[i]>=10000 do begin x[i+1]:=x[i] div 10000+x[i+1]; x[i]:=x[i] mod 10000; inc(i); if x[0]<i then x[0]:=i; end; end; function compare(a,b:st):boolean; var i:longint; begin if a[0]>b[0] then exit(true); if a[0]<b[0] then exit(false); for i:=a[0] downto 1 do if a[i]>b[i] then exit(true) else if a[i]<b[i] then exit(false); exit(false); end; procedure dp; var i,j:longint;max,min:st; begin fillchar(f,sizeof(f),0); for i:=1 to m do begin f[i,i][0]:=1;f[i,i][1]:=a[i]*2;end; for i:=m-1 downto 1 do for j:=i+1 to m do begin plus(max,f[i+1,j],a[i]);

mul(max); plus(min,f[i,j-1],a[j]); mul(min); if compare(min,max) then max:=min; f[i,j]:=max; end; add(ans,ans,f[1,m]); end; procedure re; var i,j:longint; begin readln(n,m); for i:=1 to n do begin for j:=1 to m do read(a[j]); readln; dp; end; end; procedure print; var i:longint; begin write(ans[ans[0]]); for i:=ans[0]-1 downto 1 do begin write(ans[i] div 1000 mod 10); write(ans[i] div 100 mod 10); write(ans[i] div 10 mod 10); write(ans[i] mod 10); end; end; begin re;print; end.

专题复习阶段
一、高精度计算 1.1 保留 100 位有效数字 【题目描述】 输入任意两个整数 a,b(a,b 均在长整型范围内),计算 a/b 的结果,保留 100 位有效数字,最后一位要 求四舍五入。

【输入格式】 两个数 a,b 【输出格式】 a/b 的商,保留 100 位有效数字 【输入样例】 129 13 【输出样例】 9.92307692307692307692307692307692307692307692307692307692307692307692307692307692307692307 6923076923 参考程序: Program yxsz; var x:array[1..101] of longint; a,b,c,r,l,i:longint; begin assign(input,'xiao.in');reset(input); assign(output,'xiao.out');rewrite(output); readln(input,a,b); c:=a div b; write(output,c,'.'); l:=0; while c<>0 do begin inc(l);c:=c div 10;end; r:=a mod b; for i:=1 to 101-l do begin r:=r*10; x[i]:=r div b; r:=r mod b; end; if x[101-l]>=5 then inc(x[100-l]); i:=100-l; while x[i]=10 do begin inc(x[i-1]); x[i]:=0; dec(i); end; for i:=1 to 100-l do write(output,x[i]); close(input); close(output); end.

1.2 2^k 进制数 【题目描述】 设 r 是个 2^k 进制数,并满足以下条件: (1)r 至少是个 2 位的 2^k 进制数。 (2)作为 2^k 进制数,除最后一位外,r 的每一位严格小于它右边相邻的那一位。 (3)将 r 转换为 2 进制数 q 后,则 q 的总位数不超过 w。 在这里,正整数 k(1≤k≤9)和 w(k<W≤30000)是事先给定的。 问:满足上述条件的不同的 r 共有多少个? 我们再从另一角度作些解释:设 S 是长度为 w 的 01 字符串(即字符串 S 由 w 个“0”或“1”m 组成) 对应于上述条件(3)中的 q。将 S 从右起划分为若干个长度为 k 的段,每段对应一位 2k 进制的 ,S 数,如果 S 至少可分成 2 段,则 S 所对应的二进制数又可以转换为上述的 2k 进制数 r。 例:设 k=3,w=7。则 r 是个八进制数(23=8) 。由于 w=7,长度为 7 的 01 字符串按 3 位一段分,可分 为 3 段(即 1,3,3,左边第一段只有一个二进制位) ,则满足条件的八进制数有: 2 位数:高位为 1:6 个(即 12,13,14,15,16,17) ,高位为 2:5 个,?,高位为 6:1 个(即 67) 。 共 6+5+?+1=21 个。 3 位数:高位只能是 1,第 2 位为 2:5 个(即 123,124,125,126,127) ,第 2 位为 3:4 个,?, 第 2 位为 6:1 个(即 167) 。共 5+4+?+1=15 个。 所以,满足要求的 r 共有 36 个。 【输入格式】 输入文件只有 1 行,为两个正整数,用一个空格隔开: k w 【输出格式】 输出文件为 1 行,是一个正整数,为所求的计算结果,即满足条件的不同的 r 的个数(用十进制数表示) , 要求最高位不得为 0,各数字之间不得插入数字以外的其他字符(例如空格、换行符、逗号等) 。 (提示:作为结果的正整数可能很大,但不会超过 200 位) 【输入样例】 3 7 【输出样例】 36 参考程序: program Joshua; const e=1000000000; type arr=array[0..22]of longint; var f,now:array[1..512]of arr; ans:arr; i,j,k,l,m,n,w,max:longint; function add(x,y:arr):arr; var z,v:longint; begin if x[0]>y[0] then z:=x[0] else z:=y[0];

fillchar(add,sizeof(add),0); for v:=1 to z do begin add[v+1]:=add[v]+x[v]+y[v]; add[v]:=add[v+1] mod e; add[v+1]:=add[v+1] div e; end; inc(z); while add[z]=0 do dec(z); add[0]:=z; end; BEGIN readln(k,w); n:=(w div k)+1; for i:=1 to 1 shl k-1 do begin f[i,0]:=1; f[i,1]:=1 shl k-i; end; w:=w-k; max:=1 shl k; while (w>0) and (max>0) do begin dec(max); if (w<=k)and(1 shl w-1<max) then max:=1 shl w-1; w:=w-k; now[max]:=f[max+1]; for i:=max-1 downto 1 do now[i]:=add(f[i+1],now[i+1]); ans:=add(ans,now[1]); f:=now; end; write(ans[ans[0]]); for i:=ans[0]-1 downto 1 do begin j:=trunc(ln(ans[i])/ln(10)); for l:=1 to 8-j do write('0'); write(ans[i]); end; END. 1.3 高精度运算之求 n! [分析与算法选择]: N!=1*2*3*??*N,通过普通的循环或递归可以求出 N 比较小的情况: t:=1; for I:=1 to n do t:=t*I;

如 t 定义成长整型,最大可以求出 12!。要求大于 1000 的整数的阶乘,只有让计算机模拟人工进行运算, 先来看一个算术式子 12345*543: 12345 * 543 ------------------37035 49380 61725 ------------------6703335 数学运算大家都会,可以归结为以下两点: (1)一个数乘以另一个数可能会产生进位,如 5*3=15,同一位上为 5,进位为 1; (2)当乘数超过 9 时数可以分步相乘后相加,12345*543=12345*3+12345*40+12345*500。 程序设计时也是紧扣这两点,一是进位问题,二是拆分乘数问题,将每一步的运行结果的每一位放在数组 里, 即一个数组的一个下标变量只存放一位数。 这样就可能尽可能大地进行运算了。 使用循环来进行运算, 由(N-1)!计算 N!,一步步地往下进行运算。如用数组 a 来存放结果,因为乘数要进行拆分,每一步的 结果不能再放在 a 里了,所以要用另外一个数组来存放中间结果,如计算 12345 的阶乘时,假设 12344! 已存放在 a 里,先让 a 的每一个变量乘以 5 并考虑进位放在 b 里,而乘 40 时不要再用新的数组来存放, 直接往 b 里增加就行了,后而也是这样;最后拆分的所有数字都乘过了,再将 b 的值传递给 a,进行下一 轮运算。 [程序清单]: program example11_3; var a,b:array[1..30000] of byte; n,i,j,t,len,s:integer; {len 记录阶乘结果的位数,S 存放拆分乘数后某位数字右边数字个数} begin readln(n); len:=1; a[1]:=1; {开始 1!=1,结果只有一位数字} for i:=2 to n do begin t:=i; {t 临时存放 I 的值,然后对 t 进行拆分} s:=0; {先从最低位开始,所以右边数字个数为 0} while t>0 do begin for j:=1 to len do begin b[j+s]:=a[j]*(t mod 10)+b[j+s]; {a 数组的某一位跟拆分后的数字相乘结果加到对应的 b 里去,考虑到位数因素,b 的下标值比 a 大 s} b[j+s+1]:=b[j+s+1]+b[j+s] div 10; {向上进位} b[j+s]:=b[j+s] mod 10; {进位后还原成 0 到 9 的值} end; t:=t div 10; s:=s+1; end; len:=len+s; {先假设结果的位数增加 S} while b[len]=0 do len:=len-1; {去掉高位的 0} for j:=1 to len do

begin a[j]:=b[j]; b[j]:=0;end; {将 b 的值传递给 a 并将 b 清 0} end; write(n,'!='); for j:=len downto 1 do write(a[j]); writeln; end. 1.4 高精度开根 【题目描述】 你所在的工作组正在编写一套高精度科学计算的软件,一些简单的部分如高精度加减法、乘除法早已写完 了,现在就剩下你所负责的部分:实数的高精度开 m 次根。 因为一个有理数开根之后可能得到一个无理数,所以这项工作是有较大难度的。你现在要做的只是这项工 作的第一步:只对自然数进行开整数次根,求出它的一个非负根,并且不考虑结果的小数部分,只要求把 结果截断取整即可。 你的程序需要根据给定的输入,给出符合题意的输出: 输入包括需要开根的次数,以及被开根的整数; 你需要根据输入计算出它的非负根取整后的结果。 【输入】 有两行,每行都有一个整数,并且输入中没有多余的空格: 第一行有一个正整数 m (1 <= m <= 50),表示要开的根次; 第二行有一个整数 n (0<=n <= 10^10000),表示被开根的数。 【输出】 有一行,包括一个数,即为开根取整后的结果。 【输入样例】 3 1000000000 【输出样例】 1000 【提示】 样例说明: 对于输入示例,需要做的是把 1,000,000,000 开 3 次根。

二、动态规划 2.1 传纸条 【题目描述】 小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学 安排做成一个 m 行 n 列的矩阵, 而小渊和小轩被安排在矩阵对角线的两端, 因此, 他们就无法直接交谈了。 幸运的是, 他们可以通过传纸条来进行交流。 纸条要经由许多同学传到对方手里, 小渊坐在矩阵的左上角, 坐标(1,1),小轩坐在矩阵的右下角,坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递,从小 轩传给小渊的纸条只可以向上或者向左传递。 在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩给他回复。班里每个同学都可以帮他们 传递,但只会帮他们一次,也就是说如果此人在小渊递给小轩纸条的时候帮忙,那么在小轩递给小渊的时 候就不会再帮忙。反之亦然。 还有一件事情需要注意,全班每个同学愿意帮忙的好感度有高有低(注意:小渊和小轩的好心程度没 有定义,输入时用 0 表示) ,可以用一个 0-100 的自然数来表示,数越大表示越好心。小渊和小轩希望尽 可能找好心程度高的同学来帮忙传纸条,即找到来回两条传递路径,使得这两条路径上同学的好心程度只

和最大。现在,请你帮助小渊和小轩找到这样的两条路径。 (massage.pas/c/cpp) 【输入格式】 输入文件 message.in 的第一行有 2 个用空格隔开的整数 m 和 n,表示班里有 m 行 n 列(1≤m,n≤50) 。 接下来的 m 行是一个 m*n 的矩阵,矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度。每行 的 n 个整数之间用空格隔开。 【限制】 30%的数据满足:1≤m,n≤10 100%的数据满足:1≤m,n≤50 【输出格式】 输出文件 message.out 共一行,包含一个整数,表示来回两条路上参与传递纸条的学生的好心程度之和的 最大值。 【输入样例】 3 3 0 3 9 2 8 5 5 7 0 【输出样例】 34 2.2 能量项链 【题目描述】 在 Mars 星球上,每个 Mars 人都随身佩带着一串能量项链。在项链上有 N 颗能量珠。能量珠是一颗有 头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记 一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是 Mars 人吸收能量的一种器官)的作用, 这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 m, 尾标记为 r,后一颗能量珠的头标记为 r,尾标记为 n,则聚合后释放的能量为 m*r*n(Mars 单位) ,新产 生的珠子的头标记为 m,尾标记为 n。 需要时, Mars 人就用吸盘夹住相邻的两颗珠子, 通过聚合得到能量, 直到项链上只剩下一颗珠子为止。 显然, 不同的聚合顺序得到的总能量是不同的, 请你设计一个聚合顺序, 使一串项链释放出的总能量最大。 例如:设 N=4,4 颗珠子的头标记与尾标记依次为(2,3) (3,5) (5,10) (10,2)。我们用记号⊕表 示两颗珠子的聚合操作,(j⊕k)表示第 j,k 两颗珠子聚合后所释放的能量。则第 4、1 两颗珠子聚合后释 放的能量为: (4⊕1)=10*2*3=60。 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3)=10*2*3+10*3*5+10*5*10=710。 【输入格式】 输入文件 energy.in 的第一行是一个正整数 N(4≤N≤100) ,表示项链上珠子的个数。第二行是 N 个用空 格隔开的正整数,所有的数均不超过 1000。第 i 个数为第 i 颗珠子的头标记(1≤i≤N) ,当 i 至于珠子 的顺序,你可以这样确定:将项链放到桌面上,不要出现交叉,随意指定第一颗珠子,然后按顺时针方向 确定其他珠子的顺序。

【输出格式】 输出文件 energy.out 只有一行,是一个正整数 E(E≤2.1*109) ,为一个最优聚合顺序所释放的总能量。 【输入样例】 4 2 3 5 10 【输出样例】 710 2.3 金明的预算方案 【题目描述】 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让 他高兴的是,妈妈昨天对他说: “你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过 N 元钱 就行” 。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主 件的,下表就是一些主件与附件的例子: 主件 附件 电脑 打印机,扫描仪 书柜 图书 书桌 台灯,文具 工作椅 无 如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有 0 个、1 个或 2 个附 件。附件不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的 N 元。于是,他把每件 物品规定了一个重要度,分为 5 等:用整数 1~5 表示,第 5 等最重要。他还从因特网上查到了每件物品的 价格(都是 10 元的整数倍) 。他希望在不超过 N 元(可以等于 N 元)的前提下,使每件物品的价格与重要 度的乘积的总和最大。 设第 j 件物品的价格为 v[j],重要度为 w[j],共选中了 k 件物品,编号依次为 j1,j2,??, jk,则所求的总和为:v[j1]*w[j1]+v[j2]*w[j2]+ ?+v[jk]*w[jk]。 (其中*为乘号)请你帮助金明设计 一个满足要求的购物单。 【输入格式】 输入文件的第 1 行,为两个正整数,用一个空格隔开: N m 其中 N(<32000)表示总钱数,m(<60)为希望购买物品的个数。 ) 从第 2 行到第 m+1 行,第 j 行给出了编号为 j-1 的物品的基本数据,每行有 3 个非负整数 v p q (其中 v 表示该物品的价格(v<10000) 表示该物品的重要度(1~5) 表示该物品是主件还是附件。 ,p ,q 如果 q=0,表示该物品为主件,如果 q>0,表示该物品为附件,q 是所属主件的编号) 【输出格式】 输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值 (<200000) 。 【输入样例】 1000 5 800 2 0 400 5 1

300 5 1 400 3 0 500 2 0 【输出样例】 2200 【解题指导】 “每个主件可以有0个,1个或2个附件” 。也就是说对于一套物品(包含主件,所有的附件) ,我们 称为一个属类,对一个属类的物品的购买方法,有以下5种: 1.一个都不买 2.主件 3.主件+附件1 4.主件+附件2 5.主件+附件1+附件2 这五种购买方法也是唯一的五种方法, 也就是说对一属类的物品, 我们只有上述的5种购买方法。 于 是我们很自然的就会想到把物品按物品的属类捆在一起考虑。这样我们把物品的属类作为 dp 的状态。可 以得到如下的 dp 方程: f[i,j]=max{f[i-1,j]; f[i-1,j-v[i,0]]+v[i,0]*w[i,0]; f[i-1,j-v[i,0]-v[i,1]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]; f[i-1,j-v[i,0]-v[i,2]]+v[i,0]*w[i,0]+v[i,2]*w[i,2]; f[i-1,j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]+v[i,2]*w[i,2];} 需要注意的是必须对输入数据进行重新处理,使之按属类重新编号。 最后注意题目中还有一个条件: “每件物品都是 10 元的整数倍” ,也就是说我们先可以把价格都除以 10,总钱数也除以 10,这样就可以少循环 10 倍,不过最后的结果记得要乘上 10。 2.4 过河 题目描述】 在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨 厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达 的点看成数轴上的一串整点:0,1,??,L(其中 L 是桥的长度) 。坐标为 0 的点表示桥的起点,坐标为 L 的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是 S 到 T 之间的任 意正整数(包括 S,T) 。当青蛙跳到或跳过坐标为 L 的点时,就算青蛙已经跳出了独木桥。 题目给出独木桥的长度 L,青蛙跳跃的距离范围 S,T,桥上石子的位置。你的任务是确定青蛙要想过 河,最少需要踩到的石子数。 对于 30%的数据,L <= 10000; 对于全部的数据,L <= 10^9。 【输入格式】 输入的第一行有一个正整数 L(1 <= L <= 10^9) ,表示独木桥的长度。第二行有三个正整数 S,T,M,分 别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其中 1 <= S <= T <= 10,1 <= M <= 100。 第三行有 M 个不同的正整数分别表示这 M 个石子在数轴上的位置(数据保证桥的起点和终点处没有石子) 。 所有相邻的整数之间用一个空格隔开。 【输出格式】

输出只包括一个整数,表示青蛙过河最少需要踩到的石子数。 【输入样例】 10 2 3 5 2 3 5 6 7 【输出样例】 2 2.5 球游戏 【题目描述】 上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传球游戏。 游戏规则是这样的:n 个同学站成一个圆圈,其中的一个同学手里拿着一个球,当老师吹哨子时开始 传球,每个同学可以把球传给自己左右的两个同学中的一个(左右任意) ,当老师再次吹哨子时,传球停 止,此时,拿着球没传出去的那个同学就是败者,要给大家表演一个节目。 聪明的小蛮提出一个有趣的问题:有多少种不同的传球方法可以使得从小蛮手里开始传的球,传了 m 次以后,又回到小蛮手里。两种传球的方法被视作不同的方法,当且仅当这两种方法中,接到球的同学按 接球顺序组成的序列是不同的。比如有 3 个同学 1 号、2 号、3 号,并假设小蛮为 1 号,球传了 3 次回到 小蛮手里的方式有 1->2->3->1 和 1->3->2->1,共 2 种。 【输入格式】 输入文件共一行,有两个用空格隔开的整数 n,m(3<=n<=30,1<=m<=30) 。 【输出格式】 输出文件共一行,有一个整数,表示符合题意的方法数。 【输入样例】 3 3 【输出样例】 2

综合练习阶段
1、花生采摘 【题目描述】 鲁宾逊先生有一只宠物猴,名叫多多。这天,他们两个正沿着乡间小路散步,突然发现路的告示牌上 贴着一张小小的纸条:“欢迎免费品尝我种的花生!——熊字”。 鲁宾逊先生和多多都很开心, 因为花生正是他们的最爱。 在告示牌背后, 路边真的有一块花生田, 花生植株整齐地排列成矩形网格(如图 1)。有经验的多多一眼就能看出,每棵花生植株下的花生有多少。 为了训练多多的算术,鲁宾逊先生说:“你先找出花生最多的植株,去采摘它的花生;然后再找出剩下的 植株里花生最多的,去采摘它的花生;依此类推,不过你一定要在我限定的时间内回到路边。”

我们假定多多在每个单位时间内,可以做下列四件事情中的一件: 1) 从路边跳到最靠近路边(即第一行)的某棵花生植株; 2) 从一棵植株跳到前后左右与之相邻的另一棵植株; 3) 采摘一棵植株下的花生; 4) 从最靠近路边(即第一行)的某棵花生植株跳回路边。 现在给定一块花生田的大小和花生的分布,请问在限定时间内,多多最多可以采到多少个花生? 注意可能只有部分植株下面长有花生,假设这些植株下的花生个数各不相同。 例如在图 2 所示的花生田里,只有位于(2,5),(3,7),(4,2),(5,4)的植株下长有花生,个数分 别为 13,7,15,9。沿着图示的路线,多多在 21 个单位时间内,最多可以采到 37 个花生。 【输入格式】 输入的第一行包括三个整数,M,N 和 K,用空格隔开;表示花生田的大小为 M*N(1<=M,N<=20),多多采花生 的限定时间为 K(0<=K<=1000)个单位时间。接下来的 M 行,每行包括 N 个非负整数,也用空格隔开;第 i+1 行的第 j 个整数 Pij(0<=Pij<=500)表示花生田里植株(i,j)下花生的数目,0 表示该植株下没有花生。 【输出格式】 输出包括一行,这一行只包含一个整数,即在限定时间内,多多最多可以采到花生的个数。 【输入样例】 6 7 21 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 【输出样例】 37 参考程序: program peanuts; var a:array[0..20,0..20]of integer; m,n,k,step,i,j,x,y,x1,y1,sum:integer;

yes:boolean; begin assign(input,'peanuts.in'); reset(input); assign(output,'peanuts.out'); rewrite(output); readln(input,m,n,k); for i:=1 to m do begin for j:=1 to n do read(input,a[i,j]); end; x:=0;y:=0;yes:=true;sum:=0; repeat x1:=0;y1:=0; for i:=1 to m do for j:=1 to n do if a[i,j]>a[x1,y1] then begin x1:=i;y1:=j end; if y=0 then y:=y1; step:=abs(x-x1)+abs(y-y1)+x1+1; if (k<step)or(a[x1,y1]=0)then yes:=false; if yes then begin sum:=sum+a[x1,y1]; k:=k-abs(x-x1)-abs(y-y1)-1; x:=x1;y:=y1;a[x,y]:=0; end; until yes=false; writeln(output,sum); close(input); close(output); end. 2、旅行家的预算(贪心) 【题目描述】 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城 市之间的距离 d1、汽车油箱的容量 c(以升为单位) 、每升汽油能行驶的距离 d2、出发点每升汽油价格 p 和沿途油站数 n(1≤n≤100) ,油站 I 离出发点的距离 d[I]、每升汽油价格 p[I]。 【输入格式】 输入共 n+1 行,第一行为 d1,c,d2,p,n,以下 n 行,每行两个数据,分别表示该油站距出发点的距离 d[I] 和该油站每升汽油的价格 p[I]。两个数据之间用一个空格隔开。 【输出格式】 一行,输出最少费用。 计算结果四舍五入至小数点后两位。 如果无法到达目的地,则输出-1。

【输入样例】 275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2 【输出样例】 26.95 参考程序: var n,j,k,min1,min2:integer; d1,d2,c,rest,cost,need:real; p,d:array[0..101] of real; begin assign(input,'test.in'); assign(output,'text.out'); reset(input); rewrite(output); readln(d1,c,d2,p[0],n); d[n+1]:=d1; for j:=1 to n do readln(d[j],p[j]); k:=0; rest:=0; cost:=0; repeat j:=k;min1:=0;min2:=0; while (j<=n) and (d[j+1]-d[k]<=c*d2) do begin j:=j+1; if (min1=0) and (p[j]<p[k]) then min1:=j; if (min2=0) or (p[j]<p[min2]) then min2:=j; end; if j=k then begin writeln(-1);halt; end; if min1>0 then begin need:=(d[min1]-d[k])/d2; cost:=cost+p[k]*need; rest:=0; k:=min1; end else begin if c*d2<=d[n+1]-d[k] then need:=c-rest else need:=(d[n+1]-d[k])/d2-rest;

cost:=cost+need*p[k]; rest:=c-(d[min2]-d[k])/d2; k:=min2; end; until k=n+1; writeln(output,cost:0:2); close(input); close(output); end. 3、纪念品分组 【题目描述】 元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念 品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪 念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的 数目最少。 你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。 【输入格式】 输入文件包含 n+2 行: 第 1 行包括一个整数 w,为每组纪念品价格之和的上限。 第 2 行为一个整数 n,表示购来的纪念品的总件数。 第 3~n+2 行每行包含一个正整数 pi (5 <= pi <= w),表示所对应纪念品的价格。 【输出格式】 输出文件仅一行,包含一个整数,即最少的分组数目。 【输入样例】 100 9 90 20 20 30 50 60 70 80 90 【输出样例】 6 参考程序: var a,l:array[0..30000]of longint; b,c,d,e,f,g,h,i,j,k,lk:longint; procedure qs(z,y:longint); var m,n,o:longint;

begin o:=a[z]; m:=z; n:=y; repeat while a[m]<o do m:=m+1; while a[n]>o do n:=n-1; if m<=n then begin a[0]:=a[m]; a[m]:=a[n]; a[n]:=a[0]; m:=m+1; n:=n-1; end; until m>n; if z<n then qs(z,n); if m<y then qs(m,y); end; begin assign(input,'group.in'); reset(input); assign(output,'group.out'); rewrite(output); readln(b); readln(c); for d:=1 to c do readln(a[d]); qs(1,c); e:=c+1; d:=0; while d<e do begin d:=d+1; e:=e-1; if a[d]+a[e]<=b then begin f:=f+1; l[f]:=a[d]+a[e]; a[d]:=0; a[e]:=0; end else begin f:=f+1; l[f]:=a[e]; d:=d-1; a[e]:=0; end; end; e:=0;

for d:=1 to c do if l[d]<>0 then e:=e+1; writeln(e); close(input); close(output); end. 4、排队接水 【题目描述】 有 n 个人在一个水龙头前排队接水,加入每个人接水的时间为 Ti,请编程找出这 n 个人排队的一种顺 序,使得 n 个人的平均等待时间最小 【输入格式】 输入文件 water.in 共两行,第一行为 n,第二行分别表示 n 个人的接水时间 T1,T2,...Tn。每个数据之间 有一个空格。 【输出格式】 输出文件 water.out 有两行,第一行为一种排队顺序,即 1 到 n 的一种排列,第二行为这种排列方案下的 平均等待时间(输出结果精确到小数点后两位) 【输入样例】 10 56 12 1 99 1000 234 33 55 99 812 【输出样例】 3 2 7 8 1 4 9 6 10 5 291.90 参考程序: type rtype=record num,data:longint; end; var i,j,n:longint; total:int64; x:real; a:array [1..10000] of rtype; procedure qsort(l,r:longint); var i,j,mid:longint; temp:rtype; begin i:=l; j:=r; mid:=a[(i+j) div 2].data; repeat while a[i].data<mid do inc(i); while a[j].data>mid do dec(j); if i<=j then begin

temp:=a[i]; a[i]:=a[j]; a[j]:=temp; inc(i); dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end; begin assign(input,'water.in'); assign(output,'water.out'); reset(input); rewrite(output); readln(n); for i:=1 to n do begin read(a[i].data); a[i].num:=i; end; readln; qsort(1,n); for i:=1 to n do for j:=1 to i-1 do total:=total+a[j].data; x:=total/n; for i:=1 to n do write(a[i].num,' '); writeln; writeln(x:0:2); close(input); close(output); end. 5、数字排序 【题目描述】 给 你 两 个 数 列 A=(a1,a2,a3,......,an) 和 B(b1,b2,b3,......,bm) , 把 ai ( 1<=i<=n) 和 bj(1<=j<=m)乘起来,得到一个新的有 m*n 个数的数列。把这个序列排列成非递减数列,然后请找出排在 第 K 位的数。 【输入格式】 输入有多组数据。 每组数据的第一行包含三个整数:n(1<=n<=10000),m(1<=m<=10000),k(1<=k<=m*n). 第二行包含 n 个整数,表示数列 A。 第三行包含 m 个整数,表示数列 B。

所有数列 A 和 B 里的数字范围是[0, 10000]。 每组数据之后有一空行。 【输出格式】 每组数据输出一行,为答案。 【输入样例】 1 3 3 1 3 2 1 3 3 7 1 2 3 1 2 3 【输出样例】 3 6 参考程序: program yy1; var f1,f2:text; a,b,c,k:integer; i,j,l,t,k1:integer; a1,b1,c1:array[1..10000] of integer; begin assign(input,'sort.in'); assign(output,'sort.out'); reset(input); rewrite(output); while not eof(input) do begin read(input,a,b,c); for i:=1 to a do read(input,a1[i]); for i:=1 to b do read(input,b1[i]); if a=0 then break; k:=1; for i:=1 to a do begin for j:=1 to b do begin c1[k]:=a1[i]*b1[j];k:=k+1; for l:=1 to k-1 do if c1[k-1]<c1[l] then begin

t:=c1[k-1]; for k1:=k-2 downto l do c1[k1+1]:=c1[k1]; c1[l]:=t; break; end; end; end; writeln(output,c1[c]); end; close(input); close(output); end. 6、不幸运数字 题目描述 对一些中国人来说,4 就不是一个幸运数字。在这个问题中,我们定义一个整数,如果它含有数字 4, 那么它就是一个不幸运数字,例如 4,412,1944。 那么在范围[M,N]里有多少个不幸运数字呢? 输入 输入有多组数据。 每组数据只有一行,包含两个整数 M 和 N,以一个空格分开。 (0<=M<=N<=10^50) 输出 每组数据输出一行包含一个整数,为范围[M,N]里的不幸运数字的个数。 输入样例: 1 10 30 50 输出样例: 1 11 const inf=''; ouf=''; maxn=56; type arr=array[0..maxn+5] of longint; var n,m,fm,fn:arr; d1,d2:array[0..maxn] of arr; st:ansistring; function cheng(a:arr;x:longint):arr; var k,i:longint; begin

for i:=1 to maxn do a[i]:=a[i]*x; for i:=1 to maxn do begin inc(a[i+1],a[i] div 10); a[i]:=a[i] mod 10; end; cheng:=a; end; function jian(a,b:arr):arr; var k,i:longint; begin k:=0; for i:=1 to maxn do if a[i]-b[i]-k>=0 then begin a[i]:=a[i]-b[i]-k; k:=0; end else begin a[i]:=a[i]+10-b[i]-k; k:=1; end; jian:=a; end; function jia(a,b:arr):arr; var k,i:longint; begin k:=0; for i:=1 to maxn do if a[i]+b[i]+k<10 then begin a[i]:=a[i]+b[i]+k; k:=0; end else begin a[i]:=a[i]+b[i]+k-10; k:=1; end; jia:=a; end;

procedure make; var i,j,k:longint; now,pre:arr; begin for i:=1 to maxn do begin for j:=1 to maxn do d1[i][j]:=0; fillchar(pre,sizeof(pre),0); pre[1]:=1; for j:=i-1 downto 1 do begin if j<>i-1 then pre:=cheng(pre,9); now:=pre; for k:=j-1 downto 1 do now:=cheng(now,10); d1[i]:=jia(d1[i],now); end; for j:=1 to maxn do d2[i][j]:=0; d2[i][i]:=1; end; end; procedure init; var i:longint; begin readln(st); m[0]:=pos(' ',st)-1; for i:=1 to m[0] do m[m[0]-i+1]:=ord(st[i])-ord('0'); delete(st,1,m[0]+1); n[0]:=length(st); for i:=1 to n[0] do n[n[0]-i+1]:=ord(st[i])-ord('0'); end; procedure print(a:arr); var k,i:longint; begin for k:=maxn downto 1 do if a[k]<>0 then break; for i:=k downto 1 do write(a[i]); writeln;

end; function find(a:arr):arr; var i,j:longint; now,ans:arr; begin fillchar(ans,sizeof(ans),0); for i:=a[0] downto 1 do begin if a[i]>4 then begin ans:=jia(ans,cheng(d1[i],a[i]-1)); ans:=jia(ans,d2[i]); end else ans:=jia(ans,cheng(d1[i],a[i])); if a[i]=4 then begin fillchar(now,sizeof(now),0); for j:=i-1 downto 1 do now[j]:=a[j]; now[1]:=now[1]+1; ans:=jia(ans,now); break; end; end; find:=ans; end; procedure main; var i:longint; ans,k:arr; begin fm:=find(m); fn:=find(n); fillchar(k,sizeof(k),0); for i:=1 to m[0] do if m[i]=4 then k[1]:=1; ans:=jian(fn,fm); ans:=jia(ans,k); print(ans); end; begin assign(input,inf); reset(input); assign(output,ouf); rewrite(output);

make; while not seekeof do begin init; main; end; close(input); close(output); end. 7、小胖办证 【题目描述】 小胖要办个签证。办证处是一座 M 层的大楼,1<=M<=100。 每层楼都有 N 个办公室,编号为 1..N(1<=N<=500)。每个办公室有一个签证员。 签证需要让第 M 层的某个签证员盖章才有效。 每个签证员都要满足下面三个条件之一才会给小胖盖章: 1. 这个签证员在 1 楼 2. 小胖的签证已经给这个签证员的正楼下(房间号相同)的签证员盖过章了。 3. 小胖的签证已经给这个签证员的相邻房间(房间号相差 1,楼层相同)的签证员盖过章了。 每个签证员盖章都要收取一定费用,这个费用不超过 1000000000。 找出费用最小的盖章路线,使签证生效 【输入格式】 第 1 行两个整数 M 和 N。 接下来 M 行每行 N 个整数,第 I 行第 j 个数表示第 I 层的第 j 个签证员收取的费用。 【输出格式】 使签证有效的最小费用 【输入样例】 3 4 10 10 1 10 2 2 2 10 1 10 10 10 【输出样例】 8 参考程序: program xiaopang; var m,n,i,j:longint; minf:longint; a,f:array[1..100,1..500] of longint; function min(a,b:longint):longint; begin if a<=b then min:=a else min:=b;

end; begin fillchar(f,sizeof(f),0); assign(input,'xpbz.in'); reset(input); assign(output,'xpbz.out'); rewrite(output); readln(m,n); for i:=1 to m do begin for j:=1 to n do read(a[i,j]); readln; end; for j:=1 to n do f[1,j]:=a[1,j]; for i:=2 to m do begin f[i,1]:=f[i-1,1]+a[i,1]; for j:=2 to n do f[i,j]:=min(f[i-1,j],f[i,j-1])+a[i,j];{从正下方的数相加的和,左边相邻的相加的和, 两都取最小值} for j:=n-1 downto 1 do f[i,j]:=min(f[i,j],f[i,j+1]+a[i,j]);{前面相加之后的最小值与右边相邻的数相加的和, 两都取最小值} end; minf:=f[m,1]; for j:=2 to n do{在最第M层取最小值} if minf>f[m,j] then minf:=f[m,j]; writeln(minf); close(input); close(output); end. 动态规划之吞噬比赛 【问题描述】 镇里举办贪吃比赛,一共比赛 N 天,规定:每次吃的必须比上次多,一天只能吃一次(撑死...) ,吃 的天数最多的人将获得胜利,获得 10000000000 mod 10 的奖金^_^ 现在,Sally 要参加比赛,她邀请参加 OI 的你一起帮忙,胜利后七三分成^_^ 【输入】 第一行一个数 N,表示吃的天数(N<=10000) 第二行 N 个数,表示每天能吃的数量(数量最多 10000) 【输出】 一个数,表示最多吃的天数 【样例】 输入:6

1 2 3 1 5 6 输出:5 【参考程序】 program xxx(input,output); var i,j,n,max,s:integer; a:array[1..10000,0..1]of integer; begin read(n); for i:=1 to n do begin read(a[i,1]); a[i,0]:=1; max:=0; for j:=1 to i-1 do if (a[j,0]>max) and (a[i,1]>a[j,1]) then max:=a[j,0]; inc(a[i,0],max); if a[i,0]>s then s:=a[i,0]; end; write(s); end. 动态规划之打水漂 【问题描述】 君不知,打靶大牛 goleenuoer 可喜欢打水漂了,他的靶子可以打到河面上的任何一条鱼,可是他的水 漂打得实在是烂,无论怎么打那石子只会在河面上跳跃两次就“扑通”了.这天他又来打了.这条宽 w 米,每 隔一米都会有一条鱼,每条鱼都有它的美观值.他想知道如何打才能得到两条鱼之间最大的美观值总和.刚 接触 OI 的他想请您来解答,您能帮助他吗??? 【输入】 输入文件包含 n+1 个整数,第一行为一个整数 n(n<=10000).从第二行工 n 个数,第 i 个整数表示第 i 条 鱼的美观值范(围为-500..500).当所有整数都为负数时输出 0. 【输出】 输出文件包含两行,第一行为石子的起点和落点,用空格隔开.第二行为一个整数表示所得到的两条鱼 之间美观值总和. 【样例】 输入:6 -2 11 -4 13 -5 -2 输出:2 4 20 【参考程序】 program xxx(input,output); var max:longint;

i,n,t,w:integer; a:array[0..10000,0..2]of longint; begin read(n); for i:=1 to n do begin read(a[i,0]); a[i,2]:=a[i,0]; a[i,1]:=i; if a[i-1,2]>0 then begin inc(a[i,2],a[i-1,2]); a[i,1]:=a[i-1,1]; end; if a[i,2]>max then begin max:=a[i,2]; t:=a[i,1]; w:=i; end; end; writeln(t,' ',w); write(max); end.

动态规划之迷宫路径 【问题描述】 猩猩来到一个点(1,1) ,想吃右下角(N,N)的香蕉,规定只能往下走或者往右走,试问有多少种走 法? 【输入】 第一行为一个整数 N(N<=20),以下是一个 N*N 的正方形表示迷宫 【输出】 仅有一个数,表示路径总数,如果走不通,则输出 0 【样例】 输入:2 0 0 0 0 输出:2 【参考程序】 program xxx(input,output); var n,i,j:integer; s:array[0..20,0..20]of longint; begin read(n); for i:=1 to n do

for j:=1 to n do begin read(s[i,j]); if s[i,j]=1 then s[i,j]:=-1; end; s[1,1]:=1; for i:=1 to n do for j:=1 to n do if s[i,j]<>-1 then begin if (s[i-1,j]=-1) and (s[i,j-1]<>-1) then inc(s[i,j],s[i,j-1]); if (s[i-1,j]<>-1) and (s[i,j-1]=-1) then inc(s[i,j],s[i-1,j]); if (s[i-1,j]<>-1) and (s[i,j-1]<>-1) then inc(s[i,j],s[i,j-1]+s[i-1,j]); end; write(s[n,n]); end.

动态规划之核电站问题 【问题描述】 一个核电站有 N 个放核物质的坑,坑排列在一条直线上。如果连续 M 个坑中放入核物质,则会发生爆 炸,于是,在某些坑中可能不放核物质。 任务:对于给定的 N 和 M,求不发生爆炸的放置核物质的方案总数 【输入】 输入文件只一行,两个正整数 N,M( 1<N<50,2≤M≤5) 【输出】 输出文件只有一个正整数 S,表示方案总数。 【样例】 输入:4 3 输出:13 【参考程序】 program xxx(input,output); var n,m,i,j,k:integer; ans:qword; f:array[1..50,0..5]of qword; begin fillchar(f,sizeof(f),0); readln(n,m); f[1,0]:=1; f[1,1]:=1; for i:=2 to n do begin for k:=0 to m-1 do inc(f[i,0],f[i-1,k]); for j:=1 to m-1 do f[i,j]:=f[i-1,j-1]; end;

ans:=0; for i:=0 to m-1 do inc(ans,f[n,i]); writeln(ans); end. 动规之又上锁妖塔 【问题描述】 小 D 在 X 星买完了想要的东西,在飞往下一个目的地的途中,正无聊的他转头看了看身边的小 A,发现小 A 正在玩<仙剑>,可是小 A 很奇怪,他一直在锁妖塔的周围转来转去,可是就是不进去,于是小 D 问他:” 你在 干什么?怎么不上去?”小 A 说:”我在想怎么从锁妖塔外面爬上去”(倒?) 锁妖塔的建造很特别,塔总共 有 n 层,但是高度却不相同,这造成了小 A 爬过每层的时间也不同.小 A 会用仙术,每用一次可以让他向上跳 一层或两层,但是每次跳跃后小 A 都将用完灵力,必须爬过至少一层才能再次跳跃(你可以认为小 A 需要跳 两次一层才休息),小 A 想用最短的时间爬到塔顶,可是他不能找到时间最短的方案,所以请你帮他找到一个 时间最短的方案让他爬到塔顶,小 A 只关心时间,所以你只要告诉他最短时间是多少就可以了.你可以最后 跳到塔外即超过塔高. [数据规模] 对 20%的数据,n<=10 对 40%的数据,n<=100 对 60%的数据,n<=5000 对 100%的数据,n<=10000 【输入】 第一行一个数 n (n<=10000),表示塔的层数. 接下来的 n 行每行一个数(<=100),表示从下往上每层的高度. 【输出】 一个数,表示最短时间 【样例】 输入:5 3 5 1 8 4 输出:1 【参考程序】 program xxx(input,output); var n,i:longint; h:array[1..10000]of integer; f:array[0..10000,0..1]of longint; function min(x,y:longint):longint; begin if x>y then exit(y) else exit(x);

end; begin read(n); for i:=1 to n do read(h[i]); f[1,0]:=h[1]; f[1,1]:=0; f[0,0]:=0; f[0,1]:=0; for i:=1 to n do begin f[i,0]:=min(f[i-1,1]+h[i],f[i-1,0]+h[i]); f[i,1]:=min(f[i-2,0],f[i-1,0]); end; write(min(f[n,0],f[n,1])); end. 数组之吉祥数 【问题描述】 为了迎接圣诞,信息学兴趣小组的同学在辅导老师的带领下,举办了一个盛大的晚会,晚会的第一项 内容是做游戏:猜数。老师给每位同学发一张卡片,每张卡片上都有一个编号(此编号为非负数,且小于 255),每个编号互不相同。老师制定了以下的游戏规则:第一轮,每位同学将自己卡片上编号的各位数字 进行平方后再相加得到一组新数,编号在这组新数中出现的同学淘汰出局,第二轮,余下的同学再将编号 的各位数字进行立方相加得到一组新数,编号在这组新数中出现的同学再淘汰出局,第三轮,余下的同学 再将编号的各位数字进行 4 次方相加得到一组新数,编号在这组新数中出现的同学再淘汰出局,??,以 此类推,经过 n 轮后,仍留下来的同学,将获得圣诞特别礼物,卡片上的数即为 2011 年吉祥数。(假定班 级人数不超过 200 人) 【输入】 输入有两行,第 1 行为 1 个正整数 n(n<8),表示有 n 轮游戏,第二行是卡片上互不相同的编号。 输出:剩下来的各个吉祥数,按从小到大顺序输出,每两个数之间有一个空格。 【输出】 输出是 1 行,为剩下来的各个吉祥数,按从小到大顺序输出,每两个数之间有一个空格。 【样例】 输入:1 24 123 2 12 20 14 4 6 36 72 输出:2 6 12 24 72 123 【参考程序】 program xxx(input,output); var n,i,sum:integer; ch:char; ls:string; r:array[1..200]of longint; function f(a,b:longint):longint; var

s,e,ee:longint; m,l:integer; w:array[1..3]of integer; begin fillchar(w,sizeof(w),0); l:=trunc(b*ln(2)/ln(10))+1; ee:=b; w[1]:=ee div 100; ee:=ee mod 100; w[2]:=ee div 10; ee:=ee mod 10; w[3]:=ee; e:=1; s:=0; for m:=0 to a do e:=e*w[1]; inc(s,e); e:=1; for m:=0 to a do e:=e*w[2]; inc(s,e); e:=1; for m:=0 to a do e:=e*w[3]; inc(s,e); exit(s); end; function pd(a,b:integer):boolean; var c:integer; begin for c:=a to b do if r[c]<>0 then exit(true); exit(false); end; procedure gc(x:integer); var j,k,s:integer; t:array[1..200]of longint; begin fillchar(t,sizeof(t),0); for j:=1 to sum do t[j]:=f(x,r[j]); for j:=1 to sum do if t[j]<>0 then

for k:=1 to sum do if r[k]<>0 then if t[j]=r[k] then r[k]:=0; s:=0; for j:=1 to sum do if r[j]<>0 then inc(s); j:=1; while j<=sum do begin if r[j]=0 then begin if pd(j,sum) then for k:=j to sum do r[k]:=r[k+1] else j:=sum+1; end else if r[j]<>0 then inc(j); end; sum:=s; end; procedure sort(l,ll:integer); var i,j:integer; x,y:longint; begin i:=l; j:=ll; x:=r[(l+ll) div 2]; repeat while r[i]<x do inc(i); while x<r[j] do dec(j); if i<=j then begin y:=r[i]; r[i]:=r[j]; r[j]:=y; inc(i); dec(j); end; until i>j; if i<ll then sort(i,ll); if l<j then sort(l,j); end; begin readln(n); ch:=' '; ls:=''; i:=0; while ch<>chr(10) do begin

read(ch); if ch in ['0'..'9'] then ls:=ls+ch; if ch=' ' then begin inc(i); val(ls,r[i]); ls:=''; end; end; inc(i); val(ls,r[i]); sum:=i; for i:=1 to n do gc(i); sort(1,sum); write(r[1]); for i:=2 to sum do write(' ',r[i]);

高精度之物理课考试 【问题描述】 第三节是物理课,今天进行单元考,WX 老师走了进来?? 这次考试都是选择题。考试的时候,181818181818 对每道选择题的 4 个选项的选取是基于一定的概率。比 如 ABCD 4 个选项的被他选中概率分别为 p1 p2 p3 p4, 其中 p1≥0, p2≥0, p3≥0, p4≥0, p1+p2+p3+p4=1 , 而如果正确答案为 B,他做对这道题目的概率为 p2。 一次考试总有 n 道题目,181818181818 想知道他得 100 分(就是全对)的概率有多大,他需要你的帮助。 【输入】 输入:第 1 行有一个数 n,(1≤n≤100)表示选择题的数量。第 2 行是每道题目的正确答案。第 3 行到 第 n+2 行,每行包括 4 个概率数字,以一个空格隔开,格式为 x%,表示 ABCD 4 个选项被选中的概率。 (0 ≤x≤100) 【输出】 输出:如果概率为 0 的话,输出 0。如果概率为 1 的话,输出 1。其它概率,请输出其精确值。 (即输 出所有的有效数字,忽略有效数字后的 0) 。 【样例】 输入:5 ABBAC 50% 20% 13% 37% 20% 10% 11% 59% 0% 100% 0% 0% 99% 1% 0% 0% 50% 0% 50% 0% 输出:0.02475 【参考程序】 program xxx(input,output); type sz=array[0..300]of integer;

var i,n,s:integer; ch:char; ans:array[0..100]of integer; gl:sz; function pd(x:sz;a,b:integer):boolean; var j:integer; begin for j:=a to b do if x[j]<>0 then exit(true); exit(false); end; procedure cheng(var x1,x2:sz); var j,k,l:integer; c:sz; begin if not pd(x2,1,x2[0]) then x2:=x1 else begin fillchar(c,sizeof(c),0); for j:=1 to x1[0] do for k:=1 to x2[0] do begin inc(c[j+k-1],x1[j]*x2[k]); inc(c[j+k],c[j+k-1]div 10); c[j+k-1]:=c[j+k-1]mod 10; end; l:=x1[0]+x2[0]+1; while (l>1)and(c[l]=0)do dec(l); c[0]:=l; x2:=c; end; end; procedure duru(x:integer); var p:array[1..4]of integer; ch:char; ls:string; j,w1,w2,w3:integer; f:sz; begin ch:='x'; ls:=''; j:=0; while ch<>chr(10) do begin read(ch);

if ch in ['0'..'9'] then ls:=ls+ch; if ch='%' then begin inc(j); val(ls,p[j]); ls:=''; end; end; fillchar(f,sizeof(f),0); w1:=p[ans[x]] div 100; w2:=(p[ans[x]] mod 100)div 10; w3:=p[ans[x]] mod 10; f[1]:=w3; f[2]:=w2; f[3]:=w1; if f[3]<>0 then f[0]:=3 else if f[2]<>0 then f[0]:=2 else if f[1]<>0 then f[0]:=1; cheng(f,gl); end; begin readln(n); for i:=1 to n do begin read(ch); case ch of 'A':ans[i]:=1; 'B':ans[i]:=2; 'C':ans[i]:=3; 'D':ans[i]:=4; end; end; readln; for i:=1 to n do duru(i); for i:=1 to n do begin s:=gl[i]; gl[i]:=gl[2*n-i+1]; gl[2*n-i+1]:=s; end; if gl[0]=n*2+1 then write('1.') else write('0.'); i:=0; while (i<=2*n)and(pd(gl,i+1,2*n))do begin inc(i); write(gl[i]); end; end.

猫猫的小鱼 【问题描述】 猫猫是丛林里很多动物心中的天使,她为此十分自豪。猫猫最爱吃鱼了,她每天都要去池塘钓鱼吃。 猫猫经常吃鱼脑,数学特别强,然而,小女生的性格决定了她的贪玩。 一天,猫猫钓到了很多条鱼。她并不想马上就把可怜的鱼儿吃掉,而是先折磨够之后再吃(有句话叫 什么来着~最毒不过猫猫心) 。猫猫将这很多很多(数不过来)条鱼按照外观的漂亮程度排序,每个鱼的 编号依次为 1、2、3??N,第 i 条鱼的美观程度为 3^(i-1)。猫猫要把这些鱼放到桶里去。她每次拿的鱼 的数目是任意的。中的鱼的“总美观程度”为各条鱼美观程度之和。例如:猫猫这一次拿了第一条鱼和第 三条鱼,那么美观程度为 1+9=10。 猫猫想知道,她可以获得的第 k 大的“总美观程度”是多少。 从文件中读入 k,输出猫猫能够获得的,第 k 小的“总美观程度” 。 【输入】 数据包含 n+1 行,第一行读入 n 以下 n(n<=100)行每行包含一个 k。 对于 50% 的输入文件,有 k≤5000。 对于 100% 的输入文件,有 k≤2^31-1。 【输出】 输出包含 n 行,每行输出一个对应的结果。 【样例】 输入:1 7 输出:13 样例说明: 猫猫能够拿到的美观程度从小到大为 1、3、4、9、10、12、13??所以第 7 大的美观程度是 13。 对于 50% 的输入文件,有 k≤5000。 对于 100% 的输入文件,有 k≤2^31-1。 【参考程序】 program xxx(input,output); var l,k,n:longint; function cf(y,z:longint):qword; var i:longint; sum:qword; begin sum:=1; for i:=1 to z do sum:=sum*y; cf:=sum; end; function qs(x:longint):qword; var s:qword; m:longint; begin

s:=0; m:=0; while (x<>0) and (x<>1) do begin s:=(x mod 2)*cf(3,m)+s; x:=x div 2; inc(m); end; s:=s+x*cf(3,m); qs:=s; end; begin read(n); for l:=1 to n do begin read(k); writeln(qs(k)); end; end.


更多相关文档:

暑假信息学奥赛辅导教案

暑假信息学奥赛辅导教案复习初中内容(halt:退出程序。 exit:退出过程、函数。如果在主程序,则效果和 halt 一样。 break:跳出循环。 continue 也是用在循环里面,但...

信息学奥林匹克竞赛培训教案

信息学奥林匹克竞赛培训教案_学习计划_计划/解决方案_实用文档。信息学奥林匹克...79 暑期培训第二课 枚举、子界、集合、记录、文件类型 练习 T15_005 输入今天...

信息学奥林匹克竞赛培训教案(校本课程)

信息学奥林匹克竞赛培训教案第1章 计算机的发展与应用 1.1 计算机发展简史 1.1.1 第一台电子计算机的诞生 1946 年,世界上第一台数字式电子计算机由美国宾夕法...

在信息学奥赛辅导中我的几点做法

信息学奥赛辅导中我的几点做法_学科竞赛_初中教育_教育专区。在信息学奥赛辅导中我的几点做法 各位老师,大家好! 首先感谢范老师给我这次机会, 在这里与大家一起...

信息学奥赛辅导

信息学奥赛辅导应以学生为本,以培养学生思维方法和自 学能力为立足点。 1. 注重思维方法的培养 信息学奥赛是一种思维“体操” ,那么思维如何做“体操”呢?思维...

CHH信息学奥赛培训教案

(信息学奥赛辅导)程序设... 51页 免费 信息学奥赛辅导教程 230页 免费 信息...(信息学奥林匹克科学委员会主编,清华 》 大学出版社)及网上教案,阅读要求见下...

信息学奥赛(NOIP)必看经典书目汇总

2、 《算法艺术与信息学竞赛》 (推荐指数:5 颗星) 刘汝佳著,传说中的黑书。 3、 《学习指导》 (推荐指数:5 颗星) 刘汝佳著, 《算法艺术与信息学竞赛》的...

信息学奥赛培训资料

信息学奥赛培训资料_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档信息学奥赛培训资料_学科竞赛_高中教育_教育专区。桃江一中信息学奥赛培训辅导...

普通高中信息学奥赛辅导策略

龙源期刊网 http://www.qikan.com.cn 普通高中信息学奥赛辅导策略 作者:肖波 来源:《课程教育研究· 中》2013 年第 03 期 【中图分类号】G632 【文献标识码...

高中信息学奥赛培训教案

高中信息学奥赛培训教案_学科竞赛_高中教育_教育专区。第一章 Pascal 语言概述与...(信息学奥赛辅导)程序设... 51页 免费 信息学奥林匹克竞赛培训... 80页 免...
更多相关标签:
信息学奥赛辅导 | 信息学奥赛辅导教程 | 信息学奥赛辅导资料 | 信息学奥赛辅导计划 | 暑假辅导班招生简章 | 暑假辅导班 | 石家庄暑假一对一辅导 | 暑假辅导 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com