计算斐波那契数列中终止条件的执行情况

Question

以下计算第 n 个斐波那契数的伪代码：

int fibonacci(int n)
{
    if (n == 0){
        print(0)
        return 0
    }
    if (n == 1)
    {
        print(1)
        return 1
    }
    return fibonacci(n - 1) + fibonacci(n - 2)
}

如果调用 fibonacci(3)，则会发生以下情况：

fibonacci(3) calls fibonacci(2) and fibonacci(1) (the first call).

fibonacci(2) calls fibonacci(1) (the second call) and fibonacci(0).

The second call of fibonacci(1) prints 1 and returns 1.

fibonacci(0) prints 0 and returns 0.

fibonacci(2) gets the results of fibonacci(1) and fibonacci(0) and returns 1.

The first call of fibonacci(1) prints 1 and returns 1.

fibonacci(3) gets the results of fibonacci(2) and fibonacci(1) and returns 2.

总共打印两次1，打印一次0。

Objective就是知道对于给定的整数N，0和1会打印多少次。

输入第一行包含一个整数T，表示测试用例的数量。接下来的 T 行包含一个整数 N。

输出对于每个测试用例，打印一行输出，其中包含由 space 分隔的 2 个整数。第一个整数是打印 0 的次数。第二个整数是打印 1 的次数。

约束条件

1 <= T <= 50
0 <= N <= 40

样本输入

SMAPLE 输出

1 0

1 2

代码

public class Fibonacci {

    /**
     * @param args
     */
static int zero =0,one = 0;
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] input = readInput();
    for(int i =0; i < input.length;++i) {
        System.out.println(getOutput(input[i]));
    }
}
public static int[] readInput() {
    BufferedReader bufferReader = new BufferedReader(new InputStreamReader(System.in));
    String temp;
    int[] input = null;
    try {
        temp =bufferReader.readLine();  
        int counter = Integer.parseInt(temp);
        input = new int[counter];
        for(int i =0 ; i < counter ;++i)    {
            input[i] =Integer.parseInt(bufferReader.readLine());
        }

    } catch (IOException e) {
        e.printStackTrace();
    }
    return input;
}
public static String getOutput(int number)  {
    //System.out.println(fibonacci(number));
    return zero+" "+one;
}
public static int fibonacci(int n) {
    if (n == 0) {
        //System.out.println(0);
        ++zero;
        return 0;
    }
    if (n == 1) {
        //System.out.println(1);
        ++one;
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

这对第一个测试用例工作正常，但对后续测试用例失败。

Answer 1

我认为您需要在调用 getOutput 之前重置零和一的值。

    for(int i =0; i < input.length;++i) {
        zero = 0;
        one = 0;
        System.out.println(getOutput(input[i]));
    }

计算斐波那契数列中终止条件的执行情况

Counting the execution of terminating conditions in Fibonacci series

java

algorithm

fibonacci