1. 什么是分治法？

   

   為湖口等地區(qū)用戶提供了全套網(wǎng)頁(yè)設(shè)計(jì)制作服務(wù)，及湖口網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、湖口網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！

   分治法的基本思想是將一個(gè)難以直接解決的大問(wèn)題，分解成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。

2. 何時(shí)能，何時(shí)用分治法來(lái)解決這些問(wèn)題比較好呢？

   這些問(wèn)題應(yīng)當(dāng)具備這幾個(gè)特征：

   （1）問(wèn)題的規(guī)?？s小到一定程度就可以容易的解決了。

   （2）問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同子問(wèn)題。

   （3）問(wèn)題所分解成各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。

   （4）問(wèn)題分解出的子問(wèn)題的解可以合并為原問(wèn)題的解。

   上述的第一條特征是絕大多數(shù)問(wèn)題可以滿足的，因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增大而增加；第二條特征是引用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用；第三條特征涉及分治法的效率，涉及許多不必要的工作-重復(fù)求解公共的子問(wèn)題，第四條特征是關(guān)鍵，能否利用分治法完全取決于問(wèn)題是否具有第四條特征。

3. 分治法的基本步驟：

   divide-and-conquer(P)

    {

   if ( | P | <= n0) adhoc(P);  //解決小規(guī)模的問(wèn)題

     divide P into smaller subinstances P1,P2,...,Pk；//分解問(wèn)題

     for (i=1,i<=k,i++)

     yi=divide-and-conquer(Pi); //遞歸的解各子問(wèn)題

   return merge(y1,...,yk); //將各子問(wèn)題的解合并為原問(wèn)題的解

        }

        如果問(wèn)題足夠小能夠直接解決，則解決，如果不能夠在進(jìn)行分治。

4.分治法與遞歸，分治法與循環(huán)

分治法是一種思想，遞歸和循環(huán)都只不過(guò)是一種手段，來(lái)幫助問(wèn)題來(lái)進(jìn)行分治。

示例如下：

（1）二分查找算法的非遞歸形式

 int NBinarySearch(int n,int s[n],int x)

{

int low=0,high=n-1;

//通過(guò)循環(huán)手段來(lái)進(jìn)行分治

while(low<=high)

{

int middle=(low+high)/2;

if(x==s[middle]) return middle;

else if(x>s[middle]) low=middle+1;

else high=middle-1;

}

}

(2)二分查找算法的遞歸形式

int BinarySearch(int s[n],int x,int low,int high)

{

if(low>high) return -1;

int middle=(low+high)/2;

if(x==s[middle]) return middle;

else if(x>middle)

return BinarySearch(s,x,middle,high)

else

return BinarySearch(s,x,low,middle-1);

}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。