Les entiers naturels

Definition

entier_naturel_batons.h

/******************************************/
/* entier_naturel_batons.h                */
/* auteur : Jens Gustedt & Jean Lieber    */
/* date : 22/09/09                        */
/* version : 1                            */
/******************************************/

#include `<stdio.h>`  /* Pour le printf */

#include `<stdlib.h>` /* Pour le exit */
#include `<stdbool.h>`

#define ENTIER_NAT unsigned int

/* Constructeurs */
#define ZERO 0

ENTIER_NAT succ (ENTIER_NAT x)
{
    return 1 + x ;
}

ENTIER_NAT erreur_entier_nat () {
    printf ("Erreur de manipulation d'entier naturel.") ;
    exit (EXIT_FAILURE) ;
    return 0 ;
}

/* Accès */
ENTIER_NAT est_nul (ENTIER_NAT x)
{
    return x == 0 ;
}

ENTIER_NAT prec (ENTIER_NAT x)
{
    if (x == 0)
    {
    return erreur_entier_nat () ;
    }
    return x - 1 ;
}

Exercice 1: égal

egal.c

#include `<stdio.h>`

#include `<stdlib.h>`
#include `<stdbool.h>`


/* pour utiliser les fonctions primitives sur les entiers naturels */
#include "entier_naturel_batons.h"

/* 
 Signature: egal: entier_nat X entier_nat -> booleen
 ==========

 Exemples:
 =========

            egal(0, 0) = vrai
            egal(0, 3) = faux
            egal(2, 0) = faux
            egal(3, 2) = egal(2, 1)
                       = egal(1, 0)
                       = faux

 Axiomes:
 ========
            egal(zero(), zero()) = vrai
            egal(succ(n), zero()) = faux
            egal(zero(), succ(n)) = faux
            egal(succ(n), succ(m)) = egal(prev(succ(n)), prev(succ(m))) = egal(n, m)

 Algorithme recursif:
 ====================

    fonction egal(a: entier_nat, b: entier_nat): booleen
    debut
 | si (est_zero(a))
 | ----------------
 |                  | alors si (est_zero(b))
 |                  |                        | alors retourner vrai                  
 |                  |                        | sinon retourner faux                  
 |                  | finsi                 
 |                  | sinon si (est_zero(b))
 |                  |                        | alors retourner faux                  
 |                  |                        | sinon retourner egal(prec(a), prec(b))
 |                  | finsi                 
 | finsi           
    fin

 Algorithme iteratif:
 ====================

    fonction egal(a: entier_nat, b: entier_nat): booleen
    debut
 | vara: entier_nat                                    
 | ----------------                                    
 | varb: entier_nat                                    
 | vara := a                                           
 | varb := b                                           
 | tantque non (est_zero(vara) ou est_zero(varb)) faire
 |                                                      | vara := prec(vara)
 |                                                      | varb := prec(varb)
 | fintantque                                          
 | retourner (est_zero(vara) et est_zero(varb))        
    fin

*/

ENTIER_NAT egalR(ENTIER_NAT a, ENTIER_NAT b)
{
    if (est_nul(a))
    {
    if (est_nul(b))
    {
      return true;
    }
    else
    {
      return false;
    }
    }
    else
    {
    if (est_nul(b))
    {
      return false;
    }
    else
    {
      return egalR(prec(a), prec(b));
    }
    }
}

ENTIER_NAT egalI(ENTIER_NAT a, ENTIER_NAT b)
{
    ENTIER_NAT vara;
    ENTIER_NAT varb;
    vara = a;
    varb = b;
    while (! (est_nul(vara) || est_nul(varb)))
    {
    vara = prec(vara);
    varb = prec(varb);
    }
    return est_nul(vara) && est_nul(varb);
}

void testR(ENTIER_NAT a, ENTIER_NAT b)
{
   if (egalR(a,b))
   { 
     printf(" %d et %d sont egaux (recursif)\n", a, b);
   }
   else
   {
     printf(" %d et %d ne sont pas egaux (recursif)\n", a, b);
   }
}

void testI(ENTIER_NAT a, ENTIER_NAT b)
{
   if (egalI(a,b))
   { 
     printf(" %d et %d sont egaux (iteratif)\n", a, b);
   }
   else
   {
     printf(" %d et %d ne sont pas egaux (iteratif)\n", a, b);
   }
}


int main()
{
    testR(0,0);
    testR(0,2);
    testR(3,0);
    testR(3,3);
    testR(2,3);
    testI(0,0);
    testI(0,2);
    testI(3,0);
    testI(3,3);
    testI(2,3);
    return EXIT_SUCCESS;
}

Autres exercices