Répéter une chaîne

Exercice · OCaml (option informatique), chapitre 6 — Caractères et chaînes de caractères

É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;
  !r

On 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 <em> |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.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.