Laboratory 5 Solutions
For n = 46, fibRec takes about 20 secs, but fibTail and fibWhile take less than 1 sec.
Solution to fibRec.cc code:
/******************************************************************* * Name: Brenda Student * Date: 3/12/14 * Course: CSCI 132 Section 01 * Assignment: Lab 5 * Instructor: Royden * Program: fibRec.cc * Purpose: A program that calls a recursive function to compute the nth * fibonacci number. ***************************************************************************/ #include <iostream> using namespace std; int fibRec(int); int main(void) { int num; //number for computing fibonacci function cout << "Enter an integer: "; cin >> num; cout << "The fibonacci number for month " << num << " is " << fibRec(num) << endl; } /*Recursively compute fibonacci number*/ int fibRec(int n) { if (n < 2) { return n; } else { return fibRec(n-1) + fibRec(n-2); } }
Solution to fibTail.cc code:
/******************************************************************* * Name: Brenda Student * Date: 3/12/14 * Course: CSCI 132 Section 01 * Assignment: Lab 5 * Instructor: Royden * Program: fibTail.cc * Purpose: A program that calls a tail recursive function to compute the nth * fibonacci number. ***************************************************************************/ #include <iostream> using namespace std; int fibIter(int); int fibTail(int, int, int, int); int main(void) { int num; //number for computing fibonacci function cout << "Enter an integer: "; cin >> num; cout << "The fibonacci number for month " << num << " is " << fibIter(num) << endl; } int fibIter(int n) { return fibTail(n, 1, 0, 1); } /*Use tail recursion to compute fibonacci number*/ int fibTail(int n, int i, int fib_i_minus1, int fib_i) { if (n == i) { return fib_i; } else { return fibTail(n, i+1, fib_i, fib_i + fib_i_minus1); } }
Solution to fibWhile.cc code:
/******************************************************************* * Name: Brenda Student * Date: 3/12/14 * Course: CSCI 132 Section 01 * Assignment: Lab 5 * Instructor: Royden * Program: fibwhile.cc * Purpose: A program that calls a function to compute the nth * fibonacci number using a while loop ***************************************************************************/ #include <iostream> using namespace std; int fibWhile(int); int main(void) { int num; //number for computing fibonacci function cout << "Enter an integer: "; cin >> num; cout << "The fibonacci number for month " << num << " is " << fibWhile(num) << endl; } /*Compute Fibonacci number with a while loop*/ int fibWhile(int n) { int i= 1; int fib_i_minus1 = 0; int fib_i = 1; while (i < n) { int fib_inext = fib_i + fib_i_minus1; fib_i_minus1 = fib_i; fib_i = fib_inext; i = i+1; } return fib_i; }
Home | | Syllabus | | Assignments | | Lecture Notes