Créer des fonctions dynamiques

Salut à tous,
Est-il possible de créer une fonction qui crée elle-même d'autres fonctions.
Je m'explique : j'ai une fonction avec un for (bon, on incrémente i de 1 dans le for ...), et je voudrais qu'à chaque fois que i change de valeur, une nouvelle fonction soit créée (déclarer quoi ...) en fonction de la nouvelle valeur de i.
Merci pour votre aide.

Citation:

---

Envoyé par Superne0

Salut à tous,
Est-il possible de créer une fonction qui crée elle-même d'autres fonctions.
Je m'explique : j'ai une fonction avec un for (bon, on incrémente i de 1 dans le for ...), et je voudrais qu'à chaque fois que i change de valeur, une nouvelle fonction soit créée (déclarer quoi ...) en fonction de la nouvelle valeur de i.
Merci pour votre aide.

---

Donc tu veux écrire un code qui crée des fonctions pendant l'exécution ou un code qui lors de la compilation crée des fonctions...

Jc

lors de l'éxécution a priori.

Citation:

---

Envoyé par Superne0

lors de l'éxécution a priori.

---

Tu veux faire de la compilation dynamique alors ?

ben je débute en C, je connais pas grand chose à la compilation (rien en fait), et je ne sais pas comment GCC fonctionne (je suis sous mingw).
je sais juste que mon problème pourrait peut-être se régler en creant des fonctions de cette manière.

Citation:

---

Envoyé par Superne0

ben je débute en C, je connais pas grand chose à la compilation (rien en fait), et je ne sais pas comment GCC fonctionne (je suis sous mingw).
je sais juste que mon problème pourrait peut-être se régler en creant des fonctions de cette manière.

---

Et si tu exposais ton problème pour voir s'il n'y a pas d'autre moyen de faire ?

Quoique de la compilation dynamique ... ca je serais curieux de savoir comment sa fonctionne mais ca ne doit pas être une partie de plaisir :?

C'est un problème qui vient du site d'ACM et qui consiste à afficher le nombre G(n) de la suite définie par G(n)=1+G(n-G(G(n-1))) et G(1)=1
Je pensais donc à créer une fonction qui créeraie elle-même d'autres fonctions (pour connaître G(n), il faut connaître G(n-1), et pour connaître G(n-1) il faut connaître G(n-2) etc ...).
Donc le problème se règle très bien sans fonctions récursives (donc avec un simple for), très bien avec un récursif non-terminal, mais le problème est que le "Judge Online" du site d'ACM impose un temps minimum de 10s (je crois, mais c'est pas le plus important ...).

Citation:

---

Envoyé par Franck.H

Et si tu exposais ton problème pour voir s'il n'y a pas d'autre moyen de faire ?

Quoique de la compilation dynamique ... ca je serais curieux de savoir comment sa fonctionne mais ca ne doit pas être une partie de plaisir :?

---

A priori, il faut un support runtime important. Certains langages interprétés comme Smalltalk sont capables de modifier leur propre code pendant l'exécution. Cette pratique ouvre des perspectives amusantes, et permet de modifier un programme sans avoir à l'arrêter et à le re-lancer.

Bien qu'il existe des interpréteurs pour le langage C, je n'ai jamais entendu parler de support pour de telles fonctionnalités en langage C.

Thierry

Pas besoin de créer des fonctions à l'exécution. Il s'agit juste de programmer une fonction récursive.

Citation:

---

Envoyé par stephl

Pas besoin de créer des fonctions à l'exécution. Il s'agit juste de programmer une fonction récursive.

---

Oui je crois que le mieux est d'utiliser la récursivité ou une boucle éventuellement mais du point de vue rapidité je ne sais pas trop... faire quelque chose de pointu comme tu l'as demandé et en espérant que c'est une pratique réalisable en Langage C .... mieux vaut opter pour plus simple effectivement :?

Le problème est bien fait parce que n varie entre 1 et 2 milliard.
Sur mon PC, la boucle met 6 secondes et quelques pour parcourir cet intervalle !
Le problème avec la récursivité terminale, c'est dans la fonction auxiliaire qui prend 2 paramètres, là ça devient vite le bordel ...

Hi,

Citation:

---

Envoyé par Superne0

le "Judge Online" du site d'ACM impose un temps minimum de 10s

---

Bizarre, en général, c'est plutôt des temps maxi qu'on impose.

Citation:

---

Envoyé par Superne0

Le problème est bien fait parce que n varie entre 1 et 2 milliard.
Sur mon PC, la boucle met 6 secondes et quelques pour parcourir cet intervalle !
Le problème avec la récursivité terminale, c'est dans la fonction auxiliaire qui prend 2 paramètres, là ça devient vite le bordel ...

---

