Discussion :

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

[fearyourself]

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

[Superne0]

lors de l'éxécution a priori.

[hegros]

lors de l'éxécution a priori.

Tu veux faire de la compilation dynamique alors ?

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

[Franck.H]

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

[Superne0]

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

[Thierry Chappuis]

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

[stephl]

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

[Franck.H]

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

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

[droggo]

Hi,

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.

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 ?

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

Il est clair pour faut oublier la récursivité

[Superne0]

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

[scriptoff]

Il est clair pour faut oublier la récursivité

tu connais la recursion terminale ici

[Superne0]

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.

[scriptoff]

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

[droggo]

Hu,

tu connais la recursion terminale ici

Depuis le temps, j'avais oublié

[josse95]

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

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

[Superne0]

pourquoi tu définis le tableau à 100000 ?

[josse95]

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.