Algo arbres: prefix/suffix

Questions / réponses

prefix/suffix

Bonjour, j'ai écris la fonction prefix, puis la fonction suffix en utilisant une fonction miror
Je ne comprends pas où sont mes erreurs, j'ai testé les cas suivants sur machine (au cremi):

prefix [1;2;3;4;5] 2
prefix [1;2;3;4;5] 6
prefix [] 1
prefix [1] (-1)
suffix [1;2;3;4;5] 2
suffix [1;2;3;4;5] 6
suffix [] 1
suffix [1] (-1)

et des cas avec des listes de listes

Re: prefix/suffix

par Marc Zeitoun, jeudi 8 février 2018, 15:26

Comme c'est indiqué en rouge juste avant l'exercice et comme je l'ai rappelé en cours, il faut se référer aux feuilles d'exercices déposées sous Moodle.

Les fonctions demandées dans cet exercice ne doivent pas utiliser failwith si l'entier n est plus grand que la longueur de la liste, mais simplement retourner la liste elle-même.

Re: prefix/suffix

par Imane Abed, jeudi 8 février 2018, 16:35

Merci,

J'ai modifié ma fonction, elle fonctionne sur emacs, mais toujours pas sur moodle...

Re: prefix/suffix

par Marc Zeitoun, jeudi 8 février 2018, 18:52

Le code est correct mais inefficace. La complexité de la fonction mirror est quadratique et ça ne termine pas assez rapidement.

Le problème est l'utilisation de l'opérateur @ de concaténation de listes : l1 @ l2 a une complexité en O(taille de l1). Si cela est répété sur des listes l1 de tailles (n-1), (n-2), ..., 1, comme dans le code, cela donne une complexité en O(n²).