Discussion :

[Quantactique]

Bonjour bonjour,
J'ai une petite question d'algo donc je viens vous voir.


Je cherche la manière la plus efficace d'obtenir tous les couples tels que:

Soit N (un nombre entier positif (ou nul))
La totalité des couples (i,j) tels que -N <= i,j <= N et que la somme des valeurs absolues de i et j <= N


Et comme un petit exemple est plus simple à comprendre:

Prenons par exemple N=3
Je cherche à obtenir les couple (i,j) suivants (j'ai fait un dessin, c'est pas très joli mais ça à le mérite d'être explicite)

Du coup j'ai tenté pas mal de trucs, j'ai réussi à le faire avec quelques "if" (et deux boucles imbriquées évidemment) mais je n'en suis pas satisfait, j'ai l'impression qu'on doit pouvoir faire mieux puisque dans ce cas j'itère sur beaucoup de couples qui ne respectent pas les conditions.

Code JAVASCRIPT :

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

1
2
3
4
5
6
7
8
 
for(var i = N*(-1); i < N; i++){
    for(var j = N*(-1); j < N; j++){
              if(abs(i)+abs(j) <= N){
                  // OK
              }
    }
}

Ensuite, j'ai tenté par exemple d'initialiser la seconde boucle avec un modulo de la première, bien évidemment ça ne donne pas le résusltat escompté...

Code JAVASCRIPT :

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

1
2
3
4
5
6
 
for(var i = N*(-1); i <= N; i++){ // loop on X
			for(var j = (i%N); ???; j++){ // loop on Y, j'ai tenté quelques trucs différents pour les ???
                                // print (i,j)
                       }
}

Voilà, donc je repose la question à la fin: je cherche la solution la plus efficace pour obtenir ces couples de valeurs (je ne cherche pas spécialement de code, j'ai l'impression que la question est plus mathématique qu'algorithmique mais bon )

Merci à vous

EDIT: le code n'est pas fonctionnel, il est là juste pour illustrer

[dourouc05]

Pour la boucle intérieure, à donné, tu veux trouver tous les tels que

En réécrivant un peu cette inégalité pour mettre l'inconnu à gauche et le connu à droite :

Par conséquent : et si tu utilisais pour ta boucle intérieure un qui passe de à ?

[Quantactique]

Pour la boucle intérieure, à donné, tu veux trouver tous les tels que

En réécrivant un peu cette inégalité pour mettre l'inconnu à gauche et le connu à droite :

Par conséquent : et si tu utilisais pour ta boucle intérieure un qui passe de à ?

Wow.. si simple...
Je me sens un peu con là, en effet c'est exactement ça merci à toi !