算法和数据结构综合应用

1、竞赛培训目录第三部分 算法和数据结构综合应用广度优先搜索深度优先搜索数值计算问题递推与迭代法递归与回溯 穷举法贪心算法动态规划法分治法最短路径问题背包问题关键路径最优路径典型竞赛试题分析第三部分 算法与数据结构综合应用数值计算问题：1、打印所有的“水仙花数”，所谓“水仙花数”是指一个三位数，其各位数字立方和等于该数字本身，例如：、n 是个 6 位数、若将 n 的各位数移到其余各位之前，所得的新数是 n 的 4 倍。简单背包问题递推法:例题：运动会连续开了n 天，一共发了 m 枚奖章，第一天发 1 枚并剩下（m1）枚的 1/7，问题描述 背包是一个简单的递归问题,要求是从 n 件物品中抽取几件,

2、使之质量一定.该程序只求一组解.输入:KEYBOARD 输出:SCREEN 101 2 3 4 5 6 7 8 9 129第二天发 2 枚并剩下的 1/7，以后每天按规律奖章，在最后一天即第 n 天发剩下的n枚奖章。问运动会一共开了多少天？一共发了几枚奖章？贪心算法51 2 3 4 5452 3 4- NO ANSWER!问题分析 使用递归算法完成.每件物品只有放入,不放入两种情况. program knapProg;constm = 5;var一、一、算法贪心法的基本思路：从问题的某一个初始解出发逐步 近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止

3、。该算法存在问题：1.2.3.不能保证求得的最后解是最佳的；不能用来求最大或最小解问题；只能求满足某些约束条件的可行解的范围。实现该算法的过程：从问题的某一初始解出发；while 能朝给定总目标前进一步求出可行解的一个解元素；item: array1.m ofeger;doi, w:eger;由所有解元素组问题的一个可行解；二、二、例题分析1、背包问题有一个背包，背包容量是 M=150。有 7 个物品，物品可以分割成任意大小。function knap(a, b:eger): beginif itema = b then begin;要求尽可能让装入背包中的物品总价值最大，但过总容量。knap

4、 := true; write(itema: 8); exit;end;if (itema b) and (a = m) then beginknap := false; exit;end;if knap(a + 1, b - itema) then beginknap := true; write(itema: 8); exit;end;if not knap(a + 1, b) then knap := false; end;beginwrin(Please input item weights:); for i := 1 to m doread(itemi);分析：目标函数： pi最大约

5、束条件是装入的物品总重量不超过背包容量：wi1 且 B/A=BA，则 C=B/A若 A1，则 C=B,打印 1/C转步骤（2）。c=array1.5,1.5 of(1,0,4,4,3),(2,4,0,1,2),(7,4,1,0,3);2. 贪心过程：begineger=(0,1,2,7,5),初始化所有城市的算途径标志；设置出发城市 V；for i:=1 to n-1 do n-1 个城市 begins:=从 V 至所有未曾到过的城市的边集中耗油量最少的那个城市；累加耗油量；V:=s；QBASIC 程序CLS DOINPUT a,b=; a, b LOOP UNTIL a 1 THEN PR

6、LOOP WHILE a 1+;PR END+1; b数的划分的研究问题描述求把一个整数n 无序划分成 k 份互不相同的正整数之和的方法总数。分析if cost=j then fi,j:=fi-j,j+fi-1,j-1; assign(output,outputfile); rewrite(output);wrin(fn,m); close(output);end;对于这道题很容易可以想到一种状态表示方法,即用 F(I,J,K)来表示把 J 无序划分成I 份其中最大为K 的划分方案数.那么,它就等于把 J-K 无序划分成I-1 份,其中最大不超过 K 的划分方案数，状态转移方程就是对应的pas

7、cal 程序如下:procedure dp;var i,j,k,l:eger; beginassign(output,outputfile); rewrite(output); f0,0,0:=1;for i:=1 to m do for j:=i to n dofor k:=1 to j do for l:=0 to k doinc(fi,j,k,fi-1,j-k,l);其实对于这题不再累赘了.还可以继续优化,例如用滚动数组的方法使存处空间减少,这里就这里还想介绍一种更容易的做法.若用 F(I,J) 表示把 I 无序划 分成 J 份的 方案 数 , 则 F(5,2)=(1,4,2,3);F(

8、6,3)=(1,1,4,1,2,3,2,2,2)你一定会发现如果把I 无序划分为J 份,那么它的前几个划分一定等于把I-1 无序划分成 J-1 份每份前面加 1 的方案数.for i:=1 to n wrin(count); close(output);nc(count,fm,n,i);那么后面那一部拆分方案又会等于什么呢?会发现它与F(I-J,J)是一一对应的.不妨将后面每一份中的每一个数减end;1,但是如果再把上图逆时针翻转 90 度，那么其实也就等于先在最下一行各摆上一证明如下块积木接下来也就是把I-J 块积木放上去,并要保持楼梯状.可以发现其实上就是把I-J一个自然数 I 划分为 K

9、 份，为了避免重复，于从小到大地划分。无序拆分成 1K 份。那么可以得到如下动态转移方程数 I 分为 K 份的方法数记作 F（I，K），可知：F（I，K）=F（I-K，K）+F（I-1，K-1）证明：设集合A为 I 的所有划分方案的第一项，0A=（I DIV K），设每一种划分方案的以后 K-1 个数为 A+D1，A+D2，A+D3 A+Dk-1，DiDi+1，于是：procedure dp;var i,j,k:eger; beginf0,0:=1;for i:=1 to n do for j:=1 to m doif j=i thenfor k:=0 to j do inc(fi,j,fi-

10、j,k);assign(output,outputfile);D 的不下降排列数即 I 的首项是 A 的不同划分数 。同理，设B为 I-K 的划分方案的首项集合，以后的 K-1 个数是 B+C1，B+C2 B+Ck-1，所以，for i:=2 to n doif m ai then m:=ai; (或者一次选择排序) p:=1;for i:=2 to n doif apb then maxnum:=a else maxnum:=b; end;分析比较次数：比较运算均在函数 maxnum 和 minnum 中进行，当 n=2 时，比较次数 T(n)=1当 n2 时，比较次数 T(n)=2T(n/

11、2)+2 n 是 2 的 k 次幂。设 n=2kC 的不下降排列数就是 I-K 的首项是 B 的不同划分数 ，又因为：可知当 A-1=B时 ，方案数相同，其中 A 能从 2 取到（I div k） ，而 B1，(I-k) divk即 B1,(I div k)-1, 所以，当 A2，I div k时，方案总数是 F（I-K，K）。又因为当 A=1时，方案数是 F（I-1，K-1），所以： F（I，K）=F（I-K，K）+F（I-1，K-1）成立。由此也可以推出与上面第三个程序一样的状态转移方程.分治策略一、一、算法任何一个可以用计算机求解所需的计算时间都与其规模有关。问题规模越小，解题所需的计算

12、时间往往也越少，从而也越容易计算。想解决一个较大，有时是相当的。分治法的就是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治的基本是将一个规模为 n分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题相同。找出各部分的解，然后把各部分的解组整个问题的解。1、 1、 解决算法实现的同时，需要估算算法实现所需时间。分治算法时间是这样确定的： 解决子问题所需的工作总量（由子问题的个数、解决每个子问题的工作量 决定）合并所有子问题所需的工作量2、 2、 分治法是把任意大小问题尽可能地等分成两个子问题的递归算法3、分治的具体过程:beginif开始问题不可

13、分 then 返回问题解else begin从原问题中划出含一半运算对象的子问题 1；递归调用分治法过程，求出解 1；从原问题中划出含另一半运算对象的子问题 2；递归调用分治法过程，求出解 2；将解 1、解 2 组end; end; 结束二、二、例题分析整修问题的解；1、金块问题有一袋金块(共 n 块，n 是 2 的幂（n=2）)，将有两名最优秀的雇员每人得到其中的一块，第一的得到最重的那块，第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重的金块。分析:问题可以简化为：在含 n（n 是 2 的幂（n=2）个元素的集合中寻找极大元和极小元。明显的方法是逐个的

