递归与分治
一、实验目的：
理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。
掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。
具体要求：
1. 分析并掌握“棋盘覆盖问题”的递归与分治算法示例；
2. 练习使用递归与分治策略求解具体问题；
二、实验环境：
Visual C++
三、实验内容：
1. Fibonacci数列
无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为：
第n个Fibonacci数可递归地计算如下：
int fibonacci(int n)
{
if (n <= 1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
- 编写完整的主函数，分别记录利用上述递归函数求第45,46,47,48个Fibonacci数所花费的时间。
代码如下：
//递归
#include<stdio.h>
#include<time.h>
int Fibonacci(int n);
int main()
{
int n;
scanf("%d",&n);
double x=clock()/CLOCKS_PER_SEC;
Fibonacci(n);
x=clock()/CLOCKS_PER_SEC-x;
printf("%lf\n",x);
return 0;
}
int Fibonacci(int n)
{
if(n<=1) return(n);
else return(Fibonacci(n-1)+Fibonacci(n-2));
}
2）将递归函数改为尾递归，或者是递推函数，求第45,46,47,48个Fibonacci数所花费的时间，观察效率是否得到提高。
代码如下：
//迭代
#include<stdio.h>
#include<time.h>
int Fibonacci(int n);
int main()
{
int n;
scanf("%d",&n);
double x=clock()/CLOCKS_PER_SEC;
Fibonacci(n);
x=clock()/CLOCKS_PER_SEC-x;
printf("%lf\n",x);
return 0;
}
int Fibonacci(int n)
{
int F,Fa,Fb;
Fa=0;
Fb=1;
for(int i=2;i<=n;i++)
{
F=Fa+Fb;
Fb=Fa;
Fa=F;
//printf("F(%d)=%d\n",i,F);
}
printf("F(%d)=%d\n",i-1,F);
return F;
}
2. Fibonacci数列扩展题。
在http://cpp.zjut.edu.cn/ProblemList.aspx 网站上，找到题目ID为1090，1091，1211，1451，1457，1500，1520的题目，这些题目都是以Fibonacci数列为基础的编程题，在上述题目中，至少选择1个题目完成。
（建议在网站中注册账号，提交程序进行检测）
1090：
菲波那契数的余数
Time Limit:1000MS Memory Limit:32768K
Description:
菲波那契数大家可能都已经很熟悉了： f(1)=0； f(2)=1； f(n)=f(n-1)+f(n-2) n>2。 因此，当需要其除以某个数的余数时，不妨加一些处理就可以得到。
Input:
输入数据为一些整数对P、K，P(1<P<5000)，表示菲波那契数的序号，K(1<=K<15)表示2的幂次方。遇到两个空格隔开的0时表示结束处理。
Output:
输出其第P个菲波那契数除以2的K次方的余数。
Sample Input:
6 220 100 0Sample Output:
185
代码如下：
#include<stdio.h>
int Fibonacci(int n,int m);
int main()
{
int P,K,p[100],k[100],flag,i;
flag=1;
i=0;
while(flag)
{
scanf("%d%d",&P,&K);
p[i]=P;
k[i]=K;
i++;
if(P==0||K==0)
{
flag=0;
}
}
for(int c=0;c<i-1;c++)
{
Fibonacci(p[c],k[c]);
}
return 0;
}
int Fibonacci(int n,int m)
{
int F,Fa,Fb,s;
Fa=0;
Fb=1;
s=1;
for(int i=2;i<=n;i++)
{
F=Fa+Fb;
Fb=Fa;
Fa=F;
//printf("f(%d)=%d\n",i,F);
}
for(int j=1;j<=m;j++)
{
s=2*s;
}
printf("%d\n",F%s);
return F;
}
3. 给出一个分治算法来找出n个元素序列中第2大的元素。
代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<string.h>
int findsecond(int n,int A[]);
int main()
{
int n;
int array[100];
printf("输入要生成随机数的个数：");
scanf("%d",&n);
srand(time(0));
printf("生成的随机数列为：");
for(int i=0;i<n;i++)
{
array[i]=rand()%100;
printf("%d ",array[i]);
}
printf("\n");
findsecond(n,array);
return 0;
}
int findsecond(int n,int A[])
{
int x1,x2;
x1=A[0];
x2=A[1];
if(x1<x2)
{
int t=x1;
x1=x2;
x2=t;
}
for(int i=2;i<n;i++)
{
if(x2<A[i])
{
if(x1>=A[i])
{
x2=A[i];
}
else
{
x2=x1;
x1=A[i];
}
}
}
printf("第一大的数为：%d 第二大的数为：%d\n",x1,x2);
return 0;
}
4. 棋盘覆盖问题
在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
算法描述如下：
参数说明：
子棋盘：由棋盘左上角的坐标tr，tc和棋盘大小size表示。
特殊方格：在二维数组中的坐标位置是（dr，dc）。
代码如下：
#include<stdio.h>
void chessBoard(int ,int ,int ,int ,int );
int tile=0;
int board[101][101];
int main()
{
int size,dr,dc;
printf("输入棋盘的大小（2的倍数）：\n");
scanf("%d",&size);
printf("输入特殊方格的行号和列号：\n");
scanf("%d%d",&dr,&dc);
chessBoard(0,0,dr,dc,size);
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
printf("%3d ",board[i][j]);
}
printf("\n");
}
return 0;
}
void chessBoard(int tr, int tc, int dr, int dc, int size)
{
if (size == 1) return;
int t = ++tile; // L型骨牌号
int s = size/2; // 分割棋盘
// 覆盖左上角子棋盘
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); // 覆盖其余方格
}
}
投递海康威视等公司10个岗位 >