Erreur de segmentation

Version imprimable

Bonjour,
J'essaie de résoudre le problème 14 du site project euler qui demande de trouver le plus grand nombre inférieur à 1000000 qui produit la plus longue suite de Syracuse.
Voici mon code

Code:

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
#include <stdio.h>
#include <stdlib.h>
 
#define N 1000000
 
int tab[N];
 
int syracuse(int);
int calculNbreTermes(int);
 
int main(int argc, char * argv[])
{
    int i = 0, max = 0;
    int nbreTermes = 0, maxNbreTermes = 0;
 
    for(i = 0; i < N; ++i)
        tab[i] = 0;
 
    for(i = 1; i < 1000000; ++i)
    {
        nbreTermes = calculNbreTermes(i);
        if(nbreTermes >= maxNbreTermes)
        {
            max = i;
            maxNbreTermes = nbreTermes;
        }
    }
 
    printf("Max = %d\n", max);
    printf("Nbre de termes = %d\n", maxNbreTermes);
 
    return 0;
}
 
int syracuse(int n)
{
    if(n % 2 == 0)
        return n / 2;
    else 
        return 3 * n + 1;
}
 
int calculNbreTermes(int n)
{
    int nbreTermes = 0;
    int i = 0;
 
    if(tab[n] != 0)
        return tab[n];
 
    if(n == 1)
        return 1;
    else
    {
        tab[syracuse(n)] = calculNbreTermes(syracuse(n));
        nbreTermes = 1 + tab[syracuse(n)];
 
        return nbreTermes;
    }
}

Il marche bien pour une limite de 1000 mais au delà, j'ai une erreur de segmentation.
Je n'arrive pas à en trouver l'origine.
Un petit coup de pouce ;)

06/02/2010, 15h55
jeroman

Ton tableau est beaucoup trop gros. :calim2: Alloue plutôt de la mémoire dynamiquement (malloc).
06/02/2010, 17h21
Pouet_forever

Sans parler de la taille de ton tableau, ton erreur vient du fait que tu fais un joli dépassement.
Je m'explique, ta fonction syracuse retourne n/2 si le nombre est pair, donc là pas de problème, mais elle retourne 3*n+1 quand ton nombre est impair. Dès que ton indice arrive à environ N/3 tu vas accéder aux indices plus grands que ton tableau ;)

Note que tu peux fortement améliorer ton code. Le but étant de mémoriser les nombres où tu es déjà passé en mettant le nombre d'opérations nécessaires pour arriver à 1.

Bon courage :ccool:
06/02/2010, 22h44
diogene

Tu risques aussi des problèmes liés aux appels récursifs de calculNbreTermes() dont il est sans doute difficile d'estimer la profondeur.

Citation:

Sans parler de la taille de ton tableau, ton erreur vient du fait que tu fais un joli dépassement.

Effectivement, mais même en résolvant ce problème, j'avais toujours une erreur de segmentation qui provenait du fait que le type int ne pouvait stocker certains résultats de calculNbreTermes(). Donc, j'ai utilisé des unsigned long long à la place.
Voici le code final

Code:

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
#include <stdio.h>
#include <stdlib.h>
 
#define N 1000001
 
static unsigned long long tab[N];
 
unsigned long long syracuse(unsigned long long);
unsigned long long calculNbreTermes(unsigned long long);
 
int main(int argc, char * argv[])
{
    int i = 0, max = 0;
    unsigned long long nbreTermes = 0, maxNbreTermes = 0;
 
    for(i = 1; i < N; ++i)
    {
        nbreTermes = calculNbreTermes(i);
        if(nbreTermes >= maxNbreTermes)
        {
            maxNbreTermes = nbreTermes;
            max = i;
        }
    }
 
    printf("Max = %d\n", max);
    printf("Nbre de termes = %lld\n", maxNbreTermes);
 
    return 0;
}
 
unsigned long long syracuse(unsigned long long n)
{
    if(n % 2 == 0)
        return n / 2;
    else 
        return 3 * n + 1;
}
 
unsigned long long calculNbreTermes(unsigned long long n)
{
    if(n == 1)
        return 1;
    else
    {
        if(n < N && tab[n] != 0)
            return tab[n];
        if(n < N)
        {
            tab[n] = 1 + calculNbreTermes(syracuse(n));
            return tab[n];
        }
        else
            return 1 + calculNbreTermes(syracuse(n));
    }
}

Le résultat est 837799 qui donne une suite de 525 termes
Merci