Discussion :

[Tonio12]

Bonjour,
voilà j'ai un gros problème quand il s'agit d'interpréter le but d'un programme et je dois préparer un concours.
Si quelqu'un est en mesure de m'aider qu'il me fasse signe je laisserais mon adresse email.
Je vous laisse un exemple avec lequel je n'arrive pas à me débattre:

FONCTION g(n:entier, p:entier, q:entier) RESULTAT val: entier
DEBUT
SI n<p ALORS val <- q
SINON val <- g(n-p,p,q+1)
FIN SI
FIN

Par avance merci de vos réponses.

[Jean-Marc.Bourguet]

Essaie d'appliquer cet algorithme sur un exemple. Je te suggere d'utiliser 0 comme troisieme argument.

[Rakken]

Ce programme est un programme récursif. Ce qu'il faut d'abord, c'est comprendre les opérateurs :
val <- q signifie qu'on mets la valeur de "q" dans "val".
g(n-p,p,q+1) signifie qu'on rappele le programme avec les arguments "n-p", "p" et "q+1".

Sachant cela, il faut prendre des valeurs pour chacun des arguments de la fonction et voir ce que cela fait.
Je te conseille d'écrire a chaque étape, la valeur de chacune des variables. Et lorsque tu arrives au dernier "FIN", tu regarde la valeur de "val", et c'est que que le programme est cencé retourner.

Commence effectivement avec "0" comme valeur pour "q". Cette variable défini la "profondeur" de la récursivité. Donc quand tu commence, q est cencé valoir 0 (la récursivité n'a pas encore commencé).

--
Rakken

[millie]

On t'as déjà dit que q représente le nombre de fois que tu appelles la fonction.

La condition d'arrêt étant n<p, il semble assez logique de tester avec des valeurs de p>=n. Tu peux constater que dans les arguments, le deuxième ne change jamais (c'est p), et le premier ne fait que décrementer n de p à chaque fois.

Si tu faisais tourner l'algorithme, tu trouverais vite...

Par exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
(*source camL*)
 
let rec g(n,p,q)=
 if n<p then q else g(n-p,p,q+1);;
#g : int * int * int -> int = <fun>
 
g(14,1,0);;
#- : int = 14
g(14,7,0);;
#- : int = 2

[reggae]

Partons du principe que l'on a deux nombres représentés dans le programme par n et p.
Alors

Code :

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

1
2
3
 
n>p
n/p = q          x>0

Pour obtenir n<=p, on doit faire

Code :

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

1
2
 
n-q*p

Donc on cherche à obtenir la division entière de n par p...
D'où l'exemple cité par Millie:

g(14,7,0);;
#- : int = 2

14 est un multiple de 2, donc q sera un entier:

Code :

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

1
2
 
q=n/p=14/2=7

Au contraire, si

Code :

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

1
2
 
p>n

alors q ne sera pas un entier mais un réel, d'où la vérification

Code :

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

1
2
 
SI n<p ALORS val <- q

[Tonio12]

Bonsoir,
je dois dire que j'ai été étonné de vos réponses, et je vous en remercie.
Je vais essayer avec ça.
Merci beaucoup et bonne année à tous.
Tonio

P.S: j'aurais surement d'autres questions