參考b7分治算法

分治算法分治算法所謂分治算法就是將較大規(guī)模的問題分解成幾個較小規(guī)模的問題,通過對較小規(guī)模問題的求解達到對整個問題的求解。當我們將問題分解成兩個較小問題求解時的分治方法稱之為二分法。1、解決算法實現(xiàn)的同時,需要估算算法實現(xiàn)所需時間。分治算法時間是這樣確定的：解決子問題所需的工作總量（由子問題的個數(shù)、解決每個子問題的工作量決定）合并所有子問題所需的工作量。2、分治法是把任意大小問題盡可能地等分成兩個子問題的遞歸算法。3、分治的具體過程：//開始{if

①問題不可分 ②返回問題解else

{③從原問題中劃出含一半運算對象的子問題1；④遞歸調(diào)用分治法過程，求出解1；⑤從原問題中劃出含另一半運算對象的子問題2；⑥遞歸調(diào)用分治法過程，求出解2；⑦將解1、解2組合成整個問題的解；}}//結(jié)束分治算法——例1快速排序(遞歸算法)//將當前序列在中間位置的數(shù)定義為分隔數(shù)//在左半部分尋找比中間數(shù)大的數(shù)//在右半部分尋找比中間數(shù)小的數(shù)//若找到一組與排序目標不一致的數(shù)對則交換它們void

