Last active
November 5, 2019 08:55
-
-
Save pinglunliao/b469b5576cc402461d1a to your computer and use it in GitHub Desktop.
c121: 00495 - Fibonacci Freeze. FYI: https://yunlinsong.blogspot.com/2015/03/c121-00495-fibonacci-freeze.html
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment