DEUG MIAS-2, 2000-2001
Informatique
Institut Galilée

TD 4

Le but de ce TD est de mettre en place une structure de données pour coder les rationnels dans une base b, ainsi qu’une collection d’opérations pour les manipuler. Pour çà, on abordera progressivement le cas des entiers naturels, puis des entiers relatifs et enfin celui des rationnels.

D’un point de vue pédagogique : comparer les méthodes récursives et itératives pour différents problèmes, et surtout réaliser l’importance de la modularité.

Pour stocker un entier naturel, on utilise la structure suivante :

Const N = 100 ;
Const Base = 12 ;
type Tchiffre = 0..Base-1 ;
type Tnaturel = enregistrement
                  debut,fin : entier ;
                  tab : tableau (1..N) de Tchiffre ;
                fin enregistrement ;

1.	Préliminaires

Soit n un entier naturel. On rappelle que la représentation de n en base b est l’unique suite finie (a0,..,ap) d’éléments de {0 ;... ;b-1} telle que n = a0b0 + a1b1 + ... + apbp. Avec ces notations, on dit que a0 est le chiffre de poids faible, et que ap est le chiffre de poids fort de la représentation de n en base b.

a)	Ecrire une fonction Naturel(n : entier) : Tnaturel qui renvoie le nombre correspondant à n. On conviendra que debut marque le chiffre de poids faible et fin le chiffre de poids fort. On écrira 2 versions de cette fonction : une itérative, et une récursive.

Solution : 

fonction Naturel_it(n : entier) : Tnaturel ;
var Nat : Tnaturel ;
debut
  Nat.debut  1
  Nat.fin  0 ;
  tant que n <> 0 faire
    Nat.fin  Nat.fin + 1 ;
    Nat.tab[Nat.fin]  n mod Base ;
    n  n div Base ;
  fin tant que
  retourne Nat ;
fin

Remarque : Ici le zéro est caractérisé par zéro.fin=0 

La version récursive (vraiment juste pour faire joli) :

procedure Naturel_rec(n : entier ; var Nat : Tnaturel) ;
debut
  si n <> 0 alors
    Nat.fin  Nat.fin + 1
    Nat.tab[Nat.fin]  n mod Base ;
    Naturel_rec(n div Base,Nat) ;
  fin si ;
fin ;

Appelée par

fonction Naturel(n : entier) : Tnaturel ;
var Nat : Tnaturel ;
debut
  Nat.debut  1 ;
  Nat.fin  0 ;
  Naturel_rec(n,Nat) ;
  retourne Nat ;
fin ;

A aucun endroit on tient compte des débordements éventuels de capacité car entier est assez petit et Tnaturel assez grand pour pour çà n’arrive pas.

b)	Ecrire les fonctions EgalZero(n : Tnaturel) : boolean, et EgalUn(n : Tnaturel) : boolean, Egal(n1,n2 : Tnaturel) : boolean, et Sup(n1,n2 : Tnaturel) : Boolean (vrai si n1>n2)

Solution :

On applique simplement la remarque de 1. a).

fonction EgalZero(n : Tnaturel) :booleen ;
debut
  retourne n.fin=0 ;
fin ;

fonction EgalUn(n : Tnaturel) :booleen ;
debut
  retourne (n.fin=n.debut) et (n.tab[n.fin]=1) ;

  {       à placer en premier                 }
  {l’évaluation “ paresseuse ” des booléens   }
  {empêche de regarder n.tab[n.fin] qd n.fin=0}

fin

On créé une fonction intermédiaire

fonction Long (n : Tnaturel) : entier ;
debut
  retourne n.fin-n.debut+1 ;
fin

fonction egal(n1,n2 : Tnaturel) : booleen ;
debut
  si Long(n1) <> Long(n2) alors
    retourne FAUX
  sinon
    pour i de n1.debut à n1.fin faire
      si n1.tab[i] <> n2.tab[i+n2.debut-n1.debut]
      alors retourne FAUX
    fin pour
  fin si
  retourne VRAI
