Algorithmique fondamentale, Graphes et Test

Exercise 1

1. Question 1: Write the C function fibo calculating the fibonacci number of a given rank, using the naive recursive algorithm presented during the course (with the double recursivity)

   int fibo (int n){
     if n = 0 OR n = 1
       return (1)
     else 
       return (fibo(n-1) + fibo(n-2)) 
   }
   

   • Write a test program using the frame below

     int fibo (int n){
       ...
     }
     
     int main(){
       int n;
       int resultRecursive;
       printf("Enter a value of n in order to calculate fibonacci(n)?");
     
       resultRecursive = fibo(n);  
       printf("Recursive version: result= %d", resultRecursive);
     }
     

   • Compile and test your algorithm before working on the Question 2
   • Correct output : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... the first 0 is optional
2. Question 2: Propose an iterative version of this function called fiboIter.
3. Question 3: Write a C main program that asks the user to give an argument, calls the functions fibo and fiboIter, and displays the obtained results. Test your program on several different values.

   • int fibo (int n){
       ...
     }
     
     int fiboIter (int n){
       ...
     }
     
     int main(){
       int n;
       int resultRecursive;
       int resultIterative
     
       printf("Enter a value of n in order to calculate fibonacci(n)?");
     
       resultRecursive = fibo(n);  
       resultIterative = fiboIter(n)
       printf("Recursive version: result= %d", resultRecursive);
       printf("Iterative version: result= %d", resultIterative);
     }