Discussion :

[magodeoz]

Bonjour à tous,
Pourriez-vous m'aider à programmer la fonction suivante (en OCaml):

Fonction d'Ackermann de m et n avec 0≤m,n définie par les équations récursives suivantes:
A(0,n)=n+1
A(m+1,0)=A(m,1)
A(m+1,n+1)=A(m,A(m+1,n))

profil: (int*int)-> int

Je pensais m'en sortir avec des "if" en faisant:
let rec Ackermann (m,n)(int*int):int=
if m=0 then n+1
if n=1 then m-1
La récursivité m'aurait servie pour la dernière equation mais au final je bloque...J'imagine qu'il serait plus judicieux de faire un "match" mais je n'arrive pas à m'en sortir.
D'avance merci de votre aide.
Cordialement,
Mägodeoz

[gasche]

Non, l'approche avec des if..then..else est très bien -- les débutants se trompent souvent avec le filtrage donc il vaut mieux ne pas en abuser, et s'en servir uniquement sur les structures de données (listes, arbres...).

Par contre pour obtenir un programme il vaut mieux définir A(m,n) directement au lieu de A(m+1,n+1):

A(0,n)=n+1
A(m,0)=A(m-1,1)
A(m,n)=A(m-1,A(m,n-1))

Avec cette définition tu devrais pouvoir écrire facilement un programme caml.

[magodeoz]

Merci de ta réponse gasche :-)
Donc je reprends....

Code :

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

1
2
3
4
let rec Ackermann (m,n)(int*int):int=
if m=0 then n+1
else if n=0 then Ackermann (m-1,1)
else Ackermann (m-1,Ackermann (m,n-1)) ;;

C'est correct ou pas...?
Simple curiosité... En matchant ça aurait donné quoi?

[gasche]

Il y a de petis détails syntaxiques qui clochent : je préfère les noms de variable en minuscule et "let f (m,n)(int*int):int = ..." n'est pas correct, il faudrait écrire "let f (m, n) = ..." ou bien "let f ((m, n) : int * int) : int = ...".

Pourquoi n'essaies-tu pas de tester ce programme sur de petites entrées pour te convaincre ? Ce n'est pas à nous de te dire si le code est juste, il faut que tu le vérifies toi-même.

[Ptival]

magodeoz : Pour répondre à la question "C'est correct ou pas...?", la bonne idée de ta part serait de compiler et d'essayer. Certes, ça ne répondra que négativement à ta question, mais c'est déjà une demi-réponse.

En l'occurence, si comme tu le prétends c'est du OCaml, alors non, ce n'est pas correct, pour plusieurs raisons :

- le nom d'une fonction doit commencer par une minuscule. (Ackermann -> ackermann)
- pour préciser le type d'une paire, tu dois écrire ((m, n): int * int)

Ci-dessous une version avec un match sous une forme spéciale, je te laisse corriger ta version (ne recopie pas celle ci-dessous, écris une version qui fonctionne avec des "if then else" ou avec un "match m, n", et corrige tes annotations de type).

Code :

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

1
2
3
4
5
 
let rec ackermann = function
  | 0, n -> n + 1
  | m, 0 -> ackermann (m - 1, 1)
  | m, n -> ackermann (m - 1, ackermann (m, n - 1))

Tu peux tester avec quelques valeurs comme (0, 0), (1, 1), pour te faire une idée de si ton code marche.

Ensuite, tu peux tester avec des valeurs un peu plus ambitieuses, ce qui devrait t'amener vers un nouveau problème.

[Cacophrene]

Bonjour,

C'est cool aussi si tu penses à utiliser les balises CODE pour rendre la lecture plus agréable.

Encore une autre version de la fonction d'Ackermann, mais en remplaçant les couples (n, m) par deux arguments distincts.

J'aime beaucoup le résultat ackermann 12 0

Code :

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

1
2
3
4
5
6
let rec ackermann = function
  | 0 -> (+) 1
  | m -> (function 
    | 0 -> ackermann (m - 1) 1 
    | n -> ackermann (m - 1) (ackermann m (n - 1)))

Cordialement,
Cacophrène

[magodeoz]

Merci à tous de vos réponses :-) je ne pouvais pas le tester car je suis sous windows...
Je vais mettre ubuntu sur un disque dur externe et là je pourrais tester
En effet, je penserais à la balise CODE la prochaine fois ^^

[prgasp77]

Et bien Cacophrene ? Pourquoi écrire (+) 1 quand on peut écrire succ ?

[Cacophrene]

Bonsoir,

Et bien Cacophrene ? Pourquoi écrire (+) 1 quand on peut écrire succ ?

Pour voir qui suit dans l'assemblée.

Cordialement,
Cacophrène