Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

// Prog: fibonacci2.cpp // Compute the first n Fibonacci numbers #include #include // POST: return value is the n-th Fibonacci number F_n ifm::integer fib2 (unsigned int n) { if (n == 0) return 0; if (n <= 2) return 1; ifm::integer a = 1; // F_1 ifm::integer b = 1; // F_1 for (unsigned int i = 3; i <= n; ++i) { ifm::integer a_prev = a; // F_{i-2} a = b; // F_{i-1} b += a_prev; // F_{i-1} + F_{i-2} = F_i } return b; } int main() { std::cout << "Compute the first n Fibonacci numbers for n =? "; unsigned int n; std::cin >> n; for (unsigned int i=0; i