Discussion :

[ZaaN]

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 :

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

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.

[10_GOTO_10]

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]

[Le Furet]

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...]

[10_GOTO_10]

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.

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.

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.

[Le Furet]

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).

[ZaaN]

au sujet de la complexité :

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

[Selenite]

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.