Decalage circulaire (debutant)

Version imprimable

10/12/2006, 01h12
rukov

Decalage circulaire (debutant)

Bonjour.
Voila j'ai un probleme pour resoudre un algorithme de tri circulaire en C/C++.

La premiere partie est tres simple, declarer un tableau de 200 elements, demander à l'utilisateur de rentrer une suite de nombre et qui se termine par 0.
Le remplissage et l'affichage se fait sans probleme.

Par contre, je n'arrive pas à effectuer le decalage circulaire suivant. On doit decaler le premier element d'une place vers la droite, le 2eme de 2 places...le N ieme de N places. Evidemment je n'ai pas le droit d'utiliser un autre tableau pour pouvoir faire le decalage.

Je ne vois pas quelle methode de tri je dois utiliser, je n'arrive pas à trouver une suite qui pourrais resoudre ce probleme.
Sans compter que j'ai l'impression que le decalage est impossible ( je me trompe peut etre) si le nombre d'element est pair. Que faire si 2 element differents se trouveront au final au même indice du tableau ?

Bref j'espere qu'on pourra m'eclairer un peu.
Merci.
10/12/2006, 03h02
loufoque

Rien à voir avec C++.
Voir dans le forum algorithmes.

Salut,

Pour éviter tout problème, il s'agit de prendre ton tableau "par la fin"...

En effet, si tu travaille dans l'ordre croissant des positions, la valeur se trouvant en tab[1]écrasera celle de tab[2], puis celle de tab[4], celle de tab[8]...

De plus, il ne faut essayer (si tu utilises un tableau statique) de décaler que les N/2 premiers nombres (ou N est la taille de ton tableau)... sous peine de provoquer un plantage sévere...

L'idée est de "simplement" utiliser une boucle du genre de
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #define MAX 200 //maximum de cases du tableau int main() { int tab[N]; //remplissage du tableau par l'utilisateur for(int i=MAX/2-1;i>=0;i--) //une boucle incrémentale inversée ;) { tab[i*2+1]=tab[i]; // ben oui, tab[0] est le premier élément... // il doit etre décalé de 1 ;) et les suivant se // trouvent en N-1 (ou N est leur position "humaine") } //affichage final for(int i=0;i<MAX;i++) { std::cout<<"a la position "<<i<<"on a "<<tab[i]<<std::endl; } }

10/12/2006, 09h40
b Oo

Salut,
prefere const size_t MAX = 200; plutôt que le #define MAX 200 (notation C).
size_t est un unsigned int.

Par contre je ne vois pas ce que ca change koala01 de partir de la fin ?
Ici tu modifies toujours les valeurs.

