c++ - 数字非常大的数字的组成

Question

我正在尝试使用数字 1 和 2 计算数字组合方式的数量。这可以使用斐波那契数列找到，其中F(1)=1和F(2)=2

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

由于 F(n) 可能非常大，我只需要F(n)%1000000007。为了加快我使用斐波那契指数的过程。我为同一个问题编写了两个代码（两者几乎相似）。但是其中一个对于大数字失败了。我我无法弄清楚哪一个是正确的？

CODE 1

CODE 2

虽然我觉得第一个应该是正确的。我无法弄清楚当我们乘以 saya并且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

score 0 · Accepted Answer

无符号 n 位类型的“溢出”（对于无符号数，它们并不真正称之为“溢出”）只会保留模 2^n 的值，而不是模任意模（它们怎么可能？尝试重现这些步骤）笔和纸）。因此，您必须确保没有任何操作超出您的类型的限制，以保持正确的结果 mod 100000007。

1 回答 1