在斐波那契算法中计数加法

我有两种算法都正常工作。这两种算法都是斐波纳契算法，它将在用户指定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次，并且在循环时，迭代和递归方法在它们自己的方法内迭代）。我找不出另一种方法来计算添加的行数。有什么建议？

谢谢！

来源

2013-03-28 Zephyrus 1898

我没有得到你的问题是什么？ – Ankit 2013-03-28 05:09:30

我正在计算在两种算法中分别添加的次数。当单独执行它们（在输出图像中）时，它们的行数确实被正确计数。当我使用doTheyMatch（）算法时，迭代和递归算法都会执行，但添加的行不能正确计算。我的问题是：如何在使用doTheyMatch（）方法的同时获取正确的行数正确。 – 2013-03-28 05:12:51

那是因为你没有重置的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-28 05:15:01 gerrytan

recAdd和itAdd行会重置。在我的菜单线束中的while循环结束时，我重置它们，因为在菜单上进行了任何选择后，开关盒就结束了。如果仔细观察我链接的图像，在最后的例子中，计数器变量从0开始，直接在我执行递归算法之后。 – 2013-03-28 05:18:02

但计数器是静态变量，您必须在每次循环中重置它们。也许回顾关于“静态变量”的讲座笔记 – gerrytan 2013-03-28 05:23:18

问题修复。你是对的，我没有想到我需要重置doTheyMatch（）方法的for循环中的计数器变量，而我重置了方法本身结束后的变量。 – 2013-03-28 05:36:11

与你正试图在这里做的问题是，当你调用函数递归地，数字越大，函数被调用的次数越多。您的号码为0或1的可能性仅为1，因此多次调用该函数。你需要做的就是把recAdd++;声明如果这些块中：

if(n <= 0){ 
    return 0; 
} 
if(n == 1){ 
    return 1; 
} 
else if(n == 2){ 
    return 1; 
}

来源

2013-03-28 05:16:51 Aashray

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

来源

2013-03-28 05:17:22

不知道这是否是对你有用，但如果你正在努力寻找一定数量n的斐波那契您可以用公式F(n) = (k^n-p^n)/sqrt(5)其中n是迭代k = (1+sqrt(5))/2p = (1-sqrt(5))/2数量或序列中的特定号码，且

来源

2013-03-28 05:39:50 tiantang

在斐波那契算法中计数加法

回答

相关问题