fin

Pour Sup, on balaie simplement les 2 entiers en partant des chiffres de poids forts tant qu’ils sont égaux. 

fonction Sup(n1,n2 : Tnaturel) : boolean
debut
  si Long(n1)>Long(n2) alors
    retourne VRAI
  sinon 
    si Long(n1)<Long(n2) alors
      retourne FAUX
    sinon

      {c’est que long(n1)=long(n2)}
      {On balaie alors n1 et n2 en partant des}
      {chiffres de poids fort jusqu'à ce qu’on}
      {tombe sur 2 chiffres distincts}

      pour i de n1.fin à n1.debut faire
        si n1.tab[i] > n2.tab[i+n2.fin-n1.fin]
        alors 

          {Dans ce cas n1>n2 => VRAI}

          retourne VRAI

        sinon si n1.tab[i] < n2.tab[i+n2.fin-n1.fin]
              alors 

              {Ici, n1<n2 => FAUX}

                retourne FAUX

              fin si
        fin si
      fin pour
    fin si
  fin si

  {n1=n2 => on a pas n1>n2 => FAUX}
  retourne FAUX 
fin

2.	Opérations élémentaires

a)	L’addition

i)	Ecrire une fonction Add (n1,n2 : Tnaturel) : Tnaturel qui renvoie la somme de n1 et n2.

Solution : C’est désesperement itératif...

fonction Add(n1,n2 : Tnaturel) : Tnaturel ;
var petit,grand : Tnaturel ;
    i,s,retenue,decalage : entier ;
debut
  {Un peu de cuisine...}
  si Long(n1)>Long(n2) alors 
    grand  n1
    petit  n2
  sinon
    grand  n2
    petit  n1
  fin si ;

  decalage  grand.debut-petit.debut
  retenue  0 ;

  {On somme la partie “ petit ”}

  pour i de petit.debut à petit.fin faire
    s  petit.tab[i]+grand.tab[i+decalage]
        + retenue ;
    si s >= Base alors
      retenue  1 ;
      s  s - Base ;
    sinon
      retenue  0 ;
    fin si
    grand.tab[i+decalage]  s ;
  fin pour

  {On somme le reste}

  pour i de grand.debut+Long(petit) à grand.fin
  faire
    s  grand.tab[i]+retenue ;
    si s >= Base alors
      retenue  1 ;
      s  s - Base ;
    sinon retenue  0
    fin si
    grand.tab[i]  s ;
  fin pour
  retourne grand ;
fin ;

ii)	Ecrire une fonction Dec (n : Tnaturel) : Tnaturel qui ôte 1 à n et renvoie le résultat et une fonction Inc (n : Tnaturel) : Tnaturel qui ajoute 1 à n. En déduire une version récursive de Add. Commenter cette version. Est elle plus efficace ? pourquoi ?

Solution :

fonction Dec (n : Tnaturel) : Tnaturel ;
debut

{On règle froidement le cas du zéro}

  si EgalUn(n) alors n.fin  0
  sinon
    p  n.debut ;
    tant que (n.tab[p] = 0) et (p <= n.fin)
    faire
      n.tab[p]  Base-1 ; 

      {On remplace les 0 par des 9}

      p  p + 1 ;
    fin tant que

    {Et on décrémente le chiffre du bout}
    {de la séquence de 9 (ou plutot Base-1)}

    n.tab[p]  n.tab[p] - 1 ;
    si n.tab[p]=0 alors n.fin  n.fin-1 ;
    fin si
  fin si
  retourne n ;
fin ;

Pour Inc, c’est la même chose mais à l’envers :
On remplace les 9 par des 0 et on incrèmente le chiffre du bout.

