斐波那契程序未完成执行

Question

>问题描述

通过考虑斐波那契数列中值不超过 400 万的项，找到偶值项的总和

程序

using System;
class fibonacci {
    // function to return Nth value of fibonacci
    public static long fibo_n(long N) {
        long fibon=0;
        switch (N) {
            case 1: fibon=1; break;
            case 2: fibon=2; break;
        }
        while(N>2) {
        fibon=fibo_n(N-1)+fibo_n(N-2);
        }
    return fibon;
    }
}    
class fibo_tester {
    static void Main() {
        int N=2;
        long sum=0;
        while(fibonacci.fibo_n(N) <= 13) {
            sum = sum + fibonacci.fibo_n(N);
            N=N+3;
        }
        Console.WriteLine("Sum is {0}: ", sum);
    }
}

我将测试的数字减少到 13 而不是 400 万，但它仍然挂起。有人可以建议吗？

编辑 2

switch (N) {
        case 1: fibon=1; break;
        case 2: fibon=2; break;
        default: fibon=fibo_n(N-1)+fibo_n(N-2); break;
    }

Answer 1

 while(N>2) {
        fibon=fibo_n(N-1)+fibo_n(N-2);
        }

将无限期循环，N 永远不会在循环中更新。您可能需要删除 While（） 子句并将其全部更改为 return fibo_n(N-1)+fibo_n(N-2); 我不确定您对 switch 语句等做了什么。但这应该是一个开始。

我实际上会用这个替换它（如果你想使用开关）：

class fibonacci
{
    // function to return Nth value of fibonacci
    public static long fibo_n(long N)
    {
        switch (N)
        {
            case 0:
                return 0;
            case 1:
                return 1;
            default:
                return fibo_n(N - 1) + fibo_n(N - 2);
        }
    }
}   

您可能需要考虑将 N 的每个值的值存储在字典或某种集合中，以便以后可以查找它们。因为在您的主程序中，您似乎要循环访问这些值（可能已经计算的连续更大的 N）。我不确定 N+3 在您的主循环中是关于什么的，但您可能会在那里错过一些东西（也许是递归中 N-1、N-2 的错误假设？

此外，如果求和并依赖于您的平台以及您测试的值有多大（即测试前 X 斐波那契数的总和），您可能必须使用ulong或找到一些可以处理更大数字的其他数据类型。如果我不在我的系统上将所有内容从 long 更改为 ulong，则值就会环绕。无论如何，斐波那契数不能是负数，所以为什么不使用ulong，uint64或更多位的东西。

Answer 2

你同时使用循环和递归 - 你需要选择一个或另一个。代码中的问题点在这里：

while (N>2) {
    fibon = fibo_n(N-1)+fibo_n(N-2);
}

在这个地方，N的值实际上永远不会改变 - 这发生在递归步骤中。一个示例（不好）的编写方法是：

public static long fibo_n(long N) {
    if (N <= 0) return 0;
    if (N == 1) return 1;
    if (N <= 4) return N - 1;
    return fibo_n(N-1) + fibo_n(N-2);
}

祝你好运！

---

性能说明：

这不是一个好方法的原因是，函数调用在 C# 中使用内存，并且它们也需要时间。循环总是比递归快，在这种情况下，没有充分的理由用递归（而不是简单的循环）来解决这个问题。我将保持代码原样，以便您可以与现有代码进行比较，但我认为您可以在其他地方找到更好更好的代码选项（尽管并非所有这些选项都在 C# 中）。

Answer 3

假设你调用你的方法，N等于3。

交换机不执行任何操作。

N 大于 2，因此我们进入 while 循环。 while 循环做一些事情;它计算一个值，将其分配给fibon。 然后 N，因为它没有改变，仍然大于 2，所以我们再次计算它。 它仍然会大于 2，所以我们再次计算它。 我们从未停止计算它。

每次你给fibon赋值时，你应该返回该值，因为你已经完成了;你没有什么可以计算的了。 也不需要while循环。 您永远不需要多次执行该代码。

您的实现效率也非常低。 要计算 fib（5），您需要计算 fib（4） 和 fib（3）。 然后，当计算 fib（4） 时，你计算 fib（3） [再次] 和 fib（2），当计算 fib（3） 两次时，它们各自计算 fib（2）（所以那里有三次），如果我们做数学运算，我们最终会看到你在计算 fib（n） 时执行 2^n 次计算。 最重要的是，当你在主循环中从零开始计数时，你调用了fib n次。 这是大量不必要的工作来重新计算相同的值。 如果你只是有一个简单的循环，当你使用时将数字加在一起，你可以按照N次计算的顺序计算结果。