Discussion :

[rukov]

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.

[loufoque]

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

[koala01]

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 :

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

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;
    }
}

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

[koala01]

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 :

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

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 :

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

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 :

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

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 )

[loufoque]

On peut très bien le faire depuis le début, mais ça nécessite une variable temporaire.