14、进行比较查找。(一次冒泡排序)m:=a1;三趟归并排序BEKLSUY习题:对数字 49 38 40 97 76 13 27 进行归并排序procedure mergesort(var r,r1:listtype;s,t:eger);r,r1：均为链表，排序数据；过程 mergesort(r,r1,s,t)完成把链表 r 中的关键字进行归并排序、并存放到链表 r1 中，其中 s 是下界 t 是上界过程 merge(r2,s,m,t,r1)把链表 r2 中排好序的子链r2s.m链 r2m+1.t合并到 r1 中if s=t then r1s:=rs elsemergesort(r,r2,s,(s+

15、t)div 2); mergesort(r,r2,(s+t)div 2,t); merge(r2,s,(s+t)div 2,t,r1);竞赛 第三题：棒球联赛） 为 1.N）参加的少年棒球联赛。if 问题不可分 then求解else分出问题的一个子问题 1，并求解子问题 1分出问题的一个子问题 2，求解子问题 2（3）合并子问题 1问题 24、循环赛问题（1999 年省青少年信息学问题描述：广州市体委将举行一次由 N 支队伍（队伍联赛总共不能多于N 轮（同一时间内若干支队进行一次比赛为一轮），并且每两支队之间必须而且仅必须进行一次比赛。请编程为这次比赛设计一个赛程表。循环赛问题可以用分治法解决

16、。下面是先假定 n=2kprocedure table(k:eger;a:array1.u1,1.u2 of var n,i,j,m,s,t:eger;beginn:=1;for i:=1 to k do n:=n*2; for i:=1 to n do a1,i:=i; m:=1;for s:=1 to k do beginn:=n / 2;for t:=1 to n dofor i:=m+1 to 2*m do for j:=m+1 to 2*m dobegineger);2、快速排序快速排序是基于分治策略的一个排序算法。按照分治法的分析快速排序：分解(Divide) 以元素 ap为基准元

17、素将 ap：q-1划分为三段 ap：q-1，aq和 aq+1： r，使得 ap：q-1中任何一个元素都小于 aq，aq+1：r中任何一个元素大于等于aq，下标 q 在划分中确定。递归求解(Conquer) 通过递归调用快速排序算法分别对 ap:q-1 和 aq+1:r进行排序。合并(Merge) 由于ap:q-1 和aq+1:r的排序都是在原位置进行的，所以不必进行任何合并操作就已经排好序了。在上面三个步骤中，第一步：分解是关键。一次快速排序确定划分元素的位置，具体参见排序算法快速排序3、归并排序归并排序也是基于分治策略的另一个算法。归并的思路是把两个已经排好序的数组合并为一个。(源程序)路归

18、并排序示例：ai,j+(t-1)*m*2:=ai-m,j+(t-1)*m*2-m;ai,j+(t-1)*m*2-m:=ai-m,j+(t-1)*m*2;end;m:=m*2; end;for send;三、练习题二分检索假定在 A1.9中顺序存放这九个数：-7,-2,0,5,16,43,57,102,291 291,16,101 是否在数组中。要求检索EE EYUKKSL BLBB初始值给定已排好序的 n 个元素 A1,A2,A3,，An, 找出元素 x 是否在 A 中，如果 x 在 A它在 A 中的位置。一趟归并排序两趟归并排序YUS中，KUYLS模拟wrin(o,I am a comput

19、er.);wrin(Today we are going to do addition problem.); seed:=1;for i:=1 to 10 do beginx:=random(1,19);产生一个1-19的随机整数xy:=random(1,20-x);产生另一个随机整数y,并确保它与x之和小于等于20随机函数及其应用：解决有些问题需要有一个产生随机数的函数。如果你使用的机器的Pascal未提随机数的标准函数，这里就向你介绍一个实现这个要求的函数，并举若干应用例子。生假定问题要在整区间ab集合中随机的选取一个整数r。如12上表示掷一枚硬币的正面或的结果；16上表示投一粒的面值等。

