Discussion :

[cal23]

Bonsoir.
J'ai une question sur des boucles for imbriquées.
Lors de l'exécution d'un programme java, un entier n prend une valeur de façon dynamique, et ensuite j'aimerais faire n boucles for imbriquées. Est-ce que c'est possible en java?
Sinon comment faire?
merci.

[tchize_]

Au dela du fait que tu n'a pas l'air de réaliser à quel point ton temps de calcul va exploser au delà du chiffre 5, il faut faire de la récursivité:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
public int boucler(int boucles, int profondeur, int valeur){
    if (profondeur>1)
    for (int i=0;i<boucles;i++){
         valeur=boucler(boucles,profondeur-1,valeur);
    }
}

[Alkhan]

Bonjour,

Pourrais tu nous dire pour quelles raisons tu souhaites faire n boucles imbriquées..... peut être y a t il une meilleur solution !

[kolodz]

Tu veux coder une fonction ackermann ?

Cordialement,
Patrick Kolodziejczyk.

source :
http://en.wikipedia.org/wiki/Ackermann_function
www.youtube.com/watch?v=i7sm9dzFtEI

[cal23]

Si,si, je réalise bien que le temps de calcul explose.

C'est pour générer tous les entiers à n chiffres distincts.
Si n est fixé dès le départ, je pense que le plus efficace (nombre de calculs, occupation mémoire), c'est n boucles for imbriquées.
Par contre si n est initialisé au cours du programme, j'utilise la récursivité (ça ressemble un peu à la proposition de tchize):

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
void entierNChiffres(int niveau) {
	for(int i=0; i<10; i++) {
		int j = 0;
		while (j <niveau && i != entier[j]) j++;
		if (!(i==0 && niveau==1)  && j==niveau) {
			entier[niveau-1] = i;
           	if (niveau == nbChiffres) affiche(entier);
            	else entierNChiffres(niveau+1);
		}
	}
}
void main(){
	nbChiffres = 3;
 
	entier = new int[nbChiffres];
	for(int i=0; i<nbChiffres;i++) entier[i] = -1;
	entierNChiffres(1);
}

Mais je me demandais si il n'y avait pas mieux au niveau nombre de calculs et mémoire (en évitant la récursivité par exemple).

[tchize_]

En gros tu cherche toutes les combinaisons de 10 éléments parmis 10 où l'ordre à de l'importance, ça s'appelle un arrangement et effectivement la méthode la plus simple pour le résoudre c'est récursif, de la manière suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
arrangements(elements[])
  si elements vide, retourner le vide
  pour chaque element e de elements
    resultat = resultat U (e + arrangements(elements-e))
  retourner resultat

tout simplement

[cal23]

Désolé Tchize mais je trouve ta solution moins bonne que la mienne:
Pour renvoyer un arrangement (là je dirais plutôt permutation) de n éléments, ta fonction calcule les permutations de n-1 éléments, n-2 éléments... qui sont stockées en mémoire.
Donc grosse occupation mémoire et beaucoup de calculs.
Ma solution travaille sur une variable globale qui est modifiée à chaque appel récursif (donc peu d'occupation mémoire) et beaucoup moins de calculs.
Mais est-ce qu'il n'y aurait pas une méthode encore meilleure, non récursive ?

[tchize_]

Oui, c'est du pseudo code, tu peux le faire fonctionner comme ça si tu préfère:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
arrangements(partiel, elements[])
  si elements vide, afficher partiel
  pour chaque element e de elements
    arrangements(partiel+e,elements-e))
  retourner resultat

Effectivement, ton code évite de tenir à jour la liste des éléments. Mais en contre partie, à chaque fois, il relit tous les éléments déjà placé. Mais vu qu'on ne peux pas placer plus de 10 éléments au total, je pense que ta méthode est plus rapide, même si a mes yeux plus difficile à lire

[kolodz]

Mais est-ce qu'il n'y aurait pas une méthode encore meilleure, non récursive ?

Ton approche est itérative. Ce qui revient au même au niveau de la complexité.

Point de vue performance, il est très peu probable que l'une ou l’autre des méthodes ai un impacte important sur la mémoire.
A partir du moment qu'on à un n relativement grand, ce qui va prendre de la place en mémoire, c'est le résultat. Après si N est petit et que tu considère que 2Mo en plus c'est beaucoup, n'oublie pas que tu lance l'ensemble de la JVM pour lancer ton programme.

Le récursif n'ayant jamais de doublon en mémoire, celui-ci n'explose pas la mémoire dans ce contexte. La seule limite étant le nombre d'appel récursif, limité par la taille de la pile d'appel.
Lors la méthode récursive proposé par tchize_ est d'avoir N récursion. (10 dans ton cas).
Où l'ensemble des combinaisons de niveau N sont celle de longueur N et les combinaisons de N-1
Il y aurai des problèmes de mémoire et de performance si tu commence à dupliquer tes set de données à chaque boucle ou récusions. Ce qui n'est pas le cas.

Ce qui est exactement la même chose que de faire une boucle for pour cela. En particulier, si tu considère que la JVM réalisera des optimisations techniques par dessus.

D'ailleurs à ton niveau de programmation, il est plus important d'avoir un code propre / clair / simple plutôt que de gagner quelques cycle CPU, en perdant en clarté ou en lisibilité. De nos jours, les cas où le "hack" technique est favorisé est de plus en plus remis en cause. Car, cela pose beaucoup plus de problème au final.

Sa parler que la conception de programme avec des variables globales à tendance à mener à des problèmes. Que cela soit au niveau de la responsabilité de qui doit ou ne doit pas la modifié ou de la cohérence. (Est-elle dans un état stable ? Particulièrement pour les tableaux...)

Cordialement,
Patrick Kolodziejczyk.