算法分析与设计第4章

1、第四章 基本的算法策略4.1 迭代算法4.2 蛮力算法4.3 分而治之算法4.4 贪婪算法4.5 动态规划 4.6 算法策略间的比较8/9/2022 4:03 PM14.1 迭代算法4.1.1 递推法4.1.2 倒推法4.1.3 迭代法解方程8/9/2022 4:03 PM24.1.1 递推法 【例1】兔子繁殖问题问题描述：一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。问题分析：因一对兔子从出生后第三个月开始每月生一对小兔子，则每月新下小兔子的对儿数(用斜体数字表示)显然由前两

2、个月的小兔子的对儿数决定。则繁殖过程如下： 一月 二月 三月 四月 五月 六月 1 1 1+1=2 2+1=3 3+2=5 5+3=8 8/9/2022 4:03 PM38/9/2022 4:03 PM4算法1： main( ) int i,a=1,b=1; print(a,b); for(i=1;i=10;i+) c=a+b; print (c); a=b; b=c； 数学建模：y1=y2=1，yn=yn-1+yn-2，n=3，4，5，。8/9/2022 4:03 PM5算法2：表4-1 递推迭代表达式1 2 3 4 5 6 7 8 9a b c=a+b a=b+c b=a+c c=a+b

3、a=b+c b=a+c 由此归纳出可以用“c=a+b; a=b+c; b=c+a;”做循环“不变式”。算法2如下： main( ) int i,a=1,b=1; print(a,b); for(i=1; i=4;i+) c=a+b; a=b+c; b=c+a; print(a,b,c); 算法2，最后输出的并不是12项，而是2+3*4共14项。 8/9/2022 4:03 PM6【例2】求两个整数的最大公约数。数学建模：辗转相除法是根据递推策略设计的。设ab且a/b=x.c；则a-bx=c，a、b的最大公约数也是c的约数,则a、b的最大公约数与b、c的最大公约数相同。 b/c=x1.c1 =

4、b-cx1=c1 ，直到余数为0时，除数即为所求的最大公约数。算法设计：循环“不变式”第一次是求a、b相除的余数c，第二次还是求“a”“b” 相除的余数，经a=b,b=c操作，就实现了第二次还是求“a”“b” 相除的余数，这就找到了循环不变式。循环在余数c为0时结束。 8/9/2022 4:03 PM7算法如下：main（） int a, b; input(a,b); if(b=0) print(“data error”); return; else c = a mod b; while（c0） a=b; b=c; c=a mod b; print(b);8/9/2022 4:03 PM84.

5、1.2 倒推法 所谓倒推法：是对某些特殊问题所采用的违反通常习惯的，从 后向前推解问题的方法。如下面的例题，因不同方面的需求而采用了倒推策略。【例1】猴子吃桃问题一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第10天时就只有一个桃子了，求原有多少个桃？数学模型：每天的桃子数为：a10=1, a9=(1+a10)*2, a8=(1+a9)*2,a10=1，递推公式为：ai=(1+ai+1)*2 i= 9,8,7,618/9/2022 4:03 PM9【例2】 输出如图4-1的杨辉三角形（限定用一个一维数组完成）。数学模型：上下层规律较明显，中间的数等于上行左上、右上两数之和。问题分析：题目

6、中要求用一个一维数组即完成。数组空间一定是由下标从小到大利用的，这样其实杨辉三角形是按下图4-2形式存储的。若求n层，则数组最多存储n个数据。 1 1 1 1 2 1 1 3 3 11 4 6 4 1 图4-1 杨辉三角形11 11 2 11 3 3 114 6 4 1图4-2 杨辉三角形存储格式 算法设计： A1 = Ai=1Aj = Aj + Aj-1 j=i-1，i-2，2i行 i-1行 i-1行8/9/2022 4:03 PM10算法如下：main( ) int n,i,j,a100;input(n); print(“1”); print(“换行符”);a1=a2=1;print(a1

7、,a2); print(“换行符”);for (i=3;i1;j=j-1) aj=aj+aj-1; for (j=1;j=i;j=j+1) print(aj); print(“换行符”); 11 11 2 11 3 3 114 6 4 18/9/2022 4:03 PM11【例3】穿越沙漠问题 用一辆吉普车穿越1000公里的沙漠。吉普车的总装油量为500加仑，耗油率为1加仑/公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。 问题分析： 1）先看一简单问题：有一位探险家用5天的时间徒步 横穿A、B两村，两村间是荒

