Un petit peu d'algorithmique ?

[Woodgate69]

Bonsoir tout le monde,

J'ai remarqué en lisant quelques posts sur ce forum il y a quelques temps que plusieurs membres ont l'air plutôt calé, et c'est donc tout naturellement que suite à une grosse colle je me permet de venir vous demander de l'aide.

En fait je dois réaliser un programme (rien de grave, juste du PHP) qui doit permettre de calculer le nombre de palindromes dans une chaine donnée. Mais quand je dis le nombre de palindromes, c'est le nombre de palindromes maximums.

C'est à dire que par exemple la chaine "ababab" contient deux palindromes maximums : "ababa" et "babab", mais "aba" et "bab" n'en font pas partie.

En fait, ce n'est pas le PHP qui coince, c'est l'algo. Je n'arrive pas à imaginer un système permettant de faire une chose pareille.

J'ai réalisé ce code :
http://www.asticot.net/essai.txt

Mais le petit fonctionne mal, il m'en trouve soit juste un peu trop, soit juste un peu pas assez, suivant les exemples dont je connais les réponses.

Si quelqu'un à une idée, une source, même si ce n'est pas du php, de l'algo ça m'irait déja vraiment bien.

Merci d'avance !

[Woodgate69]

Et ben ça n'aura pas suscité un engouement historique tout ça :dodo:

[Joker62]

Moi je ferais comme ça :

Un pointeur sur la première lettre
Un pointeur sur la dernière lettre

Si les deux lettres coincïdes, on est bien parti, on avance les deux pointeurs, on retourne à l'étape de comparaison

Si à partir d'un moment, les deux pointeurs ne corresponde plus, c'est à dire, qu'ils pointent vers deux valeurs différentes, alors ça ne va plus, un palyndrome maximal sera donc un mot contenu entre ces deux pointeurs strictement

En diction comme ça, c'est facile à dire, mais en prog, je dirais spécial

[Woodgate69]

C'est bien pensé.

Mais comment est ce que ça fonctionne, par exemple ici :

abacabbacaacdbdcacxcbbbbcabababacccbazhhaahh

Il est sensé y avoir 14 résultats...

[Joker62]

J'vois pas 14 palyndrômes maximaux là-dedans !
Enfin, faudrait ptète donner la définition exacte d'un palyndrome maximal

[rene38]

Bonsoir

abacabbacaacdbdcacxcbbbbcabababacccbazhhaahh
Il est sensé y avoir 14 résultats...

J'vois pas 14 palindrômes maximaux là-dedans !

Moi, je n'en vois même aucun à cause des deux lettres en rouge

[Flodelarab]

Bonsoir Moi, je n'en vois même aucun à cause des deux lettres en rouge

Ah ben si. Ya au moins "aba" ou "cabbac".
Mais de la à trouver une longueur maximale qui donne 14 spécimens .... je doute

[Flodelarab]

Code: Tout sélectionner

Pour chaque lettre:
    Pour chaque couple de position:
        Les 2 lettres sont elles les extrémités d'un palindrome ? (fonction récursive qui se déplace vers le centre du palindrme avec arret si les 2 extrémités proposées sont la meme position. cette fonction renvoie vrai ou faux)
        Si oui,
            Longueur supérieure au max ?
            si oui, remplacer le max et mettre le cardinal à 1
            si non, Longueur égale au max ?
                 si oui, augmenter le cardinal
                 si non, on passe au suivant
        Si non,
            on passe au suivant


Python inside pour la syntaxe :id:

[Woodgate69]

Merci, je vais voir ce que je peux faire (:

PS : pour les 14 palindromes, c'est mon énoncé qui me dit ça... donc j'ose le croire !

[ThSQ]

Salut

Un prog Maple qui doit faire l'affaire (aucune recherche d'efficacité ou de clarté :zen:)


> a := [1, 2, 1, 3, 1, 2, 2, 1, 3, 1, 1, 3, 4, 2, 4, 3, 1, 3, 5, 3, 2, 2, 2, 2, 3, 1, 2, 1, 2, 1, 2, 1, 3, 3, 3, 2, 1, 6, 7, 7, 1, 1, 7, 7];
> N := nops(a);
>

a := [1, 2, 1, 3, 1, 2, 2, 1, 3, 1, 1, 3, 4, 2, 4, 3, 1, 3, 5, 3, 2,

2, 2, 2, 3, 1, 2, 1, 2, 1, 2, 1, 3, 3, 3, 2, 1, 6, 7, 7, 1, 1,

7, 7]


N := 44

> cnt:= 1;
> minS := 1;
> for deb from 1 to N do
> ## print("DEBUG", deb, fin, minS);
> for fin from N by -1 to minS+1 do
> if (a[deb] = a[fin]) then
> ok := true;
> for check from 1 to fin-deb do
> if (a[deb+check] <> a[fin-check]) then ok := false; break; fi;
> od;
> if (ok) then
> printf ("trouvé n°%d : %d -> %d : ", cnt, deb, fin); cnt := cnt+1;
> for i from deb to fin do printf ("%d ", a[i]); od; printf ("\n");
> minS := fin;
> break;
> fi;
> fi;
> od;
> od;
>
>

cnt := 1


minS := 1

trouvé n°1 : 1 -> 3 : 1 2 1
trouvé n°2 : 2 -> 6 : 2 1 3 1 2
trouvé n°3 : 3 -> 10 : 1 3 1 2 2 1 3 1
trouvé n°4 : 9 -> 12 : 3 1 1 3
trouvé n°5 : 11 -> 17 : 1 3 4 2 4 3 1
trouvé n°6 : 16 -> 18 : 3 1 3
trouvé n°7 : 18 -> 20 : 3 5 3
trouvé n°8 : 20 -> 25 : 3 2 2 2 2 3
trouvé n°9 : 25 -> 33 : 3 1 2 1 2 1 2 1 3
trouvé n°10 : 33 -> 35 : 3 3 3
trouvé n°11 : 36 -> 36 : 2
trouvé n°12 : 37 -> 37 : 1
trouvé n°13 : 38 -> 38 : 6
trouvé n°14 : 39 -> 44 : 7 7 1 1 7 7

[Joker62]

Des palyndrômes à une lettre ? :D
Non, j'ai pas du comprendre la notion de palyndrôme maximal tampis.

En, fait, je suppose que c'est tant qu'on peut continuer à construire un palyndrôme, bé on continue na ?

[ThSQ]

Des palyndrômes à une lettre ?
Non, j'ai pas du comprendre la notion de palyndrôme maximal tampis.

En, fait, je suppose que c'est tant qu'on peut continuer à construire un palyndrôme, bé on continue na ?

Moi j'ai compris : palindrome max = palindrome non contenu dans un palindrome plus grand.
Et si on prend pas les palindromes de taille 1 ça en fait pas 14 donc .....


(et ça s'écrit palindrome)

[Joker62]

Je sais pas pourquoi je m'obstinais à placer ce 'y' ! désolé :)

[Quidam]

Woodgate69

J'aimerais que tu nous dises si tu es d'accord avec cette définition de ThSQ

Moi j'ai compris : palindrome max = palindrome non contenu dans un palindrome plus grand.
Et si on prend pas les palindromes de taille 1 ça en fait pas 14 donc .....


(et ça s'écrit palindrome)

Et si tu n'es pas d'accord, donne nous ta définition !