我是c 新手，同時通過學習演算法開始學習它。但是，我在寫這個演算法的時候遇到了一些問題——數字溢位，這和我想象的溢位有很大的不同。為了解決這個問題，我搜索了很長時間，但最終沒有用。這是我的代碼：
#include <iostream>
using namespace std;
long long Fs[101];
long long F(int N) {
if (Fs[N] != -1) {
return Fs[N];
}
int res = F(N - 1) F(N - 2);
Fs[N] = res;
return res;
}
void main() {
// initialize Fs array
for (auto& item : Fs) {
item = -1;
}
Fs[0] = 0;
Fs[1] = 1;
cout << F(60) << endl;
cout << endl;
for (auto& item : Fs) {
cout << item << endl;
}
}
部分結果如下所示：
165580141
267914296
433494437
701408733
1134903170
1836311903
-1323752223
512559680
-811192543
問題：
您可以看到溢位數比型別的最小值要小得多long long。為什么會這樣？
附錄
我找到了一些在生成時列印無符號型別溢位索引的方法fibonacci，代碼如下：
#include <iostream>
#include <limits>
using namespace std;
#define outFibonacci(nType) { int i = 1;\
while (i )\
if (Fibonacci<nType>(i 1)==Fibonacci<nType>(i 2)){\
cout<<"F("<<i<<")\t= "<<Fibonacci<nType>(i)<<endl;\
break;\
}\
cout<< "Max Num\t= " << numeric_limits<nType>::max() << endl << endl;\
}
template<typename _T> _T Fibonacci(_T n){
_T f, f1, f2;
f = f1 = f2 = 1;
for (auto i=3; i<=n; i){
f = f1 f2;
if (f<f2){ // Set overflow condition
f=-1;
break;
}
f1 = f2;
f2 = f;
}
return f;
}
int main(void)
{
outFibonacci(unsigned short);
outFibonacci(unsigned int);
outFibonacci(unsigned long);
outFibonacci(unsigned long long);
outFibonacci(size_t);
return 0;
}
這是我的結果：
F(24) = 46368
Max Num = 65535
F(47) = 2971215073
Max Num = 4294967295
F(47) = 2971215073
Max Num = 4294967295
F(93) = 12200160415121876738
Max Num = 18446744073709551615
F(93) = 12200160415121876738
Max Num = 18446744073709551615
uj5u.com熱心網友回復：
函式int res = F(N - 1) F(N - 2);中的這一行 使您的結果為 int，然后將其轉換為 long long。所以溢位發生在這里。應該被一些編譯器標記。
long long F(int N) {
if (Fs[N] != -1) {
return Fs[N];
}
// int res = F(N - 1) F(N - 2); // HERE !
long long res = F(N - 1) F(N - 2);
Fs[N] = res;
return res;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/478411.html
上一篇：黑客地球演習超過時間限制