Question C : recherche exhaustive
io
-
boly38 Messages postés 267 Date d'inscription Statut Membre Dernière intervention -
boly38 Messages postés 267 Date d'inscription Statut Membre Dernière intervention -
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.
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
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).
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])
}
}
}