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);
} |
Partager