Discussion :

[Invité]

Bonjour,
Sur ce code qui détecte si un item est un palindrome ou non:

Code :

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

1
2
3
4
5
6
# let rec palindrome(s) = 
    let lenItem = String.length(s) in 
        if lenItem <= 1 then true else 
        if s.[0] = s.[lenItem - 1]
        then palindrome(String.sub(s)(1)(lenItem - 2)) 
        else false;;

si je trace palindrome sur:

Code :

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

# palindrome("sages");;

ça donne:

Code :

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

1
2
3
4
5
palindrome <-- "sages"
palindrome <-- "age"
palindrome --> false
palindrome --> false
- : bool = false

Je ne comprends pas pourquoi le premier retour est faux.

Code :

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

1
2
3
4
...
if s.[0] = s.[lenItem - 1]
then palindrome(String.sub(s)(1)(lenItem - 2))
...

"s" et bien égal à "s" on peut donc passer à la sous chaîne suivante et comparer "a" et "g" qui pour le coup ne sont pas égaux.
Pour un résultat identique j'ai une variante avec cette fois des opérateurs booléens:

Code :

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

1
2
3
4
5
# let rec palindrome(s) =
    let lenItem = String.length(s) in
        (lenItem <= 1) ||
        (s.[0] = s.[lenItem -1]) &&
        (palindrome(String.sub(s)(1)(lenItem -2)));;

Et j'avoue que:

Code :

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

1
2
3
4
...
(s.[0] = s.[lenItem -1]) &&
(palindrome(String.sub(s)(1)(lenItem -2)));;
...

qui code que les deux expressions sont vraies simultanément me laisse plus que dubitative...

[SpiceGuid]

Je ne comprends pas bien ce qui te fait douter, toutes tes propositions sont correctes (même si ce n'est pas tout à fait ce qu'écrirait un expert).

palindrome "sages" retourne faux parce que palindrome "age" retourne faux.

Je pense qu'un expert aurait écrit quelque chose comme ceci :

Code OCaml :

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

1
2
3
4
5
let rec palindrome s low high =
  low >= high || (s.[low] = s.[high] && palindrome s (low+1) (high-1))
 
let palindrome s =
  palindrome s 0 (String.length s - 1);;

[Invité]

palindrome "sages" retourne faux parce que palindrome "age" retourne faux.

Évidemment,... je crois que mes neurones ont du mal à boucler dans la recursivité...
En tous cas merci pour ton salutaire déclic.

Je pense qu'un expert aurait écrit quelque chose comme ceci :

Code OCaml :

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

1
2
3
4
5
let rec palindrome s low high =
  low >= high || (s.[low] = s.[high] && palindrome s (low+1) (high-1))
 
let palindrome s =
  palindrome s 0 (String.length s - 1);;

J'aime bien, surtout low et high,... très classe.
Je te les pique:

Code OCaml :

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

1
2
3
4
# let palindrome(s) = 
        let rec build(low)(high) = 
            low >= high || (s.[low] = s.[high] && build(low + 1)(high - 1)) in
        build(0)(String.length(s) -1);;