IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Collection et Stream Java Discussion :

Remplissage de tableau de Int selon une suite mathématique


Sujet :

Collection et Stream Java

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Homme Profil pro
    Lycéen
    Inscrit en
    Mai 2015
    Messages
    10
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : Mai 2015
    Messages : 10
    Par défaut Remplissage de tableau de Int selon une suite mathématique
    Bonjour,

    Je voudrai avoir des tableaux de int qui se remplissent de cette manière . Mais ça fait deux jours que je cherche, et je n'ai pas réussi à créer un algorithme permettant de faire ceci . Cepandant j'ai pu remarquer que cette suite se comporte comme une suite de nombre à base de 4(chaque tableau correspond à un nombre en base de 4) . J'ai essayé d'utiliser cette propriété .(conversion nombre en base de 10 en tableau represantant des nombre en base de 4) . Le problème est que très vite, mon algo a besoin d'utiliser des nombres bien plus grands qu'un long . De plus, je trouve cette solution vraiment bizarre . J'ai pu tester pour des petits nombre, ça fonctionne . Mais je suis sur qu'il y a une méthode plus simple et moins coûteuse en mémoire . Merci


    Creation de Tableaux de Int.
    0
    1
    2
    3
    0,0
    0,1
    0,2
    0,3
    0,0,0
    0,0,1
    0,0,2
    0,0,3
    0,1,0
    0,1,1
    ...
    3,3,3,3 -> environ 20 "nombre 3".
    C'est pour la résolution d'un rubick's cube (20 mouvement maximum pour une résolution optimal en nombre de mouvement dans 99%des cas) . Chaque chiffre correspond à un mouvement du rubick's cube(méthode qui prend en argument un tableau de Int et qui execute un mouvemnt) . Enfaite ça va jusqu'a 11 Mais j'ai mis 3 pour simplifier . L'algo s'arrete quant un des tableaux permet la resolution du rubik's cube . Bien sur entre chaque tableau le cube reprend son êtat initiale . Cette algo permet de trouver la combinaison la moins longue pour résoudre un rubik's cube .

  2. #2
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 55
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Billets dans le blog
    2
    Par défaut
    Salut,

    Ce ne serait pas plutôt :

    0
    1
    2
    3
    0,0
    0,1
    0,2
    0,3
    1,0
    1,1
    1,2
    1,3
    2,0
    2,1
    2,2
    2,3
    3,0
    3,1
    3,2
    3,3
    0,0,0
    0,0,1
    ...
    Le nombre de lignes de ce tableau est (pour m=3 et n=20) :

    Formule mathématique

    soit

    Formule mathématique

    qui est égal à : 1 466 015 503 700 ( 1 466 milliiards, de lignes ! le nombre théorique (en pratique c'est un peu moins, et dépend des jvm) maximum de lignes étant 2 147 483 647, autant dire que c'est déjà explosé, mais on pourrait imaginer faire plusieurs tableaux). Mais toutes ces lignes prendraient dans les 106 Tebi (117 281 240 296 000 octets!), pour des int !

    Et tu dis qu'il faudrait aller jusqu'à 11 ? A mon avis, la solution de calculer un tableau par avance est inenvisageble (peut-être dans quelques années, qui sait, mais pas aujourd'hui). A voir si l'algorithme doit vraiment faire ça, mais, c'est si c'est le cas, je pense qu'il faudrait calculer au fur à mesure, uniquement les combinaisons nécessaires (la branche courante), sans toutes les stocker.

    Sinon, pour la curiosité, le programme de génération pourrait être par exemple :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    public class Exemple {
     
    	private static final int MAX=3;
    	private static final int NBCOMBI=7; // Avec 20 ça plante évidemment
     
    	public static void main(String[] args) {
     
    		int[][] tableau = new Exemple().creerTableau(NBCOMBI);
     
    		for(int[] array : tableau) {
    			System.out.println(Arrays.toString(array));
    		}
     
    	}
     
    	public int[][] creerTableau(int n) {
    		List<int[]> lignes = new ArrayList<>(); // plutôt que de calculer le nombre de combinaisons d'avance : bien sûr ça prend plus de mémoire
    		for(int i=1; i<=n; i++) {
    			creerCombinaisons(lignes, i);
    		}
    		return lignes.toArray(new int[lignes.size()][]);
    	}
     
    	private void creerCombinaisons(List<int[]> lignes, int n) {
    		int[] array=new int[n];
    		do {
    			lignes.add(Arrays.copyOf(array, n));
    		} while (!incremente(array)); // tant que la combinaison est valide
    	}
     
    	private boolean incremente(int[] array) {
                    boolean end=false;
    		for(int i=array.length-1; i>=0; i--) {
    			if ( array[i]==MAX ) {
    				if ( i==0 ) { // on est à combinaison max, on arrête là
    					end = true;
    				}
    				array[i]=0; // on passe à 0, le chiffre suivant (ou plutôt précédent) sera incrémenté par l'itération suivante (retenue)
    			}
    			else {
    				array[i]++; // on incrémente la position courante
    				break; // et on s'arr^te
    			}
    		}
    		return end;
    	}
     
    }
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  3. #3
    Membre averti
    Homme Profil pro
    Lycéen
    Inscrit en
    Mai 2015
    Messages
    10
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : Mai 2015
    Messages : 10
    Par défaut
    Alors effectivement la liste que tu donne est plûtot la bonne . Enfaite je me suis mal exprimé . Chque ligne de la liste est un tableau . Dans mon code j'ai une méthode qui prend en argument un tableau de int et qui a chaque mouvement va associer une chiffre . Ainsi si je lui donne ce tableau ci {1,0,2} .elle va executer le mouvement 1 puis 0 puis 2 . Àpres l'exucution de cette méthode . Je fais un test pour savoir si le cube est résolu. Si non , je fais retrouver au cube sa position avant l'execution de la méthode . puis J'exucute à nouveau la méthode mais avec le nouveau tableau : {1,0,3} . je refait tout ceci jusqu'a la résolution du cube ( 20 mouvement max dans 99%des cas) . Ainsi le plus grand tableau que je peux avoir aura une taille de 20 . avec des nombres compris entre [0;11] (11 mouvement possibles pour le rubick's cube] . Je pense que c'est largement dans les capacités de la JVM ça . Non ce qui prenait beaucoup de place, c'était la conversion d'un nombre en base de 10 à un tableau representant un nombre en base de 12 . En effet, je me suis servi de ca pour faire ceci . i=0 puis i++ . à chaque fois tranformation de I en base de 12 donc : 0->0'
    1->1'
    ...
    10->10'
    11->11'
    12->10
    ...
    15567->9'0'1'3

    ETC ETC le probleme est que pour un nombre duodecimal de 11'11'11'11'11 ... jusqu'a 20 le nombre décimal est de 3.8337599924474746*10²¹ . Un nombre beaucoup trop grand pour la jvm . Alors pourquoi je fait ça . Le seul moyen que j'ai trouvé pour generer une suite de tableau automatiquement de cette manière là . Chaque nouveau tableau doit avoir sa premiere(ou derniere, on peut faire dans les deux sens) case plus grande que le precedente jusqu'a atteindre la valeur de 11. Après cette valeur, le nouveau tableau doit avoir une taille plus grande de 1 . Un système de compte en base de 12 quoi . Après tu dis qu'on peut effacer les anciens tableau . Pas de problème le garbage collector s'en chargera, vu qu'une fois le test passé pour savoir si le rubick's cube est bien résolu, le tableau(qui represente une suite de mouvement) ne sert plus à rien . Seul celui qui suivera est important .

    De tout mannière si j'ai : int[] tab= tranformerEnDuodecimal(i); dans une boucle, les anciens tableau seront écrasés . en effet i va augmenter de 1 si jamais le rubik's cube n'est pas résolu . TransformerEnDuodecimal() va renvoyer un tableau de int qui va correspondre à une suite d'instruction .(méthode move(int[] suite)) Voila donc le problème des tableaux ne se pose pas, les anciens seront écrasées par les nouveaux . Le seul problème c'est la valeur de I .

  4. #4
    Membre averti
    Homme Profil pro
    Lycéen
    Inscrit en
    Mai 2015
    Messages
    10
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : Mai 2015
    Messages : 10
    Par défaut
    Au pire moi je veux juste un algo qui permette de générer des tableaux de int avec cette suite la .

    {0}-{1}-{2}-{3}-{4}-{5}-{6}-{7}-{8}-{9}-{10}-{11}-{1,0}-{1,2}-{1,3} etc jusqu'à environ {11,11,11...,11} -> 20 cases pour le dernier tableau .

    En effet chaque tableau représente une suite de mouvement( 12 mouvements, de 0 à 11) . Pour un rubik's cube dans 99% des cas, il faut 20 mouvement au max pour le résoudre . En gros ce que je fait c'est que entre chaque tableau je teste si le cube est résolu, si non , création du prochain tableau . Et ce jusqu'à résolution du cube . Donc , dans 99% des cas, j'aurai au max un tableau de int de 20 cases . Le seul problème et que j'arrive pas à crée un algo capable de faire ceci . Du coût n y a t il pas quelqu’un qui peut m'aider par ici ?

  5. #5
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 55
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Billets dans le blog
    2
    Par défaut
    L'algorithme de base, je te l'ai donné. Il te suffisait de le transformer en itérateur, on modifiant la condition de fin, pour qu'elle soit atteinte lors de la dernière combinaison, comme ça, par exemple :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    public class MoveIterable implements Iterable<int[]> {
     
    	private final int nbMove;
    	private final int maxMove;
     
    	public MoveIterable(int nbMove, int maxMove) {
    		if( nbMove<1 || maxMove<0 ) throw new IllegalArgumentException();
    		this.nbMove = nbMove;
    		this.maxMove = maxMove;
    	}	
     
    	@Override
    	public Iterator<int[]> iterator() {
    		return new MoveIterator();
    	}
     
    	private class MoveIterator implements Iterator<int[]> {
    		private int current;
    		private int[] array;
    		private boolean end;
     
    		public MoveIterator() {
    			this.current=1;
    		}	
     
    		@Override
    		public boolean hasNext() {
    			return current<=maxMove;
    		}
     
    	    public int[] next() {
    	    	if ( current<=maxMove ) {
    	    		if ( array==null ) {
    	    			array=new int[current];
    	    		}
    	    		else {
    	    			incremente(array);
    	    		}
    	    		int[] result = Arrays.copyOf(array, current);
    	    		if ( allInArrayAre(array,nbMove) ) {
    	    			current++;
    	    			array=null;
    	    		}
    	    		return result;
    	    	}
    	    	throw new NoSuchElementException();
    	    }
     
    		private boolean allInArrayAre(int[] array, int value) {
    			for(int i : array) {
    				if ( value!=i ) return false;
    			}
    			return true;
    		}
     
    		private void incremente(int[] array) {
    			for(int i=array.length-1; i>=0; i--) {
    				if ( array[i]==nbMove ) {
    					array[i]=0; 
    				}
    				else {
    					array[i]++; 
    					break; 
    				}
    			}
    		}
     
    	}
     
    	// méthode de démo :
    	public static void main(String[] args) {
     
    		for(int[] array : new MoveIterable(11, 20)) {
    			// tu peux faire ce que tu veux du tableau
    			System.out.println(Arrays.toString(array));
    		}
     
    	}
     
    },
    M'enfin, si on part du principe que le traitement d'un tableau prend 100 ms, il faudrait 13 261 934 millions d'années environ pour toutes les traiter ! A mon avis, cette façon de traiter la résolution d'un Rubik's Cube n'est pas envisageable. Même si le traitement prenait 1 ms, d'ailleurs. Tu devrais regarder plutôt du côté des méthodes de résolution, qui utilise des schémas type, et des combinaisons de mouvements type (voir http://www.francocube.com/).
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  6. #6
    Membre averti
    Homme Profil pro
    Lycéen
    Inscrit en
    Mai 2015
    Messages
    10
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : Mai 2015
    Messages : 10
    Par défaut
    Merci, je savais pas ce que c'était un itérateur . Pour l'instant je connais pas toutes les notions de base en java . J'apprends encore . Donc je vais allez voir ce que c'est qu'un itérateur . Et ça me soule un peu ce que tu me dis la . À la base je voulais faire un algo qui trouve la solution du rubick's cube la moins longue . Mais apparemment je peux pas . Vu qu'il faudrait générer 9.5396216644069*10²⁶ tableau . En plus des tableaux y'aurai 9.5396216644069*10²⁶ vérification sur le rubick's cube . Ouais en gros ce que je vais faire est impossible . Bah en tout cas merci pour ton aide . Je vais allez voir dans mon bouquin de java la partie sur les itérateurs .

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Déplacement selon une fonction mathématique
    Par Omaping dans le forum Débuter avec Java
    Réponses: 3
    Dernier message: 30/12/2014, 15h20
  2. Afficher un tableau de int[][] dans une JList
    Par kevin254kl dans le forum Composants
    Réponses: 19
    Dernier message: 16/11/2014, 17h49
  3. [XL-2007] Remplissage d'un tableau à partir d'une autre feuille selon une condition
    Par Mackinlay dans le forum Macros et VBA Excel
    Réponses: 4
    Dernier message: 05/03/2013, 10h50
  4. [C#] Modifier le int d'une clé primaire dans un tableau VS database
    Par padodanle51 dans le forum Windows Forms
    Réponses: 5
    Dernier message: 25/07/2006, 13h48
  5. [VBA] remplissage d'un champs selon une recherche
    Par Virgile59 dans le forum Access
    Réponses: 7
    Dernier message: 04/11/2005, 09h52

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo