[C/C++] Algo de parcours en spirale d'un tableau2D

TITM4v3rick · 18 Déc 2003

Soit un tableau 2D

Au lieu de faire un parcours ligne, colonne ou colonne, ligne j'aimerai faire un parcours en spirale...

Exemple sur un tableau carré de dimension 4...

01.02.03.04
12.13.14.05
11.16.15.06
10.09.08.07

Qqn a-t-il déjà réfléchis à la question ?
Mach, CvM ? autre...

zoheir · 18 Déc 2003

il faut prévoir 4 boucles (moyen d'optimiser à 2 je pense)
une pour parcourir de gauche à droite, haut en bas, droite à gauche et de bas en haut.

Je vais y réfléchir si j'ai le temps

TITM4v3rick · 18 Déc 2003

CvMz0r- a dit:
il faut prévoir 4 boucles (moyen d'optimiser à 2 je pense)
une pour parcourir de gauche à droite, haut en bas, droite à gauche et de bas en haut.

Je vais y réfléchir si j'ai le temps

Ben j'y ai pensé, mais sinon j'avais aussi pensé à 2 boucles et 4 if dont les paramètres variaient en fonction de la position dans le tableau...

(24/01/04) Après réflexion, ça ne me semble pas très utile... M'a l'air un brin compliqué alors qu'avec des fonctions séparées je devrai en venir à bout.

[Le texte de base, à remplacer...]

gogoprog · 18 Déc 2003

TITM4v3rick a dit:
CvMz0r- a dit:

il faut prévoir 4 boucles (moyen d'optimiser à 2 je pense)
une pour parcourir de gauche à droite, haut en bas, droite à gauche et de bas en haut.

Je vais y réfléchir si j'ai le temps

Cliquez pour agrandir...

Ben j'y ai pensé, mais sinon j'avais aussi pensé à 2 boucles et 4 if dont les paramètres variaient en fonction de la position dans le tableau...

ouai avec des boucles c'est tout simple, mais faudrait trouver un moyen plus beau

Jereck · 18 Déc 2003

Indices ou pointeurs ?

TITM4v3rick · 19 Déc 2003

Jereck le Blanc a dit:
Indices ou pointeurs ?

bètement indices...

AcidBird · 19 Déc 2003

Je vais peut-être dire une grosse conneries vu que j'y ai pas réfléchit des masses mais il me semble qu'avec une seule boucle de parcours de tableau on peut s'en sortir avec une procedure dans le genre

procedure ParseOneTabLine(Iterator : Integer; const fixedIterator, Increment, StopValue : Integer; IsVerticalParse : Boolean);

Dans cette procedure, une petite boucle for du genre

for iterator := Iterator to StopValue By increment do
begin
if IsVerticalparse then
ParseOneTabElement(Tab[FixedIterator, Iterator])
else
ParseOneTabElement(Tab[Iterator, FixedIterator])
end;

Après il faudra évidement une autre boucle pour gérer l'appel de cette fonction mais il n'y aura qu'une boucle qui accéde au tableau, c'est quand même plus propre

gogoprog · 19 Déc 2003

en c++

zoheir · 20 Déc 2003

gogoprog a dit:
TITM4v3rick a dit:

CvMz0r- a dit:

il faut prévoir 4 boucles (moyen d'optimiser à 2 je pense)
une pour parcourir de gauche à droite, haut en bas, droite à gauche et de bas en haut.

Je vais y réfléchir si j'ai le temps

Cliquez pour agrandir...

Ben j'y ai pensé, mais sinon j'avais aussi pensé à 2 boucles et 4 if dont les paramètres variaient en fonction de la position dans le tableau...

Cliquez pour agrandir...

ouai avec des boucles c'est tout simple, mais faudrait trouver un moyen plus beau

euh un moyen plus beau ?! tu ne peux faire ça sans boucle.

niafron · 21 Déc 2003

entre 2 chapitres detude, je me penche sur ce sujet

ma politique : une fonction recursive.
G l idee qui a l air +/- cense, mais par contre jai foire ma premiere implementation

en fait je me suis baser sur :

on part de l element central ( tab[5][5], l elt central est en 2-2 )
ensuite je parcours en spirale genre
i = 1
droite -> pas de i
bas -> pas de i
i++
gauche -> pas de i
haut -> pas de i
i++ ...

bon ok pour des tablea de type
tab[nbr pair][nbr pair]
il faut voir une autre politique mais opur le moment je look les impaires

pour les paires, je dirais : un fois le bord du tableau atteind avec ma methode, on suit les bords ( en spirale ) pour decouvrir les derniers nombres

Ghosta · 21 Déc 2003

Tu vas augmenter le nombre de calculs en faisant de la sorte...

Findecano · 21 Déc 2003

Ton tableau, il sera toujours de cette taille ou il peut changer?

TITM4v3rick · 21 Déc 2003

Findecano a dit:
Ton tableau, il sera toujours de cette taille ou il peut changer?

il varie bien sur.

piet · 24 Déc 2003

j'viens d'y réfléchir quelques minutes...
Voilà ce que j'en dis...

Si on part avec les hypothèses suivantes :

Code:

#define MAX 15

	int dim; // Dimension du tableau
// Demander la dimension
// Remplir le tableau de façon linéaire

	int i = j = imin = jmin = 0;
	int imax = jmax = dim;
	int op = 1; // OP est l'opération qu'on est en train de faire
		// Si on va de gauche à droite, 1
		// Si on va de haut en bas, 2
		// Si on va de droite à gauche 3
		// Si on va de bas en haut, 4
	
	lire (tab[dim][dim], imin, imax, jmin, jmax, i, j, op); // on lance la lecture!

ET on utilise la fonction :

Code:

int lire (int tab[dim][dim], int imin, int imax, int jmin, int jmax, int i, int j, int op)
{
	switch (op)
	{
		case 1 :
			while (i&lt;=imax)
			{
				cout &lt;&lt; tab[j][i];
				i++;
			}
			jmin++;
			op=2;
			lire (tab[dim][dim], imin, imax, jmin, jmax, i, j, op);
			break;
		case 2 :
			while (i&lt;=jmax)
			{
				cout &lt;&lt; tab[j][i];
				j++;
			}
			imax--;
			op=3;
			lire (tab[dim][dim], imin, imax, jmin, jmax, i, j, op);
			break;
		case 3 :
			while (i&lt;=imax)
			{
				cout &lt;&lt; tab[j][i];
				i--;
			}
			jmax--;
			op=4;
			lire (tab[dim][dim], imin, imax, jmin, jmax, i, j, op);
			break;
		case 4 :
			while (i&lt;=imax)
			{
				cout &lt;&lt; tab[j][i];
				j--;
			}
			imin++;
			op=1;
			lire (tab[dim][dim], imin, imax, jmin, jmax, i, j, op);
			break;
	}
	return 1;
}

Normalement, ça doit-être bon, et çe doit marcher quelle que soit la dimension!

Enfin, dites-moi...

TITM4v3rick · 25 Déc 2003

j'ai pas encore lu le code, mais en voyant une fonction récursive je dis gg.

Par contre, je me demande si ya pas bcp plus simple du genre :
utiliser des fonctions qui disent :

1/si une position x,y existe pour ce tableau
2/pour savoir sur quel "niveau" on se trouve en se basant sur la définition suivante d'un niveau

00.00.00.00
00.01.01.00
00.01.01.00
00.00.00.00

ici , ya donc 2 niveaux : le "00" et le "01"

3/et enfin une fonction qui renvoit une position x,y par rapport à une position donnée en paramètre, cette fonction en fait "calculerait" la position de base + 1 dans la bonne direction
(haut, bas, gauche, droite suivant la "position" si je puis dire

TheFornicator · 25 Déc 2003

Pour moi, une manière de faire, dans une seule boucle (ou en récursif, comme on veut), avec 4 if (ou plutôt un switch, ce qui est plus rapide) et un marqueur de direction.

Prenons le récursif (attention, dans ce cas, vu la taille de certains tableau, il faut faire du récursif terminal, sinon, ça va chier).... il suffit de passer à la fonction la position actuelle, la direction que l'on a pris pour y arriver (dans un marqueur), la taille horizontale du tableau et sa taille verticale et il va trouver l'élément suivant et l'afficher, puis, si il doit, il va appeler une nouvelle fois la fonction.
Pour afficher l'élément suivant : Tu dois simplement tester si tu es au bord d'une des dimensions, si oui, bein tu prévois ce que tu dois faire, si non, en fonction du marqueur, tu te déplace vers l'élément suivant tout de suite et tu as aussi le marqueur a donner pour le prochain appel.

Pour le marqueurs, sa donenra la direction de la spirale. Exemple: prenons 1 = gauche, 2= bas; 3=droite et 4 = haut.
Les marquers s'enchaîne par exemple 1,2,3,4 car dans le switch, un 1 donnera un 2 pour le suivant et ainsi de suite.
Si on est avec un marqueur 1, on test si bord de tableau. Si oui, a toi de trouver ou définir ce que tu dois faire, si non: tu fais simplement -1 sur l'indice de colonne. (sans marquer = premier élément... là aussi, à toi de définir quel premier élément tu veux)

sorry, mais j'ai pas envie de faire le code...

voilà mon idée....

piet · 25 Déc 2003

TITM4v3rick a dit:
3/et enfin une fonction qui renvoit une position x,y par rapport à une position donnée en paramètre, cette fonction en fait "calculerait" la position de base + 1 dans la bonne direction
(haut, bas, gauche, droite suivant la "position" si je puis dire

En fait, j'ai essayé comme ça, et ça merdait toujours pour la direction...

Par contre, avec mon code, on peut même donner un tableau avec un nombre de colonnes et de lignes différents (pourvu que le nombre de colonnes soit supérieur au nbre de ligne, mais dans l'autre cas, il suffirait de mettre une condition et de changer l'ordre en fonction de la condition) et d'ajouter la deuxième dimension, et ça marche toujours. mais bon, si quelqu'un trouve... qu'il le dise!

piet · 25 Déc 2003

TheFornicator a dit:
Pour moi, une manière de faire, dans une seule boucle (ou en récursif, comme on veut), avec 4 if (ou plutôt un switch, ce qui est plus rapide) et un marqueur de direction.

C'est marrant ça... t'as répondu avant moi, je n'ai pas vu ta "solution" et je suis tombé sur la même...

Comment ça se fait que tu as écris avant et que ça s'affiche après?

TheFornicator · 25 Déc 2003

piet a dit:
TheFornicator a dit:

Pour moi, une manière de faire, dans une seule boucle (ou en récursif, comme on veut), avec 4 if (ou plutôt un switch, ce qui est plus rapide) et un marqueur de direction.

Cliquez pour agrandir...

C'est marrant ça... t'as répondu avant moi, je n'ai pas vu ta "solution" et je suis tombé sur la même...

Comment ça se fait que tu as écris avant et que ça s'affiche après?

non non, j'ai bien é rit après, mais ta solution (j'lai pas étudiée en détail... donc, pas d'affolement, je peux me tromper) ne me plaît pas complètement.... par exemple, il me semble que tes while ne sont pas correct, en effet, tu fais un while i<= imax et tu ne change aucune des valeurs dans la boucle... donc -> boucle infinie si j'y rentrer....

puis, je veux faire de la récursivité terminale, tu fais simplement de la récursivité....(je sais que la récursivité terminale n'est pas terrible dans un langage procédural, que c'est pas beau, mais bon.... vais pas faire ce genre de fonction en camel, plus personne pigerait rien, ou pas beaucoup)

voilà voilà ... sinon, c'est vrai que ta solution va dans le même sens que celui que je prône.

piet · 30 Déc 2003

oui, t'as raison... C'est le copier coller qui fait c'est effet là... En fait, faut changer la condition et les variables...
faut prendre le principe et appliquer le premier case du switch aux autres case...

Sorry!

[C/C++] Algo de parcours en spirale d'un tableau2D

1337

cvm.mangaleet()

1337

Oprahiste vaudou

Α & Ω

1337

Elite

Oprahiste vaudou

cvm.mangaleet()

niafron

ex membre

Touriste

Findecano

ex membre

1337

piet

ex membre

1337

Elite

piet

ex membre

piet

ex membre

Elite

piet

ex membre

Autres sujets récents