Combien de possiblites dans une matrice
Cours gratuits > Forum > Forum maths || En basCombien de possiblites dans une matrice
Message de unclescrooge posté le 15-07-2020 à 20:58:11 (S | E | F)
Bonjour tout le monde,
Par avance, pardonnez mon orthographe, je dispose uniquement d un clavier qwerty, ce qui me complique la tache pour ecrire correctement en francais.
Je suis en train de rediger un petit programme en C qui me permettra de resoudre un jeu appele Sky Scrapper, je vous laisse taper sur Google pour ceux que ca interesse.
Ma question est simple, et j ai un gros doute concernant la reponse.
Je vais creer des matrices de dimension NxN, N etant defini en amont. La question est la suivante, combien de matrices <u>differentes</u> puis-je composer ? Sachant que la seule regle qui regisse mes matrices est la suivante : interdit d avoir la meme valeur sur une meme ligne ou colonne.
Ex : Pour une matrice de 2 il n y a que 2 solutions possibles
1 2
2 1
et
2 1
1 2
sachant que le pattern suivant n est par exemple pas admissible:
1 1
1 2
Pour l instant je suis arrive a la formule suivante : N * (N-1)^2 ou tout simplement N * (N - 1) * (N - 1).
Qu en pensez vous ? Cela vous semble-t-il juste ?
Message de unclescrooge posté le 15-07-2020 à 20:58:11 (S | E | F)
Bonjour tout le monde,
Par avance, pardonnez mon orthographe, je dispose uniquement d un clavier qwerty, ce qui me complique la tache pour ecrire correctement en francais.
Je suis en train de rediger un petit programme en C qui me permettra de resoudre un jeu appele Sky Scrapper, je vous laisse taper sur Google pour ceux que ca interesse.
Ma question est simple, et j ai un gros doute concernant la reponse.
Je vais creer des matrices de dimension NxN, N etant defini en amont. La question est la suivante, combien de matrices <u>differentes</u> puis-je composer ? Sachant que la seule regle qui regisse mes matrices est la suivante : interdit d avoir la meme valeur sur une meme ligne ou colonne.
Ex : Pour une matrice de 2 il n y a que 2 solutions possibles
1 2
2 1
et
2 1
1 2
sachant que le pattern suivant n est par exemple pas admissible:
1 1
1 2
Pour l instant je suis arrive a la formule suivante : N * (N-1)^2 ou tout simplement N * (N - 1) * (N - 1).
Qu en pensez vous ? Cela vous semble-t-il juste ?
Réponse : Combien de possiblites dans une matrice de puente17, postée le 16-07-2020 à 15:29:34 (S | E)
Bonjour,
J'ai supposé que les matrices 2x2 ne devaient comporter que des 1 et des 2, et pas d'autres nombres sinon le pb ???
J'ai utilisé les notions élémentaires des combinatoires.
ex: pour une 3x3
La première ligne je dispose mes 3 éléments j'ai donc 3! possibilités
Je passe à la 2ième ligne: j'ai 2 possibilités,
et pour la dernière ligne j'ai une seule possibilité donc au total il y aura 12 poss.
Remarque: 3!x2x1 = n x(n-1)² pour n =3
ce qui me gêne c'est pour la suite
dans le cas 4x4 il y a 4! possibilités de choix pour la première ligne soit 24 or 4x3²=36 et 24 n'est pas un diviseur de 36 donc la formule N x(N-1)² ne convient pas. de toute façon il lui faudrait une justification.
Seule la partie en bleu est fiable le reste n'est qu'une piste de recherche.
Réponse : Combien de possiblites dans une matrice de tiruxa, postée le 16-07-2020 à 20:35:13 (S | E)
Bonjour
La question est intéressante mais pas simple.
En fait on cherche à dénombrer les carrés latins, pour plus d'info voir :
Lien internet
.
A partir des quatre carrés latins (dits normalisés) existant pour n=4 , on peut en former 4!*3!, en effet on a 4! façons de permuter la première ligne et 3! façons de permuter les tois lignes suivantes (en les gardant telles quelles c'est à dire en bloc).
Donc pour n=4, 24*6*4 soit 576 carrés latins
pour n= 3 , 3!*2!*1 (car 1 seul carré normalisé) soit 12 carrés latins
pour les valeurs de n plus grandes il faut connaître le nombre de carés latins normalisés...!
Il y a peut être une récurrence.... à creuser !
Réponse : Combien de possiblites dans une matrice de tiruxa, postée le 17-07-2020 à 15:50:29 (S | E)
Bonjour,
Bon inutile de chercher il n' y a a pas de formule simple pour calculer le nombre de carrés latns, juste un encadrement donné ici :
Lien internet
On peut y voir que pour n=9 il y a 5,524,751,496,156,892,842,531,225,600 carrés latins soit plus de 5 milliards de milliards de milliards !
Au passage les sudokus en font partie.
Réponse : Combien de possiblites dans une matrice de unclescrooge, postée le 20-07-2020 à 16:06:24 (S | E)
Merci a tous pour vos reponses.
En effet, ca aurait ete beaucoup plus simple pour mes recherches si j avais connu la dénomination de ce type de carre !
Bon, pour vous donner le contexte, j essaie de resoudre pour le plaisir un exercice du concours d entree d Epitech. L exercice demande a ce que l on resoudre le probleme pour n = 5, mais y a du bonus si on arrive a resoudre pour 2 < n < 10.
Gros bourrin qu je suis je pensais faire un brutforce simple et basique, mais avec 5 milliards de milliards de milliards de possibilité on est bien d accord que ce n est pas viable. Surtout qu avant de determiner mes carrés latins je genere des matrices qui ne sont donc pas des carres latins et je fais le tri. Donc la rien que pour du n = 4 je pense qu on est sur un chiffre tres eleves.
Donc je pense que je vais ecrire un algorithme qui me permet de placer des chiffres sur la grille et ensuite je finirais avec du backtracking.
En tout cas merci a tous pour vos reponses.
-------------------
Modifié par unclescrooge le 20-07-2020 16:06
Cours gratuits > Forum > Forum maths
