Discussion :

[josse95]

fearyourself a écrit:
Il n'y a pas de triche dans le sens où rien ne nous interdit de faire un précalcul avant

Oui, rien ne l'interdit. Mais dans ce cas, le problème perd tout intérêt.
On peut te demander de résoudre n'importe quelle équation. Tu mets une semaine à la résoudre sur un CRAY. Tu sauvegardes le résultat dans un fichier que tu transportes sur un PC.
Sur le PC, tu relis le fichier, c'est instantané. Mais où est l'intérêt ?

[stephl]

C'est le deuxième cas en effet.

OK, mais alors il n'y a plus trop de rapport avec la suite de Golomb. Une fois que les paliers ont été calculés, il s'agit d'optimiser à fond la recherche (en tout cas avec nos méthodes).

Les modifications que j'ai faites font qu'on ne poursuit que le calcul si nécessaire, basculant sur une recherche dichotomique si on a déjà le résultat dans la table.

J'ai compris maintenant, merci .

Ceci n'enlève en rien que ton code est bon et fonctionne à merveille

Je vous remercie du compliment que je vous retourne d'ailleurs. J'ai été avantagé car je n'ai commencé à chercher que lorsque le lien vers Solomon Golomb's self*describing sequence a été donné. Ainsi, je n'ai pas été induit en erreur par la formule de récurrence de la suite .

[fearyourself]

Oui, rien ne l'interdit. Mais dans ce cas, le problème perd tout intérêt.
On peut te demander de résoudre n'importe quelle équation. Tu mets une semaine à la résoudre sur un CRAY. Tu sauvegardes le résultat dans un fichier que tu transportes sur un PC.
Sur le PC, tu relis le fichier, c'est instantané. Mais où est l'intérêt ?

L'intérêt ? Résoudre un problème. Depuis quand il faut que la solution soit intéressante ou même super top géniale et à la mode ? Qui a dit qu'on devait résoudre le problème sans avoir fait des précalculs avant ?

Si c'est dans les hypothéses alors ma solution n'est pas viable. Et d'ailleurs, pour certains calculs, il vaut mieux juste le calculer en live, ce serait plus rapide que de gérer une table et une recherche, surtout si la table serait trop grande.

Prends la fonctions f(x) = x+1 par exemple . Plus sérieusement, tu rencontreras pleins de problèmes où cette solution est la seule possible et pleins où c'est carrément pas celle qui faut utiliser. Il faut savoir quoi choisir.

Mon programme utilise plus ou moins 20 Mo de mémoire pour la table. J'aurais pu faire plus petit mais je me suis dit que j'avais 1Go pour faire tourner le programme alors...

Un programme peut se définir sur trois grands critères :
- Exactitude
- Utilisation mémoire
- Temps CPU

Généralement, nous avons une priorité sur l'exactitude et ensuite cela dépend de l'architecture et sur ce que nous voulons.

Quelqu'un qui bosse sur un système embarqué ne fera jamais ce que j'ai fait puisque cela est impossible, j'utilisais trop de mémoire. Quelqu'un sur une machine avec 8 Go de RAM le ferait sans hésiter si c'était la seule solution. Je rappelle que ma solution partait du principe que la seule formule qu'on avait était G(n) = 1 + G(n-G(G(n-1))).

Chaque solution a son mérite :

- Stephl : petit, rapide, calcul tout à la volée, réutilise les valeurs calculées mais ne suit pas la formule récursive (à juste titre d'ailleurs)
- La tienne : petit, calcul tout à la volée, réutilise les valeurs calculées mais si on lui donne directement 100000000, il se vautre (ce qui est normal vu que tu passes par la récursive)
- La mienne : énorme (vraiment !), rapide, ne calcule rien à la volée, fait une recherche dichotomique sur une table précalculée.

Jc

[josse95]

Chacun trouve son intérêt où il veut.
De mon coté, le challenge était de pouvoir calculer la formule 1+G(n-G(G(n-1))) le plus rapidement possible. J'y ai plus vu un intérêt mathématique qu'informatique.

La récursivité étant écartée au vu des valeurs manipulées, restait à trouver une autre solution (contrairement à ce que tu affirmes, ma fonction n'est pas récursive).
Je ne dis pas que ta solution n'a pas de mérite ni que ton programme n'est pas "génial". Il est bien écrit et fonctionne. Là où je parle de triche est que les temps donnés ne tiennent pas compte du pré-calcul qui bien-sûr est très long. Quand tu dis que mon programme se vautre lors d'un appel direct à g(1000000000), je te rétorque que le tien aussi si tu tiens compte du précalcul.
D'ailleurs, on pourrait aussi bien stocker toutes les valeurs de G(n) dans un ou plusieurs fichiers et y accéder ensuite par un fseek pour afficher le résultat !

Dernière remarque, tu écris:

Un programme peut se définir sur trois grands critères :
- Exactitude
- Utilisation mémoire
- Temps CPU

Pour ce type de programme peut-être, sinon, il y en a évidemment plein d'autres: ergonomie, facilité de maintenance, portabilité ... mais là n'est pas le problème.

L'essentiel est que chacun de nous a pris plaisir à réfléchir sur ce problème intéressant et qu'on a pu partager nos points de vue (parfois différents).

[fearyourself]

Chacun trouve son intérêt où il veut.

Bien sûr !

De mon coté, le challenge était de pouvoir calculer la formule 1+G(n-G(G(n-1))) le plus rapidement possible. J'y ai plus vu un intérêt mathématique qu'informatique.

En effet, c'était là le fun. Si ce n'était pas une suite sous-forme de pallier, cela n'aurait pas fonctionner.

La récursivité étant écartée au vu des valeurs manipulées, restait à trouver une autre solution (contrairement à ce que tu affirmes, ma fonction n'est pas récursive).

En effet, je viens de revoir le code, mea culpa

Je ne dis pas que ta solution n'a pas de mérite ni que ton programme n'est pas "génial". Il est bien écrit et fonctionne. Là où je parle de triche est que les temps donnés ne tiennent pas compte du pré-calcul qui bien-sûr est très long. Quand tu dis que mon programme se vautre lors d'un appel direct à g(1000000000), je te rétorque que le tien aussi si tu tiens compte du précalcul.

Je suis d'accord avec toi sur le principe, clairement mon programme perd si on prend le temps de précalcul.

Dernière remarque, tu écris:

Un programme peut se définir sur trois grands critères :
- Exactitude
- Utilisation mémoire
- Temps CPU

Non, il y en a évidemment plein d'autres: ergonomie, facilité de maintenance, portabilité ... mais là n'est pas le problème.

D'où le grand , mais oui il y en a d'autres...

L'essentiel est que chacun de nous a pris plaisir à réfléchir sur ce problème intéressant et qu'on a pu partager nos points de vue (parfois différents).

Exact et je dirais même un grand
à ceux qui se sont bien marrés à faire ce problème !

Je pense qu'on devrait s'arrêter là, on est d'accord sur, je pense, tous les points, et continuer la discussion ne fait que polluer ce beau fil

Jc

[josse95]

Entendu, un débat entre passionnés est souvent très mouvementé.
Amitiés à tous

[Superne0]

stephl, dans ton code, apparaît

Code :

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

#define VALRANGE_SIZE 1000000

.
Est-ce que ça fait référence à une librairie particulière, et est-ce que ça a un rapport avec

Code :

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

malloc(1000000*sizeof(unsigned int))

?
D'un point de vue algo, je comprends bien ce que vous faites tous, mais comme je débute en C, dès qu'une instruction fait référence à une librairie, ça devient vite compliqué pour moi ... .
Encore désolé de vous solliciter, je voyait pas le problème aussi costaud que ça quand je l'ai trouvé.

[Franck.H]

stephl, dans ton code, apparaît

Code :

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

#define VALRANGE_SIZE 1000000

En fait, ceci créé une constante symbolique ce qui signifie que le pré-compilateur, dès qu'il vois le mot VALRANGE il le remplace par 1000000. Tu peux par exemple l'utiliser pour (comme tu as montré mais en modifié):

Code :

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

malloc(VALRANGE*sizeof(unsigned int))

Ca te permet de facilement modifier des valeurs sans devoir les changer partout dans ton code, c'est le pré-compilateur qui va substituer tout ca

[Superne0]

OK ... je le mets dans le rayon des combines à connaître !
Bon ben merci à tous pour votre interêt au topic, j'ai testé les programmes sur un compte bidon et vos codes fonctionnent ... je n'ai plus qu'à faire le mien.
A bientôt

Pour ceux qui gèrent l'algo, vous avez plus de 2.000 problèmes dans le genre (http://acm.uva.es/problemset).
Perso, moi c'est pour découvrir.