plus_petit_que

plus_petit_que.c

#include "entier_nat.h"

#include "egal.h"

/* Axiomes:

plus_petit_que(x,0) = faux
plus_petit_que(0,succ(y)) = vrai
plus_petit_que(succ(x),succ(y)) = plus_petit_que(x, y)

Algorithme recursif:
--------------------
fonction plus_petit_que(a: entier, b: entier): booleen
debut
 | si est_nul(a)
 | -------------
 |               | alors si est_nul(b)
 |               |                     | alors retourner faux                           
 |               |                     | sinon retourner vrai                           
 |               | finsi              
 |               | sinon si est_nul(b)
 |               |                     | alors retourner faux                           
 |               |                     | sinon retourner plus_petit_que(prec(a), prec(b)
 |               | finsi              
 | finsi        
fin

Algorithme iteratif:
--------------------
fonction plus_petit_que(a: entier, b: entier): booleen
debut
 | tant que non est_nul(a) et non est_nul(b) faire
 | -----------------------------------------------
 |                                                 | a := prec(a)        
 |                                                 | b := prec(b)        
 | fintantque                                     
 | si est_nul(b)                                  
 |                                                 | alors retourner faux
 |                                                 | sinon retourner vrai
 | finsi                                          
 | // se simplifie en 'retourner non est_nul(b)'  
fin

*/

bool plus_petit_que_recursif(ENTIER_NAT a, ENTIER_NAT b)
{
   if (est_nul(a))
   { /*alors */
      return ! est_nul(b);
      /* remplace avantageusement:
      if est_nul(b)
      { 
         return false;
      }
      else
      { 
         return true;
      } 

      */
   }
   else
   {
      if (est_nul(b))
      { /*alors */
         return false;
      }
      else
      { /* sinon */
         return plus_petit_que_recursif(prec(a), prec(b));
      } /* finsi */
   }
}

bool plus_petit_que_iteratif(ENTIER_NAT a, ENTIER_NAT b)
{
    while ( (! est_nul(a)) && (! est_nul(b)))
    {
     a = prec(a);
     b = prec(b);
    }
    return ! est_nul(b);
}


/* tests */
void test_plus_petit_que_recursif(ENTIER_NAT a, ENTIER_NAT b)
{
   bool c;

   c = plus_petit_que_recursif(a,b);
   if (c)
   {
     printf("%d `< %d ? ->` vrai\n", a, b);
   }
   else
   {
     printf("%d `< %d ? ->` faux\n", a, b);
   }

}

void test_plus_petit_que_iteratif(ENTIER_NAT a, ENTIER_NAT b)
{
   bool c;

   c = plus_petit_que_iteratif(a,b);
   if (c)
   {
     printf("%d `< %d ? ->` vrai\n", a, b);
   }
   else
   {
     printf("%d `< %d ? ->` faux\n", a, b);
   }

}

int main()
{
   test_plus_petit_que_recursif(0,0);
   test_plus_petit_que_recursif(0,1);
   test_plus_petit_que_recursif(1,0);
   test_plus_petit_que_recursif(5,5);
   test_plus_petit_que_recursif(3,5);
   test_plus_petit_que_recursif(4,2);
   test_plus_petit_que_recursif(100,100);
   test_plus_petit_que_iteratif(0,0);
   test_plus_petit_que_iteratif(0,1);
   test_plus_petit_que_iteratif(1,0);
   test_plus_petit_que_iteratif(5,5);
   test_plus_petit_que_iteratif(3,5);
   test_plus_petit_que_iteratif(4,2);
   test_plus_petit_que_iteratif(100,100);
}