un petit problème pour les vacances

**Biname** · 14/08/2023, 23h19

Salut,
Question cruciale :

Notation re re re simplifiée

Grille m colonnes et n lignes
On peut oublier m disons m = 8

H est ligne route faite de H uniquement
? est tout sauf une ligne route
pas nécessaire de représenter toute la ligne

Pour n = 3, on a les 7 cas suivants

Code:

cas | 1   2   3   4   5   6   7
-------------------------------
L1  | ?   H   ?   ?   H   ?   H
    |
L2  | ?   ?   H   ?   H   H   H
    |
L3  | ?   ?   ?   H   ?   H   H
-------------------------------

Sachant que les cas 3, 5, 6, 7 sont identiques =

H
H
H

Combien de cas avons-nous ? 7 cas ou 4 cas ? Ma récurrence en compte 4 et Poincaré ?

En pratique des cas différents, il n'y en a ici que 4.

Biname

**GBZM** · 14/08/2023, 23h32

Toujours dans le brouillard à ce que je vois, Biname .... il ne tient qu'à toi d'en sortir.
Bonne nuit !

**GBZM** · 15/08/2023, 09h39

Faut-il lancer un avis de recherche concernant MissJenny qui a initié ce fil et qui a disparu ?

Pourquoi et-ce que Biname ne s'en sort pas alors que Poincaré y arrive les doigts dans le nez ? Parce que Poincaré prend les choses par le bon bout. L'ensemble des pavages favorables que l'on veut compter est la réunion de cas élémentaires qui sont "il y a un chemin traversant horizontal en ligne n° $\text{[math]}$ ", pour $\text{[math]}$ allant de 0 à 6. Bien sûr cette réunion n'est pas disjointe. Mais Poincaré avec sa formule du crible se débrouille très bien pour calculer de manière systématique le nombre d'éléments de cette réunion en retranchant de la somme des nombres d'éléments (qui donnerait le bon compte en cas de réunion disjointe) les nombres d'éléments d'intersections 2 à 2 (pour enlever les doubles comptes), puis en ajoutant les nombres d'éléments d'intersection 3 à 3 (parce qu'on a trop enlevé pour les triples comptes) etc. ; cette méthode de comptage porte aussi le nom de principe d'inclusion-exclusion, ce qui est assez parlant.
Cette méthode marche bien parce qu'on sait bien compter le nombres de pavages comportant des chamins traversants horizontaux en lignes $\text{[math]}$ . J'insiste ici sur le fait qu'on n'impose rien au pavage au dessus de la ligne $\text{[math]}$ , entre la ligne $\text{[math]}$ et la ligne $\text{[math]}$ , etc., au-dessous de la ligne $\text{[math]}$ , à part d'être un pavage par dominos. ON N'IMPOSE PAS QU'EN DEHORS DE CES LIGNES $\text{[math]}$ IL N'Y AIT AUCUN CHEMIN TRAVERSANT HORIZONTAL.
C'est là la différence fondamentale avec ce qu'essaie de faire Biname et qui le conduit dans un bazar inextricable où on n'est sûr de n'avoir oublié aucun cas que quand on retrouve le résultat déjà donné par la formule du crible de Poincaré, faute d'une méthode systématique facilement programmable. Biname veut compter des pavages où il n'y a aucun chemin horizontal traversant en dehors des lignes qu'il a fixées. Pourquoi ? Parce qu'il veut pour compter une liste de cas disjoints. Ses difficultés montrent bien que ce n'est pas prendre les choses par le bon bout pour ce problème.

**Biname** · 15/08/2023, 10h07

Salut,
Ma solution m'amuse et Poincaré m'ennuie. Puisque plus personne ne veut jouer avec moi, je vais jouer tout seul

Miss Jenny ? Dernière activité sur Futura le 14/08 à 17:00, dernier msg posté le 11/08 à 12:00.

Biname

**Biname** · 15/08/2023, 10h47

Salut,
En anglais, "inclusion exclusion principle", le nom de Poincaré est zappé
https://en.wikipedia.org/wiki/Inclus...sion_principle
Un peu plus riche.
Biname

**GBZM** · 15/08/2023, 11h58

Eh bien, bon courage ! Pour le moment tu n'es pas encore arrivé à 5. Il te reste du boulot pour arriver à 7.

**Liet Kynes** · 15/08/2023, 12h51

Envoyé par GBZM

Eh bien, bon courage ! Pour le moment tu n'es pas encore arrivé à 5. Il te reste du boulot pour arriver à 7.

Perso, je n'ai pas encore saisi le fonctionnement de la formule du crible, je me rappelle l'avoir vu en cours et appliqué en trouvant cela astucieux pourtant.
Par contre, en l'absence de code, si on fait "à la main" paier ou tableur.. on tombe quand même sur des écritures longues?

**GBZM** · 15/08/2023, 14h18

Liet Kynes,
As-tu compris que l'ensemble des pavages favorables que l'on cherche à dénombrer est la réunion (non disjointe !) des ensembles de pavages $\text{[math]}$ où un pavage par dominos appartient à $\text{[math]}$ si et seulement si il présente un chemin traversant horizontal en ligne n° i ?
Par ailleurs, as-tu vu que j'ai traité à la main le cas de 5 lignes en bas de page précédente ? Bien sûr, pour $\text{[math]}$ lignes il y a $\text{[math]}$ cas à considérer, ce qui fait un bon paquet. Mais le code pour traiter ces cas est court, comme tu as pu le constater.

**Biname** · 15/08/2023, 15h48

Envoyé par Liet Kynes

Perso, je n'ai pas encore saisi le fonctionnement de la formule du crible, je me rappelle l'avoir vu en cours et appliqué en trouvant cela astucieux pourtant.
Par contre, en l'absence de code, si on fait "à la main" paier ou tableur.. on tombe quand même sur des écritures longues?

GBZM ne peut pas nier que la liste des cas çi-dessous est celle utilisée par le crible. (1) signifie une route en 1 et pas ailleurs, (0,1) signifie une route en 0 et en 1 et pas ailleurs, ...
Le crible ne peut pas deviner cela.
Image :
Nom : Poincare_2.jpg
Affichages : 73
Taille : 323,3 Ko

Nom : Poincare_2.jpg
Affichages : 73
Taille : 323,3 Ko

Maintenant, il suffit de trouver un cas.
Ma récurrence permet de résoudre ce PB.
Biname

**GBZM** · 15/08/2023, 15h57

GBZM ne peut pas nier que la liste des cas çi-dessous est celle utilisée par le crible. (1) signifie une route en 1 et pas ailleurs, (0,1) signifie une route en 0 et en 1 et pas ailleurs, ...

Biname, je suis désespéré par ton absence totale de compréhension. J'ai pourtant bien pris la peine d'écrire en capitales :
"Cette méthode marche bien parce qu'on sait bien compter le nombres de pavages comportant des chamins traversants horizontaux en lignes $\text{[math]}$ . J'insiste ici sur le fait qu'on n'impose rien au pavage au dessus de la ligne $\text{[math]}$ , entre la ligne $\text{[math]}$ et la ligne $\text{[math]}$ , etc., au-dessous de la ligne $\text{[math]}$ , à part d'être un pavage par dominos. ON N'IMPOSE PAS QU'EN DEHORS DE CES LIGNES $\text{[math]}$ IL N'Y AIT AUCUN CHEMIN TRAVERSANT HORIZONTAL."

**GBZM** · 15/08/2023, 16h06

Je répète encore une fois pour Biname :
$\text{[math]}$ est l'ensemble des pavages qui présentent un chemin traversant horizontal en ligne n° $\text{[math]}$ . ON NE DIT RIEN SUR CE QUI SE PASSE AILLEURS, SAUF QUE C'EST UN PAVAGE PAR DOMINOS !!!
$\text{[math]}$ est l'ensemble des pavages qui présentent un chemin traversant horizontal en lignes n° $\text{[math]}$ ON NE DIT RIEN SUR CE QUI SE PASSE AILLEURS, SAUF QUE C'EST UN PAVAGE PAR DOMINOS !!!
Ce sont ces ensembles de pavages qui interviennent dans la formule du crible de Poincaré pour calculer le nombre de pavages dans la réunion des $\text{[math]}$ . Cette réunion est l'ensemble des pavages ayant au moins un chemin traversant horizontal.
Ce n'est pas du chinois, me semble-t-il ?

**Biname** · 15/08/2023, 16h43

Envoyé par GBZM

Biname, je suis désespéré par ton absence totale de compréhension. J'ai pourtant bien pris la peine d'écrire en capitales :
"Cette méthode marche bien parce qu'on sait bien compter le nombres de pavages comportant des chamins traversants horizontaux en lignes $\text{[math]}$ . J'insiste ici sur le fait qu'on n'impose rien au pavage au dessus de la ligne $\text{[math]}$ , entre la ligne $\text{[math]}$ et la ligne $\text{[math]}$ , etc., au-dessous de la ligne $\text{[math]}$ , à part d'être un pavage par dominos. ON N'IMPOSE PAS QU'EN DEHORS DE CES LIGNES $\text{[math]}$ IL N'Y AIT AUCUN CHEMIN TRAVERSANT HORIZONTAL."

Oui mais le cardinal de tes cas comptent des cas en trop : (1) et (0,1) = 1 cas réel et deux cas pour le crible et ça, le crible ne peut pas le deviner car c'est lié au pavage.

Avec ta personnalité, l'attitude suivante sera 'je vous ai bien eu', après les attaques 'ad hominem', après tu passeras du mode rationnel au mode plaidoirie ... si on y est pas déjà

Biname

**Liet Kynes** · 15/08/2023, 16h55

Envoyé par GBZM

Je répète encore une fois pour Biname :
$\text{[math]}$ est l'ensemble des pavages qui présentent un chemin traversant horizontal en ligne n° $\text{[math]}$ . ON NE DIT RIEN SUR CE QUI SE PASSE AILLEURS, SAUF QUE C'EST UN PAVAGE PAR DOMINOS !!!

Si un pavage contient au moins un chemin traversant alors c'est un élément de $\text{[math]}$

Envoyé par GBZM

$\text{[math]}$ est l'ensemble des pavages qui présentent un chemin traversant horizontal en lignes n° $\text{[math]}$ ON NE DIT RIEN SUR CE QUI SE PASSE AILLEURS, SAUF QUE C'EST UN PAVAGE PAR DOMINOS !!!
Ce sont ces ensembles de pavages qui interviennent dans la formule du crible de Poincaré pour calculer le nombre de pavages dans la réunion des $\text{[math]}$ . Cette réunion est l'ensemble des pavages ayant au moins un chemin traversant horizontal.
Ce n'est pas du chinois, me semble-t-il ?

$\text{[math]}$ ... $\text{[math]}$ sont des sous ensembles de $\text{[math]}$ et $\text{[math]}$ $\text{[math]}$ $\text{[math]}$ $\text{[math]}$ $\text{[math]}$

**GBZM** · 15/08/2023, 18h02

Bon, je renonce à essayer d'expliquer à Biname. À l'impossible nul n'est tenu, et si en plus c'est pour me faire injurier ...

Liet Kynes : Si un pavage contient au moins un chemin traversant horizontal, alors c'est un élément d'au moins un des $\text{[math]}$ , c.-à-d. un élément de la réuion des $\text{[math]}$

Supposons qu'un pavage a exactement trois chemins traversants (pas plus, pas moins), disons dans les lignes n°0, n°1 et n°4.
Ce pavage est dans $\text{[math]}$ , $\text{[math]}$ et $\text{[math]}$ : la formule du crible le compte trois fois positivement.
Ce pavage est dans $\text{[math]}$ , $\text{[math]}$ et $\text{[math]}$ : la formule du crible le compte trois fois négativement.
Ce pavage est dans $\text{[math]}$ : la formule du crible le compte une fois positivement.

Au total, la formule du crible compte bien ce pavage 3-3+1 = 1 fois. Bingo !
Ça marche de la même façon pour tous les pavages qui présentent au moins un chemin traversant horizontal, c.-à-d. ceux qui sont dans la réunion des $\text{[math]}$ Au total, la formule du crible compte exactement une fois chacun de ces pavages, c'est le "miracle" de l'inclusion-exclusion. Elle donne donc très exactement le nombre de pavages appartenant à la réunion des $\text{[math]}$ .

Il reste à comprendre comment on compte par exemple le nombre de pavages dans $\text{[math]}$ , puisque c'est un ingrédient de la formule du crible.
Au dessus de la ligne n°0, un rectangle de hauteur 0 : une seule possibilité de le paver.
Entre la ligne n°0 et la ligne n°1, un rectangle de hauteur 0 : une seule possibilité de le paver.
Entre la ligne n°1 et la ligne n°4, un rectangle de hauteur 2 : 34 possibilités de le paver par des dominos (ces pavages peuvent très bien coporter un chemin traversant horizontal, pas de problème : la définition de $\text{[math]}$ ne l'exclut pas).
Au dessous de la ligne n°4, un rectangle de hauteur 2 : 34 possibilités de le paver.
Donc $\text{[math]}$ compte 1 x 1 X 34 x 34 = 1156 pavages.

Le code que j'ai écrit fait ça automatiquement bien sûr.

Je me trouve d'une patience angélique.

**Biname** · 15/08/2023, 18h38

Pour écrire la liste des cas possibles niveau ligne, il suffit d'écrire tous les nombres en binaire ou le nombre de bits est le nombre de lignes.
Dans N, il n'y a ni redondances, ni trous.

(bit/lignes) : cas lignes
(1) 0, 1
(2) 00, 01, 10, 11
(3) 001, 010, ...

Biname

**Liet Kynes** · 15/08/2023, 19h20

Envoyé par GBZM

Supposons qu'un pavage a exactement trois chemins traversants (pas plus, pas moins), disons dans les lignes n°0, n°1 et n°4.
Ce pavage est dans $\text{[math]}$ , $\text{[math]}$ et $\text{[math]}$ : la formule du crible le compte trois fois positivement.

Ce n'est pas évident à comprendre car tu dis que un Li soit un Li il faut et il suffit qu'il possède un chemin traversant en i. Le dénombrement des cas avec au moins un chemin traversant en L1 devrait être 2^i

**GBZM** · 15/08/2023, 21h41

Précisément, $\text{[math]}$ est l'ensemble des pavages par dominos de la grille à 7 lignes et 8 colonnes (celle qui nous intéresse) qui ont un chemin traversant horizontal en ligne n° $\text{[math]}$ (les numéros des lignes vont de 0 à 6.
Au-dessus de cette ligne n° $\text{[math]}$ faite de 4 dominos horizontaux, il y a un rectangle de $\text{[math]}$ lignes sur 8 colonnes. En dessous de cette ligne, il y a un rectangle de $\text{[math]}$ lignes sur huit colonnes.
Le nombre de pavages en dominos de la grille entière qui appartiennent à $\text{[math]}$ (le cardinal de $\text{[math]}$ ), c'est donc le produit du nombre de pavages en dominos d'un rectangle de $\text{[math]}$ lignes sur 8 colonnes par le nombre de pavages en dominos d'un rectangle de $\text{[math]}$ lignes sur 8 colonnes.
D'où sors-tu ton $\text{[math]}$ ???

**Liet Kynes** · 16/08/2023, 07h28

Envoyé par GBZM

Le nombre de pavages en dominos de la grille entière qui appartiennent à $\text{[math]}$ (le cardinal de $\text{[math]}$ ), c'est donc le produit du nombre de pavages en dominos d'un rectangle de $\text{[math]}$ lignes sur 8 colonnes par le nombre de pavages en dominos d'un rectangle de $\text{[math]}$ lignes sur 8 colonnes.
[/TEX] ???

Je comprends que le principe l'inclusion dans la formule du crible nécessite ensuite l'exclusion= Le produit des 2 nombres de pavages de rectangles cités ci-dessus inclut des pavages avec et sans chemins traversants qu'il va falloir ensuite exclure.

Si je ne me trompe pour i lignes on obtiens donc i produits (->c'est pour cela que tu as parlé d'un rectangle de hauteur "0" au dessus de la première ligne: 0 pavage possible= 1 façon de paver ?)

Mon 2^i est une erreur de raisonnement. Il me reste à comprendre comment on procède à l'exclusion ou je n'ai pas encore compris l'inclusion?

**GBZM** · 16/08/2023, 08h51

"Si je ne me trompe pour i lignes on obtiens donc i produits".
Non, c'est i+1 : place i points sur une droite réelle. Ça fait combien d'intervalles (bornés ou non bornés) ?

Le principe d'inclusion-exclusion, c'est une généralisation (et une conséquence) de
Le nombre d'éléments de la réunion de A et B, c'est le nombre d'éléments de A plus le nombre d'éléments de B moins le nombre d'éléments de l'intersection de A et B
A et B sont inclus, l'intersection de A et B exclue.

Pour compter le nombre d'éléments de l'union de trois ensembles, les ensembles sont inclus, les intersections 2 à 2 exclues, l'intersection des 3 inclue.

**GBZM** · 16/08/2023, 08h58

Mais peut-être quand tu dis "i produits", tu veux dire "produit de i+1 quantités" ?

**MissJenny** · 16/08/2023, 14h25

merci pour vos réponses.

Quand on joue au jeu dominosa, les configurations sans "chemin traversant" sont rares, ce qui, d'après les calculs de GBZM, laisse penser que les configurations ne sont pas tirées au hasard uniformément parmi toutes les configurations possibles. Ca peut être dû à l'algorithme utilisé, mais c'est sans-doute aussi parce que dans le jeu dominosa il y a une contrainte supplémentaire : la solution doit être unique. Or le cas le plus simple de non-unicité est la situation où deux dominos forment un carré de 2x2 cases dont la diagonale porte un chiffre commun. Donc je soupçonne que les configurations choisies pour le jeu comportent relativement peu de carrés 2x2. (mais la question posée ne parlait pas ce ça).

**Liet Kynes** · 17/08/2023, 07h19

Envoyé par MissJenny

Ca peut être dû à l'algorithme utilisé, mais c'est sans-doute aussi parce que dans le jeu dominosa il y a une contrainte supplémentaire : la solution doit être unique.

Est-ce que cette idée est juste? ; une fois que tu as le dessin d'un pavage, tu peux répartir dessus tous les couples de nombres présents dans un autre dessin de pavage qui est valable en tant que solution.

**GBZM** · 17/08/2023, 07h28

Liet Kynes, j'ai l'impression que tu n'as pas bien compris le jeu de MissJenny : sur la grille 8x7, toutes les cases sont données avec un nombre de 0 à 6 (il y en a huit de chaque), et on doit retrouver dans cette grille les 28 dominos d'un jeu de dominos. Les nombres ne bougent pas, c'est le pavage par dominos qu'il faut trouver de façon qu'il y ait un et un seul double-zéro, un et un seul zéro-un etc., un et un seuk double-six.

**Liet Kynes** · 17/08/2023, 07h39

Envoyé par GBZM

Liet Kynes, j'ai l'impression que tu n'as pas bien compris le jeu de MissJenny : sur la grille 8x7, toutes les cases sont données avec un nombre de 0 à 6 (il y en a huit de chaque), et on doit retrouver dans cette grille les 28 dominos d'un jeu de dominos. Les nombres ne bougent pas, c'est le pavage par dominos qu'il faut trouver de façon qu'il y ait un et un seul double-zéro, un et un seul zéro-un etc., un et un seuk double-six.

on a 54 cases, donc pour un même pavage un nombre de solutions dénombrable, de ce que je comprends le but du jeu est en fait de dessiner le pavage si on souhaite calculer le nombre de parties possibles c'est faisable.

**Liet Kynes** · 17/08/2023, 07h43

Envoyé par GBZM

Les nombres ne bougent pas, c'est le pavage par dominos qu'il faut trouver de façon qu'il y ait un et un seul double-zéro, un et un seul zéro-un etc., un et un seuk double-six.

Rien n'empêche de faire "bouger" les nombres pour proposer une partie en effectuant la redistribution de 27 dominos dans un pavage parmi les 1292697

**MissJenny** · 17/08/2023, 09h32

ce qui est évident c'est que si on répartit au hasard les chiffres de 0 à 6 (8 de chaque) dans une grille 8x7 on ne pourra pas toujours constituer un jeu de dominos. Par contre pour une répartition donnée des chiffres il peut y avoir plusieurs solutions en dominos. Mais dans le programme avec lequel je joue ça n'est jamais le cas. C'est un programme distribué en open source d'ailleurs, quelqu'un de courageux peut regarder comment il fait.

**GBZM** · 17/08/2023, 11h33

À toutes fins utiles, il y a 28 dominos et 56 cases dans une grille 8 x 7 (pas 27 et 54).

**Liet Kynes** · 17/08/2023, 18h28

Envoyé par GBZM

À toutes fins utiles, il y a 28 dominos et 56 cases dans une grille 8 x 7 (pas 27 et 54).

OuPs, dans l'idée le jeu reste limité à une grille de 56 cases pour des dominos allant jusqu'à 6 .

Envoyé par MissJenny

ce qui est évident c'est que si on répartit au hasard les chiffres de 0 à 6 (8 de chaque) dans une grille 8x7 on ne pourra pas toujours constituer un jeu de dominos. Par contre pour une répartition donnée des chiffres il peut y avoir plusieurs solutions en dominos. Mais dans le programme avec lequel je joue ça n'est jamais le cas. C'est un programme distribué en open source d'ailleurs, quelqu'un de courageux peut regarder comment il fait.

On peux imaginer des générateurs de puzzles, le plus simpl étant celui qui utilise des carrés et/ou des rectangles taille mini 2*2

**Liet Kynes** · 19/08/2023, 19h27

J'ai repris le problème avec la méthode que j'avais envisagé. Je prends une à une les combinaisons pour lesquelles au moins une ligne est présente parmi les n lignes, le nombre de combinaisons se définit selon https://oeis.org/A077855

Si j'utilise les résultats des calculs avec la formule du crible je trouve 511333 cas favorables soit 511333/1292697= 0.3955

Pour 7 lignes il y a 36 combinaisons avec des lignes traversantes.

Si les lignes 3,4 sont traversantes, on devrais avoir pour cette combinaison (mise en évidence dans la liste ci-dessous):

- nombre de pavages possibles des lignes 1 et 2 = 34
- nombre de pavages possibles des lignes 5,6 et 7 = 153

D'après les résultats de la formule du crible donnés plus haut par GBZM:

- nombre de pavage sans lignes traversantes parmi les 34 = 1
- nombre de pavage sans lignes traversantes parmi les 153= 67

Soit pour cette combinaison ((34*153)*(67*1))=5135

0000001
0000011
0000100
0000111
0001000
0001001
0001100
0001111
0010000
0010001
0010011
0011000
0011001
0011100
0011111
1000000
1000001
1000011
1000100
1000111
1001000
1001001
1001100
1001111
1100000
1100001
1100011
1100100
1100111
1110000
1110001
1110011
1111000
1111001
1111100
1111111

**Biname** · 19/08/2023, 22h26

Liet msg #119,
Il y a en effet $\text{[math]}$ cas de pavages avec au moins une route différents,
Mon msg #105 et ton msg #106 le mentionnent, cela apparaît lorsqu'on demande au code donné par GBZM d'afficher C: le résultat du crible voir mon msg #99.
Pour lister les cas de routes, il suffit de compter de 0 à $\text{[math]}$ et d'afficher les nombres en binaire. Voici une fonction python qui fait ça. Comme je le dis msg 105 dans $\text{[math]}$ , il n'y a ni doublons, ni trous

Cliquez pour afficher

J'ai écrit un code python qui calcule mon algorithme

Cliquez pour afficher

Code:

L=7 liste sans(0 à 7) : [0, 0, 33, 86, 1973, 9398, 132921]   (récurrence avec/sans routes)
dec:  0 = bin:0000000  OK=0   no route
dec:  1 = bin:0000001  OK=1   6Z:1 = avec:132921  sans[6]^1  n_tot_avec_route=132921
dec:  2 = bin:0000010  OK=0   none single zero  = 0000011
dec:  3 = bin:0000011  OK=1   5Z:1 = avec:9398  sans[5]^1  n_tot_avec_route=9398
dec:  4 = bin:0000100  OK=1   2Z:1 = avec:33  sans[2]^1  4Z:1 = avec:1973  sans[4]^1  n_tot_avec_route=65109
dec:  5 = bin:0000101  OK=0   none single zero  = 0000111
dec:  6 = bin:0000110  OK=0   none single zero  = 0000111
dec:  7 = bin:0000111  OK=1   4Z:1 = avec:1973  sans[4]^1  n_tot_avec_route=1973
dec:  8 = bin:0001000  OK=1   3Z:2 = avec:7396  sans[3]^2  n_tot_avec_route=7396
dec:  9 = bin:0001001  OK=1   2Z:1 = avec:33  sans[2]^1  3Z:1 = avec:86  sans[3]^1  n_tot_avec_route=2838
dec: 10 = bin:0001010  OK=0   none single zero  = 0001111
dec: 11 = bin:0001011  OK=0   none single zero  = 0001111
dec: 12 = bin:0001100  OK=1   2Z:1 = avec:33  sans[2]^1  3Z:1 = avec:86  sans[3]^1  n_tot_avec_route=2838
dec: 13 = bin:0001101  OK=0   none single zero  = 0001111
dec: 14 = bin:0001110  OK=0   none single zero  = 0001111
dec: 15 = bin:0001111  OK=1   3Z:1 = avec:86  sans[3]^1  n_tot_avec_route=86
dec: 16 = bin:0010000  OK=1   2Z:1 = avec:33  sans[2]^1  4Z:1 = avec:1973  sans[4]^1  n_tot_avec_route=65109
dec: 17 = bin:0010001  OK=1   2Z:1 = avec:33  sans[2]^1  3Z:1 = avec:86  sans[3]^1  n_tot_avec_route=2838
dec: 18 = bin:0010010  OK=0   none single zero  = 0010011
dec: 19 = bin:0010011  OK=1   2Z:2 = avec:1089  sans[2]^2  n_tot_avec_route=1089
dec: 20 = bin:0010100  OK=0   none single zero  = 0011100
dec: 21 = bin:0010101  OK=0   none single zero  = 0011111
dec: 22 = bin:0010110  OK=0   none single zero  = 0011111
dec: 23 = bin:0010111  OK=0   none single zero  = 0011111
dec: 24 = bin:0011000  OK=1   2Z:1 = avec:33  sans[2]^1  3Z:1 = avec:86  sans[3]^1  n_tot_avec_route=2838
dec: 25 = bin:0011001  OK=1   2Z:2 = avec:1089  sans[2]^2  n_tot_avec_route=1089
dec: 26 = bin:0011010  OK=0   none single zero  = 0011111
dec: 27 = bin:0011011  OK=0   none single zero  = 0011111
dec: 28 = bin:0011100  OK=1   2Z:2 = avec:1089  sans[2]^2  n_tot_avec_route=1089
dec: 29 = bin:0011101  OK=0   none single zero  = 0011111
dec: 30 = bin:0011110  OK=0   none single zero  = 0011111
dec: 31 = bin:0011111  OK=1   2Z:1 = avec:33  sans[2]^1  n_tot_avec_route=33
dec: 32 = bin:0100000  OK=0   none single zero  = 1100000
dec: 33 = bin:0100001  OK=0   none single zero  = 1100001
dec: 34 = bin:0100010  OK=0   none single zero  = 1100011
dec: 35 = bin:0100011  OK=0   none single zero  = 1100011
dec: 36 = bin:0100100  OK=0   none single zero  = 1100100
dec: 37 = bin:0100101  OK=0   none single zero  = 1100111
dec: 38 = bin:0100110  OK=0   none single zero  = 1100111
dec: 39 = bin:0100111  OK=0   none single zero  = 1100111
dec: 40 = bin:0101000  OK=0   none single zero  = 1111000
dec: 41 = bin:0101001  OK=0   none single zero  = 1111001
dec: 42 = bin:0101010  OK=0   none single zero  = 1111111
dec: 43 = bin:0101011  OK=0   none single zero  = 1111111
dec: 44 = bin:0101100  OK=0   none single zero  = 1111100
dec: 45 = bin:0101101  OK=0   none single zero  = 1111111
dec: 46 = bin:0101110  OK=0   none single zero  = 1111111
dec: 47 = bin:0101111  OK=0   none single zero  = 1111111
dec: 48 = bin:0110000  OK=0   none single zero  = 1110000
dec: 49 = bin:0110001  OK=0   none single zero  = 1110001
dec: 50 = bin:0110010  OK=0   none single zero  = 1110011
dec: 51 = bin:0110011  OK=0   none single zero  = 1110011
dec: 52 = bin:0110100  OK=0   none single zero  = 1111100
dec: 53 = bin:0110101  OK=0   none single zero  = 1111111
dec: 54 = bin:0110110  OK=0   none single zero  = 1111111
dec: 55 = bin:0110111  OK=0   none single zero  = 1111111
dec: 56 = bin:0111000  OK=0   none single zero  = 1111000
dec: 57 = bin:0111001  OK=0   none single zero  = 1111001
dec: 58 = bin:0111010  OK=0   none single zero  = 1111111
dec: 59 = bin:0111011  OK=0   none single zero  = 1111111
dec: 60 = bin:0111100  OK=0   none single zero  = 1111100
dec: 61 = bin:0111101  OK=0   none single zero  = 1111111
dec: 62 = bin:0111110  OK=0   none single zero  = 1111111
dec: 63 = bin:0111111  OK=0   none single zero  = 1111111
dec: 64 = bin:1000000  OK=1   6Z:1 = avec:132921  sans[6]^1  n_tot_avec_route=132921
dec: 65 = bin:1000001  OK=1   5Z:1 = avec:9398  sans[5]^1  n_tot_avec_route=9398
dec: 66 = bin:1000010  OK=0   none single zero  = 1000011
dec: 67 = bin:1000011  OK=1   4Z:1 = avec:1973  sans[4]^1  n_tot_avec_route=1973
dec: 68 = bin:1000100  OK=1   2Z:1 = avec:33  sans[2]^1  3Z:1 = avec:86  sans[3]^1  n_tot_avec_route=2838
dec: 69 = bin:1000101  OK=0   none single zero  = 1000111
dec: 70 = bin:1000110  OK=0   none single zero  = 1000111
dec: 71 = bin:1000111  OK=1   3Z:1 = avec:86  sans[3]^1  n_tot_avec_route=86
dec: 72 = bin:1001000  OK=1   2Z:1 = avec:33  sans[2]^1  3Z:1 = avec:86  sans[3]^1  n_tot_avec_route=2838
dec: 73 = bin:1001001  OK=1   2Z:1 = avec:33  sans[2]^1  n_tot_avec_route=33
dec: 74 = bin:1001010  OK=0   none single zero  = 1001111
dec: 75 = bin:1001011  OK=0   none single zero  = 1001111
dec: 76 = bin:1001100  OK=1   2Z:2 = avec:1089  sans[2]^2  n_tot_avec_route=1089
dec: 77 = bin:1001101  OK=0   none single zero  = 1001111
dec: 78 = bin:1001110  OK=0   none single zero  = 1001111
dec: 79 = bin:1001111  OK=1   2Z:1 = avec:33  sans[2]^1  n_tot_avec_route=33
dec: 80 = bin:1010000  OK=0   none single zero  = 1110000
dec: 81 = bin:1010001  OK=0   none single zero  = 1110001
dec: 82 = bin:1010010  OK=0   none single zero  = 1110011
dec: 83 = bin:1010011  OK=0   none single zero  = 1110011
dec: 84 = bin:1010100  OK=0   none single zero  = 1111100
dec: 85 = bin:1010101  OK=0   none single zero  = 1111111
dec: 86 = bin:1010110  OK=0   none single zero  = 1111111
dec: 87 = bin:1010111  OK=0   none single zero  = 1111111
dec: 88 = bin:1011000  OK=0   none single zero  = 1111000
dec: 89 = bin:1011001  OK=0   none single zero  = 1111001
dec: 90 = bin:1011010  OK=0   none single zero  = 1111111
dec: 91 = bin:1011011  OK=0   none single zero  = 1111111
dec: 92 = bin:1011100  OK=0   none single zero  = 1111100
dec: 93 = bin:1011101  OK=0   none single zero  = 1111111
dec: 94 = bin:1011110  OK=0   none single zero  = 1111111
dec: 95 = bin:1011111  OK=0   none single zero  = 1111111
dec: 96 = bin:1100000  OK=1   5Z:1 = avec:9398  sans[5]^1  n_tot_avec_route=9398
dec: 97 = bin:1100001  OK=1   4Z:1 = avec:1973  sans[4]^1  n_tot_avec_route=1973
dec: 98 = bin:1100010  OK=0   none single zero  = 1100011
dec: 99 = bin:1100011  OK=1   3Z:1 = avec:86  sans[3]^1  n_tot_avec_route=86
dec:100 = bin:1100100  OK=1   2Z:2 = avec:1089  sans[2]^2  n_tot_avec_route=1089
dec:101 = bin:1100101  OK=0   none single zero  = 1100111
dec:102 = bin:1100110  OK=0   none single zero  = 1100111
dec:103 = bin:1100111  OK=1   2Z:1 = avec:33  sans[2]^1  n_tot_avec_route=33
dec:104 = bin:1101000  OK=0   none single zero  = 1111000
dec:105 = bin:1101001  OK=0   none single zero  = 1111001
dec:106 = bin:1101010  OK=0   none single zero  = 1111111
dec:107 = bin:1101011  OK=0   none single zero  = 1111111
dec:108 = bin:1101100  OK=0   none single zero  = 1111100
dec:109 = bin:1101101  OK=0   none single zero  = 1111111
dec:110 = bin:1101110  OK=0   none single zero  = 1111111
dec:111 = bin:1101111  OK=0   none single zero  = 1111111
dec:112 = bin:1110000  OK=1   4Z:1 = avec:1973  sans[4]^1  n_tot_avec_route=1973
dec:113 = bin:1110001  OK=1   3Z:1 = avec:86  sans[3]^1  n_tot_avec_route=86
dec:114 = bin:1110010  OK=0   none single zero  = 1110011
dec:115 = bin:1110011  OK=1   2Z:1 = avec:33  sans[2]^1  n_tot_avec_route=33
dec:116 = bin:1110100  OK=0   none single zero  = 1111100
dec:117 = bin:1110101  OK=0   none single zero  = 1111111
dec:118 = bin:1110110  OK=0   none single zero  = 1111111
dec:119 = bin:1110111  OK=0   none single zero  = 1111111
dec:120 = bin:1111000  OK=1   3Z:1 = avec:86  sans[3]^1  n_tot_avec_route=86
dec:121 = bin:1111001  OK=1   2Z:1 = avec:33  sans[2]^1  n_tot_avec_route=33
dec:122 = bin:1111010  OK=0   none single zero  = 1111111
dec:123 = bin:1111011  OK=0   none single zero  = 1111111
dec:124 = bin:1111100  OK=1   2Z:1 = avec:33  sans[2]^1  n_tot_avec_route=33
dec:125 = bin:1111101  OK=0   none single zero  = 1111111
dec:126 = bin:1111110  OK=0   none single zero  = 1111111
dec:127 = bin:1111111  OK=1   nZ=0_count=1  cas=1

debug_3 : L=7  cas(8,7)=1292697  n_tot=462677  sans_lignes : [0, 0, 33, 86, 1973, 9398, 132921, 830020]
Nombre de pavages de 0 à 7 : [1, 1, 34, 153, 2245, 14824, 167089, 1292697]
sans_lignes_list  de 0 à 7 : [0, 0, 33, 86, 1973, 9398, 132921, 830020]
avec_lignes_list  de 0 à 7 : [0, 1, 1, 67, 272, 5426, 34168, 462677]
proba avec lignes de 0 à 7 : ['1.0000', '1.0000', '0.0294', '0.4379', '0.1212', '0.3660', '0.2045', '0.3579']

Grille(8,7)    pav_possibles=1292697
   pav_sans_routes=830020  pav_avec_routes=462677
   probalilité au moins une route = 0.3579
Done in 0.0551 seconde


 Format csv
  i,         sans_routes,         avec_routes,   proba,       pav possibles
  0,                   0,                   0,  1.0000,                   0
  1,                   0,                   1,  1.0000,                   1
  2,                  33,                   1,  0.0294,                  34
  3,                  86,                  67,  0.4379,                 153
  4,                1973,                 272,  0.1212,                2245
  5,                9398,                5426,  0.3660,               14824
  6,              132921,               34168,  0.2045,              167089
  7,              830020,              462677,  0.3579,             1292697
========================================================
pour C=8 et L=0 à 19
Format csv
  i,         sans_routes,         avec_routes,   proba,       pav possibles
  0,                   0,                   0,  1.0000,                   1
  1,                   0,                   1,  1.0000,                   1
  2,                  33,                   1,  0.0294,                  34
  3,                  86,                  67,  0.4379,                 153
  4,                1973,                 272,  0.1212,                2245
  5,                9398,                5426,  0.3660,               14824
  6,              132921,               34168,  0.2045,              167089
  7,              830020,              462677,  0.3579,             1292697
  8,             9430571,             3558245,  0.2739,            12988816
  9,            68089006,            40346739,  0.3721,           108435745
 10,           689523103,           341628138,  0.3313,          1031151241
 11,          5407226470,          3533513354,  0.3952,          8940739824
 12,         51335211365,         31405794464,  0.3796,         82741005829
 13,        421873043306,        309291210527,  0.4230,        731164253833
 14,       3863839872139,       2811658364991,  0.4212,       6675498237130
 15,      32624391528796,      26929808940317,  0.4522,      59554200469113
 16,     292660727010774,     247400559526148,  0.4581,     540061286536922
 17,    2509259479402732,    2331850554263318,  0.4817,    4841110033666050
 18,   22251624701977660,   21501107871120700,  0.4914,   43752732573098360
 19,  192485915285218240,  200653229841605056,  0.5104,  393139145126823296

Sauf erreursss ... mais le code n'a probablement rien raté ?

Dans la mesure où une indexation des éléments est possible, e = E(i), les unions et les intersections peuvent se résoudre respectivement par des OU et des ET logiques. Il est donc possible d'écrire le crible avec des ET et des OU.

Biname

un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Discussions similaires

Bonsoir petit coup de main pour un DM spéciale vacances

Petit catamaran pour vos vacances

Un petit DM pour les vacances

Retour de vacances et petit souci...