題目連結 http://zerojudge.tw/ShowProblem?problemid=c121。
此題需要用到大數運算的做法,程式碼是用字串來處理。
程式碼:
#include <iostream>
#include <string>
// Fibonacci
using namespace std;
string addition(string s, string s2) // 加法
{
int len, lenS, MaxL, i, a, b, c = 0;
string BNstr(s2);
// 去掉多餘的數字0
len = BNstr.length(); // 讀取被加數的長度
lenS = s.length(); // 讀取加數的長度
for (i = 0; i < len-1; i++)
if (BNstr[0] == '0')
BNstr.erase(BNstr.begin());
else
break;
for (i = 0; i < lenS-1; i++)
if (s[0] == '0')
s.erase(s.begin());
else
break;
len = BNstr.length();
lenS = s.length();
MaxL = (len > lenS)?len:lenS;
for (i = 0; i < MaxL; i++) {
if (i < len) a = BNstr[len-1-i]-'0';
else a = 0;
if (i < lenS) b = s[lenS-1-i]-'0';
else b = 0;
if (i < len) BNstr[len-1-i] = (a+b+c)%10+'0';
else BNstr.insert(BNstr.begin(),(a+b+c)%10+'0');
c = (a+b+c)/10;
}
BNstr.insert(BNstr.begin(),c+'0');
// 去掉多餘的數字0
len = BNstr.length();
for (i = 0; i < len-1; i++)
if (BNstr[0] == '0')
BNstr.erase(BNstr.begin());
else
break;
return BNstr;
}
int main(void){
const int SIZE = 5001;
string Fibonaccinum[SIZE] = { "0", "1" };
for( int i = 2; i < SIZE; i++ )
{
Fibonaccinum[i] = addition(Fibonaccinum[i-1], Fibonaccinum[i-2]);
}
int n;
while( cin >> n )
{
cout << "The Fibonacci number for " << n << " is " << Fibonaccinum[n] << endl;
}
return 0;
}
沒有留言:
張貼留言