[计算机软件及应用]实用算法的分析与程序设计2.doc
《[计算机软件及应用]实用算法的分析与程序设计2.doc》由会员分享,可在线阅读,更多相关《[计算机软件及应用]实用算法的分析与程序设计2.doc(340页珍藏版)》请在三一文库上搜索。
1、目 录憙拕第一章 基础算法憖(4) 1.1 递推法(4) 1.2 贪心法(11) 1.3 递归法(23) 1.4 分治法(27) 1.5 枚举法(36) 1.6 模拟法(45)第二章 顺序统计算法和中位数(53) 2.1 顺序统计的算法(53) 2.2 中位数的应用(56)第三章 有关数论的算法(62) 3.1 求最大公约数(62) 3.2 求解模线性方程(66) 3.3 求解模线性方程组(71) 3.4 模取幂运算(74) 3.5 素数的测试(76) 3.6 整数的因子分解(78)第四章 计算几何学(81) 4.1 线段的性质(81) 4.2 确定任意一对线段是否相交(87) 4.3 寻找凸
2、包(94) 4.4 寻找最近点对(107)第五章 显式图的基本算法(113) 5.1 显式图的表示(113) 5.2 宽度优先搜索(116) 5.3 深度优先搜索(128) 5.4 有向图的最短路问题(142)第六章 隐式图的基本算法(160) 6.1 回溯法的讨论(160) 6.2 广度优先搜索(173) 6.3 双向广度优先搜索(188) 6.4 分支定界法(197) 6.5 A*算法(205) 6.6 博弈树(222)第七章 网络流的算法(238) 7.1 基本概念和基本定理(239) 7.2 寻求最大流的标号法(244) 7.3 最小费用最大流问题(255) 7.4 网络流算法的应用(
3、261)第八章 动态程序设计(285) 8.1 矩阵链乘法(285) 8.2 最长公共子序列(294) 8.3 应用举例(297)第九章 算法分析与NP问题简介(309) 9.1 算法的正确性和测试(309) 9.2 算法的简明性(323) 9.3 算法的时间复杂度(328) 9.4 算法的空间复杂度(339) 9.5 算法的最优性(341) 9.6 NP问题简介(344)第一章 基础算法 算法是一组(有限个)规则,它为某个特定问题提供了解决问题的运算序列。通俗点说,就是计算机解题的过程。在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法,后者是操作实现的算
4、法。憖 计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征: 憙(1)有穷性 一个算法必须保证执行有限步之后结束;憙 (2)确切性 算法的每一步骤必须确切定义; 憙(3)输入 一个算法有0个或多个输入,以刻划运算对象的初始情 况。所谓0个输入是指算法本身定出了初始条件; 憙(4)输出 一个算法有一个或多个输出,以反映对输入数据加工 后的结果。没有输出的算法是毫无意义的;憙 (5)能行性 算法原则上能够精确地进行,而且人们用笔和纸做有 穷次即可完成。 下面,我们对构成算法所依据的一些基本方法(公式、方案、原则),即解题思路展开讨论,对于读者来说,为了获得一个即有效又优美的算法,必须了解
5、一些基本的常用的算法设计思路。1.1 递推法拝 有一类试题,每相邻两项数之间的变化有一定的规律性,我们可将这种规律归纳成如下简捷的递推关系式: 这就在数的序列中,建立起后项和前项之间的关系。然后从初始条件(或最终结果)入手,一步步地按递推关系式递推,直至求出最终结果(或初始值)。很多程序就是按这样的方法逐步求解的。如果对一个试题,我们要是能找到后一项数与前一项数的关系并清楚其起始条件(最终结果),问题就好解决,让计算机一步步算就是了。让高速的计算机从事这种重复运算,可真正起到“物尽其用”的效果。 递推分倒推法和顺推法两种形式。一般分析思路: if 求解初始条件F1 then begin 倒推
6、由题意(或递推关系)确定最终结果Fn; 求出倒推关系式Fi-1 G(Fi ); i=n; 从最终结果Fn壋龇械雇? while 当前结果Fi非初始值F1攄o 由Fi-1G(Fi)倒推前项; 输出倒推结果F1和倒推过程; end of then else begin 顺推 由题意(或递推关系)确定初始值F1(边界条件); 求出顺推关系式FiG(Fi-1); i=1; 由边界条件F1出发进行顺推 while 当前结果Fi非最终结果Fn do 由Fi墸紾(Fi-1)顺推后项; 输出顺推结果Fn和顺推过程; end; of else 一、倒推法 所谓倒推法,就是在不知初始值的情况下,经某种递推关系而获
7、知问题的解或目标,再倒过来,推知它的初始条件。因为这类问题的运算过程是一一映射的,故可分析得其递推公式。然后再从这个解或目标出发,采用倒推手段,一步步地倒推到这个问题的初始陈述。 下面举例说明: 【例1】贮油点 一辆重型卡车欲穿过1000公里的沙漠,卡车耗油为1升/公里,卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立几个贮油点,使卡车能顺利穿越沙漠,试问司机如何建立这些贮油点?每一贮油点应存多少汽油,才能使卡车以消耗最少汽油的代价通过沙漠? 憙算法分析: 编程计算及打印建立的贮油点序号,各贮油点距沙漠边沿出发的距离以及存油量。 No. distance(
8、k.m.) oil(litre) 1 2 3 设disi第i个贮油点至终点(i=0)的距离; oili第i个贮油点的存贮油量; 我们可以用倒推法来解决这个问题。从终点向始点倒推,逐一求出每个贮油点的位置及存油量。图1.1-1表示倒推时的返回点。( 图1.1-1 ) 从贮油点i向贮油点i+1倒推的策略是,卡车在点i和点i+1间往返若干次。卡车每次返回i+1处时正好耗尽500公升汽油,而每次从i+1处出发时又必须装足500 公升汽油。两点之间的距离必须满足在耗油最少的条件下使i点贮足i*500公升汽油的要求(0in-1)。具体地讲,嵉谝桓鲋偷鉯=1应距终点i=0处500 km 且在该处贮藏500公
9、升汽油,这样才能保证卡车能由i=1处到达终点i=0处,这就是说dis1=500 ol1=500; 为了在i=1处贮藏500公升汽油,卡车至少从i=2处开两趟满载油的车至i=1处。所以i=2处至少贮有2*500公升汽油,即oil2=500*2=1000。另外,再加上从i=1返回至i=2处的一趟空载,合计往返3次。三次往返路程的耗油量按最省要求只能为500公升,即d12?500/3km,dis2=dis1+d12? dis1+500/3 ( 图1.1-2 ) 为了在i=2处贮存1000公升汽油,卡车至少从i=3处开三趟满载油的车至i=2 处。 所以i=3处至少贮有3*500公升汽油,即oil3=5
10、00*3=1500。加上i=2至i=3 处的二趟返程空车,合计5次。路途耗油量亦应500公升,即d23 =500/5,dis3=dis2+d23? dis2+500/5;崐 ( 图1.1-3 ) 依次类推,为了在i=k处贮藏k*500公升汽油,卡车至少从i=k+1处开k趟满载车至i=k处,即oilk+1=(k+1)*500=oilk+500,加上从i=k返回i=k+1的k-1 趟返程空车,合计2k-1次。这2k-1次总耗油量按最省要求为500公升, 即dk,k+1? 500/(2k-1),disk+1 = disk+dk,k+1 = disk+500/(2k-1); ( 图1.1-4 ) 最后
11、, i=n至始点的距离为1000-disn,oiln=500*n。为了在i=n处取得n*500公升汽油, 卡车至少从始点开n+1次满载车至i=n,加上从i=n返回始点的n 趟返程空车,合计2n+1次,2n+1 趟的总耗油量应正好为(1000-disn)*(2n+1), 即始点藏油为oiln+(1000-disn)*(2n+1)。 下面为程序题解:program oil_lib;var k: integer; d, d1: real; i=n oil, dis: array1.10 of real; i: integer; begin writeln (NO., distance(k.m):30
12、,oil(l.):80); k:=1; d:=500; i=1 dis1:=500; oil1:=500; repeat k:=k+1; d:=d+500/(2*k-1); disk:=d; oilk:=oilk-1+500; until d=1000; disk:=1000; d1:=1000-disk-1; i=n oilk:=d1*(2*k+1)+oilk-1; for i:=0 to k do , writeln (i,1000-disk-i:30,oilk-i:80);end. main憙二、顺推法 倒推法的逆过程。即由边界条件出发,通过递推关系式推出后项值,再由后项值按递推关系式推
13、出再后项值,依次递推,直至从问题初始陈述向前推进到这个问题的解为止。 下面举例说明。 【例2】实数数列 一个实数数列共有N项,已知Ai(Ai-1Ai+1)2+d,(1iN)(N60)键盘输入N,d,A1,An,m,输出Am。 输入数据均不需判错。 算法分析: 该题的数学味颇浓。解题前需耐下心来,对公式Ai(Ai-1Ai+1)2+d,(1iN)(N60) 作一番推敲,探讨其数值变换规律。不然的话,会无从入手。 令 x=A2 S2i=(Pi,Qi,Ri)表示Ai=PiX+QiD+RiA1; 我们可以根据 Ai=Ai-2 - 2Ai-1 + 2D =PiX + QiD + RiA1 推出公式 PiX
14、+QiD+RiA1 = (Pi-2 - 2Pi-1)X+(Qi-2 - 2Qi-1 + 2)D+(Ri-2 - 2Ri-1)A1 比较等号两端X、D和A1的系数项,可得 Pi=Pi-2 - 2Pi-1 Qi=Qi-2 - 2Qi-1 + 2 Ri=Ri-2 - 2Ri-1 加上两个边界条件 P1=0 Q1=0 R1=1 (A1=A1) P2=1 Q2=0 R2=0 (A2=A2) 根据Pi、Qi、Ri的递推式,可以计算出 S21=(0,0,1); S22=(1,0,0); S23=(-2,2,1); S24=(5,-2,-2); S25=(-12,8,5); S2i=(Pi,Qi,Ri); S
15、2N=(Pn,Qn,Rn); 有了上述基础,Am便不难求得。有两种方法: 1、由于An、A1和Pn、Qn、Rn已知,因此可以先根据公式 A2 = ( An - QnD - RnA1 ) / Pn 求出A2。然后将A2代入公式 A3 = A1 - 2A2 + 2D 求出A3。然后将A3代入公式 A4 = A2 - 2A3 + 2D 求出A4。然后将A4代入公式 求出Ai-1。然后将Ai-1代入公式 Ai = Ai-2 - 2Ai-1 + 2D 求出Ai。依次类推,直至递推至Am为止。 上述算法的缺陷是,由于A2是两数相除的结果,而除数Pn递增,因此精度误差在所难免,以后的递推过程又不断地将误差扩
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机软件及应用 计算机软件 应用 实用 算法 分析 程序设计
链接地址:https://www.31doc.com/p-1991931.html