fonction Inc(n : Tnaturel) : Tnaturel ;
debut
  si EgalZero(n) alors
    n.fin  n.debut ;
    n.tab[n.fin]  1 ;
  sinon
    p  n.debut ;
    tant que (n.tab[p] = Base-1) et (p <= n.fin)
    faire
      n.tab[p]  0 ;
      p  p + 1 ;
    fin tant que
    si p>n.fin alors
      n.fin  p ;
      n.tab[n.fin]=1 ;
    sinon n.tab[p]  n.tab[p] + 1 ;
    fin si ;

  fin si
  retourne n ;
fin ;

Voilà de la récursivité plutôt inutile et inefficace c’est vrai, mais bon... on ne se refuse pas un petit plaisir...

fonction Add(n1,n2 : Tnaturel) : Tnaturel ;

debut
{Cas de base : n1=0 ou n2=0}
  si EgalZero(n1) alors
    retourne (n2)
  sinon si EgalZero(n2) alors retourne n1
        sinon

        {Appel récursif, qui s’efforce de }
        {converger vers le cas de base    }

          retourne Inc(Add(n1,Dec(n2)))
        fin si;
  fin si
fin

Commentaires :

C’est bien parce que
=> C’est plus rapide à écrire (seulement 5 lignes de code contre une vingtaine pour la version itérative)

Mais en fait c’est complétement débile parce que
=>La récursivité est intrinsèquement lourde (gestion de la pile, etc...)
=>La taille de n1 et n2 est limitée par celle de la pile (d’autant qu’on fait des passages par valeur). Et c’est d’autant plus bête qu’on compte faire des ops sur les grands nombres...

b)	La soustraction

i)	Ecrire une fonction Sub(n1,n2 : Tnaturel) : Tnaturel itérative.

Solution :

Comme en primaire...

fonction Sub(n1,n2 : Tnaturel) : Tnaturel ;
var petit,grand : Tnaturel ;
    i,s,retenue,decalage : entier ;
debut
  si Sup(n2,n1) alors Erreur()
  sinon
    grand  n2
    petit  n1

    decalage  grand.debut-petit.debut
    retenue  0 ;

    {On sub la partie “ petit ”}

    pour i de petit.debut à petit.fin faire
      s  petit.tab[i]-(grand.tab[i+decalage]
          + retenue) ;
      si s < 0 alors
        retenue  1 ;
        s  s + Base ;
      sinon
        retenue  0 ;
      fin si
      grand.tab[i+decalage]  s ;
    fin pour

    {On sub le reste}

    pour i de grand.debut+Long(petit) à 
              grand.fin
    faire
      s  grand.tab[i]-retenue ;
      si s < 0 alors
        retenue  1 ;
        s  s + Base ;
      sinon retenue  0 ;
      fin si
      grand.tab[i]  s ;
    fin pour
  fin si
  retourne grand ;
fin ;

ii)	Déduire de a) ii) une version récursive de cette fonction. Commenter son efficacité.

Solution :

fonction Sub(n1,n2 : Tnaturel) : Tnaturel ;

debut
{Cas de base : n1=n2 ou n1<n2}
  si Sup(n2,n1) alors Erreur()
  sinon
    si Egal(n1,n2) alors
      retourne zero
    sinon

      {Appel récursif                   }
      {On remarque que :                }
      {n1-n2=n1-(n2+1)+1                }
      {et çà converge vers le cas de base}

      retourne Inc(Sub(n1,Inc(n2)))
    fin si;
  fin si
fin

Memes commentaires que pour Add : c’est joli, mais c’est inefficace et dangereux.

c)	La multiplication

i)	Ecrire une version itérative de la fonction Mul (n1,n2 : Tnaturel) : Tnaturel qui renvoie n1*n2.

Solution :

Mieux vaut modulariser ! On commence par créer une fonction qui multiplie un naturel par un chiffre.