20、连续掷币，或连续投得到的结果序列：r ，1r ，2称为随机序列。程序不能严格地产生ab上的随机序列，但能用wrin(Pleasel me,how much is,x:2,+,y:2,=?);数学方法产生满足应用上所要求的近似随机序列的随机数，通常称为伪随机数。程序产write(Type the answer:); read(answer);生伪随机数的最通常的方法是线性同余法。下面函数random ab上伪随机数的函数。就是这一方法编制的产生if x+y=answer then判断 wrin(Correct.)else是否正确FUNCTIONrandom(a ,b:eger) :eger;产生

21、区间ab上的一个整数，使用并改变整体变量seed CONSTwrin(end end.ts not right.The answer is,x+y:2) = 216maxseed = 65536; multipr = 25173; adder = 13849; BEGIN除了整随机数外，有时也需要（ab）区间上的实随机数。产生实伪随机数函数randomrealseed: =(multipr * seed+ adder)MODmaxseed;与函数random原理基本相同。random END;:= a + seed *( b-a +1) DIV maxseedFUNCTION randomre

22、al (a , b: real) : real;产生（ab）内的一个实数，使用并改变整体变量seed的值 CONST函数random 通过保留一个整体变量seed而产生伪随机数。变量seed由主程序提供初值。为了产生一个伪随机数，应用线性同余法改变seed的值。seed 的取值范围0maxseed被分成(b-a+1)等分，每个等分内的值代表ab上的一个数。函数random 不满足前面建议的“函数不应改变整体量值”这一规则。但是，为了满足每次调用random 能得到一个不同的值，这又是必需的。maxseed=65536; multip BEGINseed :=multipr *r=25173;s

23、eed MOD maxseed;randomreal: = a+ seed * (b-a)/maxseed例 1：利用函数 random整数，让学生回答。 简单的算法分析：产生第一个随机数 x，x:=random产生第二个随机数 y，y:=random【源程序:xoi00_13.pas】PROGRAM simpledrill(input,output);VARseed,i:eger; x,y,answer:eger;编制的一个 20 以内整数加法教学程序。计算机随机产生两个END;例2：计算椭圆的面积。设椭圆方程为x2/32 + y2/22 =1(1,19)以保证两个数相加不超过 20。 (1

24、,20-x)以保证两个数相加不超过 20。算法：为了求一个不规则平面图S的面积，选取一个长方形C围住S。产生足够多的C中的随机点，则这些随机点同时落在S中的概率是SA/CA，其中SA，CA分别是S和C的面积。如果有一个简单的标准能确定一个点是否在S内，就可通过产生随机点，计算落在S中的点数，估计S的面积。因为所给椭圆关于x轴和y轴对称，总面积是第一象限部分面积的四倍。选取长方形C为0 x3 , 0y2 , 长方形C内的点（x , y）落在椭圆内的判别标准是x2/32 + y2/22 1【xoi00_14.pas】PROGRAM area(input,output);VARtotal,insid

25、e,seed:eger; x,y:real;i:eger;FUNCTION randomreal(a,b:real):real;产生区间ab上的一个实数，使用并改变实型变量seedFUNCTION random(a,b:eger):eger;产生区间ab上的一个整数，使用并改变整体变量seedCONSTmaxseed=65536; multipr=25173; adder=13849; beginseed:=(multipr*seed+adder) MOD maxseed; random:=a+seed*(b-a+1) DIV maxseed end;randombeginCONSTmaxse

26、ed=65536; multipr=25173; beginseed:=multipr*seed MOD maxseed; randomreal:=a+seed*(b-a)/maxseed end;randomrealbeginread(total);读入要产生的随机点的数目 inside:=0;seed:=1;for i:=1 to total do begin x:=randomreal(0,3); y:=randomreal(0,2);if (x*x/9+y*y/4)100;在每次被调用时，函数AddCust就用Ran1或Random来产生到达付款处的顾客数目。 AddQueue是依照R

