Lesson of 13 July 2009

Some simple C programs

Fibonacci serie, recursive and non recursive implementation

File fibonacci.cc

/*
  A simple implementation of the calculation of Fibonacci numbers.

  F[0]   = 0 ;
  F[1]   = 1 ;
  F[k+1] = F[k] + F[k-1] ;

 */

#include <stdio.h> // use C stile I/O

// non recursive implementation

int // return an integer
fibonacci // name of the function
  ( // arguments of the function
    int k // request of the k-th Fibonacci number
  ) 
{ // begin of the body of the function
  int fk   ; // k-th Fibonacci number
  int fkp1 ; // k+1  Fibonacci number
  int fkm1 ; // k-1  Fibonacci number

  switch ( k ) {
    case 0:
      // do not need return 1 here because there is return 1 
      // for case 1:
    case 1:
      return 1 ;
      // break; is not necessary because return exit from switch
    default:
      // normal case, k>1. I can modify k because k is passed "by value".
      // In FORTRAN arguments are passed "by reference".

      // initialization, setup fk, fkp1 and fkm1 for k=1
      fkm1 = 1 ; 
      fk   = 1 ;
      fkp1 = 2 ;
      
      // update fk
      while ( k-- > 1 ) { // while ( k-- > 2 ) can be interpreted
                          // as while ( k > 2 ) whith k decremented 
                          // after the comparison
        fkp1 = fk + fkm1 ; // new value ;
        
        // shift new value
        fkm1 = fk ;
        fk   = fkp1 ;
      } ;
      return fkp1 ;  
  }

} // end of the body of the function


// Recursive implementation

int
fibonacciR( int k ) {
  printf("Entering Fibonacci %d\n",k) ;
  switch ( k ) {
    case 0:
    case 1:
      return 1 ;
    default:
      return fibonacciR(k-1)+fibonacciR(k-2) ;
  }
  printf("Exiting Fibonacci %d\n",k) ;
}


int
main() {
  // check fibonacci function
  int f10  = fibonacci( 10 ) ;
  int f10R = fibonacciR( 10 ) ;
  
  printf("fibonacci(10)  = %d\n", f10  ) ;
  printf("fibonacciR(10) = %d\n", f10R ) ;

}

QuickSort algorithm of O’Hara, recursive implementation on integer C vector

File quicksort.cc

/*
   Algorithm quick sort
 */

#include <iostream> // use I/O of C++

using namespace std ; // load the functions in standard namespace

/*
  Sort a verctor of integer by quick sort algorithm
  (John O'Hara algorithm)
 */
void
quickSort (int a[], int lo, int hi, int level) {
  // a[]: a is a pointer to the vector,
  // to access the element use a[0] = the first element
  // a[1] the second element, a[k] the k+1 element.
  //
  // lo is the lower index, hi is the upper index
  // of the region of array a that is to be sorted
  //
  // level = level of recursion
  for ( int kk = 0 ; kk < level ; ++kk ) cout << " " ;
  cout << "[" << lo << ", " << hi << "]\n" ;

  // sort only if we have at least 2 element
  if ( hi <= lo ) return ;
  
  int i     = lo ; // i is set to the beginning of the region
  int j     = hi ; // j is set to the end of the region
  int pivot = a[(lo+hi)/2] ; // (lo+hi)/2 the pivot is chosen
                             // in the middle of the vector
                             // but any index between lo and hi 
                             // can be used.
                             // (lo+hi)/2 is truncated to 
                             // the lower near integer
  //  partition
  while ( j > i ) { // if i==j only one elemet: the region is sorted
                    // if i < j empty region, nothing to sort 
    
    while ( a[i] < pivot ) i++ ; // a[ii] for ii <= i are less than pivot 
    while ( a[j] > pivot ) j-- ; // a[jj] for jj >= j are greater than pivot

    if ( i <= j ) { // check if the sub-regions are complete.
      // if not, we need to exchange the elements outside the
      // sub-regions
      int h=a[i] ; a[i]=a[j]; a[j]=h ; // exchange a[i] with a[j
      i++; j--; // a[i] and a[j] are in the correct region
                // so that we do not need to check again
    }
  } ;

  //  recursion onfy if region is not empty
  quickSort(a, lo, j, level+1);
  quickSort(a, i, hi, level+1);
}

int
main() {
  int vec[100] ; // declare and instance a vector of 100 elements
  
  // initialize some elements
  vec[0] = 9   ;
  vec[1] = 1   ;
  vec[2] = -1  ;
  vec[3] = 2   ;
  vec[4] = 2   ;
  vec[5] = 6   ;
  vec[6] = 5   ;
  vec[7] = -23 ;
  vec[8] = -2  ;
  vec[9] = 1   ;
  
  quickSort( vec, 0, 9, 0 ) ;
  
  // cout = character out object
  for ( int i = 0 ; i < 10 ; ++i )
    cout << i << " " << vec[i] << '\n' ;
    
  // define and initialize a vector
  int b[] = { 1, 2, -3, 0, -45, -1, 0, 3, 67} ;

  // evaluate the size of vector b.
  // sizeof return the size in byte of the element in argument
  // sizeof(b) return the number of bytes used by  the whole vector
  // sizeof(b[0]) return the number of bytes used by and element of the vector
  int szb = sizeof(b)/sizeof(b[0]) ;
  
  quickSort( b, 0, szb-1, 0 ) ;

  //cout = character out object
  for ( int i = 0 ; i < szb ; ++i )
    cout << i << " " << b[i] << '\n' ;

  return 0 ;
}

---