一、实验目的:
理解递归算法的思想和递归程序的执行过程,并能熟练编写递归程序。
掌握分治算法的思想,对给定的问题能设计出分治算法予以解决。
具体要求:
1. 分析并掌握“棋盘覆盖问题”的递归与分治算法示例;
2. 练习使用递归与分治策略求解具体问题;
二、实验环境:
Visual C++ 实验环境
三、实验内容:
(写出主要的内容)
1.
1) 编写完整的主函数,分别记录利用上述递归函数求第45,46,47,48个Fibonacci数所花费的时间。
a.源代码:
#include<stdio.h>
#include<time.h>
int fi(int n)
{
if(n<=1) return (n);
else
return(fi(n-1)+fi(n-2));
}
int main()
{ int i;
double X;
X= clock()/CLOCKS_PER_SEC;
for(i=0;i<=48;i++)
{ X= clock()/CLOCKS_PER_SEC;
printf("计算第%d个数 所计算得的结果为%ld\t",i,fi(i));
X= clock() / CLOCKS_PER_SEC-X;
printf("计算第%d个的需要的时间为:%f\n",i,X);
}
}
计算45、46、47、48的时间如下:
- 将递归函数改为尾递归,或者是递推函数,求第45,46,47,48个Fibonacci数所花费的时间,观察效率是否得到提高。
解:采用的是递推函数求解:源代码如下
#include<stdio.h>
#include<time.h>
double fi(int n)
{
double F;
int Fa,Fb;
Fa=0;
Fb=1;
for(int i=0;i<n;i++){
F=Fa+Fb;
Fb=Fa;
Fa=F;
}
return F;
}
int main()
{ int i;
double X;
X= clock()/CLOCKS_PER_SEC;
for(i=0;i<=48;i++)
{ X= clock()/CLOCKS_PER_SEC;
printf("计算第%d个数 所计算得的结果为%lf\t",i,fi(i));
X= clock() / CLOCKS_PER_SEC-X;
printf("计算第%d个的需要的时间为:%f\n",i,X);
}
}
测试的结果截图为:
1911--Fib数之奇偶性
Fibonacci数列定义如下: a[1]=1; a[2]=1; a[n]=a[n-1]+a[n-2](n>2)。 对于给定N (1≤N≤10000),请判别数列第N项的奇偶性。
Input:
给定整数N,如N=0则结束输入(N=0不需要判断)。
Output:
输出第N项Fibonacci数列的奇偶性,如果为奇数则请输出“ODD”,否则为“EVEN”。
Sample Input:
1
2
3
0
Sample Output:
ODD
ODD
EVEN
解:
源代码如下:
#include<stdio.h>
#include<time.h>
int fi(int n)
{
if(n<=1) return (n);
else
return(fi(n-1)+fi(n-2));
}
int main()
{
int s=1;
int N=1;
int a[1000];
int i=0;
int g=0;
while(s=1&&N!=0){
scanf("%d",&N);
a[i]=N;
i++;
g++;
}
for(i=0;i<g;i++)
{
if(fi(a[i])%2!=0)
{
if(a[i]==0){break;}
printf("ODD\n");
}
else
{ if(a[i]==0){break;}
printf("EVEN\n");
}
}
}
测试的数据截图如下:
3.(求某数列第二大的数)
源代码为:
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int a[100];
int n;
int max;//定义数列最大的数
int sec;//定义数列第二大的数
int f(int n)
{
if(n==2)
{ if(a[n-1]<a[n-2])
{
sec=a[n-1],max=a[n-2];
}
else
{
sec=a[n-2],max=a[n-1];
}
return sec;
}
else
{ sec=f(n-1);
if(a[n-1]>max)//找到数列中最大的数
{
sec=max,max=a[n-1];
}
if(a[n-1]<max&&a[n-1]>sec)
{
sec=a[n-1];//找第二大的数
}
return sec;
}
}
void r()//随机生成数列的数
{
srand(time(NULL));
for(int i=0;i<n;i++)
{
a[i]=rand()%100+1;
}
}
int main()
{
int w;
printf("生成数列的数的个数为:");
scanf("%d",&n);
r();
printf("随机生成的数列为:");
for(int j=0;j<n;j++)
{
printf("%d\t",a[j]);
}
printf("\n");
printf("第二大的数为:");
w=f(n);
printf("%d\n",w);
}
测试数据的截图:
5.棋盘覆盖
源代码如下:
#include<stdio.h>
#include<stdlib.h>
int nCount = 0;
int board[100][100];
void chessBoard(int tr, int tc, int dr, int dc, int size);
int main()
{
int size,r,c,row,col;
scanf("%d",&size);
scanf("%d%d",&row,&col);
chessBoard(0,0,row,col,size);
for (r = 0; r < size; r++)
{
for (c = 0;c<size; c++)
{
printf("%2d ",board[r][c]);
}
printf("\n");
}
return 0;
}
void chessBoard(int tr, int tc, int dr, int dc, int size)
{
int s,t;
if (1 == size) return;
s = size/2; // 分割棋盘
t = ++ nCount;//L型骨牌号
// 覆盖左上角子棋盘
if (dr < tr + s && dc < tc +s)// 特殊方格在此棋盘中
{
chessBoard(tr,tc,dr,dc,s);//继续递归下去
}
else
{
board[tr+s-1][tc+s-1] = t;// 用 t 号L型骨牌覆盖右下角
chessBoard(tr,tc,tr+s-1,tc+s-1,s);// 覆盖其余方格//有了特殊的方格之后继续递归
}
// 覆盖右上角子棋盘
if (dr < tr + s && dc >= tc + s )// 特殊方格在此棋盘中
{
chessBoard(tr,tc+s,dr,dc,s);//继续递归下去
}
else
{
board[tr+s-1][tc+s] = t;// 用 t 号L型骨牌覆盖左下角
chessBoard(tr,tc+s,tr+s-1,tc+s,s);// 覆盖其余方格
}
// 覆盖左下角子棋盘
if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中
{
chessBoard(tr+s,tc,dr,dc,s);
}
else
{
board[tr+s][tc+s-1] = t;// 用 t 号L型骨牌覆盖右上角
// 覆盖其余方格
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;// 用 t 号L型骨牌覆盖左上角
chessBoard(tr+s,tc+s,tr+s,tc+s,s);// 覆盖其余方格
}
}
代码测试结果截图:
四、心得体会:
递归算法是一种通过重复将问题分解为同类的子问题而解决的方法。该算法的思想是很简便,但是计算量很大,计算的效率很低,利用相同类似的迭代和尾递推的算法,效率大大地提高了。而分治算法则是将一个规模为N的问题分解为K个子问题,这些子问题相互独立而且原问题性质相同。求出问题的解,就可以得到原问题的解了。我觉得简单来说就是分目标解决程序问题的一种算法。在棋盘问题来说,就是利用其相关的原理,把大的棋盘一一分解成小的棋盘一次去覆盖,直到棋盘分解为最小则结束。