8、无人烟的沙漠，如果一 个人只能担负3天的食物和水，那么这个探险家至 少雇几个人才能顺利通过沙漠。 8/9/2022 4:03 PM12 A城雇用一人与探险家同带3天食物同行一天，然后被雇 人带一天食物返回，并留一天食物给探险家，这样探险 家正好有3天的食物继续前行，并于第三天打电话雇B城 人带3天食物出发，第四天会面他们会面，探险家得到一 天的食物赴B城。如图4-3主要表示了被雇用二人的行程。 A B 图4-3 被雇用二人的行程 2）贮油点问题要求要以最少的耗油量穿越沙漠，即到达终 点时，沙漠中的各临时油库和车的装油量均为0。这样只 能从终点开始向前倒着推解贮油点和贮油量。8/9/2022 4

9、:03 PM13数学模型：根据耗油量最少目标的分析，下面从后向前分段讨论。第一段长度为500公里且第一个加油点贮油为500加仑。第二段中为了贮备油，吉普车在这段的行程必须有往返。下面讨论怎样走效率高：1）首先不计方向这段应走奇数次2）每次向前行进时吉普车是满载。3）要能贮存够下一加油点的贮油量，路上耗油又最少。8/9/2022 4:03 PM14下图是满足以上条件的最佳方案，此段共走3次：第一、二次来回耗油2/3贮油1/3，第三次耗油1/3贮油2/3，所以第二个加油点贮油为1000加仑。由于每公里耗油率为1加仑，则此段长度为500/3公里。第三段与第二段思路相同。下图是一最佳方案此段共走5次：

10、第一、二次来回耗油2/5贮油3/5，第三、四次来回耗油2/5贮油3/5，第五次耗油1/5贮油4/5，第三个加油点贮油为1500加仑。此段长度为500/5。 500/5公里 第二 第三 终点贮油点（500）贮油点（1000）贮油点（1500）图4-4 贮油点及贮油量示意8/9/2022 4:03 PM15综上分析，从终点开始分别间隔 500，500/3，500/5，500/7，（公里）设立贮油点，直到总距离超过1000公里。每个贮油点的油量为500，1000，1500，。算法设计：由模型知道此问题只需通过累加算法就能解决。变量说明：dis表示距终点的距离，1000- dis则表示距起点的距离，k

11、表示贮油点从后到前的序号。8/9/2022 4:03 PM16desert（ ） int dis，k，oil,k; dis=500;k=1;oil=500; do print(“storepoint”,k,”distance”,1000-dis,”oilquantity”,oil)； k=k+1; dis=dis+500/(2*k-1); oil= 500*k; while ( dis1000) oil=500*(k-1)+(1000-dis)*( 2*k-1); print(“storepoint”,k,”distance”,0,”oilquantity”,oil)； 8/9/2022 4:

12、03 PM174.1.3 迭代法解方程迭代法解方程的实质是按照下列步骤构造一个序列x0,x1,xn,来逐步逼近方程f(x)=0的解： 1）选取适当的初值x0； 2）确定迭代格式，即建立迭代关系，需要将方程f(x)=0改 写为x=(x)的等价形式； 构造序列x0，x1，xn，即先求得x1=(x0)，再求 x2=(x1)，如此反复迭代，就得到一个数列x0， x1，xn，若这个数列收敛，即存在极值，且函数 (x)连续，则很容易得到这个极限值x*就是方程f(x)=0的根。 8/9/2022 4:03 PM18【例1】迭代法求方程组根算法说明：方程组解的初值X=（x0，x1，xn-1）,迭代关系方程组为

