算法实验——递归与分治
一、实验目的：
理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。
掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。
具体要求：
1.分析并掌握“棋盘覆盖问题”的递归与分治算法示例；
2.练习使用递归与分治策略求解具体问题；
二、实验环境：
VisualC++实验环境
三、实验内容：
(写出主要的内容)
1.
1)编写完整的主函数，分别记录利用上述递归函数求第45,46,47,48个Fibonacci数所花费的时间。
a.源代码：
#include
#include
intfi(intn)
{
if(n
F=Fa+Fb;
Fb=Fa;
Fa=F;
}
returnF;
}
intmain()
{inti;
doubleX;
X=clock()/CLOCKS_PER_SEC;
for(i=0;i2）。对于给定N(1≤N≤10000)，请判别数列第N项的奇偶性。
Input:
给定整数N，如N=0则结束输入（N=0不需要判断）。
Output:
输出第N项Fibonacci数列的奇偶性，如果为奇数则请输出“ODD”，否则为“EVEN”。
SampleInput:
1
2
3
0
SampleOutput:
ODD
ODD
EVEN
解：
源代码如下：
#include
#include
intfi(intn)
{
if(n
scanf("%d",&N);
a[i]=N;
i++;
g++;
}
for(i=0;i
sec=a[n-1],max=a[n-2];
}
else
{
sec=a[n-2],max=a[n-1];
}
returnsec;
}
else
{ sec=f(n-1);
if(a[n-1]>max)//找到数列中最大的数
{
sec=max,max=a[n-1];
}
if(a[n-1]sec)
{
sec=a[n-1];//找第二大的数
}
returnsec;
}
}
voidr()//随机生成数列的数
{
srand(time(NULL));
for(inti=0;i
printf("%d ",a[j]);
}
printf(" ");
printf("第二大的数为：");
w=f(n);
printf("%d ",w);
}
测试数据的截图：
5.棋盘覆盖
源代码如下：
#include
#include
intnCount=0;
intboard[100][100];
voidchessBoard(inttr,inttc,intdr,intdc,intsize);
intmain()
{
intsize,r,c,row,col;
scanf("%d",&size);
scanf("%d%d",&row,&col);
chessBoard(0,0,row,col,size);
for(r=0;r