cs_Kirua
Messages postés3006Date d'inscriptiondimanche 14 avril 2002StatutMembreDernière intervention31 décembre 2008 18 oct. 2004 à 17:43
les IOI ça me fait bien râler. En france ils ont un truc génial qui s'appelle ProLogin, qui est un organisme de préparation et de sélection des ados qui iront défendre la France pour les concours d'algorithmique. En Belgique, rien de tout ça :(
Je vois ce que tu veux dire pour la pile/file, c'est vrai qu'on peut le faire comme ça, et c'est en fait ce qu'on utilise pour des problèmes comme les N reines etc. J'y avais pas pensé, mais en fait on parcours bien un arbre virtuel, c'est bien vu ^^
cs_mehdibou
Messages postés365Date d'inscriptionvendredi 24 mai 2002StatutMembreDernière intervention18 octobre 2004 18 oct. 2004 à 16:41
He oui, Kirua, je te lis aussi, tu es une star ;)
(à quand une équipe de Belgique pour les IOI ?)
Et pour parcourir un arbre binaire sans fonction récursive, on peut se faire sa propre pile (en gros ça revient à faire un appel) pour une moitié et utiliser un while pour l'autre moitié, c'est assez barbare :)
Comme l'a dit Kirua, il vaut mieux utiliser un tableau complet indicé pour la fonction factorielle mais la méthode que tu montres (ne garder qu'une valeur) peut être intéressant si on est très limité en place et si les valeurs demandées sont assez proches (sinon ça revient quasiment à tout calculer et en pratique ça prendra même plus de temps), comme par exemple une courbe continue.
cs_Kirua
Messages postés3006Date d'inscriptiondimanche 14 avril 2002StatutMembreDernière intervention31 décembre 2008 18 oct. 2004 à 00:02
oki, content d'être lu :p
je vais me coucher à l'instant, bye bye ;)
LocalStone
Messages postés514Date d'inscriptionmercredi 19 mars 2003StatutMembreDernière intervention 1 mars 2009 17 oct. 2004 à 23:53
Y a pas de mal, Kirua. En fait, je disais que ça faisait longtemps, parce que ça faisait longtemps que je n'avais pas lu un des tes commentaires, voilà tout.
++ !
cs_Kirua
Messages postés3006Date d'inscriptiondimanche 14 avril 2002StatutMembreDernière intervention31 décembre 2008 17 oct. 2004 à 18:35
dis ... je suis un peu gêné ... je viens de regarder les commentaires de tous tes codes pour voir où on aurait pu se croiser auparavant, parce que je me souviens pas de toi, ... dsl :D et j'ai pas trouvé où. tu me rafraîchis la mémoire? j'ai aussi regardé sur ts mes codes php, et rien ...
cs_Kirua
Messages postés3006Date d'inscriptiondimanche 14 avril 2002StatutMembreDernière intervention31 décembre 2008 17 oct. 2004 à 18:25
suis bien d'accord avec toi, les fonctiosn récursives c'est beau à mourir :) mais si c'st lent... ben faut laisser tomber.
remarque que parfois, la récursivité reste tt de même reine, je pense aux parcours d'arbre binaires par exemple, sans la récursivité, je sais pas comment on fait, lol.
LocalStone
Messages postés514Date d'inscriptionmercredi 19 mars 2003StatutMembreDernière intervention 1 mars 2009 17 oct. 2004 à 17:25
Bon, donc j'ai regardé les variables statiques, et en fait, ça ne sert plus à rien mon tutorial, puisqu'elles font exactement ce que font mes globales ... Snif.
Bon, bah je vais pleurer et je reviens :(
++ !
LocalStone
Messages postés514Date d'inscriptionmercredi 19 mars 2003StatutMembreDernière intervention 1 mars 2009 17 oct. 2004 à 17:03
Oh ! Kirua, ça faisait longtemps !
C'est dommage que les fonctions récusives soient lentes, parce que je trouve ça super pratique est simple à coder ... Mais bonjour les overflows sur le serveur.
Alors déjà, pour répondre à ta question, si tu fais 50! et 49!, la fonction va détécter que ça vaut le coup de décrementer le factoriel d'une unité (je sais pas si ça se dit, donc : (50 - 1)! = 49!), donc il va diviser le factoriel de 50 par 50, pour arriver au factoriel de 49.
Ensuite, pour les variables statiques, bah je sais pas ce que c'est donc je vais aller voir de ce pas le lien. Merci d'avance. Par contre, je sais que les (string) au lieu des (int) comme clef d'un tableau, ça ralenti, mais je vais laisser comme ça, pour ... Disons la pédagogie. Mais tu as raison.
Enfin, oui, le script ne sauve que la dernière valeure. Et tu as raison, comme les factoriels monte rapidement, ta solution est bonne. Mais en fait j'ai appris cette technique des variables globales (ou statiques) avec le coefficient binomial (P parmis N ...), mais comme tout le monde ne connait pas forcement ça, mais plutôt le factoriel, bah voilà ...
Mais je vais de ce pas voir les variables statiques ...
Merci de ton commentaire, Kirua !
++ !
cs_Kirua
Messages postés3006Date d'inscriptiondimanche 14 avril 2002StatutMembreDernière intervention31 décembre 2008 17 oct. 2004 à 15:03
note: il faut remplacer
static $tab = array();
par
static $tab = array(1);
cs_Kirua
Messages postés3006Date d'inscriptiondimanche 14 avril 2002StatutMembreDernière intervention31 décembre 2008 17 oct. 2004 à 14:16
l'itérative sera certainement plus rapide que la récursive. il faut pas appeler l'itérative la fonction barbare, elle est meilleure ;)
dans ta description, tu dis que factoriel de n n! 1*2*3*...*(n-1)*(n+1), c'est *(n) et pas *(n+1), bien sûr, mais tu le sais. faut juste corriger la coquille.
ta troisième fonction est-ce qu'on appelle un algorithme dynamique, càd qu'à mesure qu'on l'utilise, il accélère parce qu'il sauve les résultats intermédiaires. on utilise exactement le même procédé pour les suites de fibonacci, quoique pour fibo justement, l'itérative va aussi vite que la dynamique, et environ une infinité de fois plus vite que la récursive ;)
comme ton tableau n'est utilisé que dans la fonction dynamique, tu peux déclarer ce tableau en static plutôt, et donc le tuto n'a plus rien à voir avec les globales :p ça ne change rien à l'intérêt du pt que tu soulèves, mais static sera plus approprié. cf http://be2.php.net/variables.scope
j'ai pas assez lu ton code pr savoir mais... il me semble que tu ne sauves qu'un seul résultat (et en plus ds un tableau à indices littéraux, ce qui est bcp plus lent que les indices numériques, mais soit). docn si je fais ça:
50!
et puis
49!
si j'ai bien compris, il recalcul tout, ou pas?
je reconnais que c'est une perte de place mais... souvent on sauvera toutes les factorielles calculées dans un tableau, et on combinera avec une récursive. je m'explique:
function facto($n)
{
//ce tableau n'existe que dans cette fonction
static $tab = array();
//si l'élément a déjà été calculé
if(isset($tab[$n]))
{
return $tab[$n];
}
//sinon
else
{
$res = facto($n-1) * $n;
$tab[$n] = $res;
return $res;
}
}
du moins c'est comme ça que je ferais. comme les factorielles montent TRES vite, tu n'auras jamais 1000 éléments dans ton tableau (en fait même BCP BCP moins), et donc tu ne perds pas tant de place que ça.
faudrait tester la vitesse de cette fonction-ci. en tt cas le code est minuscule et facile.
ciao ! bonne continuation.
LocalStone
Messages postés514Date d'inscriptionmercredi 19 mars 2003StatutMembreDernière intervention 1 mars 2009 17 oct. 2004 à 01:28
Merdeuuuuuuuh, j'avais pas vu quand j'ai changé le nom des fonctions ... Snif. En tout cas, je suis content que ça ait plu à quelqu'un ...
Merci !
L.S.
juki_webmaster
Messages postés947Date d'inscriptionmercredi 19 novembre 2003StatutMembreDernière intervention 5 avril 20083 16 oct. 2004 à 17:12
Ahh dommage, il à louper son 10/10 :( lol
Belle source!
Bonne continuation.
cs_windu
Messages postés282Date d'inscriptionvendredi 16 mai 2003StatutMembreDernière intervention19 juillet 2006 16 oct. 2004 à 17:02
pas mal du tout ce tutoriel... par contre juste une peitie correction dans la 1° fonction tu marque "return($n * factoriel($n - 1));", or il faut écrire "return($n * factoriel_1($n - 1));" puisque c'est une fonction récursive!
Erreur qui ne te vaudra que 9/10... loooool
18 oct. 2004 à 17:43
Je vois ce que tu veux dire pour la pile/file, c'est vrai qu'on peut le faire comme ça, et c'est en fait ce qu'on utilise pour des problèmes comme les N reines etc. J'y avais pas pensé, mais en fait on parcours bien un arbre virtuel, c'est bien vu ^^
18 oct. 2004 à 16:41
(à quand une équipe de Belgique pour les IOI ?)
Et pour parcourir un arbre binaire sans fonction récursive, on peut se faire sa propre pile (en gros ça revient à faire un appel) pour une moitié et utiliser un while pour l'autre moitié, c'est assez barbare :)
Comme l'a dit Kirua, il vaut mieux utiliser un tableau complet indicé pour la fonction factorielle mais la méthode que tu montres (ne garder qu'une valeur) peut être intéressant si on est très limité en place et si les valeurs demandées sont assez proches (sinon ça revient quasiment à tout calculer et en pratique ça prendra même plus de temps), comme par exemple une courbe continue.
18 oct. 2004 à 00:02
je vais me coucher à l'instant, bye bye ;)
17 oct. 2004 à 23:53
++ !
17 oct. 2004 à 18:35
17 oct. 2004 à 18:25
remarque que parfois, la récursivité reste tt de même reine, je pense aux parcours d'arbre binaires par exemple, sans la récursivité, je sais pas comment on fait, lol.
17 oct. 2004 à 17:25
Bon, bah je vais pleurer et je reviens :(
++ !
17 oct. 2004 à 17:03
C'est dommage que les fonctions récusives soient lentes, parce que je trouve ça super pratique est simple à coder ... Mais bonjour les overflows sur le serveur.
Alors déjà, pour répondre à ta question, si tu fais 50! et 49!, la fonction va détécter que ça vaut le coup de décrementer le factoriel d'une unité (je sais pas si ça se dit, donc : (50 - 1)! = 49!), donc il va diviser le factoriel de 50 par 50, pour arriver au factoriel de 49.
Ensuite, pour les variables statiques, bah je sais pas ce que c'est donc je vais aller voir de ce pas le lien. Merci d'avance. Par contre, je sais que les (string) au lieu des (int) comme clef d'un tableau, ça ralenti, mais je vais laisser comme ça, pour ... Disons la pédagogie. Mais tu as raison.
Enfin, oui, le script ne sauve que la dernière valeure. Et tu as raison, comme les factoriels monte rapidement, ta solution est bonne. Mais en fait j'ai appris cette technique des variables globales (ou statiques) avec le coefficient binomial (P parmis N ...), mais comme tout le monde ne connait pas forcement ça, mais plutôt le factoriel, bah voilà ...
Mais je vais de ce pas voir les variables statiques ...
Merci de ton commentaire, Kirua !
++ !
17 oct. 2004 à 15:03
static $tab = array();
par
static $tab = array(1);
17 oct. 2004 à 14:16
dans ta description, tu dis que factoriel de n n! 1*2*3*...*(n-1)*(n+1), c'est *(n) et pas *(n+1), bien sûr, mais tu le sais. faut juste corriger la coquille.
ta troisième fonction est-ce qu'on appelle un algorithme dynamique, càd qu'à mesure qu'on l'utilise, il accélère parce qu'il sauve les résultats intermédiaires. on utilise exactement le même procédé pour les suites de fibonacci, quoique pour fibo justement, l'itérative va aussi vite que la dynamique, et environ une infinité de fois plus vite que la récursive ;)
comme ton tableau n'est utilisé que dans la fonction dynamique, tu peux déclarer ce tableau en static plutôt, et donc le tuto n'a plus rien à voir avec les globales :p ça ne change rien à l'intérêt du pt que tu soulèves, mais static sera plus approprié. cf http://be2.php.net/variables.scope
j'ai pas assez lu ton code pr savoir mais... il me semble que tu ne sauves qu'un seul résultat (et en plus ds un tableau à indices littéraux, ce qui est bcp plus lent que les indices numériques, mais soit). docn si je fais ça:
50!
et puis
49!
si j'ai bien compris, il recalcul tout, ou pas?
je reconnais que c'est une perte de place mais... souvent on sauvera toutes les factorielles calculées dans un tableau, et on combinera avec une récursive. je m'explique:
function facto($n)
{
//ce tableau n'existe que dans cette fonction
static $tab = array();
//si l'élément a déjà été calculé
if(isset($tab[$n]))
{
return $tab[$n];
}
//sinon
else
{
$res = facto($n-1) * $n;
$tab[$n] = $res;
return $res;
}
}
du moins c'est comme ça que je ferais. comme les factorielles montent TRES vite, tu n'auras jamais 1000 éléments dans ton tableau (en fait même BCP BCP moins), et donc tu ne perds pas tant de place que ça.
faudrait tester la vitesse de cette fonction-ci. en tt cas le code est minuscule et facile.
ciao ! bonne continuation.
17 oct. 2004 à 01:28
Merci !
L.S.
16 oct. 2004 à 17:12
Belle source!
Bonne continuation.
16 oct. 2004 à 17:02
Erreur qui ne te vaudra que 9/10... loooool