13、：xi=gi(X)(i=0,1,n-1),w为解的精度,则算法如下：for(i=0;in;i+)xi=初始近似根;do k=k+1; for(i=0;in;i) yi=xi; for(i=0;in;i+) xi=gi(yi); for(i=0;iw and kmaxn )；for(i=0;i=1e-4); return(x1); 8/9/2022 4:03 PM22 令a0,b0=a,b，c0=(a0+b0)/2，若f(c0)=0，则c0为方程f(x)=0的根；否则，若f(a0)与f(c0)异号，即 f(a0)*f(c0)0，则令a1,b1=a0,c0；若f(b0)与f(c0)异号，即 f(b

14、0)*f(c0)0，则令a1,b1=c0,b0。 依此做下去，当发现f(cn)=0时，或区间an,bn足够小，比如| an-bn |0.0001时，就认为找到了方程的根。 用二分法求一元非线性方程f(x)= x3/2+2x2-8=0（其中表示幂运算）在区间0，2上的近似实根r，精确到0.0001.算法如下：图4-6 二分法求解 方程示意【例3】二分法求解方程f(x)=0根 用二分法求解方程f(x)=0根的前提条件是：f(x)在求解的区间a,b上是连续的，且已知f(a)与f(b)异号，即f(a)*f(b)0。8/9/2022 4:03 PM23main( ) float x,x1=0,x2=2,

15、f1,f2,f; print(“input a,b (f(a)*f(b)0) printf(No root); return; do x=(x1+x2)/2; f=x*x*x/2+2*x*x-8; if(f=0) break; if(f1*f0.0) x1=x; f1=x1*x1*x1/2+2*x1*x1-8; else x2=x;while(fabs(f)=1e-4);print(root=,x); 8/9/2022 4:03 PM244.2 蛮力法枚举法其它范例基础：计算机运算速度快实例：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配、枚举法、盲目搜索算法8/9/2022 4:0

16、3 PM254.2.1 枚举法 枚举（ enumerate）法（穷举法）根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解。枚举法设计的两个方面： 1）找出枚举范围：分析问题所涉及的各种情况。 2）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。8/9/2022 4:03 PM26【例1】百钱百鸡问题。中国古代数学家张丘建在他的算经中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?算法设计1：设x，y，z分别为公鸡、母鸡、小鸡的数量。 尝试范围：由题意给定共100钱要买百鸡，若全买公鸡最多买100

17、/5=20只，显然x的取值范围120之间；同理，y的取值范围在133之间，z的取值范围在1100之间。 约束条件： x+y+z=100 且 5*x+3*y+z/3=100 8/9/2022 4:03 PM27算法1如下： main( ) int x,y,z; for(x=1;x=20;x=x+1) for(y=1;y=34;y=y+1) for(z=1;z=100;z=z+1) if(100=x+y+z and 100=5*x+3*y+z/3) print(the cock number is,x)； print(the hen number is, y)； print(the chick n

18、umber is z); 算法分析：以上算法需要枚举尝试20*34*100=68000次。算法的效率显然太低8/9/2022 4:03 PM28算法设计2：在公鸡（x）、母鸡（y）的数量确定后，小鸡的数量z就固 定为100-x-y，无需再进行枚举了。此时约束条件只有一个： 5*x+3*y+z/3=100算法2如下： main( ) int x,y,z;for(x=1;x=20;x=x+1) for(y=1;y=33;y=y+1) z=100-x-y; if(z mod 3=0 and 5*x+3*y+z/3=100)print(the cock number is,x)； print(the

19、hen number is, y)； print(the chick number is z);算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定Z能被3整除时，才会判断“5*x+3*y+z/3=100”。这样省去了z不整除3时的算术计算和条件判断，进一步提高了算法的效率。 8/9/2022 4:03 PM29【例2】解数字迷： A B C A B A D D D D D D算法设计1：按乘法枚举1)枚举范围为： A：39（A=1，2时积不会得到六位数）,B：09, C：09 六位数表示为A*10000+B*1000+C*100+A*10+B， 共尝试700次。2)约束

