C/C++经典程序训练2---斐波那契数列
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）(n<40)。
数列：
f1=f2==1;
fn=fn-1+fn-2(n>=3)。
Input
输入整数n的值。
Output
输出fib(n)的值。
Sample Input
7
Sample Output
13
经典的斐波那契。
两种方法：
用类（C里的函数）
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n;
n = cin.nextInt();
System.out.println(f(n));
cin.close();
}
public static int f(int x)
{
if(x==1||x==2)
return 1;
else
return f(x-1) + f(x-2);
}
}
这种方法有很明显的缺陷，会进行大量的重复计算，如算5，会算4与3，4又会计算3与2，这样3便被计算了两次，所以数据大一点就会超时。
所以可以用第二种方法，动归思想，把每一步计算结果记录下来。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n,i;
int a[] = new int[45];
n = cin.nextInt();
a[1] = a[2] = 1;
for(i=3;i<=n;i++)
a[i] = a[i-1] + a[i-2];
System.out.println(a[n]);
cin.close();
}
}