程序設(shè)計綜合實踐-分治法

二、分治法

漢諾塔問題中使用的算法設(shè)計方法正是計算機科學(xué)中一種非常重要、也是最為普遍的算法設(shè)計方法：分治法（Divide-and-Conquer）。分治法的字面意思就體現(xiàn)了它解決一個規(guī)模較大復(fù)雜問題的思路：分而治之。用計算機求解問題所需的計算時間一般都與其規(guī)模有關(guān)。最小規(guī)模的問題，一般很容易直接求解，解題所需的計算時間也很??；當(dāng)遇到一個規(guī)模較大、難以直接解決問題時，分治法的設(shè)計思想是，將其分解成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。對于分解出來的相同或相似子問題，可以再用同樣方法將子問題分成更小的子問題，直至將問題分解成可以簡單直接求解的子問題為止，這是一個遞歸的過程，合并子問題的解就形成了原問題的解。分治法是設(shè)計很多高效算法的基礎(chǔ)，如數(shù)據(jù)結(jié)構(gòu)中樹形結(jié)構(gòu)處理、二分查找、快速排序、歸并排序等。1分治法一般可以用遞歸描述，包含以下三個部分：基礎(chǔ)：若問題規(guī)模足夠小，無法或沒有必要繼續(xù)分解時，很容易直接求解，這是遞歸必須的基礎(chǔ)。分解：將規(guī)模較大的復(fù)雜問題分解為若干個規(guī)?？s小、相互獨立、與原問題類型相同的子問題，類型相同的子問題可以遞歸求解。合并：將各個子問題的解合并為原問題的解。分治法的難點或關(guān)鍵點在于如何分解問題和合并各子問題的解。前面漢諾塔問題求解算法體現(xiàn)了分治法算法設(shè)計思想，下面再以無符號大數(shù)乘法為例講述分治法。22.1無符號大數(shù)Karatsuba乘法對于無符號大數(shù)乘法，我們可以用分治法按照傳統(tǒng)的思路求解兩個無符號大數(shù)X、Y乘積：基礎(chǔ):當(dāng)Y是個位數(shù)時，X乘Y可以簡單解決，用下述表示：UBigNumberMultiplyDigit(X,digit)；//digit:0~9分解:從低位到高位，將Y中每一位數(shù)字分解出來后，再與X相乘；合并:將上述分解后相乘結(jié)果依次放大...后相加求和就是需要的結(jié)果，等價于從低位到高位，將Y中每一位數(shù)字分解出來后，再與X放大...倍后的結(jié)果相乘，再把乘積累加。3形成如下算法描述，抽象數(shù)據(jù)類型UBigNumber表示無符號大數(shù)：//算法2.2返回?zé)o符號大數(shù)X、Y的乘積UBigNumberMultiply(UBigNumberX,UBigNumberY){UBigNumberresult=0;//累加結(jié)果初值為0while(Y!=0)//從低到高依次處理Y的每一位{digit=Y%10;//取得Y的一位數(shù)字result=result+MultiPlyDigit(X,digit);//將digit與放大后X相乘，再累加X=X*10;//X放大10倍Y=Y/10;//Y縮小10倍}returnresult;//返回結(jié)果}4假如X、Y的位數(shù)為m、n，MultiplyDigit子算法的時間復(fù)雜度為O(m)，需要執(zhí)行n次，上述算法的時間復(fù)雜度為O(m*n)，當(dāng)m、n接近時，就是。1960年，Karatsuba博士研究了大數(shù)乘法，提出了時間復(fù)雜度為的無符號大數(shù)乘法。假設(shè)要相乘的兩個無符號大是X、Y，可以把X，Y改為如下表示：其中Base是基數(shù)，對于十進制數(shù)，Base就是10。于是：z2=a*cz1=a*d+c*bz0=b*dz1的計算可以繼續(xù)簡化為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無符號大數(shù)X、Y的Karatsuba乘法UBigNumberKaratsuba(UBigNumberX,UBigNumberY){if(Y<10)returnMultiPlyDigit(X,Y);//返回X與數(shù)字Y相乘結(jié)果if(X<10)returnMultiPlyDigit(Y,X);//返回Y與數(shù)字X相乘結(jié)果h=(max(X的位數(shù),Y的位數(shù))+1)/2;//為X、Y兩個數(shù)位數(shù)設(shè)b、a分別為X的低h位、剩余高位組成的大數(shù)；//不足時高位補0設(shè)d、c分別為Y的低h位、剩余高位組成的大數(shù)；z2=Karatsuba(a,c);z0=Karatsuba(b,d);z1=Karatsuba(a+b,c+d)-(z2+z0);return;//返回結(jié)果}62.2Karatsuba乘法程序?qū)崿F(xiàn)本節(jié)在第1章樣例1.4基礎(chǔ)上，無符號大數(shù)用帶頭結(jié)點的雙向鏈表來表示，用程序?qū)崿F(xiàn)無符號大數(shù)Karatsuba乘法。增加_MultiplyDigit函數(shù)，實現(xiàn)無符號大數(shù)與數(shù)字相乘；增加_FetchSub函數(shù)，實現(xiàn)取無符號大數(shù)中某一段連續(xù)數(shù)字形成一個新大數(shù)；增加大數(shù)相減算法函數(shù)SubUBN；無符號大數(shù)放大倍可以通過原尾部添加0的_AppendDigit函數(shù)實現(xiàn)；在此基礎(chǔ)上實現(xiàn)了Karatsuba無符號大數(shù)乘法函數(shù)MultiplyUBN。7//無符號大數(shù)乘1位數(shù)structUBigNumber_MultiplyDigit(structUBigNumber*pA,intdigit2){structUBigNumberresult;_InitUBN(&result);if(digit2==0){_AppendDigit(&result,0);returnresult;}intiCarry=0;//進位，初始0structNode*p1;

