实验三 递归

递归"/>

实验三 递归

桂 林 理 工 大 学
实 验 报 告
同组实验者
实验名称 实验三 日期 2020年 05 月14 日
一、实验目的：
理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。
掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。

二、实验环境：
Eclipse
三、实验内容：

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);
}
1)编写完整的主函数，分别记录利用上述递归函数求第47, 48, 49, 50, 51,52个Fibonacci数所花费的时间。

	}

2）将递归函数改为尾递归，或者是递推函数，求第47, 48, 49, 50, 51,52个Fibonacci数所花费的时间，观察效率是否得到提高。

import java.util.*;public class suanfa {public static int fibonacci2(int n) {//顺序时间复杂度O(n)if(n < 1) {return 0;}else if(n == 1 || n == 2) {return 1;}int v1 = 1;int v2 = 2;int v3 = 0;for(int i = 3; i <= n; i++) {v3 = v2+v1;v1 = v2;v2 = v3;}return v3;}public static int fibonacci(int n){if (n <= 1) return 1;return fibonacci(n-1)+fibonacci(n-2);}public static void main(String[] args) {int N = 47;long start = 0;long end = 0;/*while(N < 53) {start = System.currentTimeMillis();fibonacci(N);end = System.currentTimeMillis();System.out.println("第"+N+"个Fibonacci数所花费的时间:"+(end - start)+"毫秒");N ++;}*/System.out.println(fibonacci(4));while(N < 53) {start = System.currentTimeMillis();System.out.println(fibonacci2(N));end = System.currentTimeMillis();System.out.println("第"+N+"个Fibonacci数所花费的时间:"+(end - start)+"毫秒");N ++;}}
}

2.角谷定理

public static int Kakutani(int number) {int count = 0;//System.out.print( number+"  ");//output each number count++;//count steps//exit,the last number is 1if (number == 1) {return count;}//bodyelse {if (number % 2 == 0) {//Even numberscount += Kakutani(number / 2);return count;}else {//Odd number count += Kakutani(number * 3 + 1);return count;}}
}

3. 教材80页习题第（4）题。

这题跟第一题一样，就是斐波那契数
4. 半数集问题。
问题描述：给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下：
(1) ；
(2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
(3) 按此规则进行处理，直到不能再添加自然数为止。
例如，set(6)={6,16,26,126,36,136}，半数集set(6)中有6个元素。
输入：整数n(0<n<1000)
输出：半数集set(n)中的元素个数。
请设计递归函数，求出set(n)的个数，并分析算法时间复杂度，对算法进行改进，用程序验证递归算法，以及改进之后的算法。

int comp(int n)
{//O()int ans = 1;if(n > 1)for(int i = 1;i<n/2;i++)ans += comp(i);return ans;
}//改进后的算法：int a[1000]
int comp(int n)
{int ans = 1;if(a[n]>0) return a[n];for(int i = 1;i<=n/2;i++){ans += comp(i);}a[n] = ans;return ans;
}