| // 495.cpp http://acm.uva.es/p/v4/495.html |
| // |
| // Solution to ACM problem #495 - "Fibonacci Freeze" |
| // |
| // Matthew Eagar - meagar@gmail.com |
| // Verified to work as of Dec 09 / 2005 |
| |
| #include <list> |
| #include <iostream> |
| #include <map> |
| #include <string> |
| |
| int main() { |
| typedef std::list<int> List; |
| |
| // nums holds the numbers we need to find the fib. for, in the order they appear in the input |
| List nums; |
| |
| // fibs holds the fib. number for each of the input numbers |
| std::map<int, std::string> fibs; |
| |
| int n; |
| while (std::cin >> n) { |
| nums.push_back(n); |
| fibs[n] = ""; |
| } |
| |
| fibs[0] = "0"; // constant |
| fibs[1] = "1"; // constant |
| |
| // n0 and n1 are our two big numbers |
| List n0, n1; |
| // start with the first two terms |
| n0.push_back(0); |
| n1.push_back(1); |
| |
| // find the highest input number, and loop until we hit it |
| int highest = fibs.rbegin()->first; |
| for (int n = 2; n <= highest; ++n) { |
| // Add n1 to n0, placing the result in n0 |
| List::iterator i = n0.begin(); |
| List::iterator j = n1.begin(); |
| |
| int carry = 0; |
| // write directly to n0 until it's iterator hits it's end |
| while (i != n0.end()) { |
| *i += *j + carry; |
| carry = (int)((float)*i / 10.0f); |
| *i %= 10; |
| ++i; ++j; |
| } |
| |
| // append to n0 until n1's iterator reaches it's end |
| // (n0 will always be the shorter number) |
| while (j != n1.end()) { |
| int tmp = *j + carry; |
| carry = (int)((float)tmp / 10.0f); |
| n0.push_back(tmp % 10); |
| ++j; |
| } |
| |
| // append the remainder, if any |
| if (carry != 0) |
| n0.push_back(carry); |
| |
| // Swap, so that n1 is now n0 + (n1's old value) |
| std::swap(n0, n1); |
| |
| // see if we need the n'th fib |
| if (fibs.find(n) != fibs.end()) { |
| char* str = new char[n1.size() + 1]; |
| int p = 0; |
| for (List::reverse_iterator it = n1.rbegin(); it != n1.rend(); ++it) |
| str[p++] = *it + '1' - 1; |
| str[n1.size()] = 0; |
| fibs[n] = str; |
| } |
| } |
| |
| for (List::iterator it = nums.begin(); it != nums.end(); ++it) |
| std::cout << "The Fibonacci number for " << *it << " is " << fibs[*it] << std::endl; |
| } |