递归与分治实验报告Word下载.docx
- 文档编号:8288213
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:7
- 大小:17.76KB
递归与分治实验报告Word下载.docx
《递归与分治实验报告Word下载.docx》由会员分享,可在线阅读,更多相关《递归与分治实验报告Word下载.docx(7页珍藏版)》请在冰点文库上搜索。
publicstaticvoidmain(stringargs[]){
intx,n;
inta[]={1,3,4,5,6,13,25};
x=6;
n=7;
ints;
s=binarysearch(a,x,n);
system.out.println(s);
合并排序
publicclassmergesort{
publicstaticvoidmergesort(int[]a){}publicstaticvoidmergepass(int[]x,int[]y,ints){}publicstaticvoidmerge(int[]c,int[]d,intl,intm,intr){inti=1,j=m+1,k=1;
inti=0;
while(i }}if(c[i]-(c[j])m)for(intq=j;
q 快速排序
publicclassQsort{
privatestaticvoidqsort(inta[],intp,intr){}privatestaticintpartition(inta[],intp,intr){inti=p;
intj=r+1;
intx=a[p];
inttemp;
while(true){while((a[++i]-x)0);
if(i>
=j)break;
temp=a[i];
if(p }}}a[j]=temp;
mymath.swap(a,i,j);
//a[p]=a[j];
a[j]=x;
returnj;
publicstaticvoidmain(string[]args){}
inta[]={4,2,7,9,1};
qsort(a,0,4);
for(inti=0;
;
i++){}system.out.println(a[i]);
4.实验分析和总结
掌握了递归与分治策略的基本思想
掌握了递归算法在阶乘函数、Ackerman函数、整数划分等问题上的应用掌握了二分查找、合并排序、快速排序等问题的分治算法实现
熟悉了myeclipse或eclipse等Java开发工具的使用。
篇二:
递归与分治实验报告
班级:
计科1102姓名:
赵春晓学号:
20XX31020XX31
实验目的:
进一步掌握递归与分治算法的设计思想,通过实际问题来应用递归与分治设计算法。
实际问题:
1集合划分问题,2输油管道问题,3邮局选址问题,4整数因子分解问题,5众数问题。
问题1:
集合划分
算法思想:
对于n个元素的集合,可以划分为由m个子集构成的集合,例如{{1,2}{3,4}}就是由2个子集构成的非空子集。
假设f(n,m)表示将n个元素划分成由m个子集构成的集合的个数。
那么1)若m==1,则f(n,m)=1;
2)若n==m,则f(n,m)=1;
3)若不是上面两种情况则有下面两种情况构成:
3.1)向n-1个元素划分成的m个集合里面添加一个新的元素,则有m*f(n-1,m)种方法;
3.2)向n-1个元素划分成的m-1个集合里添加一个由一个元素形成的独立的集合,则有f(n-1,m-1)种方法。
实验代码:
#include
usingnamespacestd;
intjihehuafen(intn,intm)
{
if(m==1||n==m)
return1;
else
returnjihehuafen(n-1,m-1)+m*jihehuafen(n-1,m);
}
intmain()
ifstreamfin("
c:
/input.txt"
);
ofstreamfout("
/output.txt"
intn,m,num;
fin>
>
n>
m;
num=jihehuafen(n,m);
fout return0;
问题2:
输油管道
由于主管道由东向西铺设。
故主管道的铺设位置只和各油井的y坐标有关。
要使主管道的y坐标最小,主管道的位置y坐标应是各个油井y坐标的中位数。
先用快速排序法把各个油井的y坐标排序,然后取其中位数再计算各个油
井y坐标与中位数差值的绝对值之和。
structpoint//定义坐标结构体
intx;
inty;
};
//快速排序
voidsort(pointa[],intsize)
inti=0,j=size-1;
inttemp;
//用来保存作为基准的数
if(size>
=1)
temp=a[0].y;
//用区间的第一个元素作为基准
while(i!
=j)//区间两端交替向中间扫描,知道i=j
while(i {
a[i].y=a[j].y;
i++;
a[j].y=a[i].y;
j--;
a[i].y=temp;
sort(a,i);
//对左递归
sort(a+i+1,size-i-1);
//对右递归
//取中位数
intmadian(point*a,intsize)
intnum=size+1;
returna[num/2-1].y;
//returnsize%2?
a[size>
1].y:
(a[size>
1].y+a[(size>
1)+1].y)>
1;
//计算最短路程
intlucheng(point*a,intsize)
intmid=madian(a,size);
inti,sum=0;
for(i=0;
i {
sum+=abs(a[i].y-mid);
returnsum;
intn;
n;
point*p=newpoint[n];
for(inti=0;
i fin>
p[i].x>
p[i].y;
sort(p,n);
intminlen=lucheng(p,n);
问题3:
邮局选址问题
同问题2
structpoint
voidsort_x(point*a,intsize)
temp=a[0].x;
//
=(:
递归与分治实验报告)j)
while(i if(i {
a[i].x=a[j].x;
a[j].x=a[i].x;
a[i].x=temp;
sort_x(a,i);
sort_x(a+i+1,size-i-1);
voidsort_y(point*a,intsize)
sort_y(a,i);
sort_y(a+i+1,size-i-1);
intmadian_x(point*a,intsize)
//intnum=size+1;
//returna[num/2-1].x;
returnsize%2?
1].x:
1].x+a[(size>
1)+1].x)>
intmadian_y(point*a,intsize)
篇三:
递归与分治算法编程-实验报告
南京信息工程大学实验(实习)报告实验名称递归与分治算法编程实验日期5.14得分指导教师刘文杰
院计软专业软件工程年级二班次一
姓名陈忠阳学号20XX1344012
3)采用myeclipse或eclipse编程实现基于分治策略的快速排序算法。
1:
二分搜索
packagepackage;
publicclasssuanfa{
publicstaticintbinarysearch(int[]a,intx,intn)
intleft=0;
while(left {
intmiddle=(left+right)/2;
if(x==a[middle])
returnmiddle;
a[middle])
returnmiddle+1;
right=middle+1;
publicstaticvoidmain(string[]args)
int[]aa=newint[]{1,3,5,7,9,11,13,15,17,19};
suanfamain=newsuanfa();
system.out.println("
aatheresultis:
"
+main.binarysearch(aa,9,10));
2:
合并排序算法
packagep1;
importjava.util.Arrays;
publicclassguy
privatestaticvoidmergesort(int[]array,intstart,intend,int[]tempArray)
if(end {
return;
intmiddle=(start+end)/2;
mergesort(array,start,middle,tempArray);
mergesort(array,middle+1,end,tempArray);
intk=0,leftIndex=0,rightIndex=end-start;
system.arraycopy(array,start,tempArray,0,middle-start+1);
tempArray[end-start-i]=array[middle+i+1];
while(k {
if(tempArray[rightIndex]>
tempArray[leftIndex])//从小到大
array[k+start]=tempArray[leftIndex++];
array[k+start]=tempArray[rightIndex--];
k++;
int[]array=newint[]{11,213,134,65,77,78,23,43};
mergesort(array,0,array.length-1,newint[array.length]);
system.out.println(Arrays.tostring(array));
3:
publicclassQuicksort{
publicstaticvoidmain(string[]args){
int[]array={49,38,65,97,76,13,27};
quicksort(array,0,array.length-1);
i system.out.println(array[i]);
publicstaticvoidquicksort(int[]n,intleft,intright){
intpivot;
if(left pivot=partition(n,left,right);
quicksort(n,left,pivot-1);
quicksort(n,pivot+1,right);
publicstaticintpartition(int[]n,intleft,intright){
intpivotkey=n[left];
while(left while(left n[left]=n[right];
while(left n[right]=n[left];
n[left]=pivotkey;
returnleft;
通过这次实验,使我掌握了基于分治策略的二分查找算法,合并排序算法,快速排序算法。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 递归 分治 实验 报告