Passage d'une matrice (1, j) à une matrice (i', j')

Passage d'une matrice (1, j) à une matrice (i', j') - Algo - Programmation

Marsh Posté le 12-08-2016 à 11:38:50    

Bonjour,
 
 
Je cherche à transformer une matrice 1 ligne (bwef un tableau simple :o ) en une matrice n lignes (un tableau multi-dimensionnel).
Je pars-donc d'une matrice (1, j) et souhaites arriver à une matrice (i', j') où :
- i' * j' = j (oui je garde le même nombre de données)
- i' =< j' (plus de colonnes que de lignes dans la mesure du possible)
- 2 * i' >= j' (je ne veux pas dépasser le ratio de 2 fois plus de colonnes que de lignes)
 
En gros je pense qu'on peut résumer les 2 dernières conditions par 2 >= i' / j' >= 1.
 
Une idée autre que de tester tous les couples de dividendes et diviseurs entiers (avec dividendes et diviseurs inférieur à racine carrée de j) ayant pour quotient un entier?

Message cité 1 fois

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.
Reply

Marsh Posté le 12-08-2016 à 11:38:50   

Reply

Marsh Posté le 12-08-2016 à 12:01:09    

Tu fais une bête boucle de parcours de ton tableau ligne et quand j % nb colonnes (de ta matrice) == 0, tu incrémentes i.
 
Edit : j'avais pas compris que le nb de colonnes était à déterminer.


Message édité par rufo le 12-08-2016 à 12:23:24

---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
Reply

Marsh Posté le 12-08-2016 à 12:20:43    

MaybeEijOrNot a écrit :

Bonjour,
 
 
- 2 * i' >= j' (je ne veux pas dépasser le ratio de 2 fois plus de colonnes que de lignes)


Comment tu comptes faire ça pour un vecteur de 89 éléments par exemple?
 
Tu peux partir de la racine carrée et tester tous les couples jusqu'à trouver un quotient entier en effet, mais je vois pas comment tu peux assurer le respect de cette condition.


---------------
click clack clunka thunk
Reply

Marsh Posté le 12-08-2016 à 12:24:43    

Tu peux décomposer en facteurs premiers j.

Message cité 1 fois

---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
Reply

Marsh Posté le 12-08-2016 à 14:48:12    

@DDT : oui j'ai omis de dire que je pars d'un nombre pair.


---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.
Reply

Marsh Posté le 12-08-2016 à 14:55:43    

Ok mais même question avec 94 alors. :D


---------------
click clack clunka thunk
Reply

Marsh Posté le 12-08-2016 à 15:24:17    

rufo a écrit :

Tu peux décomposer en facteurs premiers j.


 
En effet ça a l'air bien, juste qu'en fait il faudra que j'entre des limitations dans mon nombre de données pour éviter des cas pourris comme 94. :/
 
94 = 2 * 47
 
Faut donc que je commence par revoir le problème en entrée. :(  
 
Merci pour votre aide.


---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.
Reply

Marsh Posté le 12-08-2016 à 17:38:04    

C'est quoi le besoin initial. Pourquoi as-tu besoin de transformer un tableau ligne en matrice sans connaître à l'avance le nb de colonnes ?


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
Reply

Marsh Posté le 12-08-2016 à 19:08:31    

Parce que l'utilisateur fait une liste que j'affiche à ma sauce ensuite en rectangle et si ce n'est pas un rectangle complet ça ne donne pas le résultat escompté.
Mais bon problème réglé, l'utilisateur sera prévenu qu'il manque tant pour pouvoir lancer le script, 3 choix :
- l'utilisateur continue à alimenter la liste
- l'utilisateur retire de la liste pour tomber sur un format plus petit
- je complète pour arriver au format supérieur


---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.
Reply

Marsh Posté le 18-11-2016 à 17:12:01    

Problème intéressant.
 
L'astuce est de partir de la racine carré de j ;)
 
Voila ma solution en java :

Code :
  1. public class TestCarre {
  3.   public static void main(String[] args) {
  4.    
  5.     for (int J = 0; J <= 100; J++) {
  6.       // on initialise ip avec la racine carre de J
  7.       double ip = Math.sqrt(J);
  8.       double jp;
  9.       // on teste si ip est une valeur entière
  10.       if (Math.rint(ip) == ip) {
  11.         // cas simple où J est un carré => solution trouvée
  12.         jp = ip;
  13.       } else {
  14.         ip = Math.floor(ip); // on initialise ip à sa valeur entière inférieure
  15.         jp = J / ip;
  16.       }
  17.  
  18.       // Ici on est sur que ip est un entier
  19.       // Le but est de trouver la plus grande valeur de ip pour que jp = J / ip soit aussi entier
  20.       while ((ip > jp / 2) && (Math.rint(jp) != jp)) {
  21.         ip--;
  22.         jp = J / ip;
  23.       }
  24.      
  25.       // affichage si succès
  26.       if (Math.rint(jp) == jp && (ip > jp / 2)) {
  27.         System.out.println("J="+ J + " : Succes : ip="+(int)ip + ", jp=" + (int)jp);
  28.       }
  29.     }
  30.   }
  31. }


Et le résultat :
J=1 : Succes : ip=1, jp=1
J=4 : Succes : ip=2, jp=2
J=6 : Succes : ip=2, jp=3
J=9 : Succes : ip=3, jp=3
J=12 : Succes : ip=3, jp=4
J=15 : Succes : ip=3, jp=5
J=16 : Succes : ip=4, jp=4
J=20 : Succes : ip=4, jp=5
J=24 : Succes : ip=4, jp=6
J=25 : Succes : ip=5, jp=5
J=28 : Succes : ip=4, jp=7
J=30 : Succes : ip=5, jp=6
J=35 : Succes : ip=5, jp=7
J=36 : Succes : ip=6, jp=6
J=40 : Succes : ip=5, jp=8
J=42 : Succes : ip=6, jp=7
J=45 : Succes : ip=5, jp=9
J=48 : Succes : ip=6, jp=8
J=49 : Succes : ip=7, jp=7
J=54 : Succes : ip=6, jp=9
J=56 : Succes : ip=7, jp=8
J=60 : Succes : ip=6, jp=10
J=63 : Succes : ip=7, jp=9
J=64 : Succes : ip=8, jp=8
J=66 : Succes : ip=6, jp=11
J=70 : Succes : ip=7, jp=10
J=72 : Succes : ip=8, jp=9
J=77 : Succes : ip=7, jp=11
J=80 : Succes : ip=8, jp=10
J=81 : Succes : ip=9, jp=9
J=84 : Succes : ip=7, jp=12
J=88 : Succes : ip=8, jp=11
J=90 : Succes : ip=9, jp=10
J=91 : Succes : ip=7, jp=13
J=96 : Succes : ip=8, jp=12
J=99 : Succes : ip=9, jp=11
J=100 : Succes : ip=10, jp=10


Message édité par Bidem le 18-11-2016 à 17:14:33
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed