corrigé du QCM 2008

Bonjour,

Dans les archives du site, le corrigé du QCM édition 2008 n'est pas le bon. le PDF attaché correspond au corrigé de l'édition 2007.

y'a-t'il moyen de récupérer le bon corrigé ?
je suis intéressé par la solution de l'exo 4 "Mots mêlès".

merci d'avance pour votre aide.

Bon, je n'y ai pas trop réfléchi mais ça fera peut-être une solution temporaire :

Solution naïve :
Pour chaque mot, on regarde s'il est dans la grille.
Donc pour toutes les cases, on regarde dans les 4 directions si on a notre mot (en réalité il est inutile de lire à l'envers en haut et à gauche puisque ça a déjà été lu à l'endroit).
Cette solution est en O(N * M * P * longueurMotMax).
On pourrait penser que la longueur du mot n'intervient pas puisqu'on peut vérifier rapidement qu'un mot est différent d'un autre mais c'est faux, exemple :
On choisit le mot a...a (500 fois).
On choisit la grille 500 * 500 :
a...ab
.
.
.
a...ab
b...bb
Le mot sera cherché de nombreuses fois sans être trouvé. Il suffit ensuite d'ajouter des mots tels que : a...abb de longueur 500 pour se retrouver proche du pire cas.

Solution naïve améliorée :

Déjà, il est inutile de chercher un mot dans une direction si on n'a pas la longueur suffisante.
C'est-à-dire qu'on ne va pas chercher par exemple un mot de longueur l dans une grille l * l en partant d'ailleurs que des extrêmités de la grille.

Il reste néanmoins des cas pénibles. Par exemple :
On a le mot a...a (250 fois).
On a la grille :
a...aba...a
.
.
.
a...aba...a
b...bbb...b
a...aba...a
.
.
.
a...aba...a
On ne trouvera jamais le mot et on le cherchera longtemps.

Une autre optimisation consisterait à créer des listes indiquant où sont les cases commençant par un a, où sont celles commençant par un b, ...
Sur des utilisations classiques (une grille avec plein de lettres différentes) cela permettra de diviser le nombre de cases de départ potentielles pour un mot jusqu'à 26 (et donc de passer de 50*50 = 2500 à jusqu'à un peu moins de 100).

Puisqu'avec des utilisations classiques, la comparaison de l'égalité de deux mots se fait en O(1), c'est-à-dire en temps constant, on peut espérer atteindre avec cette solution sur les pires tests de Prologin un programme effectuant 500 (nombre de mots) * 500 (nombre de lignes) * 500 (nombre de colonnes) / 10 (une grille hétérogène mais pas trop) = 12,5 millions d'opérations, ce qui passe en temps avec des langages comme C++.

La suite en préparation, au programme :
-appel à des algorithmes de recherche de sous-chaînes
-arbres lexicographiques
-parade contre les tests fourbes