Discussion :

[iks37]

Bonjour à tous.

Je voudrais créer un programme qui détermine si un mot (ou du texte) est un palindrome. On admettra qu'un mot est un palindrome s'il se lit indifféremment de gauche à droite ou de droite à gauche en donnant le même mot (par exemples : radar, SOS, kayak, Laval).

Je souhaite utiliser un algorithme qui copie à "l'envers" le mot à tester dans une chaîne de caractères : d'abord on crée une chaîne de caractères qui va recevoir le mot à tester caractère par caractère à partir du dernier caractère du mot à tester [1] ; ensuite, on compare la chaîne du mot à tester à celle du mot constitué par concaténation [2] ; si les 2 chaînes sont identiques alors le mot à tester est un palindrome sinon il ne l'est pas.

La concaténation s'effectue sauf que le mot inverse débute par un espace si bien qu'il a un caractère de plus (l'espace) que le mot à tester, ce qui est illogique !
Voici le code de mon programme :

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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "fichier_init.h"
 
int main()
{
    char mot[100], temp[2], reponse[2];
    int i;
 
    do
    {
        system("cls");
        printf("\n\n\t\t\t\tCE MOT EST-IL UN PALINDROME ?\n\n");
 
        printf("Donnez le mot : ");
        fflush(stdin);
        saisirChaine(mot, 100);
 
        char inverse[100] = " ";
        for(i = strlen(mot); i>=0; i--)
        {
            temp[0] = mot[i];
            strcat(inverse, temp);
        }
 
        printf("\n\n");
 
        printf("L'inverse de \"%s\" est : \"%s\"\n", mot, inverse);
        printf("Longueur du mot \"%s\" est : %d\n", mot, strlen(mot));
        printf("Longueur de l'inverse \"%s\" est : %d", inverse, strlen(inverse));
 
        printf("\n\n");
 
        if(strcmp(mot, inverse) == 0)
        {
            printf("Le mot \"%s\" est un palindrome", mot);
        }
        else
        {
            printf("Le mot \"%s\" n'est pas un palindrome", mot);
        }
 
        printf("\n\n");
 
        do
        {
            printf("Voulez-vous recommencer (O/N)? : ");
            fflush(stdin);
            saisirChaine(reponse, 2);
        }
        while((reponse[0] != 'o')&&(reponse[0] != 'O')&&(reponse[0] != 'n')&&(reponse[0] != 'N'));
    }
    while((reponse[0] != 'n')&&(reponse[0] != 'N'));
 
    return 0;
}

Je vous épargne de la définition de la fonction saisirChaine, cette fonction a été écrite à partir de la fonction fgets.

Voici la capture de l'exécution :



Je vous remercie de m'éclairer.

[Bousk]

C'est parfaitement logique (l'ordinateur ne fait qu'exécuter ce que tu lui écris de faire après tout ), puisque tu initialises ta chaîne inverse avec un espace.
strcat, si tu lis la doc, ajoute une chaîne à la fin d'une autre, et pour trouver où se situe cette fin, il cherche un \0. Et vu que t'as déjà un espace dedans, il va pas le supprimer.
Ta concaténation marche par hasard d'ailleurs vu que temp n'est pas initialisée et n'a donc aucune raison de finir par un \0.

Au passage, je n'ai jamais entendu parler d'un algo aussi complexe et inefficace pour vérifier qu'un mot est un palindrome

[iks37]

Bousk,

La première partie de votre commentaire m'a ouvert les yeux. En effet, j'ai initialisé les chaînes temp : temp[2] = {'a'} et inverse : inverse[100] = {'\0'}, et le résultat est correct.

Pour ce qui concerne la dernière partie de votre commentaire, je souhaiterais faire remarquer que j'ai vu sur le forum (et d'autres forums) un algorithme (avec une variante) qui effectue un test en place, c'est-à-dire que l'algorithme ne fait pas appel à une autre chaîne. Je n'ai pas voulu recopier cet algorithme.

En effet, j'ai voulu trouver (pas inventer) un autre algorithme. Cet algorithme reconstruit le mot (ou la phrase) en l'inversant dans une chaîne puis effectue la comparaison pour savoir s'il y a palindrome.
Cet algorithme existe même s'il est moins efficace que celui qui effectue le test en place, et peut-être même plus naturel relativement à la pensée humaine (à démontrer).

Question : Quel algorithme utiliseriez vous si le langage C disposait du type chaîne de caractères ?

[Bousk]

Parcourir la chaîne des 2 cotés à la fois est le plus efficace.
Si vraiment tu veux tenter autre chose en inversant le mot, pourquoi pas, mais il y a de biens meilleurs moyens d'y parvenir, comme parcourir la chaîne et recopier chaque caractère et non passer par une autre chaîne intermédiaire pour la concaténer.

[iks37]

Merci pour les conseils.

[Sve@r]

Bonjour

Question : Quel algorithme utiliseriez vous si le langage C disposait du type chaîne de caractères ?

Pareil. Placer un index au début, un second à la fin et comparer les caractères des index en les faisant converger. Surtout que le tableau de caractères terminé par un null est tellement proche d'une string qu'on emploie souvent le terme "string" en guise de raccourci (même si concrètement ce type n'existe pas réellement).
En fait, le choix de l'algo ne se fait pas en fonction du type offert par le langage mais par les possibilités offertes par le type lui-même. Imaginons par exemple un langage nommé "boa" qui possèderait un type objet "string" et dans lequel cet objet possèderait la méthode "isPalindrome()" ben je n'aurais plus à me préoccuper de l'algo à utiliser.

PS: pas de fflush(stdin). Si c'est ton prof qui t'a dit de faire ça ben tu lui dis de venir lire cette faq.

[iks37]

Sve@r,

Votre commentaire sur l'utilisation de fflush(stdin) m'intéresse. Je connais bien la "restriction" quant à son utilisation. Je l'utilise pour vider le tampon. En effet, j'ai remarqué qu'après la saisie d'une chaîne (ou d'un caractère), sa variable ne se vide pas lorsque je relance le programme. Alors c'est cette fonction que j'utilise malgré moi pour vider le tampon.
Que me conseillez-vous ?


REMARQUE : J'apprends le langage C mais je ne suis pas un étudiant. Même si l'apprentissage commence à la naissance et prend fin à la mort.

[Sve@r]

Votre commentaire sur l'utilisation de fflush(stdin) m'intéresse. Je connais bien la "restriction" quant à son utilisation. Je l'utilise pour vider le tampon. En effet, j'ai remarqué qu'après la saisie d'une chaîne (ou d'un caractère), sa variable ne se vide pas lorsque je relance le programme. Alors c'est cette fonction que j'utilise malgré moi pour vider le tampon.
Que me conseillez-vous ?

Alors déjà éviter de mélanger les termes "variable" et "tampon". Une variable est une zone mémoire destinée à stocker des valeurs internes au programme et le "tampon" est lui-aussi une zone mémoire mais destinée à gérer des informations entrantes et sortantes du programme.
On peut vider le tampon mais on ne peut absolument pas vider une variable. Simplement parce que si une variable est destinée à stocker un truc (lu au clavier, lu dans un fichier, recopié depuis une autre variable) alors pourquoi vouloir qu'elle soit vide avant l'opération puisque de toute façon elle sera remplie après ?
Par ailleurs, le terme "vide" pour une variable a peu de sens. En effet, une variable ce sont des bits qui valent 0 ou 1 donc l'ensemble de ces bits (qui existent et sont déjà positionnés lorsque la variable est créée) formera toujours une valeur. Même tous les bits à 0 formera la valeur 0 qui reste quand-même une valeur (les hindous sont les premiers a avoir inventé le "0" mais même eux avaient du mal avec cette notion car ils la représentaient par un "point" non calculable. Ce n'est qu'avec l'algèbre inventée par les arabes que le "0" a pu prendre son essort et être enfin considéré comme un chiffre utilisable dans les calculs).

Sinon je conseille de faire comme les philosophes grecs qui, quand ils voulaient comprendre le monde, s'asseyaient pour réfléchir au fonctionnement des choses. Pourquoi vouloir vider le tampon puisqu'à la base il est déjà vide lorsque le programme se lance ? Si ce besoin était avéré, alors les concepteurs du langage auraient implémenté fflush(stdin). S'ils ne l'ont pas fait, alors c'est que ce besoin n'existe pas (devise shadock: s'il n'y a pas de solution c'est qu'il n'y a pas de problème).
Surtout qu'on associe souvent "stdin" au clavier mais cela n'est pas toujours le cas (exemple courant sous Unix/Linux (le C est intrinsèquement lié à ces deux OS car c'est en C qu'ils ont été écrits) de P1 pipé dans P2 => dans ce cas, le stdin de P2 contient le stdout de P1 => ce serait alors dommage que P2 vide son stdin parce qu'il ne sait pas quoi en faire !!!). Donc en fait, quand on sait gérer son stdin on n'a jamais besoin de le vider. Alors pourquoi toi tu veux le vider ? Parce que tu as conscience que quelque chose s'y trouve et que ce quelque chose ne devrait pas s'y trouver. Mais d'où vient-il ce "quelque chose" ? Ben il provient fatalement d'une saisie précédente qui a été mal gérée. Donc si on gère bien la saisie précédente (et par extension toutes les saisies) alors on n'aura plus besoin de vouloir vider ce tampon.

Ce qui se passe souvent, c'est que le débutant ne comprend pas vraiment ce qui se passe dans ce tampon de m.... Surtout avec scanf() qui est très vite enseigné par les profs parce qu'il faut bien avoir quelque chose pour saisir dans les TP (je le sais bien, moi aussi je l'ai fait) mais qui n'est pas une fonction adaptée au débutant (ni même adaptée à qui que ce soit d'ailleurs).
En effet, scanf() signifie "scan formaté" or ce que tape un humain est tout sauf formaté. Rentrer une string quand on attend un nombre mettra la grouille dans tout le programme et le plus dur c'est qu'on ne peut même pas le détecter car quand ça se passe on est dans scanf() et il est alors déjà trop tard.

Prenons un exemple simple: saisir un chiffre puis une chaine

Code c :

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

1
2
3
4
5
int c;
char str[100];
scanf("%d", &c);
scanf("%s", str);
printf("c=%d, str=[%s]\n", c, str);

Ben même avec la meilleure volonté de l'utilisateur, il ne pourra jamais saisir sa chaine. Parce que quand il saisit son chiffre, il valide par <return> et que ce caractère <return> symbolisé par '\n' est lui aussi stocké dans stdin. Ensuite scanf() extrait le chiffre du clavier pour le stocker dans "c" mais laisse ce '\n' car ça, ce n'est pas du chiffre (or scanf() s'arrête dès que le contenu de stdin ne correspond plus à ce qui est attendu).
Ensuite, à la saisie suivante, scanf() repart de stdin et lit ce qui s'y trouve. Et là, ben il lit le '\n' qui reste et le stocke dans "str" et ce que toi tu veux saisir ben peaudzob.

Une première solution donc sera de faire une saisie "à vide" pour purger le '\n' résiduel (et on mettra cette saisie "à vide" sur la même ligne pour que les lecteurs suivants comprennent qu'elles vont ensembles => lisibilité du code)

Code c :

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

1
2
3
4
5
int c;
char str[100];
scanf("%d", &c); fgetc(stdin);
scanf("%s", str);
printf("c=%d, str=[%s]\n", c, str);

Là ça fonctionne mieux mais cela n'empêchera tout de même pas l'utilisateur de rentrer n'importe quoi là où il faut du chiffre et foutre quand-même en l'air le truc.

Donc la solution correcte est de tout faire saisir comme string puis ensuite de traiter cette string via sscanf() (attention au nom, il y a un "s" en plus) pour en extraire de la string les trucs attendus et y laisser ce qui ne l'est pas. Ainsi, même si en fin d'opération la string tampon est pourrie de trucs laissés par sscanf() ben déjà on s'en fout parce que ça se passe "après" récupération et stdin, lui, est toujours clean.

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
char saisie[100];
int c;
char str[100];
 
// Saisie du chiffre
fgets(saisie, 100, stdin);
sscanf(saisie, "%d", &c);
 
// Saisie de la chaine
fgets(saisie, 100, stdin);
sscanf(saisie, "%s", str);
 
printf("c=%d, str=[%s]\n", c, str);

De là, ça permet ainsi de commencer à pouvoir gérer et contrôler sa saisie

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
char saisie[100];
int c;
 
while (1) {
	// Saisie du chiffre
	fgets(saisie, 100, stdin);
	if (sscanf(saisie, "%d", &c) == 1) break;	// Rappel: sscanf renvoie le nombre de conversions qu'il a pu effectuer
	printf("Erreur de saisie - Vous devez entrer un chiffre !!!\n");
}
 
printf("c=%d\n", c);

Ensuite, pourquoi pas déporter le truc dans une fonction dédiée

Code c :

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
int saisieNBR(char *prompt) {
	char saisie[100];
	int c;
 
	while (1) {
		fputs(prompt, stdout);
		fgets(saisie, 100, stdin);
		if (sscanf(saisie, "%d", &c) == 1) break;
		printf("Erreur de saisie - Vous devez entrer un nombre !!!\n");
	}
	return c;
}
 
double saisieDBL(char *prompt) {
	char saisie[100];
	double d;
 
	while (1) {
		fputs(prompt, stdout);
		fgets(saisie, 100, stdin);
		if (sscanf(saisie, "%lf", &d) == 1) break;
		printf("Erreur de saisie - Vous devez entrer un nombre !!!\n");
	}
	return d;
}
 
int main() {
	int c;
	double d;
	c=saisieNBR("Entrez un nombre entier:");
	d=saisieDBL("Entrez un nombre décimal:");
	printf("c=%d, d=%lf\n", c, d);
}

Et là, ce code est assez robuste pour gérer les soucis de saisie et fonctionnera donc même avec une saisie multiple

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
12
int main() {
	int tab[10];
	int i;
	char prompt[100];
	for (i=0; i < 10; i++) {
		sprintf(prompt, "Entrez le nombre %d :", i+1);
		tab[i]=saisieNBR(prompt);		// Punaise, qu'est-ce que j'aurais aimé pouvoir écrire tab[i]=saisieNBR("Entrez le nombre %d :", i+1) => suis trop habitué à Python moi ;)
	}
	for (i=0; i < 10; i++) {
		printf("Le nombre %d est %d\n", i+1, tab[i]);
	}
}

Voilà. Quand on sait ce qui se passe avec stdin, quand on maitrise en permanence ce qu'il contient, alors il n'est jamais besoin de le vider. Mais si par hasard ce besoin se présentait quand même, alors rien n'interdit de le faire manuellement.

Code c :

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

1
2
3
void clean_stdin() { 
	while (getchar() != EOF);
}