算法实验——递归与分治

古城微笑少年丶 2022-05-13 14:54 265阅读 0赞

**一、实验目的：**

理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。

掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。

具体要求：

1. 分析并掌握“棋盘覆盖问题”的递归与分治算法示例；

2. 练习使用递归与分治策略求解具体问题；

**二、实验环境：**

Visual C++ 实验环境

**三、实验内容：**

**(****写出主要的内容****)**

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的时间如下：

![70][]

1.  将递归函数改为尾递归，或者是递推函数，求第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);

测试的结果截图为：

![70 1][]

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:

Sample Output:

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");

测试的数据截图如下：

![70 2][]

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);

测试数据的截图：

![70 3][]

![70 4][]

![70 5][]

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);// 覆盖其余方格

代码测试结果截图：

![70 6][]

**四、心得体会：**

递归算法是一种通过重复将问题分解为同类的子问题而解决的方法。该算法的思想是很简便，但是计算量很大，计算的效率很低，利用相同类似的迭代和尾递推的算法，效率大大地提高了。而分治算法则是将一个规模为N的问题分解为K个子问题，这些子问题相互独立而且原问题性质相同。求出问题的解，就可以得到原问题的解了。我觉得简单来说就是分目标解决程序问题的一种算法。在棋盘问题来说，就是利用其相关的原理，把大的棋盘一一分解成小的棋盘一次去覆盖，直到棋盘分解为最小则结束。

[70]: /images/20220504/dbf5e6b44cc84913ab45d355f9321d3b.png
[70 1]: /images/20220504/957e09a2f35e44d687236196cc80ce0e.png
[70 2]: /images/20220504/97f46829d9174d6e830c3a5990343c41.png
[70 3]: /images/20220504/f7517b52901241d28ddfd4acd284cd6b.png
[70 4]: /images/20220504/9e06006944a445b3b2dba03e97e58b2e.png
[70 5]: /images/20220504/e59f38dda3f54f26ad631f220c60d30c.png
[70 6]: /images/20220504/c543d8329fc94209b03050bbdfa45ead.png