20、条件为： 每次尝试，先求六位数与A的积，再测试积的各位是否符合条件，若符合则找到了问题的解。 测试积的各位是否相同比较简单的方法是，从低位开始， 每次都取数据的个位，然后整除10，使高位的数字不断变 成个位，并逐一比较。 8/9/2022 4:03 PM30算法1如下：main（ ） int A,B,C,D,E,E1,F,G1,G2,i; for(A=3; A=9; A+) for(B=0; B=9; B+) for(C=0; C=9; C+) F=A*10000+B*1000+C*100+A*10+B; E=F*A； E1=E; G1=E1 mod 10; for(i=1; i=5; i+)

21、 G2=G1; E1=E1/10; G1= E1 mod 10; if(G1G2 ) break; if(i=6) print( F，”*”，A，”=”，E); 8/9/2022 4:03 PM31算法说明1：算法中对枚举出的每一个五位数与A相乘，结果存储在变量E中。然后，测试得到的六位数E是否各个位的数字都相同。鉴于要输出结果，所以不要改变计算结果，而另设变量E1，用于测试运算。算法分析1：以上算法的尝试范围是A：39，B：09， C：09 。共尝试700次，每次，不是一个好的算法。算法设计2：将算式变形为除法：DDDDDD/A=ABCAB。此时只需枚举A：39 D：19，共尝试7*9=63

22、次。每次尝试，测试商的万位、十位与除数是否相同，千位与个位是否相同，都相同时为解。算法2如下:8/9/2022 4:03 PM32main（）int A,B,C,D,E,F; for(A=3;A=9;A+) for(D=1;D=9;D+) E = D*100000+D*10000+D*1000+D*100+D*10+D; if(E mod A=0) F=EA; if(F10000=A and (F mod 100)10=A) if(F1000 mod 10 =F mod 10) print( F，”*”，A，”=”，E); 8/9/2022 4:03 PM334.2.2 其它范例【例3】狱吏问

23、题 某国王对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次，按所定规则转动n间牢房中的某些门锁, 每转动一次, 原来锁着的被打开, 原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。 转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1 间转动一次；问通过n次后，那些牢房的锁仍然是打开的？8/9/2022 4:03 PM34算法设计1：1）用n个空间的一维数组an,每个元素记录一个锁的状 态，1为被锁上，0为被打开。2）用数学运算方便

