Suite de Conway

**printf** · 05/11/2008, 20h31

Bonsoir je suis débutant en C (J'en fais que depuis septembre étant étudiant en génie électrique) et j'ai fait un programme qui affiche n termes de la suite de conway en C.
Le programme fonctionne correctement (enfin il en à l'air ^^) mais le compilateur m'indique un Warning et j'aimerais savoir pourquoi et comment corriger cela? :/

Voici l'avertissement en question:
http://img84.imageshack.us/img84/6277/43571358hi7.jpg

De plus je tiens a signaler que j'ai eu de la chance pour faire fonctionner le programme, au début mon programme ne fonctionnait pas, j'avais des erreurs de type dans les arguments de ma fonction....puis j'ai mis des pointeurs (un peu au hasard en testant et aussi en fonction des messages du compilateur.

Tout ça pour en venir à ma deuxième question: Est-on obligé de passer par des pointeurs pour faire une fonction qui retourne une chaine de char?

Voici ma fonction:

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
char* conway(char* chaine1)
{
    char chaine2[999999] = {'0'};
    chaine2[999998] = chaine1[99998] = '\0';
 
    int compteur, position = 0, c,t = 0;
 
    c = chaine1[0];
 
 
    while ((chaine1[position] != 0) || (chaine1[position] != '\0'))
    {
        compteur = '0';
        while (chaine1[position] == c)
        {
            compteur++;
            position++;
        }
        chaine2[t] = compteur;
        t++;
        chaine2[t] = c;
        t++;
        if (chaine1[position] !=0) c = chaine1[position];
    }
    return (chaine2);

et l'endroit où j'appelle cette fonction:

Code :

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

strcpy(chaine1,conway(chaine1));

Est ce que ce code est correct?

Voilà je remercie d'avance l'âme charitable qui pourra m'aider

**ram-0000** · 05/11/2008, 20h39

Salut,

Tuas de la chance que ton programme fonctionne.
Ton code:

Code :

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

1
2
3
4
5
6
7
 
char* conway(char* chaine1)
{
    char chaine2[999999] = {'0'};
...
   return chaine2;
}

Ta fonction retourne l'adresse d'une variable locale à ta fonction. chaine2 est une variable locale donc elle est "construite" sur la pile. Lorsque tu quittes ta fonction, ta pile est réutilisée et donc ta variable est très probablement modifiée. Donc tu risques d'utiliser quelquechose qui est modifié à ton insu.

Dans ton cas, ce qu'il faut faire, c'est allouer de la mémoire, travailler sur ce bloc de mémoire allouée et retourner ce bloc de mémoire.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
char* conway(char* chaine1)
{
    char *chaine2 = malloc(999999);
    if(chaine2 == NULL)
    {
        /* traitement d'erreur allocation mémoire */
    }
    memset(chaine2, 0, 999999);
...
    return chaine2;
}

Attention, il ne faut pas que l'appelant oublie de libérer le bloc de mémoire

**printf** · 05/11/2008, 21h04

Whoo merci pour la réponse super rapide !

Outch, mais en fait on a jamais vu malloc() et memset() en cours

Ma question se ramène alors à:

Existe-il une autre manière pour affecter ma chaine1 (qui est dans la fonction main() )
de chaine2 dans la fonction secondaire ?

**ram-0000** · 05/11/2008, 21h35

Oui mais a ce compte la, les 2 chaines appartiennent à l'appelant et ta fonction ne fait que les modifier. un truc comme cela

Code :

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

1
2
3
4
5
6
7
8
9
 
char* conway(int taille_chaine, char* chaine1, char* chaine2)
{
    char chaine2[taille_chaine] = {'0'};
    chaine2[taille_chaine - 1] = chaine1[taille_chaine - 1] = '\0';
 
...
    return chaine2;
}

et l'appel maintenant:

Code :

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

1
2
3
4
5
6
7
 
...
char chaine1[1000000];
char chaine2[1000000];
 
strcpy(chaine1,conway(1000000 - 1, chaine1, chaine2));
...

**printf** · 08/11/2008, 10h26

Merci pour l'aide, je pige un peu mieux maintenant

J'ai d'autres petites questions:
Quand on initialise une chaine de cette sorte:

Code :

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

char chaine1[1000000] = {'1'};

Le caractère de fin " \0 " se met il automatiquement après le '1' ?

Si oui, est-ce que je peux faire ça:

Appel:

Code :

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

1
2
3
4
5
6
...
char chaine1[1000000] = {'1'};
char chaine2[1000000] = {'0'};
 
strcpy(chaine1,conway(chaine1, chaine2));
...

Code :

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

1
2
3
4
5
6
char* conway(char* chaine1, char* chaine2)
{
 
...
    return chaine2;
}

Donc en gros ne pas me servir de la variable taille_chaine...c : ? :

PS: En tout cas j'ai testé et ça marche, après je ne sais pas si ça peut faire des conflits ou autre erreurs...

PS2: Il est normal qu'au bout de beaucoup d'itérations les termes de cette suite deviennent imposants... déjà a partir de la 20eme répétition, le terme X20 prend 6 ligne de la console.

Moi l'utilisateur ne doit pas demander un terme supérieur a 100, donc le max est de 99.
Voilà ce qu'il se passe quand j'affiche tous les terme jusque 99:
http://img373.imageshack.us/my.php?image=conwayvv3.jpg

Alors la console défile tellement et les termes deviennent tellement long qu'on ne peut même plus remonter tout en haut de la console (pour voir la définition de la suite), et on ne peut même pas lire le terme X99 dans sa totalité.

Est ce normal?

**printf** · 11/11/2008, 13h03

Bon le problème du warning est réglé mais j'ai un nouveau problème! yaisse2: ^^

Mon programme affiche d'abord les 5 premiers termes de la suite puis demande à l'utilisateur de choisir un terme dont il veut la solution (<100). Jusqu'ici tout va bien, je teste avec des petites valeurs du genre X12, X20...le programme fonctionne...

Mais à partir de X50, le programme plante!

Je demande X49, ça marche... mais X50..X51....X99...ça plante

Voici le code source, ça fait 5 jours que je m'arrache les cheveux:

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
 
 
char* conway(char*,char*);
 
void main(void)
{
    int i,terme;
    char chaine1[999999] = {'1','\0'};
    char chaine2[999999] = {'\0'};
 
 
 
    printf("\t************************************************************\n");
    printf("\t*** Suite 'Look and Say' de J.H.Conway, Par Nicolas xxxx ***\n");
    printf("\t************************************************************\n");
    printf("\n(*) Dans cette suite, un terme se determine en annoncant les chiffres formant \nle terme precedent:\n\n");
 
    printf("X00=1\n");
 
    for(i = 1; i <= 5; i++)
    {
        strcpy(chaine1,conway(chaine1, chaine2));
        printf("X%02i=",i);
        printf("%s\n",chaine1);
    }
 
    while (terme > 99)
    {
        printf("\n(**) Veuillez choisir le terme dont vous voulez la solution (inferieur a 100):\n--> ");
        scanf("%i",&terme);
        if (terme < 6)
        {
            while (terme < 6)
            {
                printf("Entrez un nombre superieur a 5, vous avez deja les 5 premier termes");
                scanf("%i",&terme);
            }
        }
    }
 
        for(i = 6; i <= terme; i++)
    {
        strcpy(chaine1,conway(chaine1,chaine2));
        printf("\nX%02i=",i);
        printf("%s\n",chaine1);
    }
    system("pause");
 
 
}
 
//FONCTIONS
char* conway(char* chaine1, char* chaine2)
{
    *chaine2 = '\0';
 
    int compteur, position = 0, c,t = 0;
 
    c = chaine1[0];
 
 
    while (chaine1[position] != '\0')
    {
        compteur = '0';
        while (chaine1[position] == c)
        {
            compteur++;
            position++;
        }
        chaine2[t] = compteur;
        t++;
        chaine2[t] = c;
        t++;
        if (chaine1[position] != '\0') c = chaine1[position];
    }
    return (chaine2);
 
}

**diogene** · 11/11/2008, 15h10

Mais à partir de X50, le programme plante!
Je demande X49, ça marche... mais X50..X51....X99...ça plante

Probablement, le nombre de termes dépasse la capacité de stockage de ton tableau (999999) : La croissance du nombre de termes est exponentielle.

**printf** · 11/11/2008, 15h45

Malheureusement le problème ne vient pas de là(enfin je pense), car j'ai beau agrandir le tableau de caractères, ça plante toujours...

De plus mon ancien code source fonctionnait jusque X99 avec [999999], le seul problème est qu'il retournait une adresse de variable locale. :/

Je suis bien embêté

**diogene** · 11/11/2008, 15h54

Envoyé par printf

Malheureusement le problème ne vient pas de là(enfin je pense), car j'ai beau agrandir le tableau de caractères, ça plante toujours...

De plus mon ancien code source fonctionnait jusque X99 avec [999999], le seul problème est qu'il retournait une adresse de variable locale. :/

Je suis bien embêté

Si il s'agit du code posté en 1, le fait qu'il fonctionne avec des indices élevés est lié à ce que tu tronques la suite entrante à cause d'une faute de frappe. Le résultat est alors faux (ou incomplet) pour les indices élevés.

Code :

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

    chaine2[999998] = chaine1[99998] = '\0';

**printf** · 11/11/2008, 16h12

Ok! Merci je n'avais pas vu cette erreur.

Mais j'initialise mes tableau à:

Code :

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

1
2
    char chaine1[1009000] = {'1','\0'};
    char chaine2[1009000] = {'\0'};

et le programme plante toujours à X50 :/
Ensuite su j'init à:

Code :

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

1
2
    char chaine1[1090000] = {'1','\0'};
    char chaine2[1090000] = {'\0'};

Le programme plante carremment des que je le lance... peut être qu'il supporte pas d'aussi grandes chaines.

**coyotte507** · 11/11/2008, 16h21

Salut,

une petite remarque: tu n'initialises pas ta variable terme avant de l'utiliser.

Sinon, diogène a raison:

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
 
 
char* conway(char*,char*);
 
int main(void)
{
    int i,terme = 0;
    char chaine1[999999] = {'1','\0'};
    char chaine2[999999] = {'\0'};
 
 
 
    printf("\t************************************************************\n");
    printf("\t*** Suite 'Look and Say' de J.H.Conway, Par Nicolas xxxx ***\n");
    printf("\t************************************************************\n");
    printf("\n(*) Dans cette suite, un terme se determine en annoncant les chiffres formant \nle terme precedent:\n\n");
 
    printf("X00=1\n");
 
    for(i = 1; i <= 5; i++)
    {
        strcpy(chaine1,conway(chaine1, chaine2));
        printf("X%02i=",i);
        printf("%s\n",chaine1);
    }
 
    while (terme < 6)
    {
        printf("\n(**) Veuillez choisir le terme dont vous voulez la solution (inferieur a 100):\n--> ");
        scanf("%i",&terme);
        if (terme < 6)
        {
            while (terme < 6)
            {
                printf("Entrez un nombre superieur a 5, vous avez deja les 5 premier termes");
                scanf("%i",&terme);
            }
        }
    }
 
    for(i = 6; i <= terme; i++)
    {
        strcpy(chaine1,conway(chaine1,chaine2));
        printf("\nX%02i=",i);
        printf("%i\n",strlen(chaine1));
    }
 
    return 0;
}
 
//FONCTIONS
char* conway(char* chaine1, char* chaine2)
{
    *chaine2 = '\0';
 
    int compteur, position = 0, c,t = 0;
 
    c = chaine1[0];
 
 
    while (chaine1[position] != '\0')
    {
        compteur = '0';
        while (chaine1[position] == c)
        {
            compteur++;
            position++;
        }
        chaine2[t] = compteur;
        t++;
        chaine2[t] = c;
        t++;
        if (chaine1[position] != '\0') c = chaine1[position];
    }
    return (chaine2);
}

Quand on fait 49, la longueur de la chaine vaut 894 810 caractères!
Donc quand on fait 50, elle fait certainement plus de 999 999.

**coyotte507** · 11/11/2008, 16h23

Si tu veux faire des très grandes chaines sans utiliser malloc, il faut rajouter une option de compilation pour "agrandir la taille de la pile" (tu trouveras surement sur internet).
Néanmoins c'est pas conseillé...

**diogene** · 11/11/2008, 16h23

Envoyé par printf

....
Ensuite su j'init à:

Code :

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

1
2
    char chaine1[1090000] = {'1','\0'};
    char chaine2[1090000] = {'\0'};

Le programme plante carremment des que je le lance... peut être qu'il supporte pas d'aussi grandes chaines.

Tes tableaux sont des variables locales. La taille des variables locales est limitée (Elles sont construites sur la pile). Pour avoir des variables de très grande taille, les placer en globales ou utiliser l'allocation dynamique (malloc...)

**printf** · 11/11/2008, 16h54

Encore merci pour vos explications.
Donc si j'ai bien compris c'est un problème de mémoire...
Et je ne connais pas malloc() et je n'ai jamais vu les variables globales en cours, j'viens de voir sur le net que ça se déclarait en dehors des fonctions...le prof nous en a même pas parlé.

Sinon est-ce qu'un tableau d'entier use moins de mémoire qu'un tableau de caractères?

**diogene** · 11/11/2008, 16h58

Envoyé par printf

Encore merci pour vos explications.
Donc si j'ai bien compris c'est un problème de mémoire...
Et je ne connais pas malloc() et je n'ai jamais vu les variables globales en cours, j'viens de voir sur le net que ça se déclarait en dehors des fonctions...le prof nous en a même pas parlé.

Sinon est-ce qu'un tableau d'entier use moins de mémoire qu'un tableau de caractères?

Non. Il n'y a pas de plus petite chose adressable qu'un char.

**printf** · 11/11/2008, 17h02

Ah bah j'ai fais ça;

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
    char chaine1[99999999] = {'1','\0'};
    char chaine2[99999999] = {'\0'};
 
char* conway(char*,char*);
 
void main(void)
{
    int i,terme = 100;

et ça à l'air de marcher, par contre ça met un temps fou. xD

**diogene** · 11/11/2008, 17h15

Avec des tableaux de cette taille, tu dois pouvoir aller un peu au dessus de 65 comme indice, mais pas beaucoup plus.
Bien sûr que ça va prendre beaucoup de temps de calculer sur ~100 millions de caractères

**printf** · 12/11/2008, 11h53

Bon bah j'agrandis "à taton" la taille des tableaux, car je ne sais pas comment déterminer la taille du terme 99 de cette suite.... Mais là je suis arrivé à:

Code :

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

1
2
char chaine1[1000000000] = {'1','\0'};
char chaine2[1000000000] = {'\0'};

Le compilateur met un certain temps a linker puis le programme "plante" au démarrage.

Process returned 0 (0x0) execution time: 0.025s

Je suppose que j'ai dépassé le max pour la déclaration des tableau?

**Emmanuel Delahaye** · 12/11/2008, 12h38

Envoyé par printf

Je suppose que j'ai dépassé le max pour la déclaration des tableau?

Code :

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

1
2
3
4
5
6
7
8
9
 
#include <stdio.h>
 
int main (void)
{
   printf ("Sur cette plateforme, un tableau ne peut pas avoir plus de %lu elements\n",
           (unsigned long) (size_t) (-1));
   return 0;
}

Code :

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

1
2
3
4
5
 
Sur cette plateforme, un tableau ne peut pas avoir plus de 4294967295 elements
 
Process returned 0 (0x0)   execution time : 0.025 s
Press any key to continue.