Forum |  HardWare.fr | News | Articles | PC | Prix | S'identifier | S'inscrire | Shop Recherche
791 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  Algorithme sur des "Demi-diagonales" de matrices

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Algorithme sur des "Demi-diagonales" de matrices

n°2272154
Maxime16
Posté le 22-12-2015 à 13:13:41  profilanswer
 

Bonjour à tous,et désolé par avance pour la longueur de mon post, elle est due à mes dessins d'illustration.
 
Dans un algorithme j'obtiens des matrice d'ordre n (avec n pair). Ces matrices sont définies uniquement pour le triangle supérieur et ne peuvent contenir que des 0 et des 1.
 
Par exemple:
 
 _ _ _ _ _ _
|0 1 0 0 0 1
|0 0 0 1 1 0
|0 0 0 0 1 0
|0 0 0 0 1 0
|0 0 0 0 0 0
|0 0 0 0 0 0
 
Ou dans un cas général avec x = 0 ou 1 et n = 8.
 
col 0 1 2 3 4 5 6 7
lin  _ _ _ _ _ _ _ _
0  |0 X x x x x x x
1  |0 0 x x x x x x
2  |0 0 0 x x x x x
3  |0 0 0 0 x x x x
4  |0 0 0 0 0 x x x
5  |0 0 0 0 0 0 x x
6  |0 0 0 0 0 0 0 x
7  |0 0 0 0 0 0 0 0
 
On a le droit de changer DE LA MÊME MANIÈRE l'ordre des lignes et des colonnes.
 
Par exemple on peux avoir:
col 0 3 1 2
lin _ _ _ _  
0|
3|
1|
2|
 
mais pas
col 0 1 3 2
lin  _ _ _ _  
0|
3|
1|
2|
(car les lignes font 0132 != colonnes 0312).
 
 
Enfin ce que j'appelle demi-diagonale (je ne connais pas le nom de ceci, si tenté que ça en ait un) est : aij tel que i = n/2+k et j = k avec k<n/2.
Si n = 8, elle est notée avec des x
 
col  0 1 2 3 4 5 6 7
lin  _ _ _ _ _ _ _ _
0  |0 0 0 0 x 0 0 0
1  |0 0 0 0 0 x 0 0
2  |0 0 0 0 0 0 x 0
3  |0 0 0 0 0 0 0 x
4  |0 0 0 0 0 0 0 0
5  |0 0 0 0 0 0 0 0
6  |0 0 0 0 0 0 0 0
7  |0 0 0 0 0 0 0 0
 
Voila, j'ai enfin tout défini!
 
Je cherche à un algo qui me permettrait de savoir combien on peut mettre de 1 au maximum sur la demi-diagonale. (On a le droit d'inverser les lignes colonnes comme montrées plus haut). Comme n est compris entre 0 et 200, je souhaite avoir une complexité polynomiale.
 
J'ai eu vraiment beaucoup d'idées, mais elles étaient toutes en n! ou en (n/2)!.
 
A mon avis faudrait faire une opération sur la matrice qui pourrait me donner le résultat de cette rotation sans les tester effectivement toutes...
 
Si quelqu'un à une idée, ou même une piste je suis preneur.
 
Merci d'avance :)

mood
Publicité
Posté le 22-12-2015 à 13:13:41  profilanswer
 


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  Algorithme sur des "Demi-diagonales" de matrices

 

Sujets relatifs
Eviter toutes cellules pattern (rayures diagonales fines)Conversion algorithme Python -> VBA (combinaisons de p élém. parmi n)
Explication complexité d'un algorithme[Clos]Explication mathématique d'un algorithme plus ou moins "stable"
algorithme d'enrichissementMatlab : Faire une fonction avec des matrices plutôt qu'une boucle for
Algorithme Unsharp Mask (HELP)[MATLAB] Algorithme ressortissant les plus courts chemins
algorithme pour réseau d'échange numismatiqueAlgorithme pour le calcul de % de paiements affectés à des factures
Plus de sujets relatifs à : Algorithme sur des "Demi-diagonales" de matrices


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR