java - 斐波那契算法中的计数加法

Question

我的两种算法都正常工作。这两种算法都是斐波那契算法，它们将在 n 处找到斐波那契数，其中用户指定 n。我有三个方法:其中两个返回 n 处的斐波那契数，最后一个方法执行这两个方法，同时以表格形式显示所有斐波那契数，其中一列对应代码中执行加法的次数。

我已经声明了全局计数器 recAdd 和 itAdd，它们分别表示在每个算法中添加的行。这些值在每次执行后都会重置我的测试工具，但我不会在此处显示。

public static long recFib(int n){ //Recursive Fibonacci Algorithm
    if( n <= 0){
        return 0;
    }
    if(n == 1){
        return 1;
    }
    else if(n == 2){
        return 1;
    }
    else{
        recAdd++;                               //Counts number of lines added.
        return recFib(n-1) + recFib(n-2);   //Recurisvely adds fibonnachi numbers. Starts with user's input n. Method is called repeatedly until n is less than 2.
    }
}

public static long itFib(int n){ //Iterative Fibonacci Algorithm
    long x, y, z;

    if(n == 0){
        return 0;
    }
    else{
        x = 1;
        y = 1;

        for(int i = 3; i <=n; i++){
            z = x+y;        //z is equal to the addition of x and y, which serve as f(n-1) + f(n-2).
            x = y;      //x is shifted to the next fibonacci number, previously known as y.
            y = z;      //y is set equal to z, which was the new value created by the old y and the old x.
            itAdd++;        //counts how many times addition has occured.
        }
    }
    return y;
}   

public static void doTheyMatch(int n){

    System.out.printf("%s %15s %15s %15s %15s", "i", "Recursive", "recAddCount", "Iterative", "itAddCount\n\n"); //Tab header

    for(int i = 0; i <= n; i++){
    System.out.printf("%d %12d %12d %12d %12d\n", i, recFib(i), recAdd, itFib(i), itAdd);       
    }

    System.out.printf("%s %15s %15s %15s %15s", "\ni", "Recursive", "recAddCount", "Iterative", "itAddCount\n"); //Repeat for quick referencing
}

输出在这里(我在这些文本框中发布输出时遇到问题=/):http://i.imgur.com/HGlcZSn.png

我确信我的添加计数器在“doTheyMatch()”方法期间如此频繁关闭的原因是因为执行此方法的循环。 (该方法循环 n 次，在循环时，Iterative 和 Recursion 方法在它们自己的方法内迭代)。我想不出另一种方法来计算添加的行数。有什么建议吗？

谢谢!

Answer 1

那是因为你没有在 doTheyMatch 函数上重置加法计数器

应该做类似的事情:

System.out.printf("%d %12d %12d %12d %12d\n", i, recFib(i), recAdd, itFib(i), itAdd);

// reset counters
recAdd = 0;
itAdd = 0;