Créer un tableau sans doublons

**Maha02** · 23/12/2018, 15h13

Salut je suis nouveau sur ce forum. Malheureusement je viens solliciter votre aide pour 3 exercices dont celui là.

On dispose d'un tableau de numérique qui contient des doublons (des nombres présents plusieurs fois) que l'on veut éliminer : on veut récupérer une liste contenant les mêmes éléments, mais où chaque ne serait présent qu'une seule fois.
On me demande de produire un algorithme me permettant de le faire.

Voilà je n'arrive pas trop à avancer. Toute idée ou proposition de correction serait la bienvenue venu

**tbc92** · 23/12/2018, 17h55

Une idée ... je pense que tu peux avoir des idées toi-même (enfin j'espère !!!).
Une proposition de correction : tout à fait, c'est exactement l'esprit de ce forum. Mais pour ça, il faut que tu proposes un début de solution.
Je t'invite donc à proposer quelque chose, et on pourra commencer à t'aider.

**Maha02** · 23/12/2018, 20h45

Ok bon ça peut paraître complétement fausse mais voilà

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
Algorithme Tableau(Tablo1,taille1)
Variable Tablo1[ ], tablo 2 [ ],taille2 : numérique
Variable doublons=numérique
'je commence par chercher la taille du tableau sans les doublons
Pour i= 1 à taille1-1 
     Pour j= 0 à taille-1 
     Si i != j et tablo1[i]=tablo1[j] alors
     Doublons=doublons+1
     fin pour
Fin pour 
taille2=taille1-doublons
Redim tablo2[taille2]

Après je ne sais pas comment faire (si encore c'est correct)) de façon efficace pour remplir le tablo2 sans les doublons.
J'ai pensé à essayer de reclasser le tablo de façon à obtenir tous les nombres à supprimer au bas du tableau pour pouvoir remplir mon tablo2 sans eux

**tbc92** · 24/12/2018, 09h52

Selon moi, calculer le nombre de doublons n'est pas indispensable, mais pourquoi pas. Le problème, c'est qu'ici, ton comptage de nombre de doublons est faux.
Quand on écrit un algorithme, une des pratiques très courantes, c'est de dérouler l'algorithme sur un petit jeu de données. Essaie de dérouler ton algorithme sur un tableau avec 5 nombres [1,3,5,3,7] par exemple. Tu devrais constater que ton algorithme est faux. Et en le déroulant, la correction à faire va te sauter aux yeux.

**Maha02** · 24/12/2018, 10h15

Effectivement il y'avait des erreurs j'ai compris merci pour l'astuce.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Algorithme Tableau(Tablo1,taille1)
Variable tablo 2 [ ],taille2 : numérique
Variable doublons=numérique
'je commence par chercher la taille du tableau sans les doublons
doublons=0
Pour i= 0 à taille1-1 
     Pour j= 0 à taille1-1 
     Si i différent de j et tablo1[i]=tablo1[j] alors
     Doublons=doublons+1
     fin si
Fin pour 
taille2=taille1-doublons
Redim tablo2[taille2]
Fin

Je viens de ressayer ça sur un petit tableau et ça me donne le nombre de chiffres à enlever dans le tableau donc la taille de mon tablo2 qui serra la taille de mon premier tablo moins le nombre de chiffres à enlever

**tbc92** · 24/12/2018, 10h24

Ah ?
1. tu es très rapide. Dérouler l'algorithme sur un tableau de 5 éléments, en faisant attention, ça prend quand même quelques minutes.
2. ta nouvelle proposition ne résoud pas le problème.

**Maha02** · 24/12/2018, 13h20

Ok j'ai pris mon temps et j'ai vu que c'était faux mais seulement j'ai beau réfléchir je ne vois pas comment faire

**tbc92** · 24/12/2018, 15h05

C'est faux ..soit. Mais plus précisément ? Ton algorithme trouve trop de doublons, il en trouve pas assez ? C'est à partir d'un diagnostic précis que tu trouveras les bons remèdes.
A partir de ce jeu de données [a,b,b,c,b,d,b], on est sensé avoir en sortie[a,b,c,d], donc on doit éliminer 3 éléments. Ton algorithme trouve combien de doublons ?

**Flodelarab** · 24/12/2018, 15h25

Bonjour

A mon avis, compter les doublons ne sert juste à rien.

Voici mon algorithme :
Soit tab le tableau à dédoublonner et nb le tableau qui indique le nombre d'apparition d'une valeur. (on pourrait prendre un booléen pour nb car tout ce qu'on veut savoir, c'est si c'est 0 ou plus)

Code :

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

1
2
3
4
5
Pour chaque élément d'indice i de tab
    si nb[tab[i]]==0
    alors stocker/afficher tab[i]
    nb[tab[i]]++
fin

**tbc92** · 24/12/2018, 15h51

A mon avis, dans ce genre d'exercice, il faut se placer dans un cas général (ou dans l'informatique des années 90). Tab est un tableau, c'est un tableau de réels, ou de chaines. Et dans le cadre de cet exercice je pense qu'on ne paut pas construire un tableau nb, dont les arguments sont des chaines.
nb[une_chaine] = 1 : interdit.

Ceci dit, je suis d'accord avec toi. Calculer le nombre de doublons est quasi inutile. Mais comme la difficulté est strictement la même (recenser les doublons et/ou recenser les éléments distincts), ça ne coûte pas grand chose.

**Flodelarab** · 24/12/2018, 16h47

nb[une_chaine] = 1 : interdit.

On dispose d'un tableau de numérique

**valentin03** · 24/12/2018, 19h37

Il doit bien y avoir un moyen de transformer un nombre en chaine
Il suffit alors de verser les nombres dans un tableau de chaines, de mettre des chaines vides à la place des doublons, d'éliminer les chaines vides et de remettre les chaines dans leurs valeurs numériques.

**Wachter** · 25/12/2018, 01h56

Tu pourras également utiliser l'algorithme suivant :

Code :

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

1
2
3
4
Pour chaque élément du tableau d'origine O :
* Parcourir le tableau de destination D à la recherche de cette élément
* S'il n'existe pas, rajouter cet élément dans D
* S'il existe, passer à l'élément suivant dans O

**Maha02** · 25/12/2018, 10h53

Envoyé par tbc92

A mon avis, dans ce genre d'exercice, il faut se placer dans un cas général (ou dans l'informatique des années 90). Tab est un tableau, c'est un tableau de réels, ou de chaines. Et dans le cadre de cet exercice je pense qu'on ne paut pas construire un tableau nb, dont les arguments sont des chaines.
nb[une_chaine] = 1 : interdit.

Ceci dit, je suis d'accord avec toi. Calculer le nombre de doublons est quasi inutile. Mais comme la difficulté est strictement la même (recenser les doublons et/ou recenser les éléments distincts), ça ne coûte pas grand chose.

Je l'ai enfin trouvé

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
Algorithme compteur (T[ ], taille)
Variable estdoublon : booléen
Variable Nbr_doublon : numérique
Nbr_doublon=0
Pour i=1 à taille-1
          Estdoublon=faux
          J=0
          Tantque que j<i
           J=j+1
          Si T[i]=T[i-j] alors
         Estdoublon=vrai
          Fini
         Fintantque
Si estdoublon alors
Nbr_doublon=doublon+1
Fin pour
Fin

Mais si c'est complètement inutile je trouve que c'est mieux de m'en passer.

Envoyé par Wachter

Tu pourras également utiliser l'algorithme suivant :

Code :

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

1
2
3
4
Pour chaque élément du tableau d'origine O :
* Parcourir le tableau de destination D à la recherche de cette élément
* S'il n'existe pas, rajouter cet élément dans D
* S'il existe, passer à l'élément suivant dans O

Ok c'est une idée aussi mais comment faire pour connaître la taille du tableau de destination D ? Je veux dire que avant d'utiliser un tableau il faut d'abord lui attribuer une taille non ? Et si or dans cet algorithme on ne connait pas la taille de D sauf si il y'a une instruction qui nous permet d'ajouter une case à chaque fois.

Envoyé par valentin03

Il doit bien y avoir un moyen de transformer un nombre en chaine
Il suffit alors de verser les nombres dans un tableau de chaines, de mettre des chaines vides à la place des doublons, d'éliminer les chaines vides et de remettre les chaines dans leurs valeurs numériques.

Je sais pas comment faire pour que un tableau chaîne reçoit des variables numérique

**Wachter** · 25/12/2018, 11h45

Ok c'est une idée aussi mais comment faire pour connaître la taille du tableau de destination D ? Je veux dire que avant d'utiliser un tableau il faut d'abord lui attribuer une taille non ? Et si or dans cet algorithme on ne connait pas la taille de D sauf si il y'a une instruction qui nous permet d'ajouter une case à chaque fois.

La taille du tableau de destination est incrémentée au fur et à mesure de l'insertion de nouveaux éléments. Ladite taille est initialisée à zéro.

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
 
tailleD = 0
Pour i = 1 à tailleO faire
 j = 1
 élementTrouvé = faux
 Tant que (j <= tailleD et élémentTrouvé = faux) faire
   Si D[j] = O[i] alors 
    élémentTrouvé = vrai
   Fin Si
   Incrémenter j
 Fin Tant que
 
 Si élémentTrouvé = faux alors
   Incrémenter tailleD
   D[tailleD] = O[i]
 Fin Si
Fin Pour
 
Afficher D;

**Maha02** · 25/12/2018, 13h16

Envoyé par Wachter

La taille du tableau de destination est incrémentée au fur et à mesure de l'insertion de nouveaux éléments. Ladite taille est initialisée à zéro.

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
 
tailleD = 0
Pour i = 1 à tailleO faire
 j = 1
 élementTrouvé = faux
 Tant que (j <= tailleD et élémentTrouvé = faux) faire
   Si D[j] = O[i] alors 
    élémentTrouvé = vrai
   Fin Si
   Incrémenter j
 Fin Tant que
 
 Si élémentTrouvé = faux alors
   Incrémenter tailleD
   D[tailleD] = O[i]
 Fin Si
Fin Pour
 
Afficher D;

Ok merci. Est ce que je peux écrire ton code sous cette forme ?

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
 algorithme tablosansdoublon(O[ ], tailleO)
Variable D[ ], tailleD : Numérique
Variable elementTrouve : booleen
Variable j : numerique
Début
tailleD=1
Redim D[tailleD]
D[0]=O[0] 
Pour i=1 à taille-1 pas 1
j=0
elementTrouve= faux
    Tantque j<=i et non(elementTrouve)
        Si Des[j]O[i] alors
         elementTrouve=vrai
        Finsi
        j=j+1
    Fintantque
Si non(ElementTrouve) alors
tailleD=tailleD+1
RedimD[tailleD]
D[tailleD]=O[i]
Finsi
Fin pour
Afficher D
Fin

**Wachter** · 25/12/2018, 13h34

À quoi sert cette instruction Redim D[tailleD] ?

Par ailleurs, je ne suis pas d'accord avec l'utilisation de cette condition Tantque j<=i. On recherche l'existence d'un élément dans le tableau de destination D ; c'est plutôt tailleD qui devrait être utilisée ici. Après, on pourra peaufiner l'algorithme proposé en triant le tableau d'origine O et optimiser la recherche de l'existence d'un élément dans le tableau de destination D.

**valentin03** · 25/12/2018, 14h01

Envoyé par Maha02

Je sais pas comment faire pour que un tableau chaîne reçoit des variables numérique

Voir la doc de référence du langage utilisé.

**Maha02** · 25/12/2018, 15h15

Envoyé par Wachter

À quoi sert cette instruction Redim D[tailleD] ?

Par ailleurs, je ne suis pas d'accord avec l'utilisation de cette condition Tantque j<=i. On recherche l'existence d'un élément dans le tableau de destination D ; c'est plutôt tailleD qui devrait être utilisée ici. Après, on pourra peaufiner l'algorithme proposé en triant le tableau d'origine O et optimiser la recherche de l'existence d'un élément dans le tableau de destination D.

Dans le cours que j'ai Redim D[tailleD] permet de redimensionner le tableau D. Comme dans l'algorithme
D[ ]
Redim D[2] donc le tableau D aura deux case

Et pour le j<=i oui tu as raison c'est j<=tailleD. Tu valide le code maintenant ?

Envoyé par valentin03

Voir la doc de référence du langage utilisé.

Ok merci