分治算法例题_第1页
分治算法例题_第2页
分治算法例题_第3页
分治算法例题_第4页
分治算法例题_第5页
已阅读5页,还剩8页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

本文格式为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()

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论