SOLUTION LOTO AVEC BOUCLE RECURSIVE
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
-
14 janv. 2006 à 10:38
syl20dies Messages postés 13 Date d'inscription mardi 21 octobre 2008 Statut Membre Dernière intervention 29 janvier 2009 - 21 oct. 2008 à 08:27
syl20dies Messages postés 13 Date d'inscription mardi 21 octobre 2008 Statut Membre Dernière intervention 29 janvier 2009 - 21 oct. 2008 à 08:27
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/35562-solution-loto-avec-boucle-recursive
https://codes-sources.commentcamarche.net/source/35562-solution-loto-avec-boucle-recursive
21 oct. 2008 à 08:27
j'ai ensuite vainement parcouru le net à la recherche de la manière de résoudre ce problème. La seule information que j'ai pu obtenir fut d'aller voir du coté de la récursivité et là encore le meilleur tuto trouvé ne s'employait qu'à mettre sous forme récursive l'utilisation de 2 boucles imbriquées et non k. je suis finalement parvenu en m'arrachant les cheveux à une solution 100% itérative du problème, mais au vu de la dite solution je pense que la simplicité du code de CyrVB(ne justifiant pas pour certains de s'enthousiasmer devant l'emploi de la récursivité dans une boucle) devrait au contraire en faire ressortir les bienfaits.
lors de ma tentative d'apprentissage sur la notion de récursivité, j'ai pu noter que celle-ci avait l'inconvénient de consommer une quantité de mémoire à l'exécution correspondant aux paramètres multipliés par le nombre de récursions. dans le cas présent j'imagine que ce puisse rapidement devenir un problème au vu du nombre faramineux de solutions que l'on peut obtenir dès que k se rapproche de n/2 avec un n élevé.
je me demandais donc si finalement ma solution itérative certes beaucoup plus obscure en terme de lisibilité pouvait tout de même représenter un intérêt.
celle-ci étant codée en action script je ne sais pas si elle trouverait place à cet endroit mais je serais vivement intéressé par la critique de membres éclairés tels qu'il semble que l'on puisse en rencontrer sur phpcs(même s'ils lancent parfois des benchs pour comparer deux programmes ne faisant pas du tout la même chose ;-))de plus ce sont là deux langages orientés web et souvent complémentaires, je tomberais donc peut être sur quelqu'un sachant le traduire en php et/ou l'optimiser en conservant sa nature itérative.
je profite de la confusion sur la destination du programme pour soumettre une suggestion dans le cas du calcul strict du nombre de combinaisons
C(k,n) est mathématiquement = n!/(k!(n-k)! mais si l'on réfléchit un peu, et au vu du soit-disant gain de ressource qu'était censé amener la fonction.j'émettrai une vive critique sur le fait d'appeler trois fois une fonction factorielle sans chercher un peu à simplifier ce quotient en effet il suffit de multiplier uniquement les entiers allant de k à n et de diviser ce résultat par (n-k)! en l'occurence 43! est calculé deux fois pour rien puisqu'ils se simplifient.
ceci donnerait la fonction suivante tellement simple que je vais même la traduire en php:
function loto($k,$n){
//ici le loto mais s'applique en fait à tout calcul de combinaisons de $k elements parmis $n
$tot=1;
for($r=$n;$r>$k;$r--){$tot*=$r;}
for($r=($n-$k);$r>1;$r--){$tot/=$r;}
return($tot);
}
echo 'Nombre de Solution: '.loto(6,49);
ceci étant dit revenons en à notre problématique de génération des solutions:
je l'ai codé ici dans le but de retourner un tableau bidimensionnel contenant toutes les combinaisons possibles de n elements parmis un tableau passé en paramètre ex: combi(["chat","chien","pomme","poire"],2) retourne[["chat","pomme"],["chat","poire"],["chien","pomme"],["chien","poire"],["pomme","poire"]]
function combi(arr_in,n){
comb=[];
fini=false;
id=Array(n);
for(cptid=0;cptid<n;cptid++){id[cptid]=cptid;}
id[n-1]=id[n-1]-1;
while(!fini){
exit=false;
for(i=n-1;i>=0 && !exit;i--){
if(id[i]0;cpt--){
id[n-cpt]=id[(n-1)-cpt]+((first)?2:1);
first=false;
}
}
}
if(!fini){
solution=Array(n);
for(cptid=0;cptid<n;cptid++){solution[cptid]=arr_in[id[cptid]];}
comb.push(solution);
}
}
return comb;
}
29 mai 2008 à 17:47
18 janv. 2006 à 01:54
je suis tres tres sensible comme garcon.
18 janv. 2006 à 00:25
18 janv. 2006 à 00:04
'; // On affiche la solution enelever les commentaires
Cependant ma fonction retourne aussi le nombre de solution
J4'ai fais un copier/coller de la description, lit le Post Scriptum
Description
Voila,
Ceci est mon premier et certainement dernier code poste ici.
J'en avais un peu marre de faire 6 boucles imbriquees pour calculer toutes les possibites du loto, donc j ai reflechie un peu au probleme avec un copain, et on a pondu ce code, qui s adapte facilement a n importe quelle parametres.
Si vous avez des combinaison a calculer, c'est relativement pratique.
Ca fait appel a un appel recursif dans un boucle, c est plutot joli je trouve ;)
PS: Vu qu il y a pres de 14 Millions au loto, j'ai mis en commentaire le 'echo' car sinon ca prends vraiment du temps a afficher
18 janv. 2006 à 00:00
ça va t'afficher quoi ça ? le nombre de solutions non ? je vois rien d'autre dans ta fonction qui affiche autre chose...
17 janv. 2006 à 22:56
Mon code est fait pour afficher les solutions possibles, et non de calculer le nombre de solution possible
J'espere que c'est clair pour tout le monde ;)
17 janv. 2006 à 22:48
Mon code, affiche les combinaisons possible du loto, ou de toute autre combinasion de de X1 a Xx avec Y nombre affichable possible.
Le code de monoceros01, ne fais que calculer le nombre de solution. Essayer d afficher les combinaison possible avec le code de monoceros01, vous verez que ce n est pas possible.
Vous avez tous fait la meme confusion, entre le calcul du nombre de solution possible, facielemt realisable par un simple factule factioriel, et le fais d afficher les solutions possibles.
16 janv. 2006 à 20:38
16 janv. 2006 à 18:53
16 janv. 2006 à 16:33
16 janv. 2006 à 13:33
Je mets 5, la moyenne.
- pas moins, parce que ce genre de code pourra être utile, je pense, à certains. Ca part d'une bonne idée.
- pas plus, parce que ce n'est pas génialement codé, puisque l'on peut largement optimiser (la preuve :-) ).
16 janv. 2006 à 13:30
Bon plus honnête (j'ai viré tout ce qui a trait à la génération des combinaisons sur le code de CyrVB ) :
Monoceros : 6.89029693604E-005
CyrVB : 39.918913126
On remarquera que décidément, faut toujours faire les benches sur beaucoup d'exécution, parce que le temps du code de Monoceros a très légèrement changé ;-) Enfin en l'occurence, vu la différence entre les 2 codes, ce n'est pas très grave ici ;-)
16 janv. 2006 à 13:19
16 janv. 2006 à 12:09
16 janv. 2006 à 10:03
Mooceros : 7.70092010498E-005
CyrVB : 115.388473988
je ne l'ai fait que sur 1 exécution, vu le temps que ça prend déjà...
15 janv. 2006 à 13:00
15 janv. 2006 à 11:21
Accueillez positivement et avec un regard bienveillant (respiciet disait le grand sage!) cette nouvelle question philosophique: la récursion dans une boucle, est-ce, finalement, tellement différent et plus profond? Relève-t-elle du savoir bien gardé des grands Chamanes du Nord, ou est-elle à la portée de tous, même les non initiés?
En tout cas je suis 100% coucou sur ce coup-là.
14 janv. 2006 à 19:13
define('NB_POSSIBILITES_LOTO',13........);
et hop ça c'est torché tu pourras l'avoir dans ton script (bon ok je sors)
14 janv. 2006 à 18:43
14 janv. 2006 à 18:39
function factoriel($entier)
{
$res = $entier;
for($i=$entier-1;$i>1;$i--)
{
$res *=$i;
}
return $res;
}
function loto($i, $n, $p)
{
// $i= Valeur Minimum (Loto 1)
// $n= Valeur Maximum (Loto 49)
// $p= Nombre de chiffre que la solution doit contenir (Loto 6)
return factoriel($n-$i+1) / (factoriel($n-$i+1-$p) × factoriel($p));
}
echo 'Nombre de Solution: '.loto(1,49,6);
?>
Maintenant explique moi ce que fait ta fonction que ne fait pas la mienne =) (mise a par bouffer de la ressource)
14 janv. 2006 à 18:33
<?php
function factoriel($entier)
{
$res = $entier;
for($i=$entier-1;$i>1;$i--)
{
$res *=$i;
}
return $res;
}
echo factoriel(6);
?>
14 janv. 2006 à 18:31
14 janv. 2006 à 18:28
de plus c est facilemenet adaptable, pour afficher les combinaison avec des chaines, des tableaux, etc ...
Pour cacluler le nombre de resultat un calcule factoriel est bien necessaire c est sur, j ai aussi le code en PHP si tu veux
14 janv. 2006 à 18:25
[troll]Faire une fonction qui calcule les factoriels serait déjà plus intéressant et aura plus d'utilité que de calculer les combinaisons du loto :D/troll
Tiens j'vais voir si y en a pas déjà sur CS et pitète en coder un si le coeur m'en dit (c po bien long a faire ¬¬)
14 janv. 2006 à 18:16
($n-$i+1)! / (($n-$i+1-$p)! × $p!)
Donc dans ton exemple :
(49-1+1)! / (49-1+1-6)! × 6! = 49! / (43! × 6!)
Soit :
(49×48×47×46×45×44) / 720 10 068 347 520 / 720 13 983 816 combinaisons possibles
Ce qui donnerais une fonction du style :
function loto($s, $i, $n, $p)
{
// $s= String_Resulat
// $i= Valeur Minimum (Loto 1)
// $n= Valeur Maximum (Loto 49)
// $p= Nombre de chiffre que la solution doit contenir (Loto 6)
return ($n-$i+1)! / (($n-$i+1-$p)! × $p!);
}
echo 'Nombre de Solution: '.loto('',1,49,6); // ca doit retourne 13983816
14 janv. 2006 à 18:01
@ tchaOo°
14 janv. 2006 à 17:59
14 janv. 2006 à 17:56
Je l ai mis en initie juste a cause de ca, car cest un appel recursive dans une boucle, perso c est as tous les jours que je vois ca. A chaque fois que tu appel la fonction, une boucle rappel cette meme fonction, ca commence a devenir un peu profond
for (;$i <= $n; ++$i) { loto($s." ".$i, $i + 1, $n, $p); }
14 janv. 2006 à 17:53
@ tchaOo°
14 janv. 2006 à 17:47
Pour en connaitre un peu plus, et pour vous montrez que la taupe est a pres de 14M et non 10M comme le pretant Monoceros01
14 janv. 2006 à 17:43
@COUCOU747: c est pas un char pour tuer une taupe, mais cest une solution bien plus elegante que
6 boucles imbriquees, imagine que tu veuilles faire des combinaison d un loto de 1 a 49 avec 15 numero. Tu devras donc faire 15 boucle imbriquees, ca n a aucun style !
14 janv. 2006 à 17:38
($n-$i+1)! / ($n-$i+1-$p)!
Donc dans ton exemple :
(49-1+1)! / (49-1+1-6)! = 49!/43!
Soit :
49×48×47×46×45×44 = 10 068 347 520 combinaisons possibles
Voilà la taupe :D
14 janv. 2006 à 15:58
"tu prends souvent un char pour tuer une taupe ?"
t'es sûr de pas la louper au moins (mdr)
14 janv. 2006 à 10:38
tu prends souvent un char pour tuer une taupe ?