2

我在 Project Euler 中遇到了这个问题。

这是问题的要求：

斐波那契数列中的每个新项都是通过添加前两项来生成的。从 1 和 2 开始，前 10 项将是： 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 求序列中所有偶数项的总和不超过四百万。

到目前为止我的代码：用仍然不起作用的新代码编辑。

static void Main(string[] args)
{
    int a = 1;
    int b = 2;
    int Container = 0;
    int Sum = 0;

    while (b < 4000000)
    {
        if (a % 2 == 0)
        {
            Container += a;
        }

        Sum = a + b;
        a = b;
        b = Sum;
    }

    Container += b;

    Console.WriteLine(Container.ToString());
    Console.ReadLine();
}
4

9 回答 9

9

C# 中一个有趣的特性是“yield”关键字，它对这类事情非常有用：

IEnumerable<int> Fibonacci()
{
   int n1 = 0;
   int n2 = 1;

   yield return 1;
   while (true)
   {
      int n = n1 + n2;
      n1 = n2;
      n2 = n;
      yield return n;
   }
}

long result=0;

foreach (int i in Fibonacci().TakeWhile(i => i<4000000).Where(i => i % 2 == 0))
{
    result+=i;
}
Console.WriteLine(result);

“传统的”递归斐波那契实现在这里是有问题的，因为它丢弃了在最后一个请求术语的过程中完成的所有工作。您必须在循环中一遍又一遍地调用这样的函数，这将重复大量工作，或者您可以从该实现开始并向递归函数添加一个参数以构建所需的总和结果作为最终的斐波那契项是计算出来的。我更喜欢这个，因为它的核心仍然是一个通用的斐波那契序列，而不是你必须重新编写或专门化的序列。

另一种方法是在传统实现中使用事件（委托）在每个学期完成时调用一个单独的方法，但由于我仍然更喜欢迭代器方法，我将把委托选项留给读者作为练习。

于 2009-10-17T00:38:28.273 回答
6

您的问题不在于您的代码包含错误；您的问题是您的代码包含错误并且您不知道如何找到它。先解决第二个问题，以后有bug就不用问我们了，自己找就行了。

学习如何发现错误很困难，需要大量练习。以下是我将如何解决这个问题。

我首先将问题简化为我可以自己做的事情。而不是“不超过四百万的偶数数字的总和是多少？” 我会问“不超过 40 的偶数 fib 的总和是多少？” 这很容易手工计算——2 + 8 + 34 = 44。

现在在调试器中运行你的程序，单步执行每一行，看看哪里出了问题。你的程序实际上加起来是 2、8 和 34 吗？如果是这样，它会得到正确的结果吗？

于 2009-10-17T16:22:38.587 回答
3 
int sum = 2;
for(int f1 = 1, f2 = 2, f3 = 0; !((f3 = (f1 + f2)) > 4000000); f1 = f2, f2 = f3)
    sum += f3 * (~f3 & 1);
于 2009-10-17T02:17:24.687 回答
1

您正在检查a每次b迭代。所以这意味着你几乎所有的东西都在重复计算。

编辑：

好的，我看到你的更新了。这是非常基本的调试，您应该真正学会自己尝试。想想当你的循环条件停止为真时的值a和是什么。b

于 2009-10-17T00:12:30.290 回答
1

我认为写这个问题是说您将所有偶数加在一起，而序列中的数字不超过四百万，这意味着您将添加 3,999,992。

于 2009-10-17T00:16:00.593 回答
1

Joel，我写了一个非常相似的代码；无论如何我都会发布它：

static IEnumerable<int> Fibonacci(int maximum)
{
    int auxiliar = 0;
    int previous = 0;
    int current = 1;
    while (current < maximum)
    {
        auxiliar = previous;
        previous = current;
        current = auxiliar + current;
        yield return current;
    }
}

Console.WriteLine(Fibonacci(4000000).Where(number => number % 2 == 0).Sum());
于 2009-10-17T00:46:50.550 回答
0

比较棘手的方法：

//1: Allow declaring of recursive functions
private delegate Func<T, R> FuncRec<T, R>(FuncRec<T, R> f);
static Func<T, R> RecFunction<T, R>(Func<Func<T, R>, Func<T, R>> f)
{
    FuncRec<T, R> funcRec = r => t => f(r(r))(t);
    return funcRec(funcRec);
}

//Define the factorial function
public static readonly Func<ulong, ulong> Fibonacci 
        = RecFunction<UInt64, UInt64>(fib => n =>
            (n == 1 || n == 0)
            ? n
            : fib(n - 1) + fib(n - 2)); 

//Make a "continous" version
static IEnumerable<ulong> ContinousFibonacci()
    {
        ulong count = 0;
        while(true)
        {
            ulong n = Fibonacci(count);
            count++;
            yield return n;
        }
    }

//Linq result
static void Main(string[] args)
    {


        ulong result = ContinousFibonacci()
            .TakeWhile(r => r < 4000000)
            .Where(IsEven)
            .Aggregate<ulong, ulong>(0,(current, s) => (s + current));

        Console.WriteLine(result);
        Console.ReadLine();

    }

///允许人们创建上述递归函数的Functional-Style方法是由Bart De Smet提出的。见http://bartdesmet.net/blogs/bart/archive/2009/11/08/jumping-the-trampoline-in-c-stack-friendly-recursion.aspx

于 2011-08-14T11:33:26.317 回答
0

这是查找斐波那契数的好方法。

IEnumerable<BigInteger> Fibs()
{
    for(BigInteger a = 0,b = 1;;b = a + (a = b))
        yield return b;
}
于 2014-10-06T13:05:47.130 回答
0 
     // count(user input) of Fibonacci numbers   
        int[] array = new int[20];
        array[0] = 0;
        array[1] = 1;

        Console.WriteLine(array[0] + "\n" + array[1]); 

        for (int i = 2; i < 20; i++)
        {
            array[i] = array[i - 1] + array[i - 2];
            Console.WriteLine(array[i]); 
        }
于 2016-03-01T19:11:11.640 回答