24、模拟开关锁的技巧，对i号锁的一次开 关锁可以转化为算术运算：ai=1-ai。3）第一次转动的是1，2，3，n号牢房； 第二次转动的是2，4，6，号牢房； 第三次转动的是3，6，9，号牢房； 第i次转动的是i，2i，3i，4i，号牢房，是起点为i，公差为i的等差数列。 4）不做其它的优化，用蛮力法通过循环模拟狱吏的开关 锁过程，最后当第i号牢房对应的数组元素ai为0时，该牢房的囚犯得到大赦。算法1如下： 8/9/2022 4:03 PM35main1( )int *a,i,j,n; input(n); a=calloc(n+1,sizeof(int); for (i=1; i=n;i+) ai=

25、1; for (i=1; i=n;i+) for (j=i; j=n;j=j+i) aj=1-aj; for (i=1; i=n;i+) if (ai=0) print(i,”is free.”);算法分析：以一次开关锁计算，算法的时间复杂度为n(1+1/2+1/3+1/n)=O(nlogn)。8/9/2022 4:03 PM36问题分析：转动门锁的规则可以有另一种理解，第一次转动的是编号为1的倍数的牢房；第二次转动的是编号为2的倍数的牢房；第三次转动的是编号为3的倍数的牢房；则狱吏问题是一个关于因子个数的问题。令d(n)为自然数n的因子个数，这里不计重复的因子，如4的因子为1，2，4共三个因

26、子，而非1，2，2，4。则d(n)有的为奇数，有的为偶数，见下表: 表4-3 编号与因数个数的关系 n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 d(n) 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 数学模型1：上表中的d(n)有的为奇数，有的为偶数，由于牢房的门开始是关着的，这样编号为i的牢房，所含1i之间的不重复因子个数为奇数时，牢房最后是打开的，反之，牢房最后是关闭的。8/9/2022 4:03 PM37算法设计2:1）算法应该是求出每个牢房编号的不重复的因子个数，当它为奇数时，这里边的囚犯得到大赦。2）一个数的因子是没有规律的，只

27、能从1n枚举尝试。算法2如下：main2( )int s,i,j,n; input(n); for (i=1; i=n;i+) s=1; for (j=2; j=i;j=j+) if （i mod j=0） s=s+1; if （s mod 2 =1） print(i,”is free.”); 8/9/2022 4:03 PM38算法分析： 狱吏开关锁的主要操作是ai=1- ai;共执行了n*(1+1/2+1/3+1/n)次，时间近似为复杂度为O（n log n）。使用了n个空间的一维数组。算法2没有使用辅助空间，但由于求一个编号的因子个数也很复杂，其主要操作是判断i mod j是否为0，共执

28、行了n*(1+2+3+n)次，时间复杂度为O（n2）。 数学模型2：仔细观察表4-3，发现当且仅当n为完全平方数时,d(n)为奇数；这是因为n的因子是成对出现的,也即当n=a*b且ab时，必有两个因子a，b; 只有n为完全平方数，也即当n=a2时, 才会出现d(n)为奇数的情形。算法设计3：这时只需要找出小于n的平方数即可。算法3如下：8/9/2022 4:03 PM39main3( ) int s,i,j,n; input(n); for (i=1;i=n;i+) if（i*i=n） print(i,”is free.”); else break; 由此算法我们应当注意：在对运行效率要求较高

29、的大规模的数据处理问题时，必须多动脑筋找出效率较高的数学模型及其对应的算法。8/9/2022 4:03 PM404.3 分而治之算法分治算法框架二分法二分法变异其它分治方法8/9/2022 4:03 PM414.3.1 分治算法框架 1算法设计思想 将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。三个步骤：1）分解； 2）解决； 3）合并。8/9/2022 4:03 PM422适合用分治法策略的问题满足分治法解决问题的条件：1） 能将这

30、n个数据分解成k个不同子集合，且得到k个子集合是可以独立求解的子问题，其中1kn；2） 分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制；在求出这些子问题的解之后，就可以推解出原问题的解8/9/2022 4:03 PM43分治法的一般的算法设计模式如下：Divide-and-Conquer(int n) /n为问题规模/ if（nn0） /n0 为可解子问题的规模/ 解子问题； return(子问题的解)； /*分解为较小子问题p1,p2,pk*/ for （i=1 ;i=k;i+） yi=Divide-and-Conquer(|Pi|); /递归解决Pi/ T =MERGE(

31、y1,y2,.,yk); /合并子问题/ return(T); 8/9/2022 4:03 PM444.3.2 二分法当每次都将问题分解为原问题规模的一半时，称为二分法。二分法是分治法较常用的分解策略，数据结构课程中的折半查找、归并排序等算法都是采用此策略实现的。【例1】金块问题： 老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。算法设计1：比较简单的方法是逐个的进行比较查找。先拿两块比较重量，留下重的一个与下一块比较，直到全部比较完毕，就找到了最重的金子。算法类似于一趟选择排序8/9/2

32、022 4:03 PM45算法如下： maxmin( float a,int n) max=min=a1; for(i=2 i=n i+ ) if(max ai) min=ai; 算法分析1：算法中需要n-1次比较得到max。最好的情况是金块是由小到大取出的，不需要进行与min的比较，共进行n-1次比较。最坏的情况是金块是由大到小取出的，需要再经过n-1次比较得到min,共进行2*n-2次比较。至于在平均情况下，A(i)将有一半的时间比max大，因此平均比较数是3(n1)/2。8/9/2022 4:03 PM46算法设计2:问题可以简化为：在含n（n是2的幂（n=2）个元素的集合中寻找极大元和

33、极小元。用分治法（二分法）可以用较少比较次数地解决上述问题： 1） 将数据等分为两组（两组数据可能差1），目的是分别选取其中的最大（小）值。 2）递归分解直到每组元素的个数2，可简单地找到最大（小）值。 3）回溯时将分解的两组解大者取大，小者取小，合并为当前问题的解。8/9/2022 4:03 PM47算法2 递归求取最大和最小元素 float an;maxmin （int i, int j ,float &fmax, float &fmin） int mid; float lmax, lmin, rmax, rmin; if (i=j) fmax= ai; fmin=ai; else if

34、(i=j-1)if(airmax) fmax=lmax; else fmax=rmax; if(lminrmin)fmin=rmin; else fmin=lmin; 8/9/2022 4:03 PM48算法分析：MAXMIN需要的元素比较数是多少呢？如果用T(n)表示这个数，则所导出的递归关系式是:当n是2的幂时，即对于这个某个正整数k，n=2k，有可以证明，任何以元素比较为基础的找最大和最小元素的算法，其元素比较下界均为 次。因此，过程MAXMIN在这种意义上是最优的。8/9/2022 4:03 PM49【例2】残缺棋盘残缺棋盘是一个有2k2k （k1）个方格的棋盘，其中恰有一个方格残缺。

35、图4-7给出k=1时各种可能的残缺棋盘，其中残缺的方格用阴影表示。 号 号 号 号图4-7 四种三格板这样的棋盘我们称作“三格板”，残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。在此覆盖中要求：1）两个三格板不能重叠2）三格板不能覆盖残缺方格，但必须覆盖其他所有的方格在这种限制条件下，所需要的三格板总数为(2k2k -1 )/3。 8/9/2022 4:03 PM50算法设计1：分而治之方法解决残缺棋盘问题 1）问题分解过程如下： s=size/2 号号号号k=1，2，3，4都是如此，k=1为停止条件。 8/9/2022 4:03 PM512）棋盘的识别 棋盘的规模是一个必要的信息，有了

36、这个信息，只要知道其左上角的左上角方格所在行、列就可以唯一确定一个棋盘了，残缺方格或“伪”残缺方格直接用行、列号记录。 tr 棋盘中左上角方格所在行。 tc 棋盘中左上角方格所在列。 dr 残缺方块所在行。 dc 残缺方块所在列。 size 棋盘的行数或列数。数据结构设计：用二维数组board ，模拟棋盘。覆盖残缺棋盘所需要的三格板数目为：( size2 -1 ) / 3将这些三格板编号为1到( s i z e2-1 ) / 3。则将残缺棋盘三格板编号的存储在数组board 的对应位置中，这样输出数组内容就是问题的解。结合图4-9，理解算法。8/9/2022 4:03 PM52算法如下： in

37、t amount=0; main（） int size=1,x,y; input(k); for (i=1;i=k;i+) size=size*2; print(“input incomplete pane ”); input(x,y); Cover(0, 0, x, y, size); 图4-9 一个4*4的残缺棋盘及其解 8/9/2022 4:03 PM53 Cover(int tr, int tc, int dr, int dc, int size) if (size2) return;int t = amount +, / 所使用的三格板的数目s=size/2; / 子问题棋盘大小 /

38、残缺方格位于左上棋盘if (dr tr + s & dc tc + s)Cover ( tr, tc, dr, dc, s); Boardtr + s - 1tc + s = t; / 覆盖号三格板 Boardtr + stc + s - 1 = t; Boardtr + stc + s = t; Cover (tr, tc+s, tr+s-1, tc+s, s); / 覆盖其余部分 Cover(tr+s, tc, tr+s, tc+s-1, s); Cover(tr+s, tc+s, tr+s, tc+s, s); 8/9/2022 4:03 PM54else if(dr = tc + s)

39、/残缺方格位于右上象限Cover ( t r, tc+s, dr, dc, s); Boardtr + s - 1tc + s - 1 = t; / 覆盖号三格板 Boardtr + stc + s - 1 = t; Boardtr + stc + s = t; Cover (tr, tc, tr+s-1, tc+s-1, s); /覆盖其余部分 Cover(tr+s, tc, tr+s, tc+s-1, s); Cover(tr+s, tc+s, tr+s, tc+s, s);/残缺方格位于覆盖左下象限 else if (dr = tr + s & dc = tr + s & dc = tc

40、 + s) Cover(tr+s, tc+s, dr, dc, s); Boardtr + s - 1tc + s - 1 = t; / 覆盖号三格板 Boardtr + s - 1tc + s = t; Boardtr + stc + s - 1 = t; Cover (tr, tc, tr+s-1, tc+s-1, s); /覆盖其余部分 Cover (tr, tc+s, tr+s-1, tc+s, s); Cover(tr+s, tc, tr+s, tc+s-1, s); void OutputBoard(int size) for (int i = 0; i size; i+) for

41、 (int j = 0; j size; j+) print( Boardij); print(“换行符”); 算法分析：因为要覆盖(size2 -1)/ 3个三格板，所以算法的时间复杂性为（size2）。 8/9/2022 4:03 PM564.3.3 二分法变异 【例4】大整数乘法在某些情况下，我们需要处理很大的整数，它无法在计算机硬件能直接允许的范围内进行表示和处理。若用浮点数来存储它，只能近似地参与计算，计算结果的有效数字会受到限制。若要精确地表示大整数，并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。请设计一个有效的算法，可以进行两个n位大整数

42、的乘法运算。8/9/2022 4:03 PM57数据结构设计：首先用数组存储大整数数据，再将两个乘数和积都按由低位到高位逐位存储到数组元素中。算法设计1：存储好两个高精度数据后，模拟竖式乘法，让两个高精度数据的按位交叉相乘，并逐步累加即可得到精确的结果，用二重循环就可实现。 8/9/2022 4:03 PM58算法设计1：存储两个高精度数据，模拟竖式乘法，让两个高精度数据的按位交叉相乘，并逐步累加，即可得到精确的计算结果。用二重循环就可控制两个数不同位相乘的过程。只考虑正整数的乘法，算法细节设计如下：1) 按字符型处理，存储在字符串数组s1、s2中，计算结果存储在整型数组a中。2)通过字符的A