Fonction Mul_chiffre(n : Tnaturel ; c : Tchiffre) : Tnaturel ;
var retenue,m : entier ;
debut
  si n.fin=N alors Erreur()
  sinon
    retenue  0 ;
    pour i de n.debut à n.fin faire
      m  n.tab[i]*c + retenue;
      retenue  m div base ;
      n.tab[i]  m mod Base ;
    fin pour ;
  fin si
  retourner n ;
fin

et une fonction de décalage

fonction MulBase(n : Tnaturel ; p : entier) : Tnaturel ;
{Renvoie n*Basep}
debut
  si p+n.fin>N alors Erreur() ; fin si ;

  si p <> 0 alors
    pour i de n.fin à n.debut faire
      n.tab[i+p]  n.tab[i] ;
    fin pour ;
    n.fin  n.fin-p ;
    n.debut  n.debut-p ;
  fin si
  retourner n ;
fin

D’où on tire :

fonction Mul(n1,n2 : Tnaturel) : Tnaturel ;
var inter : Tnaturel ;
debut
  inter  Naturel(0) ;
  si EgalZero(n1) ou EgalZero(n2) alors
    retourne inter ;
  fin si

  pour i de n2.debut à n2.fin faire
    inter  Add(inter,MulBase(Mul_chiffre(n1,n2.tab[i]),i-n2.debut)) ;
  fin pour
  retourner inter ;
fin

ii)	En écrire une version récursive qui fait intervenir Add. Laquelle de ces 2 fonctions est la plus efficace ? la plus simple à écrire ? Conclure sur l’intérêt de la récursivité.

Solution :

fonction Mul(n1,n2 : Tnaturel) : Tnaturel ;
debut
  si EgalZero(n1) ou EgalZero(n2) 
  alors retourne zero ;
  sinon si EgalUn(n2) alors retourne n1
        sinon retourne Add(n1,mul(n1,Dec(n2)))
        fin si
  fin si
fin

La plus simple : itérative, c’est évident ;-).

Si on a le temps, on pourra évoquer brièvement la méthode de Karatsuba. Son principe est simple : on coupe n1 et n2 en deux, mettons n1=AB et n2=CD. Alors :n1.n2=a1AC+a2AD+a3BC+a4BD
et on applique récursivement l’algo à AC, AD,...
On voit que de proche en proche, il se ramène à de bêtes multiplications entre chiffres.
C’est assez marrant à voir, enfin c’est mon point de vue.

d)	Ecrire une fonction Divi (n1,n2 : Tnaturel) : Tnaturel qui renvoie le quotient dans la division euclidienne de n1 par n2. Cette fonction sera récursive. De même, écrire une version récursive de la fonction Modulo (n1,n2 : Tnaturel) : Tnaturel qui renvoie le reste de la division euclidienne de n1 par n2.

Solution :

fonction Divi(n1,n2 : Tnaturel) : Tnaturel ;

debut
  si Sup(n2,n1) alors retourne zero

  {Remarquons que a/b = 1+(a-b)/b}

  sinon retourne Inc(Divi(Sub(n1,n2),n2))
  fin si ;
fin

fonction Modulo(n1,n2 : Tnaturel) : Tnaturel ;
debut
  si Sup(n2,n1) alors retourne n1
  sinon retourne Modulo(Sub(n1,n2),n2) ;
  fin si
fin

3.	factorielle, puissance

a)	Ecrire une version récursive de fact(n : Tnaturel) : Tnaturel qui renvoie n!. En écrire une version itérative.

Solution :

fonction Fact_rec(n : Tnaturel) : Tnaturel ;
debut
  si EgalZero(n) alors retourne Naturel(1)
  sinon retourne Mul(n,Fact_rec(Dec(n))) ;
  fin si ;
fin ;

fonction Fact_it(n : Tnaturel) : Tnaturel ;
var f,compteur : Tnaturel ;
debut
  f  Naturel(1) ;
  compteur  zero ;
  Tant que pas (Egal(compteur,Naturel(n))) faire
    compteur  Inc(compteur) ;
    f  Mul(f,compteur) ;
  fin TantQue
  retourner f ;
fin

Ici, il faut créer sa boucle POUR soit même. C’est la seule difficulté de cette question.

b)	Ecrire une version itérative de puissance (n,p : Tnaturel) : Tnaturel qui renvoie np. En écrire une version récursive. Comment modifier cette dernière version pour limiter le nombre d’appels récursifs ?
Indication : remarquer que si p=2k, np = n2k = nk*nk, et si p=2k+1, np = n2k+1 = nk*nk*n.

Solution :

fonction Puissance_it(n,p : Tnaturel) : Tnaturel ;
 var f,compteur : Tnaturel ;
debut
  compteur  zero ;
  f  naturel(1) ;
  Tant que pas (Egal(compteur,p))) faire
    compteur  Inc(compteur) ;
    f  Mul(f,n) ;
  fin TantQue
  retourner f ;
fin

fonction Puissance_rec(n,p : Tnaturel) : Tnaturel ;
debut
  si Egal(p,Zero) alors retourne Naturel(1)
  sinon retourne Mul(n,Puissance(n,Dec(p))) ;
  fin si ;
fin ;

fonction Puissance_rec_dich(n,p : Tnaturel) : Tnaturel ;
debut
  si Egal(p,Zero) alors retourne Naturel(1)
  sinon 
    si Egal(Modulo(p,2),zero) alors
      k  Divi(p,2) ;
      nk  Puissance_rec_dich(n,k) ;
      retourne Mul(nk,nk) ;
    sinon
      k  Divi(p,2) ;
      nk  Puissance_rec_dich(n,k) ;
      retourne Mul(n,Mul(nk,nk)) ;
    fin si ;
  fin si
fin

Remarque : Ces 2 derniers algos diffèrent par leur nombre d’appels récursifs. Pour Puissance_rec(n,p), il est de l’ordre de p, alors que pour Puissance_rec_dich(n,p), il est de l’ordre de ln p. Cette dernière methode, plus rapide, est appelée exponentation dichotomique.

c)	Dérouler les 2 versions récursives de puissance avec n=2 et p=8. Que remarque on ?

cf remarque précédente : 8 appels rec pour le 1er, contre 3 pour le 2ème.

4.	Les entiers relatifs

On code les entiers relatifs de la façon suivante :

type Tsigne = (plus,moins) ;
type Trelatif = enregistrement
                  signe : Tsigne ;
                  va : Tnaturel ; {pour valeur absolue}
                fin enregistrement

Ecrire une fonction Relatif(z : entier) : Trelatif, qui renvoie le relatif correspondant à z. Réécrire les fonctions Add, Sub, Mul, Divi, et Modulo Sur Trelatif. On réutilisera les fonctions précédentes.

Solution :

fonction Relatif (n : entier) : Trelatif ;
var z : Trelatif ;
debut
  si n<0 alors z.signe  moins
  sinon z.signe  plus
  fin si ;
  z.va  Naturel(|n|) ;
  retourner z
fin ;

fonction Add(z1,z2 : Trelatif) : Trelatif ;
var inter : Trelatif ;
debut
  si z1.signe=plus alors
    si z2.signe = plus alors 
      inter.va  Add(z1.va,z2.va) ;
      inter.signe  plus ;
    sinon
      si Sup(z2.va,z1.va) alors 
        inter.va  Sub(z2.va,z1.va) ;
        inter.signe  moins ;
      sinon
        inter.va  Sub(z1.va,z2.va) ;
        inter.signe  plus
      fin si
    fin si
  sinon
    si z2.signe=plus alors
      si Sup(z1.va,z2.va) alors
        inter.va  Sub(z1.va,z2.va) ;
        inter.signe  moins ;
      sinon
        inter.va  Sub(z2.va,z1.va) ;
        inter.signe  plus ;
      fin si
    sinon
      inter.va  Add(z1.va,z2.va) ;
      inter.signe  moins ;
    fin si
  fin si ;
