OCaml (option informatique) · Chapitre 6 · Exercice de TD
Répéter une chaîne
Caractères et chaînes de caractères · niveau 3 (difficile)
Énoncé
Écrire repete s n qui renvoie s concaténée n fois (repete "ab" 3 "ababab"). Discuter le coût.
Corrigé
let repete s n =
let r = ref "" in
for _i = 1 to n do
r := !r ^ s
done;
!rOn part de la chaîne vide "" et on concatène s à chaque tour. Coût : à l'étape k, l'accumulateur a déjà longueur k * |s| et est recopié — le total est quadratique en n. Pour de grandes valeurs, un tampon (Buffer, hors programme) ramènerait au linéaire ; ici la version simple suffit.
Exercices semblables
- Somme des chiffres d'une chaîne corrigé
- Ordre lexicographique corrigé
- Conversions corrigé
- Compter les mots corrigé
- Recherche d'un motif corrigé