0

数字の 1 と 2 を使用して、数字を構成する方法の数を計算しようとしています。これは、フィボナッチ数列F(1)=1を使用しF(2)=2て見つけることができます。

F(n)=F(n-1)+F(n-2)

F(n) は非常に大きくなる可能性があるため、必要なだけですF(n)%1000000007。プロセスを高速化するために、フィボナッチ指数を使用しています。同じ問題に対して 2 つのコードを書きました (どちらもほとんど同じです)。どちらが正しいかわかりませんか？

CODE 1

http://ideone.com/iCPEyz

CODE 2

http://ideone.com/Un5p2S

a先に1が正解という感じはありますが、と の掛け算bで の値aが既に の上限を超えていてaを掛けたらどうなるかわかりませんb。それが正しいとどれほど確信できるでしょうかa*b。私の知る限り、a値がデータ型の制限を超えている場合、値は以下の例のように最小値から再開されます。

#include<iostream>
#include<limits.h>
using namespace std;
int main()
{
    cout<<UINT_MAX<<endl;
    cout<<UINT_MAX+2;
}

Output

4294967295

1
4

1 に答える 1

0

符号なしnビット型の「オーバーフロー」（実際には符号なしの場合はラップアラウンドとは呼びません）は、モジュロ2 ^ nのみを保持し、モジュロ任意のモジュロではありません（どうすればよいでしょうか？次の手順を再現してみてくださいペンと紙）。したがって、mod 100000007 の正しい結果を維持するために、操作がタイプの制限を超えないようにする必要があります。

于 2013-02-03T15:52:03.333 に答える