fin

fonction oppose(s : Tsigne) :Tsigne ;
debut
  si s=plus alors retourne moins sinon retourne plus ;
  fin si
fin

fonction Sub(z1,z2 : Trelatif) ;
debut
  z2.signe=oppose(z2.signe) ;
  retourne Add(z1,z2) ;
fin ;

Pour la multiplication, on se défini une fonction 

fonction signe(s1,s2 : Tsigne) : Tsigne ;
{qui renvoie le signe de s1.s2}
debut
  si s1=plus alors retourne s2
  sinon retourne oppose(s2) ;
fin ;

Fonction Mul(z1,z2 : Trelatif) : Trelatif ;
debut
  z.signe  signe(z1.signe,z2.signe) ;
  z.va  Mul(z1.va,z2.va) ;
  retourner z ;
fin

Fonction Divi(z1,z2: Trelatif) : Trelatif ;
debut
  z.signe  signe(z1.signe,z2.signe) ;
  z.va  Divi(z1.va,z2.va) ;
  retourner z ;
fin

fonction Modulo(z1,z2 : Trelatif) : Trelatif ;
debut 
  retourne Modulo(z1.va,z2.va) ;
fin ;

Si on à le temps, on pourra aborder la question des rationnels.

5.	Les rationnels

Les rationnels seront codés de la façon suivante :

type Trationnel = enregistrement
                    a,b : Trelatif ; {pour a/b}
                  fin enregistrement

a)	Ecrire une fonction Rationnel (a,b : entier) : Trationnel, en utilisant la fonction du 4.

Solution :
fonction Rationnel(a,b : entier) : Trationnel ;
var r : Trationnel ;
debut
  r.a  Relatif(a) ;
  r.b  Relatif(b) ;
  retourner r ;
fin ;

b)	Ecrire une fonction pgcd (a,b : Trelatif) : Trelatif, en déduire une fonction 
Simplifier (r : Trationnel) : Trationnel, qui ecrit r=a/b, avec a et b minimaux.

Solution :

On applique l’algo d’Euclide

fonction pgcd (a,b : Trelatif) : Trelatif ;
var r,s : Trelatif ;
debut
  r  a ;
  s  b ;
  tant que pas(EgalZero(s)) faire
    rp  r;
    r  s;
    s  Modulo(rp,s)
  fin tant que
  retourner r;
fin;

fonction Simplifier(r : Trationnel) : Trationnel ;
var p : Trelatif ;
debut
  p  pgcd(r.a,r.b) ;
  r.a  Divi(r.a,p) ;
  r.b  Divi(r.b,p) ;
  retourner r ;
fin

c)	En utilisant b) et 4., Ecrire les fonctions d’addition, soustraction, multiplication et division sur les rationnels.

Solution :

fonction Add(r1,r2 : Trationnel) : Trationnel ;
 var r : Trationnel ;
debut
  r.a  Add(mul(r1.a,r2.b),mul(r2.a,r1.b)) ;
  r.b  Mul(r1.b,r2.b) ;
  retourner Simplifier(r) ;
fin

fonction Sub(r1,r2 : Trationnel) : Trationnel ;
var r : Trationnel ;
 debut
  r.a  Sub(mul(r1.a,r2.b),mul(r2.a,r1.b)) ;
  r.b  Mul(r1.b,r2.b) ;
  retourner Simplifier(r) ;
fin

fonction Mul(r1,r2 : Trationnel) : Trationnel ;
var r : Trationnel ;
debut
  r.a  Mul(r1.a,r2.a) ;
  r.b  Mul(r1.b,r2.b) ;
  retourner Simplifier(r) ;
fin

fonction Divi(r1,r2 : Trationnel) : Trationnel ;
var r : Trationnel ;
debut
  r.a  Mul(r1.a,r2.b) ;
  r.b  Mul(r1.b,r2.a) ;
  retourner Simplifier(r) ;
