Version imprimable
Oui, rien ne l'interdit. Mais dans ce cas, le problème perd tout intérêt.Citation:
fearyourself a écrit:
Il n'y a pas de triche dans le sens où rien ne nous interdit de faire un précalcul avant
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 ?
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).Citation:
Envoyé par fearyourself
J'ai compris maintenant, merci ;) .Citation:
Envoyé par fearyourself
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 .Citation:
Envoyé par fearyourself
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 ?Citation:
Envoyé par josse95
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 :wink:. 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
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).
Bien sûr !Citation:
Envoyé par josse95
En effet, c'était là le fun. Si ce n'était pas une suite sous-forme de pallier, cela n'aurait pas fonctionner.Citation:
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, je viens de revoir le code, mea culpa :wink:Citation:
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 suis d'accord avec toi sur le principe, clairement mon programme perd si on prend le temps de précalcul.Citation:
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'où le grand :wink:, mais oui il y en a d'autres...Citation:
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.
Exact et je dirais même un grandCitation:
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).
:lahola: à 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 :wink:
Jc
Entendu, un débat entre passionnés est souvent très mouvementé.
Amitiés à tous
stephl, dans ton code, apparaît.Code:#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: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 ... :oops:.
Encore désolé de vous solliciter, je voyait pas le problème aussi costaud que ça quand je l'ai trouvé.
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é):Citation:
Envoyé par Superne0
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 ;)Code:malloc(VALRANGE*sizeof(unsigned int))
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.