南阳OJ-No.13-Fibonacci数

[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**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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 的一大神给出的算法,投币看代码~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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标记下,看不懂~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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;
}
}
文章作者: HibisciDai
文章链接: http://hibiscidai.com/2017/02/03/2017-02-03-南阳OJ-No.13-Fibonacci数/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HibisciDai
支付宝打赏
微信打赏