递归与分治策略应用基础.docx
- 文档编号:10046497
- 上传时间:2023-05-23
- 格式:DOCX
- 页数:8
- 大小:70.98KB
递归与分治策略应用基础.docx
《递归与分治策略应用基础.docx》由会员分享,可在线阅读,更多相关《递归与分治策略应用基础.docx(8页珍藏版)》请在冰点文库上搜索。
递归与分治策略应用基础
《算法设计与分析》实验报告
实验一递归与分治策略应用基础
学号:
姓名:
班级:
一、实验目的
1、熟悉递归的概念和分治法。
2、对递归与分治算法时间空间复杂度分析,以及问题复杂性分析方法。
递归与分治策略的问题类型,并能设计相应的分治策略算法。
二、实验内容
任务:
以下题目要求应用递归与分治策略设计解决方案,本次实验成绩按百分制计,完成各小题的得分如下,每小题要求算法描述准确且程序运行正确。
1、求n个元素的全排。
(30分)
算法分析:
用递归的方法,先将n个数分成两个部分,然后将两个部分交换位子,然后再将这两个部分继续再分成四个部分,然后再将每个部分进行交换,然后就重复刚才的过程,直到不能再分为止,在这个过程中所产生的所有结果就是我们要求的全排列。
代码实现:
#include
intn=0;
voidswap(int*a,int*b)
{
intm;
m=*a;
*a=*b;
*b=m;
}
voidperm(intlist[],intk,intm)
{
inti;
if(k>2)
{
for(i=0;i<=2;i++)
printf("%d",list[i]);
printf("\n");
n++;
}
else
{
for(i=k;i<=2;i++)
{
swap(&list[k],&list[i]);
perm(list,k+1,4);
swap(&list[k],&list[i]);
}
}
}
intmain()
{
intlist[]={1,2,3,4};
perm(list,0,2);
printf("total:
%d\n",n);
return0;
}
2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。
(30分)
算法分析:
用分治策略,将大的棋盘分割为下一级的棋盘,直到不能再分为止,然后再将每一个小的棋盘填满,接着将一个一个小的棋盘再又合并成一个大的棋盘。
代码实现:
#include"iostream"
usingnamespacestd;
intboard[1025][1025];
inttile=1;
//tr,tc棋盘左上角方格坐标,dr,dc特殊方格所在坐标,size为行数
voidChessBoard(inttr,inttc,intdr,intdc,intsize)
{
if(size==1)
return;
intt=tile++;//L型骨牌号
ints=size/2;
//覆盖左上角子棋盘
if(dr
//特殊方格在此棋盘中
ChessBoard(tr,tc,dr,dc,s);
else{
//此棋盘无特殊方格,用t号L型骨牌覆盖右下角
board[tr+s-1][tc+s-1]=t;
//覆盖其余方格
ChessBoard(tr,tc,tr+s-1,tc+s-1,s);
}
//覆盖右上角子棋盘
if(dr
//特殊方格在此棋盘中
ChessBoard(tr,tc+s,dr,dc,s);
else{
board[tr+s-1][tc+s]=t;
ChessBoard(tr,tc+s,tr+s-1,tc+s,s);
}
//覆盖左下角子棋盘
if(dr>=tr+s&&dc ChessBoard(tr+s,tc,dr,dc,s); else{ board[tr+s][tc+s-1]=t; ChessBoard(tr+s,tc,tr+s,tc+s-1,s); } //覆盖右下角子棋盘 if(dr>=tr+s&&dc>=tc+s) ChessBoard(tr+s,tc+s,dr,dc,s); else{ board[tr+s][tc+s]=t; ChessBoard(tr+s,tc+s,tr+s,tc+s,s); } } intmain(){ intk,x,y,i,j; while(cin>>k) { tile=1; cin>>x>>y; intsize=1< board[x][y]=0; ChessBoard(0,0,x,y,size); for(i=0;i { for(j=0;j cout< cout< } } return0; } 3、设有n=2k个运动员要进行网球循环赛。 设计一个满足要求的比赛日程表。 (40分) #include #include #include voidTable(doublek,int**a){ inti,j,s,t,n=pow(2,k); for(i=1;i<=n;i++)a[1][i]=i; intm=1; for(s=1;s<=k;s++){ n/=2; for(t=1;t<=n;t++) for(i=m+1;i<=2*m;i++) for(j=m+1;j<=2*m;j++){ a[i][j+(t-1)*m*2]=a[i-m][j+(t-1)*m*2-m]; a[i][j+(t-1)*m*2-m]=a[i-m][j+(t-1)*m*2]; } m*=2; } } printf(int**a,intn){ for(inti=1;i<=n;i++){ for(intj=1;j<=n;j++) printf("%d",a[i][j]); printf("\n"); } } voidmain(){ printf("输入人数: "); intn,r; scanf("%d",&n); printf("比赛时间: "); scanf("%d",&r); int**a=newint*[n+1]; for(inti=0;i<=n;i++) a[i]=newint[n+1]; intk=log10(n)/log10 (2); printf("日程表: \n"); int*b; b=newint[n+1]; b[0]=0; printf(""); for(intl=1;l { b[1]=r++; printf("%d日",b[1]); } printf("\n"); Table(k,a); printf(a,n); } 提交结果: 算法设计分析思路、源代码及其分析说明和测试运行报告。 三、实验总结与体会 体会: 我们需要多多熟悉书上的知识。 虽然这些题在书上有类似的题,但真正做起来还是有一定的难度。 我们基础需要打好,使得在今后的学习中更得心应手。 如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。