Bonjour,bonjour..
 
En gros je doit faire un programme qui me dit si un mot est un PPM (Palindrome Par Morceau)..
 
Alors je m'y suis atelé.
 
Pensant bien faire, et suivie par l'exemple du prof, j'ai fait un algo qui fait par exemple pour le mot ababbaa
vérifie si ab est un palindrome, non
alors on prend un charactère de plus,on regarde aba, Ok c'est un palindrome,doncon passe au reste du mot..bb etc..
 
Cependant si l'on utilse cela,on est confronté au problème que aaabbcc ne sera pas pris en étant un palindrome..><.
 
J'ai bine pensez à prendre le palindrôme le plus grand mais on se retrouve avec des cas oublié..
 
Donc je voulais savoir si d'après vous il me faut refaire mon algo car il est tous pourrie xD.. Ou est ce qu'il y aurai un efaçon de résoudre cette oublie..
 
Je vous remercie d'avance pour votre aide

a la bourrin : tu test toutes les chaines qui commencent par le premier caractère et tu extrait ceux qui sont des palindrome
ensuite, tu passe au deuxième caractère et tu recommence  
 
mais c'est sacrement groumand comme approche

Effectivement, et sinon rien de plus...En finesse ><..

Je vois que ça comme algo
A part tester toutes les combinaisons ya aucune autre manière.
 
sur un mot de 10 lettres ça fait 99 combinaisons possibles.
et un mot de 25 lettres ben 25²-1 ca peut paraitre énorme mais une boucle de 600 itérations je trouve pas ça lourd (sauf si tu dois le faire sur 1000 mots )

Quelle est la défintion exacte d'un palidrome par morceau ?

De une je doit faire ça en récursif ><... Et un palindrôme par morceau c'est un mot composé de plusieurs palindrome...

je ne pige pas pour les combinaisons... pour un mots de n lettres tu n'as pas que :
n mots de 1 lettres
(n-1) mots de 2 lettres
(n-2) mots de 3 lettres  
...
2 mots de n-1 lettres
1 mots de n lettres  
soit n(n+1)/2  mots en tout et pour tout ?
apres tu test du plus grand mot au plus petit pour voir si c'est un palindrome et si cest le cas tu supprime ces lettres et tu recommences avec les combinaisons suivantes ?
 
pour le test aaabbcc
combinaison à 7 lettres = pas un Palindrome (NP)
à 6 lettres (aaabbc et aabbcc) NP et NP
à 5 lettres (aaabb, aabbc, abbcc) NP, NP et NP
à 4 lettres (aaab, aabb, abbc, bbcc) NP, NP, NP, NP
à 3 lettres (aaa, aab, abb, bbc, bcc) P, NP, NP, NP
bbcc est le nouveau mot
4 lettres forcement non car taille nouveau mot >taille arret
3 lettres itou
2 lettres (bb, bc, cc) P, NP, P
nouveau mot bc Taille = 2, NP on arrete
 
resultat aaabbcc est un palindrome par morceau aaa, bb et cc
 
non ?

aaabacc np
aaabac/aabacc NP/NP
aaaba/aabac/abacc NP/NP/NP
aaab/aaba/abac/bacc NP/NP/NP/NP
aaa/aab/aba/bac/acc P/NP/P/NP/NP
Le problème va venir du fait que 2 palindrome se chevauche là>>
 
donc il va falloir testé si les partie restante avec les 2 morceau...
ya un problème non?

yo !
mais la faut voir la def en question
soit on sonsidere que dans aaabacc
    il y a 3 palindromes (aaa, aba et cc) et la ca merde pas si on elimine, dans la methode le aaa et aba, il ne reste que cc
sinon
   il y en a que 2 (aaa, cc) ou (aba, cc) et la il faut faire une ruse de sioux...genre stocké le tous les palindromes trouvé et les valider à la fin
 
mais sinon je pense quil vaut mieux partir du mot complet plutot que des lettres le composant, comme cela tu es sur de ne pas louper le plus grand.
De toute facon l'algo que j'ai donné, n'est pas parfait, car il manque pas mal de cas...notament celui ou on trouve un palindrome au milieu du mot, on a effectivement deux mots en resultat (aabcbee --> bcb : analyse de aa et de ee)...
Capilotracté ?
 
 
mais effectivement, comme le dit Trap D, il faut la definition exacte, parce que celle que tu as donné précise que le mot est un palindrome par morceau mais ne donne pas sa décomposition, nisi elle doit etre unique etc etc
d'un autre coté, ta question est " si un mot est un palindrome par morceau"... bon ok je suis de mauvaise foi et j'ai fait abstraction du 'en gros'...
 

On commence par se créer une fonction qui prend en paramètre:
- une chaîne
- une position quelconque dans la chaîne
et qui renvoie la position du dernier caractère du plus grand palindrome qui commence à la position passée en paramètre. Appelons cette fonction pal. (en pratique on dira qu'elle renvoie -1 si aucun palindrome n'a été trouvé)
 
Cas 1: les palindromes ne se chevauchent pas
1] On appelle la fonction pal pal sur le premier caractère de la chaîne. S'il n'y a pas de palindrome trouvé, on sait que le mot n'est pas PPM.
2] Si on trouve un palindrome, on récupère la position de la fin du palindrome. Si c'est le dernier caractère de la chaîne qui est renvoyé, le mot est PPM. Sinon, on rappelle la fonction pal sur le caractère suivant qui a été renvoyé et on boucle sur cette étape 2.
 
Exemples (le premier caractère est indicé à 1):
chaîne s = "abbabbb"
1] pal(s, 1) renvoie 4 -- "abba" est un palindrome
2] 4 < 7
3] pal(s, 4 + 1) renvoie 7  -- "bbb" est un palindrome
4] 7 == 7, on est arrivé à la fin
5] s est PPM
 
chaîne s = "ababba"
1] pal(s, 1) renvoie 3 -- "aba" est un palindrome
2] 3 < 7
3] pal(s, 3 + 1) renvoie -1 -- "bba" n'est pas un palindrome
4] s n'est pas PPM
 
Cas 2: les palindromes se chevauchent
Paradoxalement, ce cas est presque plus simple.
On utilise un tableau de booléens contenant autant d'éléments que de caractères dans la chaîne. Il va servir à "marquer" chaque caractère de la chaîne.
 
Initialement, aucun caractère n'est marqué.
On va simplement appeler la fonction pal sur chaque position dans la chaîne, de la première à l'avant-dernière (la dernière ça ne sert à rien, ca revient à demander si un seul caractère est un palindrome, ce qu'on considère faux par convention).
Si pal détecte un palindrome, on marque tous les caractères du début du palindrome (paramètre passé à la fonction pal) à la fin du palindrome (valeur de retour de la fonction pal).
A tout moment, si tous les caractères ont été marqués, le mot est PPM. Sinon il ne l'est pas.
 
Exemple:
chaîne s = "ababba"
marqueurs = [......]
1] pal(s , 1) renvoie 3 -- "aba" est un palindrome
2] on marque tous les caractères de 1 à 3 : [XXX...]
3] pal(s, 2) renvoie 4 -- "bab" est un palindrome
4] on marque tous les caractères de 2 à 4 : [XXXX..]
5] pal(s, 3) renvoie 7 -- "abba" est un palindrome
6] on marque tous les caractèrs de 3 à 7 : [XXXXXX]
7] tous les caractères ont été marqués, le mot est PPM

 
heuuu dans ton exemple il y a un souci, on manque le plus grand de tout les palindrome de abbabbb à savoir 'bbabb'
parcourir du plus grand au plus petit et stocker les palindromes trouvés, puis effectuer une fonction de tri sur ce qu'on a trouvé semble le plus stable

 
Ce dont se fout royalement à priori, vu l'énoncé de l'exercice. Le détail des palindromes composant le mot PPM n'est pas demandé (ou alors j'ai vraiment mal lu). Par contre j'ai zappé que l'exercice demandait une fonction récursive.