27、an2的结果用来把顾客放到有服务的付款处排队，而且当每个付款处都客满时，它会再开放另一个付款处。Display会显示模拟的情形。Check使用Ran2去设定每个顾客一个付款的次序，而且每次调用时，都会使计数器减一，直到计数器为0时，此顾客就离开了付款处了。变量time会改变产生顾客的速度，使得可以满足商店完一次就表示过了一个小时的十分之一。你可以直接控制程序中的一些变量。首先，你可以更改顾客到达的方式和顾客到时间的要求，循环每做时段或时段快结束时，渐渐地增加或减少AddCust达的数目，你也能在快接近返回的顾客人数。此程序是假定顾客会随机的选择付款处，虽然有些人是这种情形，但是大部分人都会选择

28、人较少的付款处，所以你可以把各付款处的人数记下来，然后更改 AddQueue函数，改成有时把顾客放到人最少的付款处，而有时是随机的选择付款处。这个程序没有考虑到一些突发状况。例人把酱油弄翻了，或是付款处有位叼钻的顾客，这两种情形都会使付款工作稍微停顿。关键路径：【源程序：xoi00_16.pas,演示程序：DEM00_07.zip】1.问题描述下图是一个工程的AOE（Activity On Edge)网。图中N1至N10表示该工程由十项子工程组成。有向边a1至a14表示各子工程的活动情况，其权代表各项子工程持续的时间。点及下午5点到6点是时间，而中午12点到1点的顾客是一般情形的两倍，下午5点

29、到6点是平时的三倍。【源程序：xoi00_12.pas，演示程序：DEM00_14.exe】算法 ：当模拟开始后，第一个随机函数产生顾客的到来，第二个随机函数决定此顾客要用多少时间付款，第三个随机函数决定顾客要到哪一个付款处去付款。此模拟的主要目的是要帮助管理者找出最适当的付款处数目，满足百货商店的要求，使顾客排队付款的时间在十分钟以内，但是不要让收款员空闲在哪儿没有人付款。这种方式的模拟，主要在于建立多重的处理，虽然Trubo Pascal并没有提供多重处理的功能，但是你可以让主程序内的各个函数，轮流使用然后循环，本质上就是使用时间分段式函数达到多重处理的效果。例如，模拟付款的函数每次被调用

30、时，只能计算每个对列的一部分，此种方式下，主程序的每个函数都轮流执行。下面是模拟的主要循环：repeatAddCust; AddQueue; Display Check;Displayif (time30) and (time70) and (time80) thenbeginAddCust;AddCustend;对于AOE网，研究是：(1)完成整个工程至少需要多少时间； (2)哪些活动是影响工程进度的关键。 2.算法分析完成工程的最少时间，是从开始点到完成点的最长路径长度（路径长度是这条动持续时间之和），人们把路径长度最长的路径称为关键路径。的活分析关键路径的目的为辨别哪些是关键活动，以便提

31、高关键活动的工效，缩短整个工程的期限。链表的结构来表示有向图AOE网。把每个子工程视为一个结点，并设可以采用置五个域，当作一个。其中TAIL和HEAD域分别表示有向边的尾顶点J和头顶点K，DUT表示活动的持续时间，HLINK以K为头的另一有向边，TLINK为以J为尾的另一有向边。则求关键路径的算法如下所示：初始化十个结点。从源点N1出发，令VE1=0，按拓扑有序求其余各顶点的最早发生时间VEi。如果得到的拓扑有序序列中顶点的个数小于10，则说明网中存在环，不能求关键路径，算法终止；否则，执行步骤3。从汇点N10出发，令VL10=VE10，按逆拓扑有序求其余各顶点的最迟发生时间VLi。 (4)根据各顶点的VE和VL值，求每条弧R的