Algorithme du palindrome help please - aide pour faire algorithme du palindrome

Logiciel & apps Programmation
1

salut à tous
je dois créer un algorithme du palindrome(min 3 lettres) mais je n’y arrive pas.
le problème est que je n’arrive pas “à ne pas trouver les palindromes intermédiaires”
exemple: avec la chaine : “accacttcagakayakc”
mon algo trouve: “acca” + “cttc” + “aga” + “kayak”.
alors qu’il devrais trouver uniquement “ACTTCA” + “KAYAK”

mon algo est très simple: je prend le 1er caractère et le 3eme ,
si ils sont identiques je vérifie si ce qui y’a entre eux l’est également sinon je passe au 2eme et 4eme caractère…

j’espere que quelqu’un pourra m’aider à le faire .

Merci :jap: :super:

2

A mon avis tu dois essayer de rechercher les palindromes les plus longs en commençant par le mot entier, et ainsi de suite.

3

Salut,

Je t’ai créé le code en VB (le langage le plus simple pour faire un algo rapide, je trouve). Tu pourras très facilement le convertir en un autre.

  Dim Chaine As String: Chaine = "accacttcagakayakc"
    
    Dim DebutMot As Integer, FinMot As Integer
    Dim TailleMot As Integer, Palindrome As Boolean
    Dim NbPalindromes As Integer: NbPalindromes = 0
    
    For DebutMot = 1 To Len(Chaine)
        For FinMot = Len(Chaine) To DebutMot + 1 Step -1
            If Mid$(Chaine, DebutMot, 1) = Mid$(Chaine, FinMot, 1) Then
                ' Le début et la fin de la chaîne sont identiques
                ' Il faut vérifier que l'intérieur l'est aussi
                
                Palindrome = True: TailleMot = 1
                
                While Palindrome = True And TailleMot <= (FinMot - DebutMot) / 2
                    If Mid$(Chaine, DebutMot + TailleMot, 1) = Mid$(Chaine, FinMot - TailleMot, 1) Then
                        TailleMot = TailleMot + 1
                    Else
                        Palindrome = False
                    End If
                Wend
                
                If Palindrome = True Then
                    NbPalindromes = NbPalindromes + 1
                    Debug.Print NbPalindromes & ". " & Mid$(Chaine, DebutMot, FinMot - DebutMot + 1)
                End If
            
            End If
        Next
    
    Next

Je trouve 10 palindromes avec :

  1. acca
  2. cc
  3. cac
  4. acttca
  5. cttc
  6. tt
  7. aga
  8. aka
  9. kayak
  10. aya

Il faut évidemment que tu vérifies avec un dictionnaire après.

4

en fait tu doit decouper la chaine en prenant uniquement les palindrome les plus grands qui ne se recouvrent pas … c ça ?

donc il ya 2 partie a l algo :

  • definir tous les pali
  • choisir la meilleur combi

ça me parait difficile de tout faire a la fois (ou alors en faisant un arbre de prediction)

tu peux utiliser l’algo de juky meme si il est pas optimisé :stuck_out_tongue:

5

Qu’optimiserais-tu par exemple ?

Je viens de voir que j’ai oublié de minimiser à 3 lettres mais à part ça :??:

6

si j’ai bien compris ton code :
tu parcours la chaine et tu teste si ce qui reste a droite est un palindrome en considerant la position actuelle dans la chaine comme le debut potentiel

je pense qu’il vaudrait mieux considerer la position actuelle comme le centre du palindrome postentiel et comparer caratere a caractere

en gros en algo pourrav c

boucle sur la chaine
loop

i : position actuelle

//test palindrom impaire
j=0;
while (chaine[i-j]==chaine[i+j]) j++;
//affichage

//test palindrom paire
j=0;
while (chaine[i-j]==chaine[i+1+j]) j++;
//affichage

end loop

statistiquement on elimine plus vite et on boucle moins pour rien et on utiise pas de teste sur des chaine (encore une boucle en interne)

on pourrait meme optimiser en testant dans une seul boucle l impaire et le paire en utilisant une variable pour empiler les resultats des testes mais ct moins lisible pour expliquer :stuck_out_tongue:

7

Je ne suis vraiment pas sûr que la différence soit si évidente.

Et puis tu utilises aussi des tests sur des chaines : chaine[i-j] ==

Là je suis d’accord : pour moi, l’optimisation peut se faire à cet endroit.

Je trouve qu’il manque dans mon algo (et dans le tien), c’est un test supplémentaire pour prendre les palindromes intermédiaires : si on a “kayak” comme palindrome, on a aussi obligatoirement “aya”.

8

en c


#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
  char chaine[]="accacttcagakayakc";
  char buffer[256];
  int i,j,l,n=0;
  l=strlen(chaine);
  for(i=0;i<l;i++)
  {
   for(j=1;i-j>=0&&i+j<l&&chaine[i-j]==chaine[i+j];j++)
   {
    sprintf(buffer,"%%0.%ds\n",j*2+1); 
    printf(buffer,chaine+i-j);
    n++;
   }
   for(j=0;i-j>=0&&i+j+1<l&&chaine[i-j]==chaine[i+j+1];j++)
   {
    sprintf(buffer,"%%0.%ds\n",j*2+2); 
    printf(buffer,chaine+i-j);
    n++;
   }
   n++;
  }
  printf("n=%d\n",n);
  system("PAUSE");	
  return 0;
}

cc
acca
cac
tt
cttc
acttca
aga
aka
aya
kayak
n=27
Appuyez sur une touche pour continuer…

ça prend les intermediaires ;/

concours de prog sur calculettes c formatteur :stuck_out_tongue:

ps : je compare pas des chaines mais des caractere (8bits)

9

Bon, bisso a de quoi faire avec tout ça. :slight_smile:

Ben oui puisqu’en C le type STRING n’existe pas.
En VB, j’utilisais la fonction MID$ pour comparer un seul caractère (car le type CHAR n’existe pas en VB).