分治算法例題

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

C語言分治算法例題

目錄

1031輸油管道問題2

解題思路2

程序代碼2

1032郵局選址5

解題思路5

程序源代碼5

1034集合劃分27

解題思路：7

程序源代碼：7

1033集合劃分9

解題思路9

程序源代碼9

C語言分治算法例題

1031輸油管道問題

解題思路

此題目可以分為兩個(gè)步驟：

1、找出主管道的位置；

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

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

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

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

|yyi

i1nm|，輸出即可。

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

程序代碼

#includestdio.h

#includestdlib.h

voidswap(inta,intb)

{

inttmp=a;

a=b;

b=tmp;

}

C語言分治算法例題

//本函數(shù)求arr[p:q]的一個(gè)劃分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ù)的下標(biāo)mid，然后計(jì)算距離

longlongsum=0;

intmid=arr[n/2];

C語言分治算法例題

}

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

C語言分治算法例題

1032郵局選址

解題思路

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

xp等于所有居民點(diǎn)x坐標(biāo)的中位數(shù)；

yp等于所有居民點(diǎn)y坐標(biāo)的中位數(shù)；

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

i1n

程序源代碼

#includestdio.h

#includestdlib.h

#includealgorithm

usingnamespacestd;

intx[10000],y[10000];

intmain()

{

intn;

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

)

C語言分治算法例題

}

{//讀取x和y坐標(biāo)for(inti=0;in;i++){scanf(%d%d,x[i],y[i]);}//調(diào)用STL中的排序算法,分別對(duì)x坐標(biāo)和y坐標(biāo)進(jìn)行排序sort(x,x+n);sort(y,y+n);//取x，y坐標(biāo)的中位數(shù)并計(jì)算距離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]);}//輸出結(jié)果printf(%I64d\n,res);}return0;

C語言分治算法例題

1034集合劃分2

解題思路：

遞推公式如下：

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

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

n個(gè)元素的集合可以劃分為F(n,m)個(gè)不同的由m個(gè)非空子集組成的集合。考慮3個(gè)元素的集合，可劃分為

①1個(gè)子集的集合：{{1，2，3}}

②2個(gè)子集的集合：{{1，2}，{3}}，{{1，3}，{2}}，{{2，3}，{1}}③3個(gè)子集的集合：{{1}，{2}，{3}}

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

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

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

B.往②里的任意一個(gè)子集添一個(gè)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位長(zhǎng)整型即__int64或者longlong。

程序源代碼：

#includestdio.h

//計(jì)算把含有n個(gè)元素的集合分割為m個(gè)子集，有多少種解決方案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位長(zhǎng)整型即__int64或者longlong。

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

#includestdio.h

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

{

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

{

return1;

}

else

{

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

}

}

intmain()