43、SCII码，数字字符可以直接参与运算，k位数字与j位数字相乘的表达式为：(s1k-48)*(s2j-48)。3)每一次数字相乘的结果位数是不固定的，而结果数组中每个元素只存储一位数字，所以用变量b暂存结果，若超过1位数则进位，用变量d存储。这样每次计算的表达式为： b= ai+(s1k-48)*(s2j-48)+d。8/9/2022 4:03 PM59main( ) long b,c,d; int i,i1,i2,j,k,n,n1,n2,a256; char s1256,s2256; input(s1); input(s2); for (i=0;i255;i+) ai=0; n1=strlen

44、(s1); n2=strlen(s2); d=0; for (i1=0,k=n1-1;i1n1;i1+,k-) for (i2=0,j=n2-1;i20) i=i+1; ai=ai+d mod 10; d=d/10; n=i; for (i=n;i=0;i-) print(ai);8/9/2022 4:03 PM60算法说明：循环变量j、k分别是两个乘数字符串的下标。i1表示字符串str1由低位到高位的位数，范围0n1-1（与k相同）。i2表示字符串str2由低位到高位的位数，范围0n2-1（与j相同）。i表示乘法正在运算的位，也是计算结果存储的位置。算法分析1：算法是以n1,n2代表两个乘数