Et tu penses réellement que créer des fonctions, leur demander un résultat... va améliorer les choses ?

Citation:

---

Envoyé par Superne0

Le problème est bien fait parce que n varie entre 1 et 2 milliard.

---

Il est clair pour faut oublier la récursivité

Pour la première citation c'est une confusion de ma part.
Pour la deuxième t'as raison.
Et pour la troisième, le problème c'est qui si la suite de ne se programme pas en récursif terminal, alors je vois pas trop de solutions ... (aucune même).
Et pourtant il y a bien un moyen de règler le problème (certains l'ont régler en 0.00 secondes et un espace de mémoire minimum).

Citation:

---

Envoyé par droggo

Il est clair pour faut oublier la récursivité

---

tu connais la recursion terminale ici

En fait la récursion terminale c'est bien connu ...
Le problème dans la programmation de cette séquence c'est plutôt l'encapsulation.

a partir de n=5 je trouve

G(n)=1+G(n-G(G(n-1))) équivalent a
G(n)=1+G(n-3)

je ne l'ai pas démontré mais juste fais les calculs jusqu'a n=15

Hu,

Citation:

---

Envoyé par scriptoff

tu connais la recursion terminale ici

---

Depuis le temps, j'avais oublié :oops:

Citation:

---

équivalent a
G(n)=1+G(n-3)

---

: ce n'est pas exact.
Par contre, il est vrai que la fonction progresse par paliers.
Partant de là, j'ai fait un petit essai sans utiliser la récursivité.
Dans le tableau tab, je me contente de stocker les abscisses lors des changements de palier.

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

unsigned int tab[100000]; unsigned int max,i,k,v; long t1,t2;   tab[0] = 0; tab[1] = 1;     t1 = time(0);   for (i=2,max=1;i<1000000;i++) { // G(i-1)=max for (k=max;tab[k]>=max;k--);   // G(G(i-1)) = k+1 // détermination de i-G(G(i-1)) v = i - (k+1); // retrouve G(v) for (k=max;tab[k]>=v;k--);   if (k+2>max) { tab[k+2] = i; } else tab[max] = i; // G(i) = 1+G(i-G(G(i-1))) = k+2 max = k+2; } t2 = time(0)-t1;   printf("%d - %d sec\n",max, t2);

---

pour 1000000 passages dans la boucle, on est déjà à 7 sec (sur le PC utilisé et pour une valeur de la fonction de 6137). Bref, ce n'est pas le bon algorythme mais ça donne des idées pour se passer de la récursivité.

Pour atteindre des performances telles que demandées, je pense qu'il faut effectivement réussir à exprimer G(n) en fonction de n. Mais du coup, cela perd de l'intérêt !

pourquoi tu définis le tableau à 100000 ?

C'est juste un petit essai que j'ai fait. En indice, tab reçoit les valeurs de G(x).
G(1000000) vaut un peu plus de 6000. Dans mon exemple, unsigned tab[6300] suffirait donc.

Je n'ai par contre pas d'idée sur la valeur de G(1000 000 000). Peut-être 100000 est-il insuffisant ? En fait, il faudrait faire dans une première étape un test pour vérifier qu'on ne déborde pas du tableau afin de pouvoir le dimmensionner correctement. Pour des souvis de performance, il faudrait ensuite supprimer le test.

Dans l'exemple que j'ai donné, je parcours tab de manière séquentielle pour retrouver G(x). En fait, il faudrait une méthode plus rapide (ex: dichotomie ?).
Mais même avec ça, je doute qu'on descende sous les 10 secondes.

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

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

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

Citation:

---

Envoyé par josse95

: ce n'est pas exact.

---

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

Citation:

---

Envoyé par scriptoff

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'à ...)

Citation:

---

Envoyé par koala01

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

Citation:

---

Envoyé par scriptoff

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 :P)

Voici le code de la fonction récursive:

Code:

---

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 :D

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

Code:

---

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

---

Citation:

---

Envoyé par koala01

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

Voici le code de la fonction récursive:

Code:

---

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 :D

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

Code:

---

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 ...

Citation:

---

Envoyé par Superne0

ç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 :P...

Code:

---

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:

---

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

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 ...

Citation:

---

Envoyé par Superne0

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

---

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

Jc

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:

---

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

---

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:

---

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:

---

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:

---

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:

---

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:

---

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:

---

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:

---

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:

---

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:

---

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:

---

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...
:wink:
Jc

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 ...

Citation:

---

Envoyé par 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 ...

---

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

Citation:

---

Envoyé par souviron34

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

Citation:

---

Envoyé par Superne0

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 ???

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.

Citation:

---

Envoyé par 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.

---

d'où sors tu ces valeurs limites ?

Citation:

---

Envoyé par 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 ...

---

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