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.