Sujet Précédent Sujet Suivant

Question C : recherche exhaustive

Fermé
io - 4 mai 2011 à 12:28
boly38 Messages postés 267 Date d'inscription mercredi 23 février 2011 Statut Membre Dernière intervention 29 septembre 2016 - 4 mai 2011 à 17:00
Bonjour,

J'ai actuellement un petit soucis avec un algorithme qui ne me semble pourtant pas si compliqué que cela à implémenter. Le problème est le suivant : je dispose d'une chaine d'entier positif dans un tableau ; par exemple :

int array[]={3,1,4,2,3,6,5,10};

Ce que j'aimerais obtenir à partir de cette chaine, c'est toutes les sous-chaines non contiguës qu'elle possède (3, 1, 4, .., 5, 10, 3 1, 3 4, 3 2, etc jusqu'à la chaine elle-même) le tout avec un algorithme bête et méchant de recherche exhaustive. La complexité n'a pas d'importance, ni même la manière de l'implémenter... Il me faudra juste un moyen de retrouver toutes ces sous-chaines et de faire un simple test (de palindrome par exemple) sur celles-ci.

Quelqu'un voit une solution à mon problème ? :/

Merci d'avance.


1 réponse

Réponse 1 / 1
boly38 Messages postés 267 Date d'inscription mercredi 23 février 2011 Statut Membre Dernière intervention 29 septembre 2016 80
4 mai 2011 à 17:00
bonjour,
voici une description de l'algorithme (à transformer en C ..)

on a un double parcours : pour toutes les tailles d'ensembles t (chaînes de t éléments possibles) depuis des ensembles de 1 élément jusque des ensembles de tailleTab éléments
on parcours à chaque fois le tableau de départ en ajoutant au résultat les ensembles contigües et le restant (correspond au sinon). 

montableau = {3,1,4,2,3,6,5,10};
tailleTab = taille(montableau);
resultat = nouveau tableau;
pour (t = 1 ; t<tailleTab; t++) {
  pour (index = 0; index < tailleTab; index += t) {
      si (index+t < tailleTab) {
        resultat.add(montableau[index..index+t])
      } sinon {
        resultat.add(montableau[index..tailleTab])
      }
 }
}
0