2012年8月23日

UVa 495 - Fibonacci Freeze


#include <cstdio>
#include <string>
using std::string;

string add(string a, string b) { 
  string answer;
  int carry = 0, temp;
  int digit, digitA, digitB;
  digitA = a.length();
  digitB = b.length();;
  digit = digitA > digitB ? digitA : digitB;
  while (digit > 0) {
    temp = carry;
    if (--digitA >= 0) temp += a[digitA] - '0';
    if(--digitB >= 0) temp += b[digitB] - '0';
    carry = temp / 10;
    temp %= 10;
    answer.insert(answer.begin(), temp + '0');
    --digit;
  }
  if (carry) answer.insert(answer.begin(), carry + '0');
  return answer;
}

int main() {
  int i, n;
  string num[5001];
  num[0] = "0";
  num[1] = "1";
  for (i = 2; i < 5001; i++)
    num[i] = add(num[i - 1], num[i - 2]);
  while (scanf("%d", &n) == 1)
    printf("The Fibonacci number for %d is %s\n", n, num[n].c_str());
  return 0;
}

沒有留言:

張貼留言