Discussion :

[Nirolac]

Bonjour à tous,

En cours on nous a donné un algorithme dont on doit faire la preuve (une preuve par induction), or je ne sais pas par où commencer car dans les différents exemples que l'on a eu en cours, ça n'a toujours été que sur une seule variable, or dans ce programme (qui développe le nombre a dans la base b, a et b étant des entiers supérieur ou égal à 0). Voici le programme :

Dev(a, b) :

si (a < b)

renvoie a

sinon

afficher (a modulo b)

renvoie Dev(a/b, b)

Fin Dev

Je ne demande pas la solution mais qu'on m'aide, c'est-à-dire comment trouver la base de la récurrence pour pouvoir commencer s'il vous plaît, je pense que la base doit commencer par a = 0 si c'est le cas quelle est la valeur de b s'il vous plaît ?

je vous remercie d'avance et vous souhaite une bonne journée !

[anapurna]

il manque quelque définition
"a" c'est quoi un entier naturel positif ou autre chose
"b" c'est quoi ? (Idem A)

DEBUT Dev(a, b) :
SI b <> 0 ALORS // évite les division par zero
SI (a < b) ALORS // ici tu as a < b
renvoie a
SINON
afficher (a modulo b)
renvoie Dev(a/b, b) // Ici tu vois la récurrence "a" devient "a/b" si b=1 que fait ton programme ?
FIN SI
FIN SI
FIN Dev

[Nirolac]

Bonsoir Anapurna,
A est supérieur à 0
B strictement supérieur à 1
Je pense en tout cas que c'est cela car vous avez marqué que se passe t'il si b=1, eh bien ça ne s'arrêterait pas donc comme base on à A = 0 et B = 2 ? Est ce bien cela (car je ne suis vraiment pas sûr )?
Bonne soirée

[anapurna]

salut,

regarde bien la première condition il faut absolument que a soit supérieur a b pour que la boucle continu
si a < b on arrête la boucle et on affiche a donc la condition de rupture est .... a < b
si b est inférieur a 1 on multiplie
exemple a=3 b = 0.5 la prochaine boucle seras 3/1/2 = 3*2 = 6
donc effectivement b doit être strictement supérieur a 1 sinon on se retrouve avec des boucle infini
et faut que a > b donc a > 1 aussi

[wiwaxia]

Bonjour,

Il s'agit apparemment d'un programme récursif visant le développement d'un entier en base (b): ce terme ne peut donc être inférieur à 2.

Pour décrire correctement ce qui se passe, il faut absolument discerner les valeurs successives de la variable (a), qui n'est en soi qu'une mémoire dont le contenu change à chaque étape.

Regardons par exemple le développement d'un entier en base (10), soit a = 1843 . On aura schématiquement:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
a0 = 1843 ---- a1 = a0 DIV b = 0184 ---- a2 = a1 DIV b = 0018 ---- a3 = a2 DIV b = 0001 ---- a4 = a3 DIV b = 0000
 |              |                         |                         |                         |
 |              |                         |                         |                         |
a0 MOD b = 3   a1 MOD b = 4              a2 MOD b = 8              a3 MOD b = 1              a4 MOD b = 0

La fonction récursive Dev(a, b) réitère la division entière de (a) par (b) jusqu'à ce que l'on obtienne la condition d'arrêt (a<b) - cas précédent l'apparition définitive de termes nuls, donc la fin du développement du nombre initial (a₀) dans la base considérée.
On récupère donc successivement: 3 , 4 , 8 , 1 par l'instruction afficher (a modulo b).

Je ne vois pas très bien en quoi consiste la preuve d'un programme, si ce n'est vérifier dans le détail la tâche accomplie; les remarques précédentes devraient te permettre de mettre en forme la réponse demandée.

[lulzec]

Bonjour,
Pour prouver la correction d'un algorithme récursif, le plus simple est de faire une preuve par induction.
En gros:

• Tu testes d'abord la condition de fin de boucle, c'est-à-dire, si a < b alors tu affiches simplement a qui est la représentation de a dans la base b, évidemment
• Maintenant, soit a > b. On suppose le résultat vrai pour tout k tel que 0 <= k <= a-1, c'est-à-dire que dev(k,b) renvoie l'écriture de k dans la base b.
  Dans ce cas, comme a > b, alors on affiche a % b puis comme a / b < a on affiche a / b dans la base b.
  Voilà la structure, il te reste à rédiger la fin, et bien rédiger le début que j'ai écrit vraiment à l'arrache

[Nirolac]

Bonjour à tous et désolé de ne répondre que maintenant mais j'ai eu des soucis qui ont fait qu je ne pouvais étudier ... Enfin bref, d'abord merci à tous pour vos réponses, Lulzec oui c'est d'ailleurs ce que l'on fait en cours, donc ici ma condition d'arrêt c'est effectivement a < b, cependant je ne comprends pas pourquoi tu écris "puisque a/b < a alors on affiche a/b dans la base b" sinon je pense avoir pigé le truc manque plus que de m'entraîner un peu je pense
Bonne journée et merci d'avance

[lulzec]

En fait, quand tu es dans le cas a > b, alors tu passes par le "else" de la condition. Tu affiches donc d'abord a mod b.
Une fois ça fait, tu fait un appel à Dev(a/b, b). Comme b > 1, alors a/b < a. Tu peux donc appliquer ton hypothèse de récurrence, qui ici est: "Dev(a/b,b) affiche la décomposition du nombre a/b dans la base b."
Avec un peu de maths, si on écrit a dans la base b on a:

Ainsi

et

En gros tu affiches d'abord a_0, et ensuite grace à ton hypothèse de récurrence tu dis que tu affiches a_1, a_2, ..., a_n.
Tu affiches donc bien tous les chiffres de a dans la base b (à l'envers néanmoins)

[Nirolac]

D'accord j'ai compris merci beaucoup !
Je vais faire des exos sur ça (je suppose que y a pas de miracle)
Bonne journée à toi Lulzec et aux autres qui m'ont aidé