範例程式碼 uva495
//uva495
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef unsigned int uint;
const uint MX = 5000, CARRY = static_cast<uint>(1e9);
class BigNum {
uint len, *num;
public:
void set(uint n) {
if (n < CARRY) {
len = 1;
num = (uint *)calloc(len, sizeof(uint));
num[0] = n;
} else {
len = 2;
num = (uint *)calloc(len, sizeof(uint));
num[0] = n % CARRY;
num[1] = n / CARRY;
}
}
void sum(const BigNum &l, const BigNum &s) { // l.len must >= s.len
len = l.len;
num = (uint *)calloc(len + 1, sizeof(uint));
memcpy(num, l.num, len * sizeof(uint));
for (int i = 0; i < s.len; i++) num[i] += s.num[i];
for (int i = 0; i < len; i++) {
num[i+1] += num[i] / CARRY;
num[i] %= CARRY;
}
if (num[len] > 0) len++;
}
friend ostream &operator <<(ostream &os, const BigNum &bn);
} fib[MX+1];
ostream &operator <<(ostream &os, const BigNum &bn) {
printf("%u", bn.num[bn.len-1]);
for (int i = (bn.len-2); i >= 0; i--) {
printf("%09u", bn.num[i]);
}
return os;
}
int main() {
fib[0].set(0);
fib[1].set(1);
for (int i = 2; i <= MX; i++) fib[i].sum(fib[i-1], fib[i-2]);
int x;
while (cin >> x) {
cout << "The Fibonacci number for " << x << " is " << fib[x] << endl;
}
return 0;
}