fin

d)	On souhaite avoir un début d’écriture décimale d’un rationnel.

i)	Montrer que a/b = a div b + (a mod b)/b. Conséquence sur l’écriture décimale ?

Solution :

Ecrivons a = b(a div b) + a mod b.
alors a/b=le resultat.

Moralité : a div b=partie entiere et a mod b = partie flottante de l’écriture “ décimale ” (enfin en base Base).

En déduire une procédure PartieEntière(r :Trationnel) qui affiche la partie entière de a/b ie a div b.

Solution :

procedure PartieEntiere(r : Trationnel) ;
var n : Trelatif ;
debut
  n  Divi(r.a,r.b) ;
  si n.signe=moins alors write (‘-‘) ;
  fin si
  pour i de n.va.fin à n.va.debut faire
    write (n.va.tab[i]) ;
  fin pour ;
fin

=> pbs d’affichage pour Base>10

ii)	On s’intéresse à la partie flottante (ie (a mod b)/b). On la note p/q
Montrer que son premier chiffre est [p*Base] div q.

Solution :

  puisque a mod b < b, a mod b/b s’écrit
  0.a0a1a2a3..., en le multipliant par Base, on le décale d’un cran :
Base*(a m b/b) = a0.a1a2a3... et le quotient dans la division euclidienne est alors :a0.

En déduire un algorithme itératif qui affiche ses n premiers chiffres

Solution :

procedure PartieFlottante(r:Trationnel ;p:ntier)
{p=précision}
var chiffre1 : entier ;
debut
  r.a  Modulo(r.a,r.b) ;
  pour i de 1 à p faire
    r.a.va  MulBase(r.a.va,1) ;
    chiffre1  Divi(r.a,r.b) ;
    write (chiffre1) ;
    r  Sub(r,Rationnel(Relatif(chiffre1),Relatif(1))) ;
    
  fin pour ;
fin ;

iii)	Déduire de i) et ii) une procédure Afficher (r : Trationnel ; precision :entier) qui affiche l’écriture décimale de r avec precision chiffres après la virgule.

Solution : 

procedure Afficher(r : Trationnel ; precision : entier) ;
debut
  PartieEntiere(r) ;
  write(‘.’) ;
  PartieFlottante(r,precision) ;
fin ;

6.	Une application

On défini la suite u par un = 1/(0!) + 1/(1!) + 1/(2!) + 1/(3!) + ... + 1/(n!), où n est un entier naturel. On montre que u converge vers e.

a)	Ecrire une fonction terme(n : Tnaturel) : Trationnel, qui renvoie 1/(n!).

Solution :

fonction terme(n : Tnaturel) : Trationnel ;
var r : Trationnel ;
debut
  r.a  Relatif(1) ;
  r.b.va  fact(n) ;
  r.b.signe  plus ;
  retourne r ;
fin

b)	Ecrire une fonction U(n : Tnaturel) : Trationnel, qui renvoie un.

Solution :

fonction U(n : Tnaturel) : Trationnel ;
var compteur,s : Tnaturel ;
debut
  compteur  naturel(0) ;
  s  naturel(0) ;
  tant que pas (Egal(compteur,n)) faire
    compteur  Inc(compteur) ;
    s  Add(s,terme(compteur)) ;
  fin tant que ;
  retourne s ;
fin ;

c)	En utilisant 5. d) iii), ecrire une procédure E(n : Tnaturel) qui affiche l’écriture décimale du nième terme de u.

Solution :

procedure E(n : Tnaturel) ;
debut
  Afficher(U(n)) ;
fin ;

Conclusion : Tout çà donne un ensemble assez lent et inefficace. Pour faire un programme plus puissant, il faudrait travailler avec des structures “ non figées ” comme les listes chainées, qui seront vues plus tard ; et modifier la représentation des entiers