斐波那契数列递归版
package Chapter9;
public class Fepo {
public static int fe(int n){
if(n==1){
return 1;
}
if(n==0){
return 0;
}
if(n==2){
return 1;
}
return fe(n-1)+fe(n-2);
}
public static void main(String[] args) {
System.out.println(fe(7));
}
}
斐波那契数列动态规划版
package Chapter9;
public class Fepo {
public static int fe(int n){
if(n==1){
return 1;
}
if(n==0){
return 0;
}
if(n==2){
return 1;
}
return fe(n-1)+fe(n-2);
}
static int[] list=new int[1000];
public static int fe2(int n){
if(n==1){
return 1;
}
if(n==0){
return 0;
}
if(n==2){
return 1;
}
if(list[n]!=0){
return list[n];
}else{
int value=fe2(n-1)+fe2(n-2);
list[n]=value;
return value;
}
}
public static void main(String[] args) {
int count=40;
long startTime = System.currentTimeMillis(); //获取开始时间
System.out.println(fe(count)); //测试的代码段
long endTime = System.currentTimeMillis(); //获取结束时间
System.out.println("程序运行时间：" + (endTime - startTime) + "ms"); //输出程序运行时间
long startTime1 = System.currentTimeMillis(); //获取开始时间
System.out.println(fe2(count)); //测试的代码段
long endTime1 = System.currentTimeMillis(); //获取结束时间
System.out.println("程序运行时间：" + (endTime1 - startTime1) + "ms");
}
}
image.png
