racine carree

racine_carre.c

/* racine_carree: la racine carree entiere d'un entier naturel */

#include `<stdio.h>`

#include `<stdbool.h>`
#include "entier_nat.h"

#include "egal.h"


/* Profil:

 * -------
 *   entier_nat -> entier_nat
 *
 * Exemples:
 * ---------
 *
 * racine_carre(0) = 0
 * racine_carre(1) = 1
 * racine_carre(2) = 1
 * racine_carre(3) = 1
 * racine_carre(4) = 2
 * racine_carre(5) = 2
 * racine_carre(6) = 2
 * racine_carre(7) = 2
 * racine_carre(8) = 2
 * racine_carre(9) = 3
 * racine_carre(10) = 3
 *
 * il est necessaire de passer par une fonction auxiliaire
 *
 * aux: entier_nat x entier_nat -> entier_nat
 *
 *
 * Axiomes:
 * --------
 * aux(a, b) = si_alors_sinon_finsi( egal(carre(a), b),
 *                                   a, 
 *                                   si_alors_sinon_finsi( plus_petit_que(carre(a), b),
 *                                                         aux(succ(a), b),
 *                                                         prec(a)
 *                                                       )
 *                                 )
 *
 * carre(b) = aux(0, b)
 *
 * Algorithme recursif:
 * --------------------
 *  fonction racine_carre(a: entier_nat): entier_nat
 *  debut
 *     retourner aux(0, a)
 *  fin
 *
 *  fonction aux(a: entier_nat, b: entier_nat): entier_nat
 *  debut
 *   | si egal(carre(a), b)
 *   |  | alors retourner a
 *   |  | sinon si plus_petit_que(carre(a), b)
 *   |  |        | alors retourner aux(succ(a), b)
 *   |  |        | sinon retourner prec(a)
 *   |  |       finsi
 *   | finsi
 *  fin
 *
 * Algorithme iteractif:
 * ---------------------
 *  fonction racine_carre(a: entier_nat): entier_nat
 *  debut
 *     b: entier_nat
 *     b := 0
 *     tant que plus_petit_que(carre(b), a) faire
 *        b = b+1
 *     fintantque
 *     si egal(carre(b), a)
 *        alors retourner b
 *        sinon retourner prec(b)
 *  fin
 */

ENTIER_NAT carre(ENTIER_NAT a)
{
   return a*a;
}

ENTIER_NAT aux(ENTIER_NAT a, ENTIER_NAT b)
{
   if (egal_recursif(carre(a), b))
   {
      return a;
   }
   else
   {
      if (carre(a) < b)
      {
         return aux(succ(a), b);
      }
      else
      {
         return prec(a);
      }
   }
}

ENTIER_NAT racine_carre_recursif(ENTIER_NAT a)
{
   return aux(0, a);
}

ENTIER_NAT racine_carre_iteratif(ENTIER_NAT a)
{
   ENTIER_NAT b;
   b = 0;
   while (carre(b) < a)
   {
      b = b+1;
   }
   if (egal_iteratif(carre(b), a))
   {
      return b;
   }
   else
   {
      return prec(b);
   }
}

int main()
{
   int i;
   printf("Recursif / Iteratif\n");
   for (i = 0; i <= 16; i = i+1)
   {
      printf("carre de %d vaut: %d / %d\n", i, racine_carre_recursif(i), racine_carre_iteratif(i));
   }
}