Discussion :

[tulipelydia]

Bonjour à tous,
j'ai un exercice d'algorithme que j'ai résolu, il demande d'écrire un algorithme qui dit si la chaine est palindrome ou non, en utilisant une chaine de n caractères.
Je vous demande de corriger mes erreurs s'il vous plaît, j'ai énormément besoin de votre aide. Merci d'avance

Code x :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Algorithme  mot_palindrome;
Var   mot: chaine[n];
          b: booléen;
          i, n: entier;
Debut
 
  Ecrire("Veuillez introduire un mot de plus de 2 caractères: ");
  
  Repeter
   Lire(mot);
  Jusqu'à(longueur(mot)>2)

b<-- vrai;
n<-- longueur(mot);
i<--1;
  Si(n mod 2 =0) alors
     debut
    Tant que ((b=vrai) et (n<>i+1)) faire // <> veut dire =/= (different)
      debut
        Si(mot[i]=mot[n]) alors b<-- vrai;
        Sinon b<-- faux;
        i <--  i+1; n <--  n-1;
    fait;
     fin;
   Sinon
      debut
    Tant que((b<--vrai) et (n<>i))faire
      debut
        Si(mot[i]=mot[n]) alors b<--vrai;
        Sinon b<-- faux;
        i <--  i+1; n <--  n-1;
       fait;
        fin;
Si(b=vrai) alors Ecrire("Le mot introduit est palindrome");
Sinon Ecrire ("Le mot introduit n'est pas palindrome");

FIN.

[Trap D]

Pourquoi distinguer 2 cas, nombre de lettres pair ou impair ?

[Flodelarab]

Bonjour

Tu n'as besoin de parcourir que la moitié du mot.

[tulipelydia]

Bonsoir, merci à vous deux pour votre réponse,

Trap D, j'ai pensé à la parité du nombre de lettres composant le mot, comme j'ai besoin de deux conditions d'arrêt pour les variables (i et n), voici un exemple de déroulement:
Si le nombre de caractères du mot est paire : exemple le mot 'haut'
au début i=1 et n=4 (n étant la longueur du mot=4) on vérifie si h=t, la 2ème étape: i=2 et n=3 on vérifie encore si a=u puis on sort de la boucle, j'ai pensé à ce que l'incrémentation de i et n s'arrête ici, car si on continue on aura ça : i=3 et n=2 le système va comparer si u=a ce qui serait inutile car il a déjà passé par cette comparaison.
Dans le cas où le nombre de caractères est impaire, exemple pour le mot 'bas'
i=1 et n=3 , on vérifie si b=s. 2ème étape i=n=2 on vérifie si a=a, et on s'arrête ici, on sort de la boucle, et on arrête l'incrémentation afin que le système ne refait pas la comparaison qu'il a déjà fait.. Autrement dit, si i=3 et n=1 on retombe sur la première comparaison: s=b qu'on es pas censé refaire.
Je ne vois pas comment écrire l'algorithme avec une seule boucle, pourriez vous me l'écrire afin que je comprenne mieux ? Merci.


Flodelarab, oui en effet, c'est ce que j'ai fait dans la boucle tant que, dans la 1ère Tant que ((b=vrai) et (n<>i+1) dans la 2ème Tant que((b<--vrai) et (n<>i)), mon exemple que j'ai écrit en dessus explique ma façon de parcourir la chaine.

[Flodelarab]

Soit N le nombre de lettres du mot. Il ne bouge pas ! Contrairement à ton n.
Soit i un indice.

La lettre à la i^ème place est la même qu'à la (n-i+1)^ème place, quelque soit la parité de N.

i parcourt les nombres de 1 à N/2 quelque soit la parité et le signe "/" étant la division entière:
6/2=3
5/2=2
4/2=2
Dans un mot de 5 lettres, la lettre centrale n'a pas à être testée puisqu'elle est forcément bonne.

Tu n'as pas besoin de plusieurs boucles, ni d'étudier la parité, ni de dépasser N/2.

Simplifie ton algorithme.

[Trap D]

L'algorithme est une simple boucle tant que avec deux conditions et des incrementations.

On peut écrire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
debut
  initialisation des indices
  tant que condition_1 et conditions_2 faire
       (in/de)cremetation des indices
  fin tant que
  si condtion alors
     c'est un palindrome
  sinon
    ce n'est pas un palindrome
  fin si
fin

A toi de trouver ce qu'il faut ettre à certains endroits !

PS je trouve plus simple d'utiliser 2 indices plutôt qu'un seul, question de goût.

[anapurna]

salut

sur le net il existe une multitude d'algorithme pour les palindrome

ma préférer étant celle-ci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
Fonction Palindrome(T: tab[1..n]: caractère): booléen;
Var
    i, j: entier;
    résultat: booléen;
Debut
    i := 1;
    j := longueur(Mot);
    résultat := Vrai;
    TantQue ((résultat = Vrai) Et (i < j)) Faire
        Si(T[i] = T[j]) Alors
            résultat = Vrai;
            i = i + 1;
            j = j - 1;
        Sinon
            résultat := Faux;
        FinSi
    FinTantQue
    Renvoyer résultat;
Fin

tu la trouveras ici

[Trap D]

Resultat = vrai est complètement inutile.

[souviron34]

Resultat = vrai est complètement inutile.

Et aussi le fait d'aller au bout :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Fonction Palindrome(T: tab[1..n]: caractère): booléen;
Var
    i, j: entier;
Debut
    i := 1;
    j := longueur(Mot);
    TantQue ( i < j ) Faire
        Si(T[i] = T[j]) Alors
            i = i + 1;
            j = j - 1;
        Sinon
            Renvoyer Faux;
        FinSi
    FinTantQue
    Renvoyer Vrai;
Fin

[Trap D]

Moi je l'avais vu sur la forme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
Fonction Palindrome(T: tab[1..n]: caractère): booléen;
Var
    i, j: entier;
Debut
    i := 1;
    j := longueur(Mot);
    TantQue ( i < j ) et T[i] = T[j] Faire
            i = i + 1;
            j = j - 1;
     FinTantQue
    Renvoyer  i >= j;
Fin

[souviron34]

Yep mais ceci est un peu..... difficile éventuellement à comprendre..

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Renvoyer  i >= j;

[Trap D]

Tu as raison, je suis trop influencé par le C

[souviron34]

Bah

Suffit de l'écrire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
Si i >= j renvoie vrai
sinon renvoie faux

et ça se comprend

[picodev]

Bonjour,
il y a là une orgie avec le même algo … mais on peut aussi imaginer d'autres approches (pas forcément des plus utiles ou utilisées ou adéquates) :

Une version récursive :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
fonction est_palindrome( chaine, longueur) : booleen
début
  si longueur=0 ou 1 alors
    revoyer vrai
  sinon si premiere_lettre(chaine)=derniere_lettre(chaine) alors
    renvoyer est_palindrome(sous_chaine(chaine,2,longueur-2), longueur-2)
  sinon
    renvoyer faux
  fin si
fin

Une version autre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
fonction est_palindrome( chaine ) : booleen
début
  eniahc=renverser(chaine)
  si chaine=eniach alors
    renvoyer vrai
  sinon
    renvoyer faux
  fin si
fin

...

[anapurna]

Resultat = vrai est complètement inutile.

exact copier coller malheureux ^^
l'affectation ne sert a rien

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
Fonction Palindrome(T: tab[1..n]: caractère): booléen;
Var
    i, j: entier;
Debut
    i := 1;
    j := longueur(Mot);
    TantQue ( i < j ) Faire
        Si(T[i] = T[j]) Alors
            i = i + 1;
            j = j - 1;
        Sinon
            Renvoyer Faux;
        FinSi
    FinTantQue
    Renvoyer Vrai;
Fin

je ne suis pas d'accord avec ton écrit les conditions de sortie de boucle dans un algo sont importante
dans ton cas tu fait un mixte entre du pseudo code et du C si je l’écrit en pascal il ne marcheras pas a moins de lui adjoindre un exit après le renvoyer
pour moi un pseudo code ne doit en aucune présumer de quelque langage que ce soit et donc être le plus descriptif possible

[Trap D]

Quite à donner des exemples d'algo, j'aime bien celui-là en Prolog :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
palindrome(X) :-
   phrase(palindrome,X).
 
palindrome -->   % base case for even number of elements
   [].
palindrome -->   % base case for odd number of elements
   [A].
palindrome -->   % general case: a palindrome is
   [A],          % some element A...
   palindrome,   % ... followed by a palindrome ...
   [A].          % ... followed by element A