COMBINSIMPLE
cs_cantador
Messages postés
4720
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
31 juillet 2021
-
31 oct. 2008 à 15:38
Bacterius Messages postés 3792 Date d'inscription samedi 22 décembre 2007 Statut Membre Dernière intervention 3 juin 2016 - 5 nov. 2008 à 19:13
Bacterius Messages postés 3792 Date d'inscription samedi 22 décembre 2007 Statut Membre Dernière intervention 3 juin 2016 - 5 nov. 2008 à 19:13
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/48347-combinsimple
https://codes-sources.commentcamarche.net/source/48347-combinsimple
5 nov. 2008 à 19:13
Cordialement, Bacterius !
3 nov. 2008 à 18:02
on s'écarte un peu du sujet et d'ailleurs aujourd'hui ce n'est plus une chance sur 13983816 puisqu'il faut cocher mais 5 numéros + un nombre de 1 à 9 ce qui donne :
1 chance sur 17161956.
Mais cela n'a pas d'importance..car comme je te l'indiquais le Loto.. en ce qui me concerne c'est Bof..
En tout cas bravo, pour ton travail sur cet algorithme qui pourra être ré-utilisé dans d'autres programmes.
cantador
3 nov. 2008 à 17:25
Ce générateur de combinaison est utile dans une longue liste d'applications ou il est important de savoir générer l'ensemble des cas possibles :
Simulation numérique, décryptage force brute etc.
Dans tous ces cas, la première étape du besoin est de générer l'ensemble des cas possibles en mémoire, pas de les afficher (lol).
Je te donne un exemple pratique où ce programme peut servir avec le loto, pour que tout le monde comprenne (je sais que tu n'aimes pas le loto, c pour l'exemple) :
Si je veux connaitre mes chances de gagner avec 1 grille, un jeune matheux en herbe me donne rapidement mes chances de gain à 6 nuémros (1 sur 13983816), 5 numéros,.... 3 numéros : Facile
Si on connait la subtile différence qu'il y a entre jouer 10 fois une grille ou jouer 10 grilles différentes,
...tu vas épuiser le plus chevronné des matheux de la planète en lui demandant tes chances exacts d'avoir au moins une grille à 6 numéros, 5 numéros...et 3 num, avec le jeu de grilles suivant (pour l'exemple, 2 , 1 et 0 numéros en commun):
grille n°1 : 1 2 3 4 5 6
grille n°2 : 5 6 7 8 9 10
grille n°3 : 10 11 12 13 14 15
grille n°4 : 20 21 22 23 24 25
(Je ne parle pas des cas avec recoupements plus complexes s'il y a 20 grilles particulières)
La seule façon de répondre rapidement au problème est :
- générer les 6/49 combinaisons possibles; 4 secondes de calcul, qd c'est bien programmé ;-)
- compter le comportement de ton jeu de grille pour tout les tirages (16-20 s de calcul)
- afficher les stats !
On en revient à ce que je disais, un PC ca va vite, sinon c'est à 99% un problème de conception.
C'est ainsi, par énumération, qu'un nombre infinies d'applications informatiques sont traitées, là où la théorie devient trop complexe pour résoudre des cas pratiques aussi nombreux que particuliers ...
En aucun cas tu n'affiches les combinaisons essayées (Toutes !).
Pour rappel, le loto distribue une somme fixe (% des sommes perçues) que se partagent les gagnants :
Si tu joues 10 fois la même grille, tu gagnes 10 fois 1/10 eme de la somme, soit autant que si tu avais joué 1 seule grille ! Il est donc 10 fois plus intéressant de jouer 10 grilles différentes, mais cela, tout le monde le sait déjà.
Ce qu'il est plus difficile d'appréhender, c'est ce qu'il se passe pour les combinaisons à 5 num, 4 num etc,
ce que tu vas pouvoir analyser maintenant que tu as un bel algo.
LudoDelphi
3 nov. 2008 à 13:58
procedure TForm1.Button2Click(Sender: TObject);
var
a, b, c, d, e, f, nob: integer;
TempsCombi: longWord;
begin
TempsCombi := GetTickCount;
nob := 19;
for a := 1 to (nob - 5) do
for b := a + 1 to (nob - 4) do
for c := b + 1 to (nob - 3) do
for d := c + 1 to (nob - 2) do
for e := d + 1 to (nob - 1) do
for f := e + 1 to nob do
ListBox1.Items.Add(IntToStr(a) + ';' + IntToStr(b) + ';'
+ IntToStr(c) + ';' + IntToStr(d) + ';' + IntToStr(e) + ';'
+ IntToStr(f));
ShowMessage(IntToStr(GetTickCount - TempsCombi));
end;
3 nov. 2008 à 13:51
si tu veux faire des grilles tu es bien obligé d'afficher quelque chose ne serait ce que pour les reproduire..
De toutes façons, le Loto ne m'a jamais beaucoup intéressé et encore moins aujourd'hui avec la nouvelle mouture..
J'ai trouvé nettement mieux depuis longtemps..
3 nov. 2008 à 12:14
Mais cela dit, au niveau des temps cela ne change pas grand chose et le plus étonnant est que la première méthode (celle avec les tous les tests) reste la plus rapide des deux !
et je pense qu'on peut faire mieux encore..
3 nov. 2008 à 11:12
je suis étonné de tes résultats :
Ton algo génére tous les arrangements possibles et non les combinaisons
rappel de ton algo:
for i := 1 to nob do
for j := i to nob do
for k := j to nob do
for l := k to nob do
for m := l to nob do
for n := m to nob do
if ((i <> j) and (i <> k) and (i <> l) and (i <> m) and (i <> n))
and ((j <> i) and (j <> k) and (j <> l) and (j <> m) and (j <> n))
and ((k <> i) and (k <> j) and (k <> l) and (k <> m) and (k <> n))
and ((l <> i) and (l <> j) and (l <> k) and (l <> m) and (l <> n))
and ((m <> i) and (m <> j) and (m <> k) and (m <> l) and (m <> n)) then
begin
inc(cpt);
sl.Add(IntToStr(i) + ';' + IntToStr(j) + ';' + IntToStr(k) + ';' +
IntToStr(l) + ';' + IntToStr(m) + ';' + IntToStr(n));
end
Ce sont ces n! cas supplémentaires que tu es obligé de supprimer dans ta batterrie de test, avec re-perte de temps à la clef.
Cette méthode (améliorable comme tu le dit toi-meme) a l'inconvénient de générer n! (n factorielle) fois trop de cas, (6*5*4*3*2*1=720 pour le loto)
rappel : Arrangements = p! / (p-n)!
Combin = p! / ((p-n)! n!)
Je ne sais pas ce que tu as chronométré, mais fais un dernier essai avec cet algo (c'est l'otptimum connu que tu cherchais, adapté au loto 6/49)
var a,b,c,d,e,f:integer;
begin
for a:=1 to 44 do
for b:=a+1 to 45 do
for c:=b+1 to 46 do
for d:=c+1 to 47 do
for e:=d+1 to 48 do
for f:=e+1 to 49 do
begin
//génération des grilles
inc(cptCbn);
end;Tu verras que cptCbn p! / ((p-n)! n!) 13 983 816 (Bon signe !)
Il génére directement les combinaisons et QUE les combinaisons voulus
(il ne fait pas d'arrangements, donc pas besoin de ta batterie de test en plus)
Il est légèrement plus rapide (10%) que celui que j'utilise (itératif) et au minimum n! fois plus rapide que le tien (moins de cas générés, 0 test supplémentaires) Dans le cas du loto 6/49, n 6 et 6! 720 : il devrai aller 1000 fois plus vite que ton algo, et pas de besoin de getTickCount pour le vérifier
L'affichage, infiniment plus lent que le calcul, ne doit pas étre chronométré.
Ludo
1 nov. 2008 à 18:40
31 oct. 2008 à 15:38
testé avec GetTickCount :
avec ta méthode : 6 parmi 19 affichage en 14875 secondes
(et en enlevant la gauge bien sûr)
et avec la mienne : 14797 secondes.
hé hé..