0

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

我已经声明了全局计数器 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 方法在它们自己的方法中进行迭代）。我想不出另一种方法来计算添加的行数。有什么建议吗？

谢谢！

4

4 回答 4

1

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

应该做类似的事情：

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

// reset counters
recAdd = 0;
itAdd = 0;
于 2013-03-28T05:15:01.940 回答
0

您在这里尝试做的问题是，当您递归调用函数时，数字越大，调用函数的次数就越多。您的数字为 0 或 1 的可能性仅为 1，因此该函数被多次调用。您需要做的是将recAdd++;语句放在这些 if 块中：

if( n <= 0){
    return 0;
}
if(n == 1){
    return 1;
}
else if(n == 2){
    return 1;
}
于 2013-03-28T05:16:51.453 回答
0

这是因为使用递归，方法调用分支，并且在递归过程中您多次调用该方法。这意味着它以比迭代更快的速度累加。尝试在纸上为较小的数字绘制一些方法调用并跟踪您的 itAdd 和 recAdd 变量，您将明白我的意思。希望这可以帮助。

于 2013-03-28T05:17:22.980 回答
0

不确定这是否对您有用，但如果您试图找到某个数字的斐波那契，n您可以使用公式F(n) = (k^n-p^n)/sqrt(5)，其中n是迭代次数或序列中的特定数字，k = (1+sqrt(5))/2并且p = (1-sqrt(5))/2

于 2013-03-28T05:39:50.500 回答