8（待續(xù)）p1=pA->pTail;//從低位開始處理while(p1!=pA->pHead)//第一大數(shù)剩余位處理{intdigit=p1->digit*digit2+iCarry;iCarry=digit/10;digit%=10;_AppendFrontDigit(&result,digit);p1=p1->prev;}if(iCarry!=0)//最后進位處理_AppendFrontDigit(&result,iCarry);returnresult;}9//返回?zé)o符號大數(shù)中[start,end)數(shù)字子序列組成的無符號大數(shù)//超出范圍部分數(shù)字忽略，忽略后子序列不存在時返回0structUBigNumber_FetchSub(structUBigNumber*pA,intstart,intend){structUBigNumberresult;_InitUBN(&result);inti=0;structNode*p=pA->pHead->next;while(i<start&&p!=NULL){p=p->next;++i;}（待續(xù)）

10while(i<end&&p!=NULL){_AppendDigit(&result,p->digit);//添加在尾部p=p->next;++i;}_Normalize(&result);returnresult;}11//兩個無符號大數(shù)相乘structUBigNumberMultiplyUBN(structUBigNumber*pA,structUBigNumber*pB){if(pB->digitCount==1)//遞歸終止條件return_MultiplyDigit(pA,pB->pTail->digit);elseif(pA->digitCount==1)return_MultiplyDigit(pB,pA->pTail->digit);//計算拆分長度intm=pA->digitCount;intn=pB->digitCount;inth=(m>n?m:n)/2;/*拆分為a,b,c,d*/structUBigNumbera,b,c,d;（待續(xù)）

12a=_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,此處的乘法使用遞歸structUBigNumberz0,z1,z2;z2=MultiplyUBN(&a,&c);//z2=a*c;z0=MultiplyUBN(&b,&d);//z0=b*d;structUBigNumbert1,t2,t3,t4,t5,result;t1=AddUBN(&a,&b);//t1=a+bt2=AddUBN(&c,&d);//t2=c+d//銷毀各不再使用的無符號大數(shù)DestoryUBN(&a);DestoryUBN(&b);DestoryUBN(&c);DestoryUBN(&d);

13（待續(xù)）t3=MultiplyUBN(&t1,&t2);//t3=(a+b)*(c+d)t4=AddUBN(&z0,&z2);//t4=z0+z2z1=SubUBN(&t3,&t4);//z1=(a+b)*(c+d)-z2-z0inti;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*10^2h+z1*10^hresult=AddUBN(&t5,&z0);//result=z2*10^2h+z1*10^h+z014（待續(xù)）

DestoryUBN(&z0);DestoryUBN(&z1);DestoryUBN(&z2);DestoryUBN(&t1);DestoryUBN(&t2);DestoryUBN(&t3);DestoryUBN(&t4);DestoryUBN(&t5);returnr