[TOC]

南阳OJ-No.13

时间限制:3000ms,空间限制:65535KB

描述

无穷数列1，1，2，3，5，8，13，21，34，55…称为Fibonacci数列，它可以递归地定义为
F(n)=1 ………..(n=1或n=2)
F(n)=F(n-1)+F(n-2)…..(n>2)
现要你来求第n个斐波纳奇数。（第1个、第二个都为1)

输入

第一行是一个整数m(m<5)表示共有m组测试数据
每次测试数据只有一行，且只有一个整形数n(n<20)

输出

对每组输入n，输出第n个Fibonacci数

样例输入

3
1
3
5

样例输出

1
2
5

---

java

**时间46，内存311**

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int a = cin.nextInt();
		int temp;
		
		for (int n=0; n<a; n++) {
			temp = cin.nextInt();
			
			System.out.println(Fibonacci(temp));
		}
	}
	
	public static int Fibonacci(int n) {
		if (n == 1) {
			return 1;
		}else if (n == 2){
			return 1;
		} else {
			return Fibonacci(n-1) + Fibonacci(n-2);
		}
	}
}

**时间25，内存311**

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int a = cin.nextInt();
		int temp;
		
		for (int n=0; n<a; n++) {
			temp = cin.nextInt();
			
			System.out.println(Fibonacci(temp));
		}
		/***/
		cin.close();
		/***/
	}
	
	public static int Fibonacci(int n) {
		if (n == 1) {
			return 1;
		}else if (n == 2){
			return 1;
		} else {
			return Fibonacci(n-1) + Fibonacci(n-2);
		}
	}
}

主动关闭Scanner流会节省时间！！！

**时间24，内存311**

import java.util.Scanner;

public class Main_13 {
	
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int a = cin.nextInt();
		int temp;
		
		while (a>0) {
			temp = cin.nextInt();
			
			System.out.println(Fibonacci(temp));
			a--;
		}

		cin.close();
	}
	
	public static int Fibonacci(int n) {
		if (n == 1) {
			return 1;
		}else if (n == 2){
			return 1;
		} else {
			return Fibonacci(n-1) + Fibonacci(n-2);
		}
	}
}

将for改成while节省1时间！！！

**时间3，内存61**
依旧是用户名为 Bryan 的一大神给出的算法，投币看代码~

import java.util.Scanner;

public class Main {
	public static Scanner cin=new Scanner(System.in);
	
	public static void main(String[] args) {
		int line = 0;
		int number = cin.nextInt();
		
		for(int i = 0; i < number; i++){	
			line = cin.nextInt();
			System.out.println(f(line));
		}
	}

	static int f(int i){
		if (i <= 2 && i >= 0 ) {
			return 1;
		}
		return f(i - 1) + f(i - 2);
	}
}

将数据转换为 static 类型的重要性！！！（且Scanner主动关闭与否不影响时间）

**时间1，内存61**
Google出来的算是最高效的算法了，2017.2.3标记下，看不懂~

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws IOException{
		int lineNum = Main.readInt();
		int f1 = 1;
		int f2 = 1;
		int fn = 0;
		for(int i = 0; i < lineNum; i++){
			int num = Main.readInt();
			if(num <= 2){
				System.out.println(f1);
			}else{
				f1 = 1;
				f2 = 1;
				for(int j = 3; j <= num; j++){
					fn = f1 + f2;
					f1 = f2;
					f2 = fn;
				}
				System.out.println(fn);
			}
		}
		in.close();
	}
	public static int readInt() throws IOException{
		String str = in.readLine();
		int num = Integer.parseInt(str);
		return num;		
	}
}

---

c++

时间0，内存240

#include<iostream> 
using namespace std;

int f(int i)
{
	if (i <= 2 && i >= 0 ) {
		return 1;
	}
	return f(i - 1) + f(i - 2);
}

int main()
{
  int a;
  cin >> a;
  int temp;
  
  for(int i = 0; i < a; i++){	
		cin >> temp;
		cout << f(temp) << endl;
	}
}