Discussion :

[souviron34]

ya déjà eu tout un thread là-dessus :

http://www.developpez.net/forums/sho...d.php?t=278583

[koala01]

Salut,

Une idée en passant, bien que ce ne soit qu'une idée...

Si le résultat évolue "par pallier", en fonction de n, il ne serait sans doute pas impossible, sur base d'un échantillon représentatif de resultats, de retrouver la logique d'évolution des palliers...

Partant de là, on pourrait vraissemblablement gagner pas mal de temps à l'exécution en ne calculant que les différents palliers, et le résultat serait le pallier de la borne supérieure...

Maintenant, il faut trouver la logique à suivre pour y arriver

[scriptoff]

: ce n'est pas exact.

Pourquoi ?
j'ai bien dit pour n=>5 que G(n)=1+G(n-3)

[koala01]

Pourquoi ?
j'ai bien dit pour n=>5 que G(n)=1+G(n-3)

Simplement parce que, si tu as un pallier à 5 et le suivant, ne serait-ce qu'à 16... tu n'es pas sur que le résultat soit équivalent à 1+G(n-3) de manière systématique (la valeur suivante pouvant arriver aussi bien à 16 qu'à ...)

[scriptoff]

Simplement parce que, si tu as un pallier à 5 et le suivant, ne serait-ce qu'à 16... tu n'es pas sur que le résultat soit équivalent à 1+G(n-3) de manière systématique (la valeur suivante pouvant arriver aussi bien à 16 qu'à ...)

faut le prouver par recurrence mais ca je vais pas le faire

[koala01]

faut le prouver par recurrence mais ca je vais pas le faire

La récursivité peut etre très facile à implémenter, mais pour le moins longue (surtout pout n <=50, ca commence à prendre du temps )

Voici le code de la fonction récursive:

Code :

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

1
2
3
4
5
6
7
8
9
int G(int i)
{
    if(i==1)
        return 1;
    else
    {
            return 1+G(i-G(G(i-1)));
    }
}

aussi simple que cela

Le résultat obtenu (quelques valeurs...avec les palliers)

Code :

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

1
2
3
4
5
6
7
8
9
10
 
resultat   valeur de N
    1              1
    2              2
    3              4
    4              6
    5              9
    6              13
    7              16
    8              20

[Superne0]

La récursivité peut etre très facile à implémenter, mais pour le moins longue (surtout pout n <=50, ca commence à prendre du temps )

Voici le code de la fonction récursive:

Code :

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

1
2
3
4
5
6
7
8
9
int G(int i)
{
    if(i==1)
        return 1;
    else
    {
            return 1+G(i-G(G(i-1)));
    }
}

aussi simple que cela

Le résultat obtenu (quelques valeurs...avec les palliers)

Code :

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

1
2
3
4
5
6
7
8
9
10
 
resultat   valeur de N
    1              1
    2              2
    3              4
    4              6
    5              9
    6              13
    7              16
    8              20

ça c'est la méthode récursive non-terminale, la base quoi ...
Mais si t'arrives à faire de même avec la terminale, alors il y a de fortes chances que le problème soit résolu : en non terminale, entres n=100000.
Tu vas voir le temps qu'elle met ...

[koala01]

ça c'est la méthode récursive non-terminale, la base quoi ...
Mais si t'arrives à faire de même avec la terminale, alors il y a de fortes chances que le problème soit résolu : en non terminale, entres n=100000.
Tu vas voir le temps qu'elle met ...

il faut meme pas entrer 10000... Déjà rien qu'aux alentours de 60, ca commence à "patiner" sur mon "antique" athlon 170 XP ...

[fearyourself]

Code :

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

1
2
3
4
5
6
7
8
9
10
 
resultat   valeur de N
    1              1
    2              2
    3              4
    4              6
    5              9
    6              13
    7              16
    8              20

Es-tu sûr de tes résultats, l'algo sur lequel je bosse me donne ceci :

Code :

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

1
2
3
4
5
6
7
8
9
10
resultat   valeur de N
    1              1
    2              2
    3              4
    4              6
    5              9
    6              12
    7              16
    8              20

Jc

[Superne0]

En récursif non terminal, il me renvoie aussi 12 pour n=6.
Mais pour n=13 et 14, G(n) est aussi égal à 6.
Et quand n=16, G(n)=17, ça c'est sûr ...

[fearyourself]

Quand n=16, G(n)=17, ça c'est sûr ...

Hmm quand n=16, g(n) =7...

Jc

[Superne0]

Oui c'est une erreur de frappe de ma part ... c'est bien 7 et non 17.
Voici mon algo en récursif non-terminal :

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
#include <stdio.h>
 
int golomb(int n){
	if(n==1){
		return(1);
	}else{
		return(1+golomb(n-golomb(golomb(n-1))));
	}
}
 
int main(){
	int n;
	scanf("%d",&n);
	printf("%d\n",golomb(n));
	return(0);
}

[fearyourself]

Ok, je me suis intéressé à ce cas puisque c'est quelque chose qu'on ne voit pas trop souvent et que je voulais voir ce qu'on pouvait faire...

La problématique est de résoudre le calcul de cet suite :

Code :

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

g(n) = 1 + g(n - g(g(n-1)))

Le plus rapidement possible et de facon intelligente.

En reprenant l'idée que nous pouvions stocker les palliers de cette facon :

Code :

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

1
2
3
4
5
6
7
8
9
resultat   valeur de N
    1              1
    2              2
    3              4
    4              6
    5              9
    6              13
    7              16
    8              20

Je me suis dit qu'on pouvait créer un tableau contenant ces valeurs. Ensuite, si on cherche une valeur, il nous reste à trouver la bonne case et récupérer la valeur.

Ceci est monnaie courante dans ce genre de problèmatique.

Du coup, j'ai écrit un code qui écrivait un tableau dans un fichier. Lorsque le programme commence, il lit ce fichier, le met en mémoire et calcule tous les entiers jusqu'à un certain seuil passé en ligne de commande.

Lorsqu'il est en train de calculer les valeurs pour la première fois, c'est plus lent mais lors de la deuxième exécution, c'est beaucoup plus rapide.

Ensuite, il affiche le tableau qu'on pourrait mettre dans un code C pour l'utiliser comme j'ai fait sans devoir le charger (voir la fin du post).

Je vais présenter le code rapidement :

Les structures de base, nous allons avoir un tableau qui contiendra le minimum, maximum et valeur des palliers et une structure contenant le tableau des palliers et sa taille.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
/* Structures de base */
typedef struct sTab {
    unsigned int min;
    unsigned int max;
    unsigned int val;
}STab;
 
typedef struct sInfo{
    STab *tab;
    size_t size_alloc;
    size_t size_used;
}SInfo;

Les fonctions utilisatrices seront :

Code :

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

1
2
3
4
5
6
7
8
 
static void Info_affiche(SInfo *info); 
static int Info_ajouteElem(SInfo *info, unsigned int nbr, unsigned int val); 
static SInfo* Info_lireFichier(char *file); 
static int Info_memeValeurQueFin(SInfo *info, unsigned int val); 
static int Info_ecrireFichier(SInfo *info, char *file); 
static int Info_plusGrandQueFin(SInfo *info, unsigned int nbr); 
static unsigned int Info_rechercheVal(SInfo *info, unsigned int nbr);

Je pense que les noms sont assez représentatives de ce qu'elles font.

Ensuite, le main est défini comme suit :

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
 
/* Main */
int main(int argc, char **argv)
{
    SInfo *info;
    unsigned int i;
    unsigned long max;
    char *endptr;
 
    if(argc != 2) {
        printf("Usage : %s <Limite>\n", argv[0]);
        return EXIT_FAILURE;
    }
 
    max = strtol(argv[1], &endptr, 0);
 
    if(*endptr != '\0') {
        printf("Erreur avec le parametre\n");
        return EXIT_FAILURE;
    }
 
    info = Info_lireFichier("reponse.txt");
    for(i=1;i<max;i++) {
        g(info, i);
    }
    printf("Ecriture %d\n",Info_ecrireFichier(info, "reponse.txt"));
    Info_affiche(info);
 
    if(info != NULL) {
        free(info->tab);
    }
    free(info);
 
    return EXIT_SUCCESS;
}

Comme vous voyez, il lit le fichier, lance une boucle pour les calculs, affiche le tableau et ecrit dans le fichier...

La fonction g est définie comme 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
37
38
39
40
41
42
43
 
/* Calcul de g */
unsigned int g(SInfo *info, unsigned int nbr)
{
    unsigned int val;
 
    if(info == NULL) {
        return -1;
    }
 
    /* On regarde si on est plus petit que la derniere valeur */
    if(Info_plusGrandQueFin(info, nbr) == 0) {
        /* Recherche dichotomique */
        return Info_rechercheVal(info, nbr);
    }
 
    /* Condition finale */
    if(nbr==1) {
        val = 1;
    }
    else {
        /* Nouveau nombre a tester */
        val = 1 + g(info, nbr - g(info, g(info, nbr-1)));
        if(val > nbr) {
            printf("Bizarre\n");
            exit(1);
        }
    }
 
    /* On regarde si c'est la meme valeur que la derniere du tableau */
    if(Info_memeValeurQueFin(info, val)) {
        /* On met a jour */
        info->tab[info->size_used - 1].max = nbr;
    }
    else {
        /* On ajoute */
        if(Info_ajouteElem(info, nbr, val)<0) {
            fprintf(stderr, "Erreur dans l'ajout d'un element\n");
            exit(EXIT_FAILURE);
        }
    }
    return val;
}

Nous avons d'abord un test pour savoir si la valeur est dans le tableau, si c'est le cas, une recherche dichotomique récupère la valeur.

Sinon, on calcule le nombre avec la récursivité et la condition finale et on regarde si c'est la même valeur que le dernier pallier. Si c'est le cas, on étend ce pallier, sinon on ajoute la valeur.

Ceci permet de calculer les nombres avec ces temps. BS est la borne supérieure de la boucle dans le main. Du coup, si BS==1000, on calcule les 1000 premiers nombres.

Ces temps ont été calculés en compilant avec gcc 4.1.2 en -O3. Le fichier avait à chaque fois le minimum de palliers pour le calcul, c'est à dire que pour le temps à 1000 élément, le fichier avait juste les palliers pour les nombres de 1 à 1000. Et j'ai pris le premier temps obtenu...

Je me suis arrêté à 800 millions parce que c'est la première fois que je dépassais une minute...

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
BS 		NbrPalliers 	Temps
1000		86		0.017s
10000		356		0.020s
100000		1479		0.030s
1000000		6137		0.098s
10000000	25474		0.728s
100000000	105729		7.448s
200000000	162271		15.152s
500000000	285872		37.890s
800000000	382226		64.104s

Enfin voici le code complet :

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
#include <stdlib.h>
#include <stdio.h>
 
 
/* Structures de base */
typedef struct sTab {
    unsigned int min;
    unsigned int max;
    unsigned int val;
}STab;
 
typedef struct sInfo{
    STab *tab;
    size_t size_alloc;
    size_t size_used;
}SInfo;
 
/* Afficher la structure comme si c'etait du code C*/
void Info_affiche(SInfo *info)
{
    unsigned int i;
    if(info != NULL) {
        printf("Tableau :\n");
        printf("typedef struct sTab {\n\tunsigned int min,max,val;\n}STab;\n");
        printf("STab tab[%d] = {\n", info->size_used);
 
        for(i=0;i<info->size_used-1;i++) {
            printf("{ %u, %u, %u }, ", info->tab[i].min, info->tab[i].max, info->tab[i].val);
            if((i+1)%10==0) {
                printf("\n");
            }
        }
        printf("{ %u, %u, %u }};\n", info->tab[i].min, info->tab[i].max, info->tab[i].val);
    }
}
 
/* Ajoute un element dans la table, gere l'allocation memoire */
int Info_ajouteElem(SInfo *info, unsigned int nbr, unsigned int val)
{
    if(info == NULL) {
        return -1;
    }
 
    /* Teste la taille */
    if(info->size_used >= info->size_alloc) {
        /* Allocation de plus d'espace */
        size_t newsize;
        STab *tmp;
 
        newsize = info->size_alloc * 2 + 1;
        tmp = realloc(info->tab, sizeof(*(info->tab)) * newsize);
 
        if(tmp == NULL) {
            return -1;
        }
 
        info->tab = tmp;
        info->size_alloc = newsize;
    }
 
    /* Ajoute un element */
    info->tab[info->size_used].min = nbr;
    info->tab[info->size_used].max = nbr;
    info->tab[info->size_used].val = val;
    info->size_used++;
 
    return 0;
}
 
/* Lire le fichier pour charger le tableau */
SInfo* Info_lireFichier(char *file)
{
    FILE *f = fopen(file, "r");
    size_t tmp;
    SInfo *res;
 
    /* Allocation */
    res = malloc(sizeof(*res));
 
    if(res == NULL) {
        fclose(f);
        return NULL;
    }
 
    res->tab = NULL;
    res->size_used = 0;
    res->size_alloc = 0;
 
    if(f==NULL){
        return res;
    }
 
    /* Lire la taille */
    if(fread(&tmp, 1, sizeof(tmp), f) == 0) {
        fclose(f);
        return res;
    }
 
    /* Allocation */
    res->tab = malloc(sizeof(*(res->tab))*tmp);
    if(res == NULL) {
        fclose(f);
        return res;
    }
    res->size_alloc = tmp;
 
    /* On lit le fichier */
    if(fread(res->tab, sizeof(*(res->tab)), tmp, f) != tmp) {
        fclose(f);
        return res;
    }
    res->size_used = tmp;
 
    fclose(f);
    /* Retourne la structure */
    return res;
}
 
/* Regarde si le dernier element a la meme valeur */
int Info_memeValeurQueFin(SInfo *info, unsigned int val)
{
    /* Si la table est vide */
    if(info==NULL) {
        return 0;
    }
 
    /* Si la taille est nulle */
    if(info->size_used == 0) {
        return 0;
    }
 
    /* Retourne le test booleen */
    return (info->tab[info->size_used-1].val == val);
}
 
/* Ecrire dans un fichier la structure */
int Info_ecrireFichier(SInfo *info, char *file)
{
    FILE *f;
 
    if(info == NULL) {
        return 0;
    }
 
    f = fopen(file, "w");
    if(f==NULL) {
        return -1;
    }
 
    /* Ecrire la taille de la table interne */
    if(fwrite(&(info->size_used),1, sizeof(info->size_used), f)==0) {
        printf("Erreur avec l'ecriture de la taille\n");
        fclose(f);
        return -1;
    }
 
    /* Ecrire la table */
    if(fwrite(info->tab, sizeof(*(info->tab)), info->size_used, f)!=info->size_used) {
        fclose(f);
        return -1;
    }
 
    fclose(f);
    return 1;
}
 
/* Est-ce que le dernier element est plus petit que nbr */
int Info_plusGrandQueFin(SInfo *info, unsigned int nbr)
{
    /* Si info==NULL alors oui */
    if(info==NULL) {
        return 1;
    }
 
    /* Si aucun element alors oui */
    if(info->size_used == 0) {
        return 1;
    }
 
    /* Sinon on teste */
    return (info->tab[info->size_used-1].max < nbr);
}
 
/* Recherche dichotomique de la valeur */
unsigned int Info_rechercheVal(SInfo *info, unsigned int nbr)
{
    int min = 0;
    int max = info->size_used;
    int mid = (max + min) / 2;
 
    do {
        /* Est-ce le bon element */
        if(info->tab[mid].min > nbr) {
            max = mid;
            mid = (max+min)/2;
        }
        else {
            if (info->tab[mid].max < nbr) {
                min = mid;
                mid = (max+min)/2;
            }
            else {
                return info->tab[mid].val;
            }
        }
    }while(min != max);
 
    /* 
     * On ne devrait jamais arriver ici puisqu'on teste pour savoir si
     * nbr est contenu dans le tableau 
     */
    fprintf(stderr, "Ceci ne devrait jamais arriver\n");
 
    return 0;
}
 
/* Calcul de g */
unsigned int g(SInfo *info, unsigned int nbr)
{
    unsigned int val;
 
    if(info == NULL) {
        return -1;
    }
 
    /* On regarde si on est plus petit que la derniere valeur */
    if(Info_plusGrandQueFin(info, nbr) == 0) {
        /* Recherche dichotomique */
        return Info_rechercheVal(info, nbr);
    }
 
    /* Condition finale */
    if(nbr==1) {
        val = 1;
    }
    else {
        /* Nouveau nombre a tester */
        val = 1 + g(info, nbr - g(info, g(info, nbr-1)));
        if(val > nbr) {
            printf("Bizarre\n");
            exit(1);
        }
    }
 
    /* On regarde si c'est la meme valeur que la derniere du tableau */
    if(Info_memeValeurQueFin(info, val)) {
        /* On met a jour */
        info->tab[info->size_used - 1].max = nbr;
    }
    else { 
        /* On ajoute */
        if(Info_ajouteElem(info, nbr, val)<0) {
            fprintf(stderr, "Erreur dans l'ajout d'un element\n");
            exit(EXIT_FAILURE);
        }
    }
    return val;
}
 
/* Main */
int main(int argc, char **argv)
{
    SInfo *info;
    unsigned int i;
    unsigned long max;
    char *endptr;
 
    if(argc != 2) {
        printf("Usage : %s <Limite>\n", argv[0]);
        return EXIT_FAILURE;
    }
 
    max = strtol(argv[1], &endptr, 0);
 
    if(*endptr != '\0') {
        printf("Erreur avec le parametre\n");
        return EXIT_FAILURE;
    }
 
    info = Info_lireFichier("reponse.txt");
    for(i=1;i<max;i++) {
        g(info, i);
    }
    printf("Ecriture %d\n",Info_ecrireFichier(info, "reponse.txt"));
    Info_affiche(info);
 
    if(info != NULL) {
        free(info->tab);
    }
    free(info);
 
    return EXIT_SUCCESS;
}

Dernier point, pour une raison de performances, on préférera utiliser le tableau que j'affiche à la fin du programme, pour cela il faut rajouter un code à la fin qui fait la recherche dichotomique mais qui refusera de calculer plus loin... Du coup, on ne lit plus le tableau et on ne l'écrit plus non

Voici un code exemple, reprennant le tableau allant jusqu'à 800 millions et ajoutant ce code à la suite :

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
 
#include <stdio.h>
#include <stdlib.h>
 
/* Ajouter la structure et le tableau ici */
 
/* Recherche dichotomique de la valeur */
unsigned int Info_rechercheVal(unsigned int nbr)
{
    int min = 0;
    int max = sizeof(tab)/sizeof(tab[0]);
    int mid = (max + min) / 2;
 
    do {
        /* Est-ce le bon element */
        if(tab[mid].min > nbr) {
            max = mid;
            mid = (max+min)/2;
        }
        else {
            if (tab[mid].max < nbr) {
                min = mid;
                mid = (max+min)/2;
            }
            else {
                return tab[mid].val;
            }
        }
    }while(min != max);
 
    /* 
     *      * On ne devrait jamais arriver ici puisqu'on teste pour savoir si
     *           * nbr est contenu dans le tableau 
     *                */
    fprintf(stderr, "Ceci ne devrait jamais arriver\n");
 
    return 0;
}
 
 
/* Calcul de g */
unsigned int g(unsigned int nbr)
{
    unsigned int val;
 
    /* On regarde si on est plus petit que la derniere valeur */
    if(nbr > tab[(sizeof(tab)/sizeof(tab[0]))-1].max) {
        fprintf(stderr, "Valeur trop grande\n");
        exit(EXIT_FAILURE);
    }
 
    /* Recherche dichotomique */
    return Info_rechercheVal(nbr);
}
 
/* Main */
int main(int argc, char **argv)
{
    unsigned int i;
    unsigned long max;
    char *endptr;
 
    if(argc != 2) {
        printf("Usage : %s <Limite>\n", argv[0]);
        return EXIT_FAILURE;
    }
 
    max = strtol(argv[1], &endptr, 0);
 
    if(*endptr != '\0') {
        printf("Erreur avec le parametre\n");
        return EXIT_FAILURE;
    }
 
    for(i=1;i<max;i++) {
        g(i);
    }
 
    printf("Pour forcer le calcul... %d\n",tab[10].min);
 
    return EXIT_SUCCESS;
}

Et voici les temps obtenus pour les différentes valeurs :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
BS 		Temps
1000		0.011s
10000		0.003s
100000		0.008s
1000000		0.053s
10000000	0.518s
100000000	5.272s
200000000	10.719s
500000000	26.736s
800000000	43.214s

Donc c'est encore mieux !

Encore désolé du long post, mais c'était marrant à faire...

Jc

[Superne0]

Je dois dire que c'est assez impressionant, en tout en ce qui me concerne.
Le problème que j'expose là est tiré du site de l'université de Valladolid, et le seul hic de ton programme fearyourself, c'est que le site ne peut valider un code source que s'il son éxécution passe sous la barre des 10.0s ... (je sais, le "Judge Online" est très sévère).
Donc bien que ton programme tourne assez rapidement pour la réalité du problème, je ne doute qu'il soit validé par le site, malheuresement.
Ce problème est décidemment une grosse prise de tête ...

[souviron34]

Je dois dire que c'est assez impressionant, en tout en ce qui me concerne.
Le problème que j'expose là est tiré du site de l'université de Valladolid, et le seul hic de ton programme fearyourself, c'est que le site ne peut valider un code source que s'il son éxécution passe sous la barre des 10.0s ... (je sais, le "Judge Online" est très sévère).
Donc bien que ton programme tourne assez rapidement pour la réalité du problème, je ne doute qu'il soit validé par le site, malheuresement.
Ce problème est décidemment une grosse prise de tête ...

10 secondes pour quel nombre ? sous quelle plateforme ? avec quel processeur ??

[Superne0]

10 secondes pour quel nombre ? sous quelle plateforme ? avec quel processeur ??

Moins de 10 secondes pour tester un certain nombres de valeurs (nombre que j'ignore), donc moins de 10s pour deux milliards.
Plateforme et processeur : Linux 2.4.18-27.7.x i686

[souviron34]

Moins de 10 secondes pour tester un certain nombres de valeurs (nombre que j'ignore), donc moins de 10s pour deux milliards.
Plateforme et processeur : Linux 2.4.18-27.7.x i686

????? Comment déduis-tu 2 milliards alors que tu dis que tu ignores ???

[Superne0]

Parce que les valeurs limites pour n sont 1 et 2000000000, donc il est très probable que le logiciel teste, entre autres, ces deux valeurs.

[souviron34]

Parce que les valeurs limites pour n sont 1 et 2000000000, donc il est très probable que le logiciel teste, entre autres, ces deux valeurs.

d'où sors tu ces valeurs limites ?

[fearyourself]

Je dois dire que c'est assez impressionant, en tout en ce qui me concerne.
Le problème que j'expose là est tiré du site de l'université de Valladolid, et le seul hic de ton programme fearyourself, c'est que le site ne peut valider un code source que s'il son éxécution passe sous la barre des 10.0s ... (je sais, le "Judge Online" est très sévère).
Donc bien que ton programme tourne assez rapidement pour la réalité du problème, je ne doute qu'il soit validé par le site, malheuresement.
Ce problème est décidemment une grosse prise de tête ...

Ben non parce que je fais le calcul sur les 800 millions de possibilités, si tu en prends juste un millier, mon programme tournera très rapidement...

Le plus long c'est de générer la table d'information...

Je me demande si on ne pourrait pas aussi factoriser les palliers en faisant une interpolation linéaire...

Jc