分治算法例题

本文格式为Word版，下载可任意编辑——分治算法例题

C语言分治算法例题

目录

1031输油管道问题2

解题思路2

程序代码2

1032邮局选址5

解题思路5

程序源代码5

1034集合划分27

解题思路：7

程序源代码：7

1033集合划分9

解题思路9

程序源代码9

C语言分治算法例题

1031输油管道问题

解题思路

此题目可以分为两个步骤：

1、找出主管道的位置；

2、根据主管道的位置，计算各个油井到主管道的长度之和。

根据题意，设主管道贯穿东西，与y轴平行。而各个子油井则分布在主输油管道的上下两侧。如下图：

由上图，其实只需要确定主管道的y坐标，而与各个子油井的x坐标无关！根据猜测，易知：主管道的y坐标就是所有子油井y坐标的中位数。（可以用平面几何知识证明，略）

求中位数的方法可以用排序后取a[(left+right)/2]，当然更推荐用书上的线性时间选择算法解决。记求得的主管道为ym，最终要输出的结果只需要计算：

|yyi

i1nm|，输出即可。

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

程序代码

#includestdio.h

#includestdlib.h

voidswap(inta,intb)

{

inttmp=a;

a=b;

b=tmp;

}

C语言分治算法例题

//本函数求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)

{

//读取数据

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

{

//读取y

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

}

//排序

qsort(arr,0,n-1);

//取中位数的下标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坐标的中位数；

yp等于所有居民点y坐标的中位数；

分别求中位数的过程和上题类似，不再陈述。最终的计算结果：要求距离之和，输出|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坐标的中位数并计算距离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)

提醒：由于此题数据范围比较大，需要用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）表示整数n的m划分，则整数n的所有划分是：F(n,m)。

m1n

提醒：

1）由于此题数据范围比较大，需要用64位长整型即__int64或者longlong。

2）假使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()