20

だから私はC++を学んでいます。「C++プログラミング言語」と「EffectiveC++」を入手し、ProjectEulerを実行しています。問題1...ダンゾ。問題2...それほど多くはありません。Win32コンソールアプリでVS2008を使用しています。

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：

フィボナッチ数列の新しい各項は、前の2つの項を追加することによって生成されます。1と2から始めると、最初の10項は次のようになります。

1、2、3、5、8、13、21、34、55、89、..。

400万を超えないシーケンス内のすべての偶数値の項の合計を見つけます。

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

したがって、デバッグコードの3つの列があります...生成関数から返される数値、（int）generatedNumber、および（int）generatedNumber％2

つまり、第11学期には、

55,54,0

（int）55 = 54なのはなぜですか？

4

8 に答える 8

57

キャストしintて番号を切り捨てます-と呼んだ場合と同じですfloor(currentFib)。したがって、currentFib... 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.9999999999999986のようなものです。

于 2009-02-16T17:59:04.020 に答える
4

簡単に言うと、どのような条件下でも（int）55 == 54であってはならないので、関連するコード行が実際に何をしているのかを自問する必要があります。

==最初の質問：型キャストと比較して、バインドはどのくらい強力ですか？

于 2009-02-16T17:59:47.030 に答える
4

Shog9 は正しく、このような問題に double 型を使用することは、物事を int にキャストする場合に最適な方法ではありません。コンパイラがサポートしている場合は、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

整数演算に浮動小数点値を使用しないという上記のすべての提案は注目に値します!

正の浮動小数点値に対して整数の「丸め」が必要な場合、小数部分が 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 に答える
2

shog9 の回答に 100% 同意します。フィボナッチの計算に使用したアルゴリズムでは、浮動小数点値には十分注意する必要があります。ページcubbi.com: fibonacci numbers in c++は、それらを取得する他の方法を示しているようです。

GenerateNthFibonacciNumber の実装で double 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);
}

最後に、GenerateNthFibonacciNumber(FibIndex) がコード内の 1 か所でのみ呼び出されるように Solve() メソッドを書き直した方法を次に示します。また、偶数フィボナッチ項の現在の累計を含む列を出力に追加しました。

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 に答える
0

生成のためにコードを壊してください。長い式で使用されたときに浮動小数点数が私たちが考えるように振る舞わないことがあります...コードを壊してチェックしてください。

于 2009-02-17T17:17:08.167 に答える