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

Discussion dans 'Web, design' créé par TITM4v3rick, 18 Décembre 2003.

Statut de la discussion:
Fermée.
  1. Offline
    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...
    TITM4v3rick, 18 Décembre 2003
    #1
  2. Offline
    zoheir cvm.mangaleet()
    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 :)
    zoheir, 18 Décembre 2003
    #2
  3. Offline
    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...]
    TITM4v3rick, 18 Décembre 2003
    #3
  4. Offline
    gogoprog Oprahiste vaudou
    ouai avec des boucles c'est tout simple, mais faudrait trouver un moyen plus beau :)
    gogoprog, 18 Décembre 2003
    #4
  5. Offline
    Jereck Procrastinateur
    Equipe GamerZ.be
    Indices ou pointeurs ?
    Jereck, 18 Décembre 2003
    #5
  6. Offline
    bètement indices...
    TITM4v3rick, 19 Décembre 2003
    #6
  7. Offline
    AcidBird Touriste
    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 :)
    AcidBird, 19 Décembre 2003
    #7
  8. Offline
    gogoprog Oprahiste vaudou
    en c++ ;)
    gogoprog, 19 Décembre 2003
    #8
  9. Offline
    zoheir cvm.mangaleet()
    euh un moyen plus beau ?! tu ne peux faire ça sans boucle.
    zoheir, 20 Décembre 2003
    #9
  10. Offline
    niafron ex membre
    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
    niafron, 21 Décembre 2003
    #10
  11. Offline
    Ghosta Touriste
    Tu vas augmenter le nombre de calculs en faisant de la sorte...
    Ghosta, 21 Décembre 2003
    #11
  12. Offline
    Findecano ex membre
    Ton tableau, il sera toujours de cette taille ou il peut changer?
    Findecano, 21 Décembre 2003
    #12
  13. Offline
    il varie bien sur.
    TITM4v3rick, 21 Décembre 2003
    #13
  14. Offline
    piet ex membre
    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<=imax)
    			{
    				cout << tab[j][i];
    				i++;
    			}
    			jmin++;
    			op=2;
    			lire (tab[dim][dim], imin, imax, jmin, jmax, i, j, op);
    			break;
    		case 2 :
    			while (i<=jmax)
    			{
    				cout << tab[j][i];
    				j++;
    			}
    			imax--;
    			op=3;
    			lire (tab[dim][dim], imin, imax, jmin, jmax, i, j, op);
    			break;
    		case 3 :
    			while (i<=imax)
    			{
    				cout << tab[j][i];
    				i--;
    			}
    			jmax--;
    			op=4;
    			lire (tab[dim][dim], imin, imax, jmin, jmax, i, j, op);
    			break;
    		case 4 :
    			while (i<=imax)
    			{
    				cout << 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...
    piet, 24 Décembre 2003
    #14
  15. Offline
    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 ;)
    TITM4v3rick, 25 Décembre 2003
    #15
  16. Offline
    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....
    TheFornicator, 25 Décembre 2003
    #16
  17. Offline
    piet ex membre
    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écembre 2003
    #17
  18. Offline
    piet ex membre
    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?
    piet, 25 Décembre 2003
    #18
  19. Offline
    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.
    TheFornicator, 25 Décembre 2003
    #19
  20. Offline
    piet ex membre
    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!
    piet, 30 Décembre 2003
    #20
Statut de la discussion:
Fermée.