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
| #include <stdio.h>
#include <time.h>
#include <malloc.h>
#include <stdlib.h>
unsigned int *palier;
unsigned int maxpalier=1,maxval=1;
unsigned long g(unsigned int n)
{
unsigned int max,i,v,vmin,vmax,delta;
if (n<=1) return 1;
/* cas n<=maxval. On a déjà calculé G(n) */
/* recherche donc (par dichotomie) dans palier la valeur correspondante */
if (maxval>=n)
{
for (vmin=1,vmax=maxpalier;;)
{
delta = (vmax-vmin)>>1;
if (delta<=0) break;
if (palier[vmax-delta]<n)
{
vmin += delta;
}
else
{
vmax -= delta;
}
}
return(vmax);
}
palier[0] = 0;
palier[1] = 1;
palier[2] = 2;
/* calcule maintenant G(x) pour x=(maxval+1) jusqu'à n */
/* les valeurs de 2 jusqu'à maxval ont déjà été calculées */
/* et figurent dans le tableau palier */
for (i=maxval+1,max=maxpalier;i<=n;i++)
{
/* à ce niveau, on a G(i-1)=max */
/* calcule ensuite G(G(i-1))=G(max) en recherchant par */
/* dichotomie à quel palier correspond max */
for (vmin=1,vmax=max;;)
{
delta = (vmax-vmin)>>1;
if (delta<=0) break;
if (palier[vmax-delta]<max)
{
vmin += delta;
}
else
{
vmax -= delta;
}
}
/* en sortie du for, on a G(G(i-1))=vmax */
v = i - vmax;
/* calcule maintenant G(i-G(G(i-1))) toujours en recherchant */
/* dans palier par dichotomie */
for (vmin=1,vmax=max;;)
{
delta = (vmax-vmin)>>1;
if (delta<=0) break;
if (palier[vmax-delta]<v)
{
vmin += delta;
}
else
{
vmax -= delta;
}
}
/* en sortie de la boucle for, on a G(i-G(G(i-1)))=vmax */
/* maintenant, on met à jour le tableau des paliers */
if (vmax+1>max)
{
/* nouveau palier */
max = vmax+1;
}
/* on a G(x)=max pour x=palier[max-1]+1 jusqu'à i */
palier[max] = i;
}
/* mémorise la valeur maxval la plus haute pour laquelle on a calcule G */
/* ainsi que maxpalier=G(maxval) */
if (n>maxval)
{
maxval = n;
maxpalier = max;
}
return max;
}
int main(int argc, char* argv[])
{
time_t t1;
unsigned long v;
char s[32];
palier = (unsigned int *) malloc(10000000*sizeof(int));
palier[0] = 0;
palier[1] = 1;
maxpalier = 1;
while (true)
{
printf("Entrez la valeur de N (RETURN pour sortir): ");
fflush(stdout);
gets(s); /* je ne fais pas de test sur la valeur saisie */
if (*s == 0) break;
t1 = time(0L);
v = g(atoi(s));
printf("G(%u)=%u - %u sec\n\n", atoi(s), v, time(0L)-t1);
}
free(palier);
} |
Envoyé par souviron34
Répondre avec citation
A méditer: La solution la plus simple est toujours la moins compliquée
Partager