Je pense que tu devrais commencer par ton 1er élément, tu va l'inserer à la position 2, donc tu sauvegarde l'element de la position 2, tu le décales position 4 (tu as sauvegarder l'élément de la position 4) ...
10/12/2006, 10h19
koala01
Citation:

Envoyé par b Oo

Salut,
prefere const size_t 200; plutôt que le #define MAX 200 (notattion C).
size_t est un unsigned int.

Par contre je ne vois pas ce que ca change koala01 de partir de la fin ?
Ici tu modifies toujours les valeurs.

Je pense que tu devrais commencer par ton 1er élément, tu va l'inserer à la position 2, donc tu sauvegarde l'element de la position 2, tu le décales position 4 (tu as sauvegarder l'élément de la position 4) ...

Hé bien, justement...

Si tu limite (vu que ton tableau ne dispose que de 200 emplacement) l'introduction à 100 éléments, tout l'espace restant apres le dernier élément... est inutilisé...

En déplacant, d'abord l'élément qui se trouve à la position tab[100], tu peux donc ne pas t'en faire si l'élément qui se trouve en position tab[50] vient écraser la valeur de tab[100]... vu qu'il a déjà été déplacé...
Au final, tu auras quelque chose dont les positions de départs seront
Code:

1 2 1, 1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7, 14, 8, 15, 9, 16, 10...
(tu n'aura donc perdu aucune valeur)
alors que si tu parcourres ton tableau dans l'autre sens, tu obtiendra
Code:

1 2 1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 11, 3, 13, 7, 15, 1, 17, 9 ...
(avec perte de toutes les valeurs paires... et une tres fortes redondance de 1...)

Ou alors, comme tu le signale, il faut partir sur la récursivité...

Mais il sera beaucoup plus simple de partir sur une simple boucle (on travaille juste dans l'ordre décroissant) que de partir dans une récursivité du genre de
Code:

1 2 3 4 5 6 7 void deplace(int pos) { if(tab[pos*2]!=0) deplace(pos*2); tab[pos*2]=tab[pos]; }
Bien sur, au final le résultat sera le même...

Mais honnetement parlant, la récursivité n'a ici qu'un intéret tout didactique...

Une boucle itérative descendante fournira un résultat tout aussi valable, et bien plus rapide...

Souviens toi toujours que dans bien des cas, la récursivité peut avantageusement etre remplacée par une boucle itérative (le calcul de l'exposant et de la factorielle, si ce sont de bons exemples pour faire comprendre le principes de la récursivité, seront bien plus rapides en boucles itératives ;) )
10/12/2006, 14h53
loufoque

On peut très bien le faire depuis le début, mais ça nécessite une variable temporaire.
10/12/2006, 16h39
b Oo

Le tableau est-il toujours de taille 200 ?
Car si le tableau est une puissance de 2, l'algo n'est pas réalisable.
Ex :
tableau de 4 éléments :
1 2 3 4
Le 2 doit se trouver à la place du 4, mais le 4 doit rester à sa place.
(le dernier élément ne bouge pas).

De plus l'idée que j'ai soumise ne peut s'appliquer que sur certains tableaux, ceux où chaque permutation renvoie sur une case non traitée.
10/12/2006, 17h41
loufoque

Je vois pas le rapport avec les puissances de 2.

T'obtiens
1, 1, 3, 2, undef, 3, undef, 4
si j'ai bien compris le sujet.
10/12/2006, 17h54
rukov
Non le tableau n'est pas toujour de taille 200.
C'est l'utilisateur qui entre chaque element jusqu'a ce qu'il ecrive la valeur 0.
Le tableau à donc une nouvelle dimension apres le remplissage.

Le 1er probleme c'est lorsque le nombre d'element est paire.
Exemple:

1 2 3 4 5 6.
Le 1 sera en position 2, le 2 en position 4, le 3 en position en 6, le 4 en position 2, le 5 en position 4 et le 6 en position 6.
Le 1 et le 4 auront la même position ; le 2 et le 5 auront aussi la même position.

Dans le cas d'un tableau impaire j'essaye toujours sans succes de faire le decalage. Mon idée etait d'utiliser une variable temporaire. Mes premiers elements sont bien decalé mais des que j'arrive vers le milieu du tableau rien ne va plus.

Mon traitement:
Code:

1 2 3 4 5 6 7 8 for (i=(n/2)-1;i>=0;i--) { temp=tab[i*2+1]; tab[i*2+1]=tab[i]; tab[i]=temp; }
A l'affichage avec 7 éléments rentrés:

1 2 3 4 5 6 7

4 1 6 2 5 3 7

1,2,3 et 4 sont bien placé. Le 5 devrait etre a la place du 6 et le 6 à la place du 5... Le 7 est bien placé. Il y a une erreur mais je n'ai pas encore trouvé.

Je vais peut etre essayer avec une fonction recursive, bien que cela est un peu complexe pour moi.
10/12/2006, 18h25
loufoque

Citation:

Le 1 sera en position 2, le 2 en position 4, le 3 en position en 6, le 4 en position 2, le 5 en position 4 et le 6 en position 6.

Ce n'est pas ce que tu avais dit au début.
Il semblerait qu'en fait le décalage se fasse modulo n.

Citation:

Le 1 et le 4 auront la même position ; le 2 et le 5 auront aussi la même position.

Ça n'a pas de sens.
10/12/2006, 19h30
rukov

Voila ce que j'ai dis au debut:

Citation:

Par contre, je n'arrive pas à effectuer le decalage circulaire suivant. On doit decaler le premier element d'une place vers la droite, le 2eme de 2 places...le N ieme de N places.

Exemple:
1 2 3 4 5 deviens 3 1 4 2 5

Voila ce qui se passe si le tableau a un nombre d'element paire:

Citation:

Le 1er probleme c'est lorsque le nombre d'element est paire.
Exemple:

1 2 3 4 5 6.
Le 1 sera en position 2, le 2 en position 4, le 3 en position en 6, le 4 en position 2, le 5 en position 4 et le 6 en position 6.
Le 1 et le 4 auront la même position ; le 2 et le 5 auront aussi la même position.

Comme tu dis, ça n'a pas de sens, donc pour le moment j'admet que le decalage est impossible pour un nombre d'element paire.

Pour l'instant j'essaye de regler le probleme avec un tableau d'elements impaire.
10/12/2006, 20h04
b Oo

L'algorithme que tu fais ne peux pas fonctionner car tu échanges a chaque fois deux choses.
Tu mets une chose à la bonne place et l'autre soit à la bonne soit à la mauvaise.
Je suis parti d'une autre idée.
Tu as le tableau :
1 2 3 4 5 6 7

Tu prends le 1, tu sauvegardes le 2 et tu mets le 1 à la place du 2 :
1 1 3 4 5 6 7
2
tu sauvegardes le 4 et tu mets le 2 à la place :
1 1 3 2 5 6 7
4
Ensuite tu mets le 4 a la place du 1er 1.
Ensuite il faut le faire pour le 3 de la meme manière.
Et la il va etre trié comme tu veux.

Je pense que si tu prends un tableau très grand, il faut faire la meme chose avec tous les nombres premiers <= la taille/2 (c'est une hypothèse).

Evidemment, j'étais parti sur un autre porblème (je n'avais pas trop compris ce que tu voulais dire par "décalage circulaire", excuses-moi :oops:)

Il s'agira donc, effectivement, de faire appel à de la récursivité...

Mais pour cela, il s'agira de réfléchir un peu à comment y arriver...

En se basant sur le résultat à obtenir, on peut se dire que, en partant d'une position N, l'élément doit arriver à une position (N*2+1)%nombre d'élément introduits...

Cela nous amene à une limitation à apporter: il faut impérativement un nombre d'éléments introduits impaires...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/* fonction de permutation
 *
 * @pre: nombre d'éléments introduits exclusivement impaire
 * @in: position actuelle à permuter
 *      position de départ de la récursivité
 *      pointeur sur le tableau à permuter
 *      taille du tableau à permuter
 * @verif si (pos*2+1)%taille== depart: sauvegarder tableau[depart]
 * @out: valeur sauvegardée
 */
int Permuter(int position, int depart, int* tableau, size_t taille)
{
    int retour;
    /* valeur utilisée en maintes occasion*/
    int arrivee=(position*2+1)%taille;
    /*verif: est-on au point de retour? */
    if(arrivee==depart)
    {
    /* sauvegarde de la valeur */
        retour=tableau[arrivee];
    /* modification du tableau */
        tableau[arrivee]=tableau[position];
    }
    else
    {
/* Permuter la position d'arrivee */
            retour=Permuter(arrivee,depart,tableau,taille);
/*deux cas envisageables: première exécution, ou toutes les suivantes */
            if(depart==position)
                tableau[arrivee]=retour;
            else
                tableau[arrivee]=tableau[position];
    }
    return retour;
}
int main()
{
    int tab[200];
    int cpt=0;
    int intro=0;
    do
    {
        std::cout<<"introduisez le nombre"<<cpt+1<<" (0 pour quitter)"<<std::endl;
        std::cin>>intro;
        if(intro!=0)
        {
            tab[cpt]=intro;
            cpt++;
        }
    }while(intro>0);
     /* si le nombre d'éléments itroduits est paire, on abandonne le dernier
     *  (cf pre)*/
    if(cpt%2!=1)
    {
 
        std::cout<<"il faut un nombre impair d'éléments... le dernier sera omis"
                 <<std::endl;
        cpt--;
    }
    /*permutation en partant de pos=0 */
    Permuter(0,0,tab, cpt);
    /*permutation en partant de pos=2 */
    Permuter(2,2,tab, cpt);
    /*affichage final */
    for(int i=0;i<cpt;i++)
        std::cout<<tab[i]<<" ";
	return 0;
}

NOTA:
Plutot que de me baser sur des variables globales pour la position de départ, le tableau et le nombre d'éléments introduits, chose dont j'ai horreur (je parle des variables globales), j'ai décidé de les passer systématiquement à la fonction