20

所以我正在学习C++。我已经完成了“C++ 编程语言”和“Effective C++”，并且正在运行 Project Euler。问题 1...邓佐。问题2...不是那么多。我在 VS2008 上的 Win32 控制台应用程序上工作。

低于 400 万的斐波那契数列的所有偶数项的总和是多少？

它不起作用，所以我减少了一个 100 个测试用例......

这是我写的...

// Problem2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    cout << "Project Euler Problem 2:\n\n";
    cout << "Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:\n\n";
    cout << "1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\n\n";
    cout << "Find the sum of all the even-valued terms in the sequence which do not exceed four million.\n\n";
    cout << "Answer:  " << Solve();
}

double Solve() {
    int FibIndex = 0;
    double result = 0.0;
    double currentFib = GenerateNthFibonacciNumber(FibIndex);
    while (currentFib < 100.0){
        cout << currentFib << " " << (int)currentFib << " " << (int)currentFib % 2 << "\n";
        if ((int)currentFib % 2 == 0){
            result += currentFib;
            cout<<(int)currentFib;
        }
        currentFib = GenerateNthFibonacciNumber(++FibIndex);
    }
    return result;
}

double GenerateNthFibonacciNumber(const int n){
    //This generates the nth Fibonacci Number using Binet's Formula
    const double PHI = (1.0 + sqrt(5.0)) / 2.0;
    return ((pow(PHI,n)-pow(-1.0/PHI,n)) / sqrt(5.0));
}

这是输出...

欧拉计划问题 2：

斐波那契数列中的每个新项都是通过添加前两项来生成的。从 1 和 2 开始，前 10 个术语将是：

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

求序列中所有不超过四百万的偶数项之和。

0 0 0
1 1 1
1 1 1
2 2 0
3 3 1
5 5 1
8 8 0
13 13 1
21 21 1
34 34 0
55 54 0
89 89 1
答案：99

所以我有三列调试代码...从生成函数返回的数字，(int)generatedNumber 和 (int)generatedNumber % 2

所以在第 11 个学期，我们有

55,54,0

为什么 (int)55 = 54？

4

8 回答 8

57

强制转换为int截断数字 - 就像你打电话一样floor(currentFib)。因此，即使currentFibis 54.999999...（一个非常接近 55 的数字，在打印时会四舍五入），(int)currentFib也会产生 54。

于 2009-02-16T17:58:03.197 回答
13

由于浮点舍入，这 55 行正在计算类似 54.99999 的值。将 double 转换为 int 会立即截断 .99999。

在我的机器上，打印一列显示(currentFib-(int)currentFib)会显示 1.42109e-14 顺序的错误。所以它更像是 0.999999999999986。

于 2009-02-16T17:59:04.020 回答
4

好的，简短的回答是，在任何情况下都不应该 (int)55 == 54，所以你需要开始问自己相关的代码行到底在做什么。

==第一个问题：与类型转换相比，绑定的强度如何？

于 2009-02-16T17:59:47.030 回答
4

Shog9 说得对，如果要将事物转换为整数，则使用 double 类型来解决此类问题并不是最好的方法。如果您的编译器支持它，您应该使用 long long 或其他一些 64 位整数类型，这几乎肯定会保存小于 400 万斐波那契数列的所有偶数项之和的结果。

如果我们使用斐波那契数列遵循奇偶奇偶奇偶奇偶模式的事实......下面的东西应该可以解决问题。

...
unsigned int fib[3];
fib[0]=1;
fib[1]=1;
fib[2]=2;

unsigned long long sum=0;

while(fib[2]<4000000)
{
    sum+=fib[2];

    fib[0]=(fib[1]+fib[2]);
    fib[1]=(fib[2]+fib[0]);
    fib[2]=(fib[0]+fib[1]);
}

std::cout<<"The sum is: "<<sum<<". \n";
....

那应该可以解决问题，可能还有更快的方法，但是这个方法非常直接且易于阅读。

看着它，我意识到您可能会使用标准的无符号 32 位整数作为总和数，但我会保留它以防万一。

此外，您的代码对生成第 n 个斐波那契数函数进行了大量函数调用。一个体面的优化编译器会内联这些调用，但如果不这样做，事情就会变慢，因为函数调用比其他技术更昂贵。

于 2009-02-16T18:28:39.830 回答
2

我 100% 同意 shog9 的回答——使用你用来计算斐波那契的算法，你必须非常小心浮点值。我发现页面cubbi.com: fibonacci numbers in c++似乎显示了其他获取它们的方法。

我四处寻找一个关于如何让 GenerateNthFibonacciNumber 的实现处理返回双精度 54.999999 的情况的好主意，但是当你转换为 int 或 long 时，你会得到 54。

我在C++ Rounding遇到了似乎是一个合理的解决方案，我在下面的代码中对其进行了调整。

此外，这不是什么大问题，但您可能希望预先计算 PHI，然后将其作为参数传递或将其作为全局引用 - 现在您每次调用函数时都会重新计算它。

double GenerateNthFibonacciNumber(const int n)
{
        //This generates the nth Fibonacci Number using Binet's Formula   
        const double PHI = (1.0 + sqrt(5.0)) / 2.0;
        double x = ((pow(PHI,n)-pow(-1.0/PHI,n)) / sqrt(5.0));
        // inspired by http://www.codingforums.com/archive/index.php/t-10827.html
        return ((x - floor(x)) >= 0.5) ? ceil(x) : floor(x);
}

最后，这是我如何重写您的 Solve() 方法，以便 GenerateNthFibonacciNumber(FibIndex) 仅在代码中的一个位置调用。我还将包含当前偶数斐波那契项的当前运行总计的列添加到您的输出中：

double Solve() {
    long FibIndex = 0;
    double result = 0.0;
    double oldresult = 0.0;
    int done = 0;
    const double PHI = (1.0 + sqrt(5.0)) / 2.0;

    while (!done)
    {
        double currentFib = GenerateNthFibonacciNumber(++FibIndex);
        if ((int)currentFib % 2 == 0)
        {
            oldresult = result;

            if (currentFib >= 4000000.0)
            {
                done = 1;
            }
            else
            {
                result += currentFib;
            }

        }
        cout << currentFib << " " << (int)currentFib << " " << (int)currentFib % 2 << " " << (int)result << "\n";       
    }
    return result;
}
于 2009-02-16T20:49:57.463 回答
2

我知道这对您的真正问题没有帮助，但您提到您正在学习 C++。出于学习目的，我建议尽可能接近 ANSI。我认为这是/Za在 MSVC 上（您可能正在使用的）或-ansi -pedanticGCC 上。

特别是，您应该使用这些签名之一， main直到您有充分的（特定于平台的）理由不这样做：

int main(int argc, char *argv[]);
int main(int argc, char **argv); // same as the first
int main();

...而不是任何特定于平台的版本，例如这个（仅限 Windows）示例：

#include <windows.h> // defines _TCHAR and _tmain
int _tmain(int argc, _TCHAR* argv[]); // win32 Unicode vs. Multi-Byte
于 2009-02-17T03:07:10.567 回答
2

以上所有关于整数数学不要使用浮点值的建议都值得注意！

如果您想要整数“舍入”正浮点值，以便小数分量低于 0.5 的值舍入到下一个最小整数，而小数部分的值 0.5 或更大的值舍入到下一个更高的整数，例如

0.0 = 0
0.1 = 0
0.5 = 1
0.9 = 1
1.0 = 1
1.1 = 1
...etc...

将 0.5 添加到您要投射的值。

double f0 = 0.0;
double f1 = 0.1;
double f2 = 0.5;
double f3 = 0.9;

int i0 = ( int )( f0 + 0.5 );  // i0 = 0
int i1 = ( int )( f1 + 0.5 );  // i1 = 0
int i2 = ( int )( f2 + 0.5 );  // i2 = 1
int i3 = ( int )( f3 + 0.5 );  // i3 = 1
于 2009-02-17T09:33:39.373 回答
0

打破生成的代码，有时浮点数的行为与我们在长表达式中使用时的想法不同......打破代码并检查它。

于 2009-02-17T17:17:08.167 回答