Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 20-08-2024 13:21:54

Matmusgep
Invité

Dénombrement

Bonjour, je faisais un exercice de dénombrement assez classique et j'avais un doute quand à ma réponse.

On dispose au hasard de 5 pions sur un damier de 25 cases réparties sur 5 lignes et 5 colonnes. Chaque case peut recevoir plusieurs pions. Quelle est la probabilité pour que les pions soient tous sur une même ligne ou tous sur une même colonne ?

On raisonnera évidemment sur les card vu qu'on peut munir un Omega de la probabilité équidistribuée.
J'ai pris comme univers des possibles l'ensemble Omega des 5-listes d'éléments de [[1;25]], si (X1,X2,X3,X4,X5) est un résultat possible, Xi est le numéro de la case où est placé le pion Pi.

Ainsi Card(Omega)=25^5

et j'ai simplement fait un schéma pour trouver card de l'évènement. Où on voit bien que pour placer le premier pion on a 25 possibilités, puis 9 pour le suivant (ce qui déterminera la colonne ou ligne) puis 5 possibilités, puis encore 5 possibilités, puis encore 5 possibilités.
d'où 25x9x5x5x5

Qu'en pensez-vous ?

#2 20-08-2024 14:31:51

Michel Coste
Membre
Inscription : 05-10-2018
Messages : 1 170

Re : Dénombrement

Bonjour,
Si les deux premiers pions sont placés sur la même case, cela ne détermine pas le choix entre colonne et ligne.

Hors ligne

#3 20-08-2024 14:49:41

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 417

Re : Dénombrement

Bonjour,

Les 5 pions sont placés en lignes ou en colonnes ( ou "inclusif"  à cause des seuls cas communs  tous les 5 sur une seule case).

