




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
本文格式为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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025至2030中国生物质固体成型燃料行业深度研究及发展前景投资评估分析
- 2025至2030中国现金和硬币存放袋行业市场深度研究及发展前景投资可行性分析报告
- 2025至2030中国特氟龙板材行业市场竞争格局及有效策略与实施路径评估报告
- 探索教育机器人在远程教育中的应用
- 教育科技产业的政策环境分析
- 家庭教育资源的全球化及教育政策的推动作用
- 医疗健康教育与教师的责任担当研究
- 探索虚拟现实VR在体育训练中的运用
- 医疗教育改革中的教育投入分析
- 教学软件的安全性与数据保护问题探讨
- 小米员工管理手册
- 反恐防范重点目标档案 空白模板2023年
- 部队荣誉室设计方案
- 物业部季度经营分析报告
- 超声波式热量表超声波热量表
- 剑桥Think第一级Unit+1+Welcome课件
- 报告流动式起重机械定期检验自检报告
- 腺垂体功能减退症诊疗规范内科学诊疗规范诊疗指南2023版
- 北师大版八年级上册物理(基础版)(全册知识点考点梳理、重点题型分类巩固练习)(家教、补习、复习用)
- GB 2762-2022食品安全国家标准食品中污染物限量
- 工程力学基础(讲义)
评论
0/150
提交评论