程序设计综合实践教学课件2-2-分治法.pptx

二、分治法 汉诺塔问题中使用的算法设计方法正是计算机科学中一种非常重要、也是最为普遍的算法设计方法：分治法（Divide-and-Conquer）分治法的字面意思就体现了它解决一个规模较大复杂问题的思路：分而治之用计算机求解问题所需的计算时间一般都与其规模有关最小规模的问题，一般很容易直接求解，解题所需的计算时间也很小；当遇到一个规模较大、难以直接解决问题时，分治法的设计思想是，将其分解成一些规模较小的相同问题，以便各个击破，分而治之对于分解出来的相同或相似子问题，可以再用同样方法将子问题分成更小的子问题，直至将问题分解成可以简单直接求解的子问题为止，这是一个递归的过程，合并子问题的解就形成了原问题的解分治法是设计很多高效算法的基础，如数据结构中树形结构处理、二分查找、快速排序、归并排序等1分治法一般可以用递归描述，包含以下三个部分：基础：若问题规模足够小，无法或没有必要继续分解时，很容易直接求解，这是递归必须的基础分解：将规模较大的复杂问题分解为若干个规模缩小、相互独立、与原问题类型相同的子问题，类型相同的子问题可以递归求解合并：将各个子问题的解合并为原问题的解分治法的难点或关键点在于如何分解问题和合并各子问题的解。

前面汉诺塔问题求解算法体现了分治法算法设计思想，下面再以无符号大数乘法为例讲述分治法22.1无符号大数Karatsuba乘法对于无符号大数乘法，我们可以用分治法按照传统的思路求解两个无符号大数X、Y乘积：基础:当Y是个位数时，X乘Y可以简单解决，用下述表示：UBigNumber MultiplyDigit(X,digit)；/digit:09分解:从低位到高位，将Y中每一位数字分解出来后，再与X相乘；合并:将上述分解后相乘结果依次放大 .后相加求和就是需要的结果，等价于从低位到高位，将Y中每一位数字分解出来后，再与X放大 .倍后的结果相乘，再把乘积累加3形成如下算法描述，抽象数据类型UBigNumber表示无符号大数：/算法2.2 返回无符号大数X、Y的乘积UBigNumber Multiply(UBigNumber X,UBigNumber Y)UBigNumber result=0;/累加结果初值为0 while (Y!=0)/从低到高依次处理Y的每一位 digit=Y%10;/取得Y的一位数字 result=result+MultiPlyDigit(X,digit);/将digit与放大后X相乘，再累加 X=X*10;/X放大10倍 Y=Y/10;/Y缩小10倍 return result;/返回结果 4 假如X、Y的位数为m、n，MultiplyDigit子算法的时间复杂度为O(m)，需要执行n次，上述算法的时间复杂度为O(m*n)，当m、n接近时，就是 。

1960年，Karatsuba博士研究了大数乘法，提出了时间复杂度为 的无符号大数乘法假设要相乘的两个无符号大是X、Y，可以把X，Y改为如下表示：其中Base是基数，对于十进制数，Base就是10于是：z2=a*c z1=a*d+c*b z0=b*d z1的计算可以继续简化为3次加法、1次乘法、1次减法推算如下：z1=a*d+c*b+(a*c+b*d-(a*c+b*d)=(a*d+c*b+a*c+b*d)-(a*c+b*d)=(a+b)*(c+d)-(z2+z0)5/算法2.3 无符号大数X、Y的Karatsuba乘法 UBigNumber Karatsuba(UBigNumber X,UBigNumber Y)if(Y 10)return MultiPlyDigit(X,Y);/返回X与数字Y相乘结果 if(X pTail;/从低位开始处理 while(p1!=pA-pHead)/第一大数剩余位处理 int digit=p1-digit*digit2+iCarry;iCarry=digit/10;digit%=10;_AppendFrontDigit(&result,digit);p1=p1-prev;if(iCarry!=0)/最后进位处理 _AppendFrontDigit(&result,iCarry);return result;9/返回无符号大数中start,end)数字子序列组成的无符号大数/超出范围部分数字忽略，忽略后子序列不存在时返回0struct UBigNumber _FetchSub(struct UBigNumber*pA,int start,int end)struct UBigNumber result;_InitUBN(&result);int i=0;struct Node*p=pA-pHead-next;while(i next;+i;（待续）10 while(i digit);/添加在尾部 p=p-next;+i;_Normalize(&result);return result;11/两个无符号大数相乘struct UBigNumber MultiplyUBN(struct UBigNumber*pA,struct UBigNumber*pB)if(pB-digitCount=1)/递归终止条件 return _MultiplyDigit(pA,pB-pTail-digit);else if(pA-digitCount=1)return _MultiplyDigit(pB,pA-pTail-digit);/计算拆分长度 int m=pA-digitCount;int n=pB-digitCount;int h=(m n?m:n)/2;/*拆分为a,b,c,d*/struct UBigNumber a,b,c,d;（待续）12 a=_FetchSub(pA,0,m-h);/高m-h位 b=_FetchSub(pA,m-h,m);/低h位 c=_FetchSub(pB,0,n-h);/高m-h位 d=_FetchSub(pB,n-h,n);/低h位 /计算z2,z0,z1,此处的乘法使用递归 struct UBigNumber z0,z1,z2;z2=MultiplyUBN(&a,&c);/z2=a*c;z0=MultiplyUBN(&b,&d);/z0=b*d;struct UBigNumber t1,t2,t3,t4,t5,result;t1=AddUBN(&a,&b);/t1=a+b t2=AddUBN(&c,&d);/t2=c+d /销毁各不再使用的无符号大数 DestoryUBN(&a);DestoryUBN(&b);DestoryUBN(&c);DestoryUBN(&d);13（待续）t3=MultiplyUBN(&t1,&t2);/t3=(a+b)*(c+d)t4=AddUBN(&z0,&z2);/t4=z0+z2 z1=SubUBN(&t3,&t4);/z1=(a+b)*(c+d)-z2-z0 int i;for(i=0;i 2*h;+i)/z2*=(10(2*h)_AppendDigit(&z2,0);for(i=0;i h;+i)/z1*=(10 h)_AppendDigit(&z1,0);t5=AddUBN(&z2,&z1);/t5=z2*102h+z1*10h result=AddUBN(&t5,&z0);/result=z2*102h+z1*10h+z014（待续）DestoryUBN(&z0);DestoryUBN(&z1);DestoryUBN(&z2);DestoryUBN(&t1);DestoryUBN(&t2);DestoryUBN(&t3);DestoryUBN(&t4);DestoryUBN(&t5);return result;15再将测试源程序文件test.c内无符号大数相加函数调用改为相乘函数调用后，运行情况如下：214332453275432764736247632453247003424637245673425873258743258745544752143324532754327647362476324532470034*2463724567342587325874325874554475=528056130713490902053138976214445429921605279211318761390100103810215016。