分治算法例題

本文格式為Word版，下載可任意編輯——分治算法例題

C語言分治算法例題

目錄

1031輸油管道問題2

解題思路2

程序代碼2

1032郵局選址5

解題思路5

程序源代碼5

1034集合劃分27

解題思路：7

程序源代碼：7

1033集合劃分9

解題思路9

程序源代碼9

C語言分治算法例題

1031輸油管道問題

解題思路

此題目可以分為兩個步驟：

1、找出主管道的位置；

2、根據(jù)主管道的位置，計算各個油井到主管道的長度之和。

根據(jù)題意，設主管道貫穿東西，與y軸平行。而各個子油井則分布在主輸油管道的上下兩側。如下圖：

由上圖，其實只需要確定主管道的y坐標，而與各個子油井的x坐標無關！根據(jù)猜測，易知：主管道的y坐標就是所有子油井y坐標的中位數(shù)。（可以用平面幾何知識證明，略）

求中位數(shù)的方法可以用排序后取a[(left+right)/2]，當然更推薦用書上的線性時間選擇算法解決。記求得的主管道為ym，最終要輸出的結果只需要計算：

|yyi

i1nm|，輸出即可。

另外要提醒的是此題多Case。

程序代碼

#includestdio.h

#includestdlib.h

voidswap(inta,intb)

{

inttmp=a;

a=b;

b=tmp;

}

C語言分治算法例題

//本函數(shù)求arr[p:q]的一個劃分i，使arr[p:i-1]都小于arr[i]，arr[i+1,q]都大于arr[i]

intpartition(int*arr,intp,intq)

{

intindex=p-1,start=p,base=arr[q];

for(;startq;start++)

{

if(arr[start]=base)

{

swap(arr[start],arr[++index]);

}

}

swap(arr[++index],arr[q]);

returnindex;

}

//快速排序

voidqsort(int*arr,intp,intq)

{

if(p=q)

{

intpos=partition(arr,p,q);

qsort(arr,p,pos-1);

qsort(arr,pos+1,q);

}

}

intarr[10001];

intmain()

{

intn;

//注意多case寫法

while(scanf(%d,n)!=EOF)

{

//讀取數(shù)據(jù)

for(inti=0;in;i++)

{

//讀取y

scanf(%d%d,arr[i],arr[i]);

}

//排序

qsort(arr,0,n-1);

//取中位數(shù)的下標mid，然后計算距離

longlongsum=0;

intmid=arr[n/2];

C語言分治算法例題

}

for(inti=0;in;i++){sum+=abs(mid-arr[i]);}printf(%I64d\n,sum);}return0;

C語言分治算法例題

1032郵局選址

解題思路

此題和上一題十分類似，這次是要找出在居民點中郵局的最正確位置。很簡單想到，這次不僅要確定y坐標，還要確定x坐標。類似猜想可以知道，郵局最正確位置(xp,yp)應當為：

xp等于所有居民點x坐標的中位數(shù)；

yp等于所有居民點y坐標的中位數(shù)；

分別求中位數(shù)的過程和上題類似，不再陳述。最終的計算結果：要求距離之和，輸出|xixp||yiyp|。

i1n

程序源代碼

#includestdio.h

#includestdlib.h

#includealgorithm

usingnamespacestd;

intx[10000],y[10000];

intmain()

{

intn;

while(scanf(%d,n)!=EOF

)

C語言分治算法例題

}

{//讀取x和y坐標for(inti=0;in;i++){scanf(%d%d,x[i],y[i]);}//調用STL中的排序算法,分別對x坐標和y坐標進行排序sort(x,x+n);sort(y,y+n);//取x，y坐標的中位數(shù)并計算距離intmidx=x[n/2];intmidy=y[n/2];longlongres=0;for(inti=0;in;i++){res+=abs(midx-x[i]);res+=abs(midy-y[i]);}//輸出結果printf(%I64d\n,res);}return0;

C語言分治算法例題

1034集合劃分2

解題思路：

遞推公式如下：

F(n,m)=m*F(n1,m)+F(n1,m1)

F（n，m）表示把n個元素的集合分為m個子集，有多少種分法。證明如下：

n個元素的集合可以劃分為F(n,m)個不同的由m個非空子集組成的集合?？紤]3個元素的集合，可劃分為

①1個子集的集合：{{1，2，3}}

②2個子集的集合：{{1，2}，{3}}，{{1，3}，{2}}，{{2，3}，{1}}③3個子集的集合：{{1}，{2}，{3}}

∴F(3,1)=1;F(3,2)=3;F(3,3)=1;

假使要求F(4,2)該怎么辦呢？

A.往①里添一個元素{4}，得到{{1，2，3}，{4}}

B.往②里的任意一個子集添一個4，得到

{{1，2，4}，{3}}，{{1，2}，{3，4}}，

{{1，3，4}，{2}}，{{1，3}，{2，4}}，

{{2，3，4}，{1}}，{{2，3}，{1，4}}

∴F(4,2)=F(3,1)+2*F(3,2)＝1+2*3＝7

推廣，得F(n,m)=F(n-1,m-1)+m*F(n-1,m)

提醒：由于此題數(shù)據(jù)范圍比較大，需要用64位長整型即__int64或者longlong。

程序源代碼：

#includestdio.h

//計算把含有n個元素的集合分割為m個子集，有多少種解決方案longlongdivide(intn,intm)

{

if(m==1||m==n)

{

return1;

}

else

{

returndivide(n-1,m-1)+m*divide(n-1,m);

}

C語言分治算法例題

}

intmain()

{

intn,m;

//多case輸入

while(scanf(%d%d,n,m)!=EOF)

{

printf(%I64d\n,divide(n,m));

}

return0;

}

C語言分治算法例題

1033集合劃分

解題思路

假定F（n,m）表示整數(shù)n的m劃分，則整數(shù)n的所有劃分是：F(n,m)。

m1n

提醒：

1）由于此題數(shù)據(jù)范圍比較大，需要用64位長整型即__int64或者longlong。

2）假使n比較大的話，遞歸算法計算時間會比較長，最好用動態(tài)規(guī)劃算法實現(xiàn)。程序源代碼

#includestdio.h

//計算把含有n個元素的集合分割為m個子集，有多少種解決方案longlongsubset(intn,intm)

{

if(n==m||m==1)

{

return1;

}

else

{

returnsubset(n-1,m-1)+m*subset(n-1,m);

}

}

intmain()