quart de spirale

salut,
je cherche à pondre un algo simple qui permette un parcours en "quart de spirale" dans un tableau à 2 dimensions.Attention la zone à parcourir n'est pas forcement carrée. On peut rencontrer le bord bas ou gauche prematurement.

Voici un exemple de l'ordre souhaité dans le parcours du tableau

Code:

---

1 2 3 4 5 6 7 8 9 10 11

exemple : Start ici 63 56 49 36 25 16 09 04 01 00 64 57 50 37 26 17 10 05 02 03 65 58 51 38 27 18 11 06 07 08 66 59 52 39 28 19 12 13 14 15 67 60 53 40 29 20 21 22 23 24 68 61 54 41 30 31 32 33 34 35 69 62 55 42 43 44 45 46 47 48 -------------------BORD BAS-------------------

---

si qqn à une bonne idée pour ce parcours.... :?:


PS: j'ai déja une version avec des for imbriqués mais je veux plus simple. Actuellement j'ai une boucle qui parcours de droite a gauche avec à l'interieur : le calcul de la hauteur et largeur du 'L' à parcourir, puis 2 for à la suite (hauteur+largeur) pour le parcours proprement dis des elements du tableau.

Soit I le numéro dans ton tableau

Premier cas : |Racine(I)| < plus petite dimension du tableau
alors le quart de spirale est une zone carrée
Soit H = |Racine(I)|
Soit R = I - H²
Si R < H + 1 alors X = H + 1 et Y = R + 1
Sinon X = 2 * H - R + 1 et Y = H + 1

Exemple: I = 18
H = 4
R = 2 < 4
donc la case 18 est sur la 5ième colonne en partant de la droite (H + 1) et sur la troisième ligne (R + 1)

Second cas :

Soit D la plus petite dimension

X = | I / D | + 1
Y = Reste de la division par D + 1

Exemple I = 60
X = | 60 / 7 | + 1 = 9 (Neuvième colonne)
Y = 4 + 1 = 5 (Cinquième ligne)

[Edit] Bon, c'est pas garanti à 100%, mais c'est un début [/Edit]

Franchement, es-tu sûr que ce sera plus simple ? Ce ne sera vraisemblablement pas plus rapide en tout cas, et dis-toi que si ça se trouve, tu devras relire ton code dans un an ou deux, et comprendre ta formule risque d'être assez difficile alors.

[Ca me fait penser aux gens qui, pour dire que deux réels x et y sont non simultanément nuls, écrivent x²+y² != 0. C'est vrai, mais bon...]

Citation:

---

Envoyé par Le Furet

Franchement, es-tu sûr que ce sera plus simple ?

---

En tous cas c'est pas plus compliqué: deux "if" imbriqués ou deux "for" imbriqués, pour moi, c'est aussi simple à comprendre.

Citation:

---

Envoyé par Le Furet

Ce ne sera vraisemblablement pas plus rapide en tout cas

---

Alors là, je suis bien persuadé du contraire: deux "for" imbriqués, ça a une complexité de N², alors que là c'est de l'accès direct. On ne peut pas faire plus rapide.

Citation:

---

Envoyé par Le Furet

tu devras relire ton code dans un an ou deux, et comprendre ta formule risque d'être assez difficile alors.

---

Avec quelque commentaires pertinents, aucun problème. Je ne suis pas un génie, mais si une formule de trois lignes devait m'être difficile à comprendre, j'arrêterais l'informatique tout de suite.

Ma remarque était destinée à l'auteur du post, pas à toi. Ta solution est ingénieuse, même si je maintiens que je n'en vois pas l'intérêt.

Je ne comprens néanmoins pas ta phrase sur la complexité. Si tu veux remplir le tableau avec ta formule (ou avec quopi que ce soit d'autre), il faut bien le parcourir non ? Donc c'est au moins en n^2 (je suppose que n est l'ordre de grandeur d'une dimension du tableau).

au sujet de la complexité :

http://www.enseignement.polytechniqu...w-poly008.html

Citation:

---

Citation:

---

Envoyé par Le Furet

Ce ne sera vraisemblablement pas plus rapide en tout cas

---

Alors là, je suis bien persuadé du contraire: deux "for" imbriqués, ça a une complexité de N², alors que là c'est de l'accès direct. On ne peut pas faire plus rapide.

---

Sauf que les deux algorithme comparés ne font pas la même chose.
L'un génère tout les indices, l'autre génère UN indice, à la demande.

La complexité de ton algo est constante pour un indice. La complexité de l'autre est proportionnelle au nombre d'élément du tableau. Cela revient donc au même.
Sauf que avec ton algo, les calculs pour chaque indices sont beaucoup plus lourds.
Comme toujours, l'efficacité de l'algo dépend donc de l'usage.