Preuve de programme

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 !

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

Citation:

---

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

---

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

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

Bonjour, :D

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:

---

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.

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

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 :D
Bonne journée et merci d'avance

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)

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é