递归与分治策略应用基础.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=tc+s）
//特殊方格在此棋盘中
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&&dcChessBoard（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;jcout<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）;
}
提交结果：
算法设计分析思路、源代码及其分析说明和测试运行报告。
三、实验总结与体会
体会：
我们需要多多熟悉书上的知识。
虽然这些题在书上有类似的题，但真正做起来还是有一定的难度。
我们基础需要打好，使得在今后的学习中更得心应手。
升级会员 