exactement ce que j'ai dit///
 
mais pas la peine d'etre vulgaire

 
Bah y'avait pas de souçi dans mon exemple en fait

Erf, ababba n'est pas un PPM pour ma definition, car on doit pourvoir le decouper en palindrome distinct (enfin à ce que j'ai compris), aba palindrome, bb aussi mais pas a qui ets seul..(selon ma definition, enfin celle du prof >< )..
 
De plus ton exemple sur le mot aaabbcc, il va prendre le mot aa, revoiyé 2, donc tu commence aux troisième a et donc tu rerouve pas de palindrome..
 
Donc bug xD..
ça me bouffe cet exo...
 
Et ya une question bonus pour le fait de donner le nombre de decoupage possible ><...mais bon>>, on verra après

Pour être tout à fait rigoureux il aurait fallu préciser que les palindromes qui composent ton mot sont de longueur 2 au moins (parce qu'une lettre est un palindrome ).
 
Si j'ai bien compris l'énoncé du problème, la solution est simple. Il suffit de raisonner récursivement. Soit N la taille de ton mot, tu supposes que tu sais résoudre le problème pour tous les mots de taille inférieure à N et l'algorithme est alors le suivant :
 
- Si N = 0, on renvoie vrai.
 
- Si N = 1, on renvoie faux.
 
- Si N >= 2, pour k allant de 2 à N, on distingue deux cas :
 
  1. Le sous-mot composé des k premières lettres est un palindrome et le sous-mot composé des N-k dernières lettres est un PPM, alors le mot est un PPM et on s'arrête.
 
  2. Dans le cas contraire, on continue pour la valeur suivante de k.

Comment cet algo gère-t-il "aabaa" ?

 
Je viens de corriger l'algorithme, qui ne prenait pas en compte les PPM premiers.
 
Edit : en fait le truc chiant c'est de savoir quoi faire du mot à une lettre, le considérer ou non comme un PPM... Si on suppose que non ça simplifie les choses (d'ailleur ce cas est recouvert par la définition corrigée que j'ai donnée).
 
Si on veut absolument que le mot à une lettre soit un PPM, il suffit de transformer mon algo en fonction auxiliaire et de distinguer le cas N = 1 dans l'algorithme principal (alors que dans l'algo auxiliaire je supposerais toujours que pour N = 1, c'est faux, mais le N de départ ne vaudra jamais 1 donc pas de problème).

Haan mais c'est que c'est pas bête nyrk.. Je te remercie bcp =)!!
 
Bon, ensuite je vais essayé de voir tous les cas possible.. =)!!!
 
Encors merci à tosu eux qui m'ont aider^^

 
Regarde bien mon dernier edit, j'ai clarifié les choses (après un certain nombre d'edit foireux ).

Une implémentation en Caml :
 

RHoo, ya un truc qui m'embète.. C'est ton pour.. Je voit que ça va marché, quoique qie c'est k arrive à N il se passe quoi??
 
ENfin ce qui me gène c'est l'itération...ALors que le programme doit être récursif.. En faite il utilise les deux ><...
 
Je sais pas si c'ets grave, mais tu pense qu'il serai possible de mettre la valeurs de k en paramètre de la fonction et ainsi fair que de la récursivité..
 
J'essaye et je vosu tient au courant!!
 
Edit:Erfje connait pas le caml, mais je doit le prog en C ensuite..>>

Le fait qu'une fonction s'utilise de façon récursive n'exclue pas qu'elle effectue certains traitement de façon itérative

Je suis sûr que même sans connaître Caml tu peux traduire mon programme en sa version C.

Vivi,j'était entrain de faire l'algo car il faut le rendre aussi.. Puios je traduit en prog C =), mici tous le monde