java 笔试题1

题目：计算斐波那契数列第N项。下面给出了三种方法，测试代码如下

这个是自己写的代码：

package com.li.test.classes;
/**
 * 斐波那契数列求第N项。对比了两种算法的效率。
 * 
 * @author li
 * 
 */
public class Fibonaqie {

	public long getint(long i, long j, long n) {
		long x = i + j;
		if (n <= 3) {
			return x;
		}

		return getint(j, x, --n);
	}

	public long get(long n) {
		long i = 1, j = 1;
		long x = 1;
		for (; n > 2; n--) {
			x = i + j;
			i = j;
			j = x;
		}
		return x;
	}
           

public static void main(String[] args) {
		// TODO Auto-generated method stub
		Fibonaqie f = new Fibonaqie();
		long start = System.nanoTime();
		System.out.println(f.getint(1, 1, 92));
		System.out.println(System.nanoTime() - start);
		long start1 = System.nanoTime();
		System.out.println(f.get(92));
		System.out.println(System.nanoTime() - start1);
		System.out.println(Long.MAX_VALUE);
	}
}
           

运行结果：

7540113804746346429

362895

7540113804746346429

58387

9223372036854775807

注：对于long类型的数据，最多可以计算斐波那契第92项，第93项会溢出。

面试宝典上给出的答案：

package com.li.test.classes;
/**
 * 此方法为面试宝典上的方法，效率极低，特别当N>=40时，内存消耗很大。该方法时间复杂度为O（2^n）.
 * 
 * @author li
 * 
 */
public class Fibonacci {
	public static int k = 0;


	public static long fibonacci(long m) {
		k++;
		if (m == 0 || m == 1) {
			return m;
		}
		return fibonacci(m - 1) + fibonacci(m - 2);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// Scanner cin = new Scanner(System.in);
		// long a = cin.nextLong();
		long start = System.nanoTime();


		System.out.println(fibonacci(40));
		double a = java.lang.Math.pow(2, 14);
		System.out.println("共递归调用了" + k + "次");
		System.out.println(System.nanoTime() - start);
	}
}
           

运行结果：

102334155

共递归调用了331160281次

5779017165

总结：递归调用的效率很低，斐波那契数列调用次数C(n)=C(n-1)+C(n-2)+1