Discussion :

[rimenis]

Bonjour,
pour cette excercice : Ecrire une Decalage*: permet de supprimer les répétitions par un décalage à gauche et de remplacer la valeur supprimée par 0.
exple :
entré : int T[6]={1,4,7,7,5,8,10,4,13,3,3,25,10,25,13,13,4, 7, 7, 10 }
Sortie :
4
7
10
13
3
25
0
0
0
0
0
0
0
0
Voici mon code :

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
19
20
21
22
23
24
25
26
27
28
29
30
void main()
{
 int T[6]={1,4,7,7,5,8};//,10,4,13,3};//,3,25,10,25,13,13};//4 7 7 10 
 int n,decalage;
 n=6;
 //decalage 
 int decalege;
 for(int i=0;i<n;i++){
     //do{decalage=0;
          decalage=1;
           while(decalage>0){
              for(int j=i+1;j<n;j++){
           if(T[i]==T[j]){
               decalage+=1;
               for(int k=j;k<n-1;k++){
                   T[k]=T[k+1];
               }
               T[n-1]=0;
           }
            else
            decalage=0;
         //  for(int p=0;p<n;p++)printf("%d | ",T[p]);
 
          }
 }
 }
 for(int i=0;i<n;i++)
     printf("%d | ",T[i]);
 
}

MAis le résultat est incorrecte, pouvez vous svp m'aider à trouver l'erreur.

[Bousk]

Tu as le droit d'aérer ton code, au pire il sera plus lisible.
Ton code est tabulé n'importe comment, c'est impossible de voir où commence et finit chaque bloc.
Tu déclares decalege puis decalage.
Tu peux déclarer tes variables plus proches de leur utilisation pour limiter les erreurs.
n devrait être const, et utilisée pour T rendrait le tout plus clair.
Ou rendre T dynamique avec la syntaxe [] pour initialiser n avec sa taille, vu que tu sembles avoir plusieurs cas d'utilisation en commentaires.
Après on pourra enfin analyser l'algorithme et voir les problèmes qui s'y trouvent.

[foetus]

je n'arrive pas à comprendre l'exercice ?

Parce que si on applique l'énoncé avec l'éntrée, on s'approche + d'1 sortie "4, 7, 7, 0, 0, 10, 4, 13, 3, 3, 25, 10, 25, 13, 13, 4, 7, 7, 10, 0".

Là, on prend la première répétition et on supprime les suivantes (avec 1 décalage vers la gauche, derrière la précédente répétition - on conserve l'ordre des nombres), en bourrant la fin avec des zéros

Et pourquoi l'entrée est 1 tableau de 6

[Sve@r]

Bonjour

pouvez vous svp m'aider à trouver l'erreur.

Je n'arrive pas à piger comment un tableau qui contient {1,4,7,7,5,8,10,4,13,3,3,25,10,25,13,13,4, 7, 7, 10 } (et qui, soit dit en passant, me semble avoir légèrement peu plus que 6 éléments) peut donner 4, 7, 10, 13, 3. Il est où le premier "1" ? ils sont où le "5" et le "8" ?

Ensuite il faudrait clarifier ce que tu entends pas "répétition". Ok dans 3, 3, 5 le second "3" est répété, pas de souci. Mais dans 3, 5, 3, le second "3" est-il considéré comme une répétition ???

Déjà fait l'exercice avec un papier et un crayon. Identifie les manipulations que tu fais pour pouvoir les coder.

[foetus]

Avec l'exemple, en regardant la sortie "4, 7, 10, 13, 3, 25, 0, 0, 0, 0, 0, 0, 0, 0" on peut dire

Il est où le premier "1" ? ils sont où le "5" et le "8" ?

le 1, 5 et 8 sont supprimés parce qu'ils ne sont pas répétés (ils apparaissent 1 seule fois, pas de répétitions)

Ensuite il faudrait clarifier ce que tu entends pas "répétition".

Ce sont les doublons d'1 nombre mais pas le premier (l'original) (si on lit les nombres de gauche à droite)

Ok dans 3, 3, 5 le second "3" est répété, pas de souci. Mais dans 3, 5, 3, le second "3" est-il considéré comme une répétition ???

Le premier (l'original) est conservé. Mais les doublons (les répétitions) sont supprimés.

Et comme on supprime les doublons et les nombres uniques, on crée des trous. D'où les décalages à gauche pour "tasser" les nombres restants et le bourrage de la fin avec des zéros.

Donc on est loin de "supprimer les répétitions par un décalage à gauche et de remplacer la valeur supprimée par 0" ... surtout le "remplacer par des zéros" et rien n'est dit sur les nombres uniques, 2 règles qui ne sont pas appliquées/ dites

[Guesset]

Bonjour,

Dans la ligne d'un problème assez peu cadré, je présume que la valeur 0 est interdite à l'origine ?

A vue de nez :

• Tri sur copie (copie si on veut garder l'ordre initial) du tableau : complexité en O(n.ln(n))
• Suppression in situ des valeurs uniques (successeur != ou pas de successeur(éventuellement watchdog)) et des valeurs dont le prédécesseur (s'il existe) est ==. Noter l'indice m de la dernière valeur gardée (x2) : complexité en O(n)
• Balayage du tableau d'origine et recherche dichotomique de 2xvaleur dans le tableau secondaire. Si la valeur n'existe pas dans le tableau secondaire, aller à la suivante du tableau d'origine et réitérer. Si la valeur est trouvée l'écrire en i (initialisée à 0)du tableau d'origine, incrémenter i, et mettre à valeur | 1 dans le tableau secondaire (n'existe plus en tant que valeur paire) puis passer à la valeur suivante. En fin, remplir de 0 de i à DimArray - 1 : complexité en O(n.ln(m+1))

Il y a certainement mieux

Salutations

[Sve@r]

Il y a certainement mieux

Ben... il faut se remettre dans le contexte. Ca ressemble à un exercice d'apprentissage de boucles et tableaux donc toutes ces réflexions sur la complexité ne sont probablement pas à l'ordre du jour.
Création d'un tableau de taille identique au premier destiné à stocker les valeurs déjà trouvées. Taille identique comme ça on est certain d'avoir assez de place (il n'y aura jamais plus de valeur à stocker que de valeurs dans le tableau initial).
Ensuite on balaye le tableau initial et si la valeur en cours n'est pas dans la copie alors on l'affiche et on la stocke dans la copie. Ok complexité en 0(n²) mais c'est encore ce qui reste le plus simple à coder pour un débutant...

[foetus]

Je pense plus à 1 algo simple "sur place" ("in-place" en anglais)

Tu vas avoir 1 indice "pivot" : à gauche tu vas avoir toutes les valeurs à conserver (initialisation à 0)

Pour chaque valeur v (à l'indice n), tu vas parcourir de n+1 à taille (taille de ton tableau), et mettre à zéro toutes les valeurs égales à v.
Si tu en as trouvé, tu vas déplacer ta valeur v à l'indice pivot et l'incrémenter de 1 (++pivot_index).
Sinon, tu mets cette valeur v à zero ... mais je ne pense pas que ce soit utile.

Et à la fin du parcours, tu memset à zéro de l'indice pivot à taille.

Ainsi, on s'approche + de l'énoncé de "supprimer les répétitions par un décalage à gauche et de remplacer la valeur supprimée par 0"

Et comme l'a précisé @Guesset, la valeur 0 doit être proscrite .
Édit : la valeur zéro semble même avoir la signification "je passe à la valeur suivante" parce que c'est [très probablement] 1 répétition/ doublon d'1 valeur précédente.
Et en complexité, on est plus en n² (le fameux (n(n + 1)) / 2) si je ne me trompe pas.

[Sve@r]

Je pense plus à 1 algo simple "sur place" ("in-place" en anglais)

Pas mal

Et en complexité, on est plus en n² (le fameux (n(n + 1)) / 2) si je ne me trompe pas.

Même si tu ne fais pas exactement n² itérations, ça reste "de l'ordre" de n² donc la complexité reste en n².