qsort(int

l,

int

r){int

i,

j,

mid,

p;i=l;j=r;mid=a[(l+r)/2];

do{while

(a[i]<mid)

i++;while

(a[j]>mid)

j--;if

(i<=j){p=a[i];

a[i]=a[j];

a[j]=p;i++;j--;

//繼續(xù)找//注意這里要有等號//若未到兩個數(shù)的邊界,則遞歸搜索左右區(qū)間}}while(i<=j);if

(l<j)

qsort(l,

j);if

(i<r)

qsort(i,

r);}分治算法——例2用遞歸算法實現(xiàn)二分查找即：有n個已經(jīng)從小到大排序好的數(shù)據(jù),輸入一個數(shù)m,用二分查找算法,判斷它是否在這n個數(shù)中。#include<iostream>using

namespace

std;int

jc(int,

int);int

n,

a[1000],

m;int

main(){int

x,

y,

i;cin

>>

n;x=1;

y=n;for

(i=1;

i<=n;

i++)cin

>>

a[i];

//輸入已排序的數(shù)cin

>>

m;

//輸入要查找的數(shù)jc(x,

y);

//二分遞歸查找

cout<<endl;}//遞歸過程int

jc(int

x,

int

y){int

k;k=(x+y)/2;if

(a[k]==m)//取中間位置點//找到查找的數(shù),輸出cout<<"then

num

in"<<k<<endl;if

(x>y)

//找不到該數(shù)cout

<<

"no

find"

<<

endl;else{if

(a[k]<m)jc(k+1,y);

//在后半段查找

if

(a[k]>m)jc(x,

k-1);

//在前半段查找}}分治算法——例3一元三次方程求解有形如：ax3+bx2+cx+d=0這樣的一個一元三次方程。給出該方程中各項的系數(shù)（a,

b,

c,

d均為實數(shù)）,并約定該方程存在三個不同實根（根的范圍在-100至100之間）,且根與根之差的絕對值≥1。要求由小到大依次在同一行輸出這三個實根（根與根之間留有空格）,并精確到小數(shù)點后2位。提示：記方程f(x)=0,

若存在2個數(shù)x1和x2,且x1<x2,f(x1)*f(x2)<0,則在(x1,x2)之間一定有一個根。【輸入】a,

b,

c,

d【輸出】三個實根（根與根之間留有空格）【輸入樣例】1

-5

-4

20【輸出樣例】-2.00

2.00

5.00分治算法——例3xx1=x-0.0005x2=x+0.0005xx1=x-0.0005【算法分析】為了便于求解,設方程f(x)=ax3+bx2+cx+d=0設根的值域（-100至100之間）中有x,其左右兩邊相距0.0005的地方有x1和x2兩個數(shù),即x1=x-0.0005,x2=x+0.0005。x1和x2間的距離（0.001）滿足精度要求（精確到小數(shù)點后2位）。若出現(xiàn)如圖所示的兩種情況之一,則確定x為f(x)=0的根。1、f(x1)*f(x2)<0 2、f(x1)=0分治算法——例3【思路1-枚舉法】根據(jù)題目的精度要求（小數(shù)點后2位）,我們可以在值域（-100至100之間）內(nèi)間隔0.01依次枚舉x的值,然后驗證x是否為根這里,不妨把根和值域都擴大100倍（-10000至10000之間）,然后依次枚舉該區(qū)間的每一個整數(shù)值x,

并在題目要求的精度內(nèi)設定區(qū)間：x1=(x-0.05)/100,x2=(x+0.05)/100。若區(qū)間端點的函數(shù)值f(x1)和f(x2)異號或者區(qū)間端點x1的函數(shù)值f(x1)=0,

則確定x/100為f(x)=0的一個根。//枚舉當前根*100的可能范圍輸入方程中各項的系數(shù)a,b,c,d

；for

(x=-10000;

x<=10000;

x++){x1=(x-0.05)/100;

x2=(x+0.05)/100;

//在題目要求的精度內(nèi)設定區(qū)間if

(f(x1)*f(x2)<0||f(x1)==0)

//區(qū)間兩端函數(shù)值異號或x1處函數(shù)值為0,

則x/100為根printf("%.2f",

x/100);}分治算法——例3【思路2-分治法】枚舉根的值域中的每一個整數(shù)x(-100≤x≤100)。由于根與根之差的絕對值≥1,

因此設定搜索區(qū)間[x1,x2],其中x1=x,

x2=x+1。若⑴f(x1)=0,

則確定x1為f(x)的根；⑵f(x1)*f(x2)>0,

則確定根x不在區(qū)間[x1,x2]內(nèi),設定[x2,x2+1]為下一個搜索區(qū)間⑶f(x1)*f(x2)<0,

則確定根x在區(qū)間[x1,x2]內(nèi)。如果確定根x在區(qū)間[x1,x2]內(nèi)的話,令x=(x1+x2)/2,

采用二分法,將區(qū)間[x1,x2]分成左右兩個子區(qū)間：左子區(qū)間[x1,x]和右子區(qū)間[x,x2]如果f(x1)*f(x)≤0,

則確定根在左區(qū)間[x1,x]內(nèi),將x設為該區(qū)間的右指針（x2=x）,繼續(xù)對左區(qū)間進行對分；如果f(x1)*f(x)>0,

則確定根在右區(qū)間[x,x2]內(nèi),將x設為該區(qū)間的左指針（x1=x）,繼續(xù)對右區(qū)間進行對分；上述對分過程一直進行到區(qū)間的間距滿足精度要求為止（x2-x1<0.001）。此時確定x1為f(x)的根。分治算法——例3{//枚舉每一個可能的根for

(x=-100;x<=100;x++){x1=x;

x2=x+1;//確定根的可能區(qū)間if

(f(x1)==0)printf("%.2f

",x1);//若x1為根,則輸出//若根在區(qū)間[x1,x2]中//若區(qū)間[x1,x2]不滿足精度要求,則循環(huán)//計算區(qū)間[x1,x2]的中間位置//若根在左區(qū)間,則調(diào)整右指針//若根在右區(qū)間,則調(diào)整左指針else

if

(f(x1)*f(x2)<0){while

(x2-x1>=0.001{xx=(x2+x1)/2;if

((f(x1)*f(xx))<=0)x2=xx;else

x1=xx;}printf("%.2f

",x1);

//區(qū)間[x1,x2]滿足精度要求,確定x1為根}}cout

<<

endl;}分治算法——例4設有N個選手進行循環(huán)比賽,其中N=2M,要求每名選手要與其他N-1名選手都賽一次,每名選手每天比賽一次,循環(huán)賽共進行N-1天,要求每天沒有選手輪空。【輸入】M【輸出】表格形式的比賽安排表【樣例輸入】3【樣例輸出】1

23456782

14365873

41278564

32187655

67812346

58721437

85634128

7654321分治算法——例4【問題分析】以M=3(即N=23=8)為例,可以根據(jù)問題要求,制定出如下圖所示的一種方案：以表格的中心為拆分點,將表格分成四個部分,就很容易看出有：①左上=右下,右上=左下；②左上所有單元格的數(shù)字加上4（n/2）后,就與右上相等。③將各個部分再進行分拆,同樣符合以上規(guī)律所以：1×1

2×2

4×4

8×8Day1Day2Day3Day4Day5Day6Day7123456782

1

4 3

+4

6587341278564321876556781234658721437856341287654321分治算法——例4//變量half表示當前方陣的大小,也是要生成的下一個方陣的大小的一半//構(gòu)造右上方方陣#include<cstdio>const

int

MAXN=33,

MAXM=5;intmatchlist[MAXN][MAXN];intm;intmain(){printf("Input

m:");scanf("%d",

&m);int

n=1<<

m,

k=1,half=1;matchlist[0][0]=1;while(k<=m){for(int

i=0;i<half;

i++)for(int

j=0;j<half;j++)matchlist[i][j+half]=matchlist[i][j]+half;for(int

i=0;i<half;i++)

//對稱交換構(gòu)造下半部分方陣

for(int

j=0;j<half;j++){

matchlist[i+half][j]=matchlist[i][j+half];

//左下方方陣等于右上方方陣matchlist[i+half][j+half]=matchlist[i][j];

//右下方方陣等于左上方方陣}half*=2;k++;}for(int

i=0;i<n;

i++){ for(int

j=0;j<n;j++)

printf("%4d",matchlist[i][j]);putchar('\n');}return

0;}分治算法——例5取余運算（mod）輸入b,p,k的值,求b^pmodk的值。其中b,p,k*k為長整形 數(shù)?！据斎霕永?109【輸出樣例】2^10mod9=7分治算法——例5【算法分析】本題數(shù)據(jù)規(guī)模大（b,

p都是長整形）,如果直接求bp,時間復雜度過大可以將bp分解成較小的數(shù),利用以下原理：A*B

%

K

=

(

(A

%

K)

*

(B

%

K)

)

%

K采用二分法,如：B19=

B9*B9

*

BB9

=B4*B4

*

BB4

=B2*B2B2

=B1*B1B1

=B0*B0

*

B是否要再乘以B11001分治算法——例5//利用分治求b^p%k//

b^0

%

k=1//分治,求tmp=b^(p/2)%k//b^p

%

k=(b^(p/2))^2

%

k//若p為奇數(shù),則需再乘以b#include<iostream>#include<cstdio>using

namespace

std;int

b,

p,

k,

a;int

f(int

p){if

(p==0)

return

1;int

tmp=f(p/2)%k;tmp=(tmp*tmp)

%

k;if

(p%2==1)

tmp=(tmp*b)

%k;return

tmp;}int

main(){cin

>>

b

>>

p

>>

k;int

tmpb=b;b%=k;//讀入3個數(shù)//將b的值備份//防止b太大printf("%d^%d

mod

%d=%d\n",

tmpb,

p,

k,

f(p));return

0;}分治算法——例6黑白棋子的移動（chessman）有2n個棋子（n≥4）排成一行,開始位置為白子全部在左邊,黑子全部在右邊,如下圖為n=5的情形：○○○○○●●●●●移動棋子的規(guī)則是：每次必須同時移動相鄰的兩個棋子,顏色不限,可以左移也可以右移到空位上去,但不能調(diào)換兩個棋子的左右位置。每次移動必須跳過若干個棋子（不能平移）,要求最后能移成黑白相間的一行棋子。如n=5時,成為：○●○●○●○●○●任務：編程打印出移動過程?！据斎霕永?【輸出樣例】chessman.outstep

0:ooooooo*******--step

1:oooooo--******o*step

2:oooooo******--o*step

3:ooooo--*****o*o*step

4:ooooo*****--o*o*step

5:oooo--****o*o*o*step

6:oooo****--o*o*o*step

7:ooo--***o*o*o*o*step

8:ooo*o**--*o*o*o*step

9:o--*o**oo*o*o*o*step10:o*o*o*--o*o*o*o*step11:--o*o*o*o*o*o*o*分治算法——例6【算法分析】我們先從n=4開始試試看：{－表示空位}初始：○○○○●●●●第1步：○○○－－●●●○●第2步：○○○●○●●－－●第3步：○－－●○●●○○●第4步：○●○●○●－－○●第5步：－－○●○●○●○●如果n=5呢？我們繼續(xù)嘗試,希望看出一些規(guī)律： 初始：

○○○○○●●●●●第1步：

○○○○－－●●●●○●第2步：

○○○○●●●●－－○●這樣,n=5的問題又分解成了n=4的情況,下面只要再做一下n=4的5個步驟就行了。同理,n=6的情況又可以分解成n=5的情況,……,所以,對于一個規(guī)模為n的問題,我們很容易地就把他分治成了規(guī)模為n-1的相同類型子問題。數(shù)據(jù)結(jié)構(gòu)如下：數(shù)組c[1..max]用來作為棋子移動的場所,初始時,c[1]~c[n]存放白子（用字符o表示）,c[n+1]~c[2n]存放黑子（用字符*表示）,c[2n+1],c[2n+2]為空位置（用字符—表示）。最后結(jié)果在c[3]~c[2n+2]中。分治算法——例6#include<iostream>using

namespace

std;int

n,

st,

sp;char

c[101];void

print()//打印{int

i;cout

<<

"step

"

<<

st

<<

':';for

(i=1;

i<=2*n+2;

i++)

cout

<<

c[i];cout

<<

endl;st++;}void

init(int

n)

//初始化{int

i;st=0;sp=2*n+1;for

(i=1;

i<=n;

i++)

c[i]='o';for

(i=n+1;

i<=2*n;

i++)

c[i]='*';c[2*n+1]='-';c[2*n+2]='-';print();}void

move(int

k)

//將c[k]、c[k+1]移動到空位{int

j;for

(j=0;j<=1;j++){c[sp+j]=c[k+j];c[k+j]='-';}sp=k;print();}//將2*n個棋子移動到合適位置//注意,這里的n是局部變量,與全局變量n不同void

mv(int

n){inti,k;if(n==4)

//n等于4的情況要特殊處理{move(4);

move(8);move(2);move(7);

move(1);}else{move(n);move(2*n-1);mv(n-1);}}intmain(){cin>>n;init(n);mv(n);}分治算法——例7月度開銷農(nóng)夫約翰是一個精明的會計師。他意識到自己可能沒有足夠的錢來維持農(nóng)場的運轉(zhuǎn)了。他計算出并記錄下了接下來N

(1≤N≤100,000)天里每天需要的開銷。約翰打算為連續(xù)的M

(1≤M≤N)

個財政周期創(chuàng)建預算案，他把一個財政周期命名為fajo月。每個fajo月包含一天或連續(xù)的多天，每天被恰好包含在一個fajo月里。約翰的目標是合理安排每個fajo月包含的天數(shù)，使得開銷最多的fajo月的開銷盡可能少。輸入：第一行包含兩個整數(shù)N、M，用單個空格隔開。接下來N行，每行包含一個1到10000之間的整數(shù)，按順序給出接下來N天里每天的開銷。輸出：一個整數(shù)，即最大月度開銷的最小值。分治算法——例7【算法分析】直接求解答案較困難。轉(zhuǎn)換思路，不難想到將問題轉(zhuǎn)換為判定性問題求 解，從1到10000*N（最大可能答案為N個數(shù)的和）枚舉答案i，找到第一 個滿足存在一種方案，使得開銷最多的fajo月開銷小于等于i的i輸出。設check(i)表示是否存在方案使得開銷最多的fajo月的開銷小于等于i。判斷check(i)可以用貪心法，從左到右掃描每一天的開銷，采用“物盡 其用”原則，在不超過i的前提下讓每一個fajo月的天數(shù)越多越好。如果最終得到的預算案小于等于M，則check(i)=1，否則check(i)=0；每次判斷時間復雜度O(N)，總的時間復雜度O(10000*N^2)，會超時。分治算法——例7如果check(i)=1,則答案必定小于等于i；如果check(i)=0，則答案必 定大于i。我們不必從小到大逐一枚舉答案，而用“二分枚舉答案”i值。用left表示二分區(qū)間左邊界，right表示右邊界，當right-left>1時：①mid=(left+right)/2②如果check(mid)=1則right=mid，否則left=mid重復執(zhí)行直到right-left<=1，由于left的左邊都是小于答案的，right的右邊是大于等于答案的。所以最終答案就是right。時間復雜度O（n*log(n*10000)）,可以通過本題。這就是非常常見的

“二分答案+貪心判斷”分治算法——例7#include

<iostream>

using

namespace

std;const

int

MAXN

=

100005;int

A[MAXN],N,M;//判斷l(xiāng)imit對應的fajo月數(shù)是否不超過Mbool

ok(int

limit){int

c

=

1;for(int

i=1,sum=0;

i<=N;

i++)if

(sum+A[i]<=limit)sum+=A[i];else{++c;

//找到一個fajo月sum=A[i];//若有一個數(shù)比limit大，則一定不符合要求

if

(sum>limit)return

0;}return

c<=M;}int

main(){cin

>>

N

>>

M;for(int

i=1;

i<=N;

i++)

cin

>>

A[i];int

l=1,

r=10000*N;while

(r-l>1){int

mid=l+r>>1;

//比(l+r)/2快if

(ok(mid))

r=mid;else

l

=

mid;}cout

<<

r

<<

endl;return

0;}分治算法——例8路由器安置一條街道安裝無線網(wǎng)絡，需要放置M個路由器。整條街道上一共有N戶居 民，分布在一條直線上，每一戶居民必須被至少一臺路由器覆蓋到?，F(xiàn) 在的問題是所有路由器的覆蓋半徑是一樣的，我們希望用覆蓋半徑盡可 能小的路由器來完成任務，因為這樣可以節(jié)省成本。輸入格式：輸入第一行包含兩個整數(shù)M和N，以下N行每行一個整數(shù)Hi表 示該戶居民在街道上相對于某個點的坐標。（不保證Hi有序）輸出格式：輸出僅包含一個數(shù)，表示最小的覆蓋半徑，保留一位小數(shù)。1

≤N,

M

≤100000，-10000000≤Hi≤10000000分治算法——例8【算法分析】跟上題類似，二分答案：設check(i)=0表示半徑為i不符合題目要 求，反之check(i)=1表示半徑為i符合題目要求。用貪心思想計算check(i)：對于最左邊的一戶居民，一定在第一 個圓的左邊緣。接著找到最左邊一個未被圓覆蓋到的居民，再畫一 個圓...如下圖共需要3個路由器。分治算法——例8答案要求精確到小數(shù)點后一位怎么辦？求出精確到小數(shù)點后兩位的答案，保留一位小數(shù)輸出。二分答案不僅適用于整數(shù)答案，也適用于求小數(shù)答案。答案集合想象成后一個數(shù)比前一個數(shù)大0.01遞增，將二分查找的指 向條件改為right-left>0.01即可。分治算法——例8#include

<iostream>using

namespace

std;constint

MAXN=100005