Discussion :

[groscask]

Ah, voilà, j'ai enfin réussi en me basant sur tes fonctions :
char * con(char * s1, char * s2);
char * mir(char * chaine);

A faire un code récursif, qui marche, et sans utiliser d'allocation dynamique

Mon main est celui-ci :

Code :

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

1
2
3
4
5
6
7
8
9
int main(void)
{
    char chaine[200] = "Hello World ! Encore une victoire de canard !";
    printf("%s\n", chaine);
    mir(chaine);
    printf("%s\n", chaine);
 
    return 0;
}

Enfantin !

Alors, étant donné que je ne veux pas donner la solution complète, voici déjà l'algorithme :

Code :

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

1
2
3
4
5
6
7
8
9
10
con(a, b):
retourner (a + b)
 
mir(chaine):
si la chaine fait plus d un élément:
    préparer une chaine temporaire 'tmp' contenant les n/2 premiers caractères.
    préparer une chaine temporaire 'tmp2' contenant les n/2 derniers caractères de la chaine.
    chaine <- con(mir(tmp2), mir(tmp1))
fin si
retourner chaine

Les seules fonctions que j'ai utilisées sont strncpy (pour préparer les chaines temporaires), strcpy et strcat.

A toi de l'implémenter N'hésite pas à demander si tu as besoin d'aide ;-)

[Médinoc]

Mais dans ce code, tu as quand même besoin de copies temporaires de la sous-chaîne entière.

Je pense qu'on peut y parvenir sans:

Code algo :

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
//Echanger les deux char référencés en passant par un temporaire.
echanger_chars(ref rc1 : char, ref rc2 : char) :
	VARIABLES:
		tmp : char
	tmp := rc1
	rc1 := rc2
	rc2 := tmp

//Echanger deux chaînes de même longueur,
//en échangeant leur caractères un à un.
echanger_chaines(s1 : ptr char, s2 : ptr  char, lg : size_t) :
	VARIABLES:
		i : size_t
	POUR i DE 0 À lg-1:
		echanger_chars(ref s1[i], ref s2[i])

//Miroirise les deux "moitiés" de la chaîne
//(si la chaîne est de longueur impaire, le caractère du milieu reste en place)
//Puis les échange
miroir( s : ptr char, lg : size_t ) :
	VARIABLES:		
		lg2 : size_t
	lg2 := lg/2
	miroir(s, lg2)
	miroir(s+lg-lg2, lg2)
	echanger_chaines(s, s+lg-lg2)

Note: le paramètre indique bien la longueur de la chaîne (en caractères) et non sa taille de stockage (en clair, le zéro terminal, s'il existe, n'est pas compté)

[groscask]

C'est ce que je voulais faire - sensiblement -, seulement les prototypes de fonction définis dans le premier post du sujet ne me le permettaient pas : en effet, on ne spécifie jamais la taille !

D'où mes multiples copies...
Mais si l'on regarde bien, nous avons le même algo, sauf que le fait de préciser la taille te permet d'éviter les copies

J'ai par contre une petite question : quand est-ce que la récursivité peut s'arrêter dans la tienne ?

Code :

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

1
2
3
4
5
6
7
8
9
 
miroir( s : ptr char, lg : size_t ) :
    SI lg > 1 ALORS:
        VARIABLES:  
            lg2 : size_t
        lg2 := lg/2
        miroir(s, lg2)
        miroir(s+lg-lg2, lg2)
        echanger_chaines(s, s+lg-lg2)

Ne serait-il pas mieux ? Ou quelque chose d'approchant... Mais je me trompe peut-être, auquel cas, j'aimerais beaucoup être éclairé !

[yous18]

Alors, étant donné que je ne veux pas donner la solution complète, voici déjà l'algorithme :

Code :

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

1
2
3
4
5
6
7
8
9
10
con(a, b):
retourner (a + b)
 
mir(chaine):
si la chaine fait plus d un élément:
    préparer une chaine temporaire 'tmp' contenant les n/2 premiers caractères.
    préparer une chaine temporaire 'tmp2' contenant les n/2 derniers caractères de la chaine.
    chaine <- con(mir(tmp2), mir(tmp1))
fin si
retourner chaine

Les seules fonctions que j'ai utilisées sont strncpy (pour préparer les chaines temporaires), strcpy et strcat.

A toi de l'implémenter N'hésite pas à demander si tu as besoin d'aide ;-)

merci bcp groscask
les variable temp1 et temp2 sont des pointeurs de type char ou des tableau de char ?
car s'il sont des tableau ça sera le meme code que moi sauf moi j'ai mis tab1 et tab2 ... n'est ce pas ?
et s'il sont des tableau alors c'est le meme code que je®ome

Code :

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

1
2
3
4
5
6
7
8
9
mir : ab(0022FE50) = a(0022FD30) + b(0022FCC0)
mir : a = a(0022FD30)
mir : b = b(0022FCC0)
con : b(0022FCC0) + a(0022FD30) = ba(0022FCC0)
mir : cd(0022FDE0) = c(0022FD30) + d(0022FCC0)
mir : c = c(0022FD30)
mir : d = d(0022FCC0)
con : d(0022FCC0) + c(0022FD30) = dc(0022FCC0)

pourquoi il y a des meme valeures quand on utilise des tableau ?

[Médinoc]

Est-ce qu'on a le droit de faire un strlen et passer la taille à la fonction récursive ?

[groscask]

Comme je l'ai dit, je me suis basé sur les prototypes du début de ce post :

Code :

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

1
2
3
 
char* con(char mot[] , char Mot[] );   
char* mir(char mot[]);

Donc non, la taille n'est jamais passée !

Et sinon, je dirai que la meilleure méthode reste l'échange symétrique des caractères deux à deux (bien que je n'en soit pas sur), qui n'implique *que* un swap entre deux char...
Mais là, on s'éloigne encore beaucoup du prototype d'origine... Reste donc à savoir s'il s'agissait d'une contrainte ou non ;-)

[yous18]

En fait, dans ta version, tu déclares les tableaux par

Code :

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

char tab1[N], tab2[N];

les espaces mémoire vers lesquels pointent tab1 et tab2 sont alloués dès que tu appelles la fonction. Dans la solution de je®ome, les espaces mémoire sont alloués dynamiquement.

Si tu regardes quelle est la valeur des pointeurs dans ton implémentation, par exemple en faisant ceci

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
char *con(char mot[],char Mot[]) {
    int i, m=strlen(mot), n=strlen(Mot);
 
    printf("con : %s(%p) + %s(%p) = ",mot,mot,Mot,Mot);
 
    for(i=0;i<n;i++) {
        mot[m+i] = Mot[i];
    }
    mot[m+i] = '\0';
 
    printf("%s(%p)\n",mot,mot);
 
    return mot;
}
 
char *mir(char mot[]) {
    int i, m=strlen(mot);
    char tab1[N], tab2[N];
    if( m != 1 ) {// le test d'arret quand le mot contient un seul caractère
        for (i=0;i<m/2;i++) {// je divise en deux voici la 1ér facteur
            tab1[i]=mot[i];
        }
        tab1[i]='\0';
 
        for (i=m/2;i<=m;i++) {// le 2ème
            tab2[i-(m/2)]=mot[i];
        }
 
        printf("mir : %s(%p) = %s(%p) + %s(%p)\n",mot,mot,tab1,tab1,tab2,tab2);
 
        return con(mir(tab2),mir(tab1)); // la recursivité
    } else {
        printf("mir : %s = %s(%p)\n",mot,mot,mot);
        return mot;
    }
}

tu te rends compte qu'il y a des pointeurs qui sont conservés et donc des espaces mémoires qui sont écrasés. Par exemple, si tu traites la chaine "abcd", il t'affiches :

Code :

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

1
2
3
4
5
6
7
8
9
10
mir : abcd(0022FF00) = ab(0022FE50) + cd(0022FDE0)
mir : ab(0022FE50) = a(0022FD30) + b(0022FCC0)
mir : a = a(0022FD30)
mir : b = b(0022FCC0)
con : b(0022FCC0) + a(0022FD30) = ba(0022FCC0)
mir : cd(0022FDE0) = c(0022FD30) + d(0022FCC0)
mir : c = c(0022FD30)
mir : d = d(0022FCC0)
con : d(0022FCC0) + c(0022FD30) = dc(0022FCC0)
con : dc(0022FCC0) + dc(0022FCC0) = dcdc(0022FCC0)

On voit ainsi, sur la première ligne (décomposition de "abcd"), que la fonction mir donne a tab1 et tab2 les valeurs 0022FE50 et 0022FDE0. Pour la décomposition de "ab" et de "cd", la fonction donne à tab1 et tab2 les mêmes valeurs (0022FD30 et 0022FCC0) alors qu'il y a deux appels différents.

Je ne sais pas si l'absence d'allocation dynamique est la cause de ce problème, il faut peut-être attendre la réponse d'experts.

j'ai pas bien compris corentin59 ? vous pouvez encors m'expliquer ?