Pour moi C(9,5) étant le nombre de façons de les répartir alignés, et comme il y a 10 rangées possibles (5 colonnes et 5 lignes), ça ferait
10C(9,5) auquel il faut retrancher 25 disposition (vu qu'on a compté deux fois les cas où une seule case est remplie).

Donc sauf erreur ça fait 1235 ( en supposant les jetons indistinguables, comme ceux d'un jeu de Dames)

Dernière modification par bridgslam (20-08-2024 16:39:02)


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#4 20-08-2024 15:14:30

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 417

Re : Dénombrement

Re-

Si les jetons sont différenciés ( rouge, vert, bleu, jaune, blanc par exemple) mon calcul donne $ 10 \times 5^5 - 25$, soit 31225 dispositions.

par exemple avec deux couleurs (B/N) et un damier 2x2 pour simplifier

B+N  -
-        -   et 3 autres cas similaires

B     N            N   B    et  encore deux cas (autre ligne)         

-      -              -    -               

N   -           B   -

B  -            N   -      et encore deux cas sur l'autre colonne


Sauf erreur de ma part. 12 possibilités (  $ 4 \times 2^2  - 4$)

Avec n jetons différents sur un damier nxn  , le résultat (pour moi ) est $2 \times n^{n+1} - n^2$

Cette expression reste valable si n=1 ( cas où on aurait eu vite fait le tour de la question) et par ailleurs a toujours même parité que n
(cela permet de déceler d'éventuelles erreurs de calcul, si vous trouvez un nombre de dispositions impair avec un damier ou un échiquier, il y a un pb)

A.

Dernière modification par bridgslam (20-08-2024 18:25:24)


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#5 31-08-2024 13:47:00

Ernst
Membre
Inscription : 30-01-2024
Messages : 140

Re : Dénombrement

Bonjour,

Le problème est intéressant, à cause des différentes configurations possibles. En plus ce que j’aime bien avec les forums, c’est qu’on a le temps d’y réfléchir, d’y revenir, de peaufiner tout ça, donc ce genre de petit problème c’est sympa. Bref, sur ce coup j’ai eu envie de programmer une simulation, pour voir...

bridgslam a écrit :

Avec n jetons différents sur un damier nxn  , le résultat (pour moi ) est $2 \times n^{n+1} - n^2$

Eh bien les résultats que j’obtiens sont parfaitement en accord avec cette formule, donc je dis bravo, étant incapable de calculer des probabilités théoriques, admiration sincère.

À noter que si j’arrive à une concordance de plusieurs décimales pour des $n$ petits, à partir de la dizaine c’est mort puisqu’il faut plusieurs milliards de tirages pour voir apparaître des occurrences, d’où le manque de précision de ma méthode.

Comme quoi les formules, il n’y a que ça de vrai !

Hors ligne

#6 31-08-2024 15:59:23

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 417

Re : Dénombrement

Bonjour,

Comme pour moi, de façon classique, rien ne ressemble plus à un pion sur un damier qu'un autre pion, j'ai cru au départ qu'il ne distinguait pas les pions entre eux,
d'où le nombre de configurations beaucoup plus faible dans mon premier post que dans le deuxième, et j'aurais aimé savoir en retour ce qu'il considérait réellement dans sa question.

C'est sûr (surtout si on distingue les pions) que simuler un nombre suffisant de tirages pour analyser le comportement en fréquences des tirages (en comparant au dénombrement théorique rapporté au cardinal des possibles),  au lieu d'effectuer un dénombrement pur et simple, doit devenir gigantesque assez rapidement.
Il est possible aussi (mais je n'y connais rien) qu'une surabondance de tirages ne mettent finalement en valeur que le biais du caractère pseudo-aléatoire de la machine, et difficile alors d'estimer le résultat de la simulation vis à vis d'un calcul théorique quelconque (mais j'insiste je ne suis pas un spécialiste, et peut-être des calculs de probabilités sur... les probabilités sont-ils possibles).

Même sans simulation, mais de simples vérifications calculatoires, on peut aussi se heurter parfois assez rapidement à des limites digitales de taille:
j'ai évoqué dans la rubrique "énigmes" une question arithmétique (la stationnarité des suites a^(a^(a...) modulo un entier n donné ), si on veut faire quelques essais numériques bruts, on va vite dans le mur ! Un peu mieux est de suivre la démarche de la  preuve numériquement, étape par étape, mais c'est franchement assez pénible.
Côté formel, les écritures elles-même devenant particulièrement lourdes, un mathématicien (D. Knuth) a eu l'idée d'adopter une notation spéciale pour condenser les expressions.
Bref on surnage (ou on essaye de ...) dans un monde impitoyable :-)

Merci pour les tests de simulation.
Pour éviter les décimales avec des calculs en fréquence, un algorithme et un programme de recherche des configurations est peut-être faisable.

Alain


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#7 31-08-2024 23:32:15

Michel Coste
Membre
Inscription : 05-10-2018
Messages : 1 170

Re : Dénombrement

Bonsoir,

Si on s'intéresse aux probabilités, distinguer ou non les jetons n'a pas vraiment d'importance.
En suivant la démarche de Matmusgep, mais de façon correcte, on arrivait bien à une probabilité de $1249/25^4$, où
$$1249 = 2\times(5-1)\times(5^3+5^2+5+1) +1=2\times5^4-1$$

Hors ligne

#8 01-09-2024 09:56:37

Ernst
Membre
Inscription : 30-01-2024
Messages : 140

Re : Dénombrement

Bonjour tout le monde,

Dans mes simulations les jetons sont indistincts. Au départ je pose les cinq au hasard puis j’étudie la validité du placement. Pour n petit cela marche bien, les probabilités d’alignement restent assez élevées et les calculs sont vite menés, mais quand n grandit cela devient problématique parce qu’il y a de moins en moins d’alignements et donc je perds de plus en plus de temps à faire un tas de calculs pour rien, pas top.

Pour aller plus vite, je teste la pose à chaque jeton et je passe à l’essai suivant dès qu’un jeton est mal placé et empêche tout succès ultérieur. Pour tester la validité de ce jeton, inutile d’ailleurs de mémoriser son emplacement exact, il suffit d’incrémenter la ligne et la colonne où il se place. À ce moment, s’il n’y en a pas au moins une des deux qui correspond au nombre de jetons déjà posés, c’est qu’on est hors ligne et hors colonne, donc échec, inutile d’aller plus loin, j’arrête cette tentative. Si le cinquième passe sans échec, c’est un succès, yeah !

Hors ligne

#9 01-09-2024 10:00:50

Ernst
Membre
Inscription : 30-01-2024
Messages : 140

Re : Dénombrement

Bonjour toujours,

En fait il y a deux cas de figure. Si on compte toutes les dispositions possibles, on obtient ce genre de choses :

n |  Total  |  Alignés | Temps (s)
----------------------------------
1 |       1 |        1 | 0.0000
2 |      16 |       12 | 0.0000
3 |     729 |      153 | 0.0010
4 |   65536 |     2032 | 0.1250
5 | 9765625 |    31225 | 19.410

Si on ne compte que les dispositions uniques, on obtient ce genre de choses :

n |  Total  | Alignées | Temps (s)
-----------------------------------
1 |       1 |        1 | 0.0000
2 |      10 |        8 | 0.0000
3 |     165 |       51 | 0.0000
4 |    3876 |      264 | 0.0080
5 |  118755 |     1235 | 0.2390

En fait il doit y avoir une question d’équiprobabilité là-dedans, quand je simule je tombe sur les premiers chiffres, pas les seconds. Je vais mettre les programmes plus bas, au cas où ça intéresse quelqu’un.

Hors ligne

#10 01-09-2024 10:25:20

Ernst
Membre
Inscription : 30-01-2024
Messages : 140

Re : Dénombrement

Bonjour encore,

Voici le code Python qui permet d’évaluer un million de configurations en moins de dix secondes en le copiant / collant sur ce site (script à gauche, execute en bas)

import random
import time

def optimized_trials(n, num_trials):
    successes = 0
    for _ in range(num_trials):
        rows = [0] * n
        cols = [0] * n
        for _ in range(n):
            x, y = random.randrange(n), random.randrange(n)
            rows[y] += 1
            if rows[y] == n:
                successes += 1
                break
            cols[x] += 1
            if cols[x] == n:
                successes += 1
                break
    return successes

def main():
    n = 5
    num_trials = 1000000
   
    start_time = time.time()
   
    successes = optimized_trials(n, num_trials)
   
    end_time = time.time()
    elapsed_time = end_time - start_time
   
    success_rate = (successes / num_trials) * 100
   
    print(f"Nombre de tirages : {num_trials}")
    print(f"Nombre de succès : {successes}")
    print(f"Pourcentage de succès : {success_rate:.5f}%")
    print(f"Temps d'exécution : {elapsed_time:.2f} secondes")

if __name__ == "__main__":
    main()

En def main() on peut bien sûr s'amuser à changer le nombre de jetons et de tirages.

Le C est beaucoup plus efficace, on peut s'en rendre compte par exemple en copiant / remplaçant le programme sur ce site (script à gauche, execute en haut).

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 5
#define NUM_TRIALS 1000000
#define RAND_MAX_PLUS_1 ((unsigned long long)RAND_MAX + 1)
#define RAND_MAX_PLUS_1_SQUARE ((unsigned long long)RAND_MAX_PLUS_1 * RAND_MAX_PLUS_1)

static inline unsigned long long xorshift64star(void) {
    static unsigned long long x = 1;
    x ^= x >> 12;
    x ^= x << 25;
    x ^= x >> 27;
    return x * 0x2545F4914F6CDD1DULL;
}

static inline unsigned int fast_rand(void) {
    return (unsigned int)(xorshift64star() & 0xFFFFFFFF);
}

static inline unsigned int fast_rand_range(unsigned int limit) {
    return (unsigned int)((fast_rand() * (unsigned long long)limit) >> 32);
}

int main(void) {
    unsigned int successes = 0;
    unsigned int rows[N], cols[N];
    unsigned int i, j, x, y;
    clock_t start, end;
    double cpu_time_used;

    start = clock();

    for (i = 0; i < NUM_TRIALS; ++i) {
        for (j = 0; j < N; ++j) {
            rows[j] = cols[j] = 0;
        }

        for (j = 0; j < N; ++j) {
            x = fast_rand_range(N);
            y = fast_rand_range(N);
            if (++rows[y] == N || ++cols[x] == N) {
                ++successes;
                break;
            }
        }
    }

    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

    printf("Nombre de tirages : %d\n", NUM_TRIALS);
    printf("Nombre de succès : %u\n", successes);
    printf("Pourcentage de succès : %.5f%%\n", (double)successes / NUM_TRIALS * 100);
    printf("Temps d'exécution : %.2f secondes\n", cpu_time_used);

    return 0;
}

On peut s'amuser à changer le nombre de jetons et le nombre d’essais (N 5 et NUM_TRIAL 1000000 lignes 4 et 5), n'importe comment on tombe bien sur la formule de @bridgslam. Au-delà d'un certain $n$ ça devient compliqué (temps de plus en plus long et nécessité d’augmenter les essais pour avoir quelques succès tant la proba devient faible).

Hors ligne

#11 01-09-2024 10:46:18

Ernst
Membre
Inscription : 30-01-2024
Messages : 140

Re : Dénombrement

Bon, je termine.

Les simulations, je les avais programmé tranquillou chez moi, mais pour un forum valait mieux du standard que tout le monde puisse utiliser. La grande mode actuelle c’est Python, ok, mais c’est quand même pas mal lent.

J’ai donc utilisé un assistant IA, ici Perplexity, et je lui ai expliqué ce que j’attendais. Résultat, il m’a pondu ces deux programmes sans une ligne de code de ma part. Bon, faut être honnête, je savais quand même assez bien ce qu’il fallait faire. Quant à l’exécution de ces programmes, il fallait qu’elle soit accessible à tous, donc rien sur ma machine mais tout à distance sur des sites qui proposent les calculs.

On peut se faire une idée de la démarche, la discussion complète (erreurs comprises) est > ici <. Il est toujours possible bien sûr de copier / remplacer le code dans les sites donnés précédemment pour reproduire la progression complète, mais il est peut être plus simple de lire uniquement mes interventions en gras pour comprendre à quel point la méthode de travail est efficace.

(je me demande d'ailleurs s'il ne faudrait pas dupliquer ces deux derniers messages dans la partie « programmation »)

Hors ligne

#12 01-09-2024 11:30:13

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 417

Re : Dénombrement

Bonjour,

Vu le ( gros ) travail déjà fourni, je n'ose pas vous demander de simulations avec 5 jetons placés au hasard sur un plateau ... d'Abalone ... :-), et avec la problématique analogue des situations d'alignements ou même en généralisant à un cube n x n x n (et quid des hypercubes ? :-) , plus proche  )
Vis à vis de ce que je connais en informatique, ton labeur est d'autant plus intéressant que j'avais travaillé sérieusement avec le langage Python, C, C++ ( principalement on va dire, je passe sur les scripts shell, Perl, java, java3d, pour me diriger ensuite côté web, avec une prédilection pour le framework Angular au plan client-side et notamment j'avais adoré la notion d'"observables" absolument géniale.

Sinon, Michel Coste tombe sur le même résultat, en suivant la logique de dénombrement amorcée par le posteur initial, ce qui mérite clairement des louanges.
J'ai préféré abordé le dénombrement en lui-même différemment, peut-être (à mon goût) plus synthétique.
La distinction des jetons ou pas ne change rien à l'affaire probabiliste, mais pour dénombrer les cas favorables, il faut bien se placer dans un cas de figure déterminé et s'y tenir.

J'ai de gros trous sur mon quota de connaissances global en math ( en autodidacte ), que je tente d'améliorer, c'est chronophage quand on s'essaie sur de bons exercices ou pbs en // , du coup j'avoue avoir lâché (ou plutôt relâché) sur l'algorithmique et la programmation, à mon grand dam.

Bon courage et encore merci pour cet excellent travail.

[nota]: pour l'hypercube de côté n en dimension d, le nombre de configurations semble être $n^d( 2n^{n-1} - d + 1)$ sauf erreur, donc la probabilité est
$\frac { n^d( 2n^{n-1} - d + 1)}{n^{nd}}$

Alain

Dernière modification par bridgslam (01-09-2024 14:47:53)


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#13 01-09-2024 18:53:29

Ernst
Membre
Inscription : 30-01-2024
Messages : 140

Re : Dénombrement

bridgslam a écrit :

simulations avec 5 jetons placés au hasard sur un plateau ... d'Abalone ... :-)

Re-bonjour,
J’ai d’abord testé un plateau d’Abalone avec deux billes au hasard – qui ne peuvent pas se superposer, normal, ce sont des billes – avec affichage si alignement ou non, pour ce genre de sortie :

Plateau 15:
        . . . . .
       . . . . ● .
      . ● . . . . .
     . . . . . . . .
    . . . . . . . . .
     . . . . . . . .
      . . . . . . .
       . . . . . .
        . . . . .
NON

Plateau 16:
        . . . . .
       . . . . . .
      . . . . . . .
     . . . . . . . .
    . . . . . . ● . .
     . . . . . . . .
      . . . . . . .
       . . . . . .
        . . . ● .
NON

Plateau 17:
        . . . . .
       . . ● . . .
      . . . . . . .
     . . . . . . . .
    . . . . . . . . .
     . . . . . . . .
      . . . . . . .
       . . . . . ●
        . . . . .
OUI

Plateau 18:
        . . . . .
       . . . . . .
      . . . . ● . .
     . . . . . . . .
    . . . . . . . . .
     . . . ● . . . .
      . . . . . . .
       . . . . . .
        . . . . .
OUI

Plateau 19:
        . . . . .
       . . . . . .
      . . ● . . . .
     . . . . . . . .
    . ● . . . . . . .
     . . . . . . . .
      . . . . . . .
       . . . . . .
        . . . . .
NON

Plateau 20:
        . . ● . .
       . . . . . .
      . . . . . . .
     . . . . . . . .
    . . . . . . . . .
     . . . . . . ● .
      . . . . . . .
       . . . . . .
        . . . . .
OUI

Une fois que c’est validé, statistiques sur une centaine de tirages, extrait :

Alignement trouvé (simulation 91):
        . . . . .
       . . . . . .
      . . . . . . .
     . . . . . . . .
    . ● ● . . . . . .
     . . . . . . . .
      . . . . . . .
       . . . . . .
        . . . . .

Alignement trouvé (simulation 93):
        . . . . .
       . . . . . .
      . . . ● ● . .
     . . . . . . . .
    . . . . . . . . .
     . . . . . . . .
      . . . . . . .
       . . . . . .
        . . . . .

Alignement trouvé (simulation 97):
        . . . . .
       . . . ● . .
      . . . . . . .
     . . . . . . . .
    . . . . . . . . .
     . . . . . . . .
      . . . . . . .
       ● . . . . .
        . . . . .

Alignement trouvé (simulation 100):
        . . . . .
       . . . . . .
      . . . . . . .
     . . . . . . . .
    . . . . . . . . .
     . . . . . . . .
      . . . . . . .
       . . . . . .
        . ● . . ●

Statistiques finales:
Nombre total de simulations: 100
Nombre d'alignements trouvés: 31
Taux d'alignement: 31.00%

Donc ça marche, fin des procédures de vérification.

Dans ce cas, proba d’alignement de $2$ billes sur un plateau d’Abalone :
Nombre total de simulations: 1 000 000
Nombre d'alignements trouvés: 301 203
Taux d'alignement: 30.120%
Temps d'exécution total: 27.26 secondes

On passe à $3$ billes, les probas s’effondrent :
Nombre total de simulations: 1 000 000
Nombre d'alignements trouvés: 27 366
Taux d'alignement: 2.737%
Temps d'exécution total: 30.76 secondes

Et enfin avec $5$ billes :
Nombre total de simulations: 1 000 000
Nombre d'alignements trouvés: 156
Taux d'alignement: 0.016%
Temps d'exécution total: 42.26 secondes

J’ai mis ici le programme en Python, qui permet de modifier la taille du plateau, le nombre de billes et le nombre de simulations directement dans le script, tout en bas :

import random
import time

class Board:
    def __init__(self, side_length):
        self.side_length = side_length
        self.cells = {}
        for q in range(-side_length + 1, side_length):
            r_start = max(-side_length + 1, -q - side_length + 1)
            r_end = min(side_length - 1, -q + side_length - 1)
            for r in range(r_start, r_end + 1):
                s = -q - r
                self.cells[(q, r, s)] = None

    def place_random_marble(self):
        empty_cells = [coord for coord, value in self.cells.items() if value is None]
        if empty_cells:
            chosen_cell = random.choice(empty_cells)
            self.cells[chosen_cell] = "black"
            return chosen_cell
        return None

def are_marbles_aligned(marbles):
    if len(marbles) < 2:
        return True
   
    for axis in range(3):
        if all(marble[axis] == marbles[0][axis] for marble in marbles):
            return True
    return False

def run_simulations(num_simulations, num_marbles, side_length):
    start_time = time.time()
    alignments = 0
    for _ in range(num_simulations):
        board = Board(side_length)
        marbles = []
        aligned = True
        for _ in range(num_marbles):
            new_marble = board.place_random_marble()
            if new_marble is None:
                aligned = False
                break
            marbles.append(new_marble)
            if not are_marbles_aligned(marbles):
                aligned = False
                break
       
        if aligned:
            alignments += 1

    end_time = time.time()
    execution_time = end_time - start_time

    alignment_rate = (alignments / num_simulations) * 100

    print(f"Statistiques finales:")
    print(f"Taille du plateau: {side_length} emplacements par côté")
    print(f"Nombre de billes: {num_marbles}")
    print(f"Nombre total de simulations: {num_simulations:,}")
    print(f"Nombre d'alignements trouvés: {alignments:,}")
    print(f"Taux d'alignement: {alignment_rate:.4f}%")
    print(f"Temps d'exécution total: {execution_time:.2f} secondes")

# Définir une seed aléatoire
random.seed(int(time.time()))

# Paramètres configurables
NUM_SIMULATIONS = 1_000_000
NUM_MARBLES = 5
SIDE_LENGTH = 5  # Nombre d'emplacements sur chaque côté du plateau

# Exécuter les simulations
run_simulations(NUM_SIMULATIONS, NUM_MARBLES, SIDE_LENGTH)

Hors ligne

#14 01-09-2024 19:17:06

Ernst
Membre
Inscription : 30-01-2024
Messages : 140

Re : Dénombrement

bridgslam a écrit :

pour dénombrer les cas favorables, il faut bien se placer dans un cas de figure déterminé et s'y tenir.

C'est vrai, d'autant que ce qu'on appelle « alignement » est déjà en soi une problématique.

En restant sur un tableau orthogonal classique genre papier quadrillé, quid des diagonales ? Les grandes diagonales ok, mais celles qui lui sont parallèles ? Puisque les jetons peuvent être superposés, rien n'empêche d'avoir les cinq jetons sur quatre ou trois emplacements seulement, donc des diagonales courtes, voire alignés « géométriquement » comme dans ces quelques exemples :

. . x . .     o . . x .     x . . . o
. . . x o     . . o . .     . . x . .
. . . o x     . . x . o     . . . o x
. . o . .     . . . . .     . . . . .
. o . . .     . x . . .     . . o . .
. . . x .     . . . x .     . . . . .
. . . . x     . x . . .     . . . . .
. . . . o     . . . . .     o . . . .
. . . . .     o . . . .     . . . x .
. . o . .     . . . o .     . . . . .

On revient donc bien au problème des dénombrements, titre de cette enfilade, et je me souviens de casse-têtes géométriques dans lesquels on devait dénombrer les triangles ou des rectangles crées par des figures enchevêtrées, rigolo.

Hors ligne

#15 01-09-2024 19:32:01

Michel Coste
Membre
Inscription : 05-10-2018
Messages : 1 170

Re : Dénombrement

Bonsoir,

Dénombrement pour deux alignés (dans une des trois directions) sur le plateau d'Abalone :
$$(1\times24+6\times22+12\times20+18\times18+24\times 16)/2$$Ce qui fait une proba (en supposant les positions équiprobables) de $92/305 \simeq 30,16\%$

Hors ligne

#16 01-09-2024 22:13:54

Ernst
Membre
Inscription : 30-01-2024
Messages : 140

Re : Dénombrement

Bonsoir,

Michel Coste a écrit :

Dénombrement pour deux alignés (dans une des trois directions) sur le plateau d'Abalone :
$$(1\times24+6\times22+12\times20+18\times18+24\times 16)/2$$Ce qui fait une proba (en supposant les positions équiprobables) de $92/305 \simeq 30,16\%$

Ah oui, très bien ! Je suis toujours admiratif de ces formules, perso il me faut des millions de simulations pour approcher cette valeur, qu’on en juge :

Avec Python et interpréteur en ligne :

Taille du plateau: 5 emplacements par côté
Nombre de billes: 2
Nombre total de simulations: 1 000 000
Nombre d'alignements trouvés: 302 100
Taux d'alignement: 30,2100 %
Temps d'exécution total: 31,66 secondes

En C compilé sur ma bécane :

Taille du plateau: 5 emplacements par côté
Nombre de billes: 2
Nombre total de simulations: 100 000 000
Nombre d'alignements trouvés: 30 161 130
Taux d'alignement: 30,1611 %
Temps d'exécution total: 24,98 secondes

En poussant les feux j’arrive au milliard (C multi-threadé sur ma bécane i7 8 coeurs)

Taille du plateau: 5 emplacements par côté
Nombre de billes: 2
Nombre total de simulations: 1 000 000 000
Nombre d'alignements trouvés: 301 620 323
Taux d'alignement: 30,1620 %
Temps d'exécution total: 34,87 secondes

Bon, il n’y a peut-être pas besoin d’autant, n’empêche que je suis content de voir qu’on trouve la même chose, j’ai toujours peur de me planter.

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
soixante quatre moins trente trois
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums