2)
{
result = recursion(n-1) + recursion(n-2);
//System.out.print(result+" ");
}
return result;
}
//规定时间内，递归法计算出的最大斐波那契数是第几个
public static int recursion_time(long time){
long starttime_dg=System.currentTimeMillis();
int i=3;
long endtime_dg=0;
while(endtime_dg60000;){
recursion(i);
i++;
t2 = System.currentTimeMillis();
if(t2-t1 == 1000)
System.out.println("1秒内最大斐波那契数是第："+i+"个 ");
if(t2-t1 == 5000)
System.out.println("5秒内最大斐波那契数是第："+i+"个 ");
if(t2-t1 == 10000)
System.out.println("10秒内最大斐波那契数是第："+i+"个 ");
if(t2-t1 == 50000)
System.out.println("50秒内最大斐波那契数是第："+i+"个 ");
}
}
//直接求值法(利用公式F(n) = [@n/sqrt(5)]快速计算第n个斐波那契数)
public static double formula(int n){
double result = 0;
double temp = Math.sqrt(5.0);
result = (1/temp)*(Math.pow((1+temp)/2,n)-Math.pow((1-temp)/2, n));
return result;
}
//利用直接求值法，出现误差时最小的n值
public static int min_formula(){
double result_fn=1;
int i=1;
while(result_fn-(double)iteration(i)<1){
result_fn=formula(i);
i++;
}
return i;
}
//新算法法
public static int new_way(int n){
//int a = 1,b = 1,c = 2,d = 3;
int result = 0; //定义最后一个斐波那契数
//根据输入n,求出最后一个斐波那契数
if(n == 0)
result = 0;
else if(n == 1 || n == 2)
result = 1;
else if(n == 3)
result = 2;
else if(n >= 4){ //若n大于4返回resul
int a1 = n/4;
int b1 = n%4;
int a = new_way(a1);
int b = new_way((a1+1));
int c = new_way((a1-1));
int d = new_way((a1+2));
if(b1 == 0)
result = (int) ((Math.pow(b,2) - Math.pow(c,2))*(Math.pow(c, 2) + 2*Math.pow(a, 2) + Math.pow(b,2)));
if(b1 == 1)
result = (int) (Math.pow((Math.pow(b,2) - Math.pow(c,2)),2) + Math.pow((Math.pow(a, 2) + Math.pow(b,2)),2));
if(b1 == 2)
result = (int) ((Math.pow(a, 2) + Math.pow(b,2))*(3*Math.pow(b,2)+Math.pow(a, 2)-2*Math.pow(c,2)));
if(b1 == 3)
result = (int) (Math.pow((Math.pow(a, 2) + Math.pow(b,2)),2) + Math.pow((Math.pow(d,2)-Math.pow(a,2)),2));
}
return result;
}
// 关联矩阵
private static final int[][] UNIT = { { 1, 1 }, { 1, 0 } };
// 全0矩阵
private static final int[][] ZERO = { { 0, 0 }, { 0, 0 } };
/**
* 求斐波那契数列
*
* @param n
* @return
*/
public static int[][] fb(int n) {
if (n == 0) {
return ZERO;
}
if (n == 1) {
return UNIT;
}
// n是奇数
if ((n & 1) == 0) {
int[][] matrix = fb(n >> 1);
return matrixMultiply(matrix, matrix);
}
// n是偶数
int[][] matrix = fb((n - 1) >> 1);
return matrixMultiply(matrixMultiply(matrix, matrix), UNIT);
}
/**
* 矩阵相乘
*
* @param m
* r1*c1
* @param n
* c1*c2
* @return 新矩阵,r1*c2
*/
public static int[][] matrixMultiply(int[][] m, int[][] n) {
int rows = m.length;
int cols = n[0].length;
int[][] r = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
r[i][j] = 0;
for (int k = 0; k < m[i].length; k++) {
r[i][j] += m[i][k] * n[k][j];
}
}
}
return r;
}
//具体实现矩阵相乘算法
public static int matrix(int n){
int[][] m = fb(n);
return m[0][1];
}
public static void main(String[] args){
System.out.print(max_int_iteration());
System.out.println();
System.out.print(max_long_iteration());
System.out.println();
System.out.println();
long t1 = System.currentTimeMillis();
long a = recursion(47);
long t2 = System.currentTimeMillis();
System.out.println("递归法求斐波那契数：");
System.out.println(a);
System.out.println("递归算法Time is: " + (t2 - t1)/1000.0+"秒");
//此处下面可以直接通过给相关类传递参数，实现相应功能，上面的中代码仅仅提供示例
}
}