45、的位数，由算法中的循环嵌套知，算法的主要操作是乘法，算法的时间复杂度是O（n1*n2）。 算法设计2：下面们用分治法来设计一个更有效的大整数乘积算法。设计的重点是要提高乘法算法的效率，设计如下：设X和Y都是n位的二进制整数，现在要计算它们的乘积X*Y。图4-10 大整数X和Y的分段8/9/2022 4:03 PM61 将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)，如图4-10所示。显然问题的答案并不是A*C*K1+C*D*K2（K1、K2与A、B、C、D无关），也就是说，这样做并没有将问题分解成两个独立的子问题。按照乘法分配律，分解后的计算过程如下：记：

46、X=A*2n/2+B ，Y=C*2n/2+D。这样，X和Y的乘积为：X*Y=(A*2n/2+B)(C*2n/2+D)=A*C*2n+(AD+CB)*2n/2+B*D(1)模型分析：如果按式(1)计算X*Y，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法，此外还要做2次移位 (分别对应于式(1)中乘2n和乘2n/2)。所有这些加法和移位共用O(n)步运算。设T(n)是2个n位整数相乘所需的运算总数，则由式(1)，我们有以下(2)式： 8/9/2022 4:03 PM62 T（1）=1 T（n）=4T(n/2)+O(n) （2）由此递归式迭代过程如下：

47、T(n)=4T(n/2)+cn =4(4T(n/22)+cn/21)+cn =42(T(n/23)+ cn/22)+41cn/21+cn = =4 k+4k-1 *2c+4k-2 *4c+4c2k-1+c2k =O（4k）= O(nlog4) =O（n2）所以可得算法的时间复杂度为T(n)=O(n2)。8/9/2022 4:03 PM63模型改进：X*Y=A*C*2n+(A-B)(D-C)+AC+BD*2n/2+B*D (3)式(3)看起来比式(1)复杂，但它仅需做3次n/2位整数的乘法：AC，BD和(A-B)(D-C)，6次加、减法和2次移位。由此可得: (4)用解递归方程的迭代公式法，不妨

48、设n=2k： T(n)=3T(n/2)+cn =3(3T(n/4)+cn/2)+cn =9(T(n/8)+ cn/4)+3cn/2+cn = =3k +3k-1 *2c+3k-2 *4c+3c2k-1+c2k = O(nlog3)则得到T(n)=O(nlog3)=O(n1.59)。8/9/2022 4:03 PM64MULT(X,Y,n) X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY S=SIGN(X)*SIGN(Y); /S为X和Y的符号乘积 X=ABS(X); Y=ABS(Y); /X和Y分别取绝对值 if（ n=1） if (X=1 and Y=1) return(S)； el

49、se return(0)； else A=X的左边n/2位; B=X的右边n/2位; C=Y的左边n/2位; D=Y的右边n/2位; ml=MULT(A,C,n/2); m2=MULT(A-B,D-C,n/2); m3=MULT(B,D,n/2); S=S*(m1*2n+(m1+m2+m3)*2n/2+m3); return(S); 8/9/2022 4:03 PM65【例】求数列的最大子段和。给定n个元素的整数列（可能有负整数）a1,a2,an，求形如：ai,ai+1,aj i,j=1,2,n, i0) return(aleft) ; else return(0);else center=(left+right)/2; left_sum=max_sub_sum(a,left,center); right_sum=max_sub_sum(a,center+1,right); s1=0; lefts=0;8/9/2022 4:03 PM68for (i=center;i=left;i-) lefts=lefts+ai; if( leftss1) s1=lefts;s2=0; rights=0;for( i=