Tableau et valeurs identiques [Sources]

**spongebob1** · 12/11/2006, 00h56

Bonjour !
Je suis eleve et on me demande de réaliser la fonction suivante mais je n'arrive pas à la programmer , j'ai des idees mais aucune n'aboutit. Voici l'enoncé :

soit un tableau T(50) consitué de n valeurs entieres dans un ordre quelconque.
ecrire une fonction qui elimine les valeurs identiques et n'en conserver qu'une
l'algorithme de reorganisation du tableau ne doit pas utiliser de tableau intermediaire . la derniere valeur des tableaux sera de valeur nulle.

Je vous remercie par avance.

Un programmeur (tres) débutant !

**Trap D** · 12/11/2006, 01h10

As-tu essayé de le faire à la main. Trouve une méthode simple avec des exemples.
Ecris un pseudo code en français, teste le sur des exemples et ensuite essaie de programmer en C.
On t'aidera pour le C, l'algo c'est ton affaire.
Un parcours de tableau se fait en utilisant un indice, mais on peut utiliser plusieurs indices sur le même tableau.

**Emmanuel Delahaye** · 12/11/2006, 01h13

Envoyé par spongebob1

Je suis eleve et on me demande de réaliser la fonction suivante mais je n'arrive pas à la programmer , j'ai des idees mais aucune n'aboutit. Voici l'enoncé :

soit un tableau T(50) consitué de n valeurs entieres dans un ordre quelconque.
ecrire une fonction qui elimine les valeurs identiques et n'en conserver qu'une
l'algorithme de reorganisation du tableau ne doit pas utiliser de tableau intermediaire . la derniere valeur des tableaux sera de valeur nulle.

C'est surtout une question d'algorithme, donc de conception. Commence par décrire avec des phrases simples et claires comment tu ferais ce travail.

Par exemple, tu as 2 jeux de cartes identiques mélangés devant toi. Comment tu fais pour en constituer un complet ?

L'informatique c'est surtout de la reflexion.

J'attends ton post.

**giggs** · 12/11/2006, 03h26

J'ai peut-ètre une solution, j'ai fait l'exercice et ça marche chez moi, donc je vais pas te donner les réponses toutes faites (juste dans ton intéret) mais je peux te donner des idées pour le faire. Je pense qu'il existe d'autres moyens probablement plus simple pour le faire, mais la rien d'autre me viens alors voici comment je ferai:

-Déclaration d'un tablo[50]
-écrire deux boucles l'une dans l'autre pour tester les valeures de chaque entiers(la première boucle prendra un a un les éléments du tablo qui seront ensuite comparé entre eux via l'autre boucle)sachant qu'il faudra veiller à ce que chaque valeure ne soit pas comparée avec elle même en se servant par exemple d'une instruction if.
-intialiser ensuite la dernière valeure du tablo pour qu'elle soit nulle...

**spongebob1** · 12/11/2006, 14h25

J'avais bien l'idee des boucles imbriquees mais je n'arrive pas à realiser la fonction sans fabriquer un autre tableau . Je ne sais pas où mettre les valeurs une fois traitees.

Merci.

**Emmanuel Delahaye** · 12/11/2006, 14h43

Envoyé par spongebob1

J'avais bien l'idee des boucles imbriquees mais je n'arrive pas à realiser la fonction sans fabriquer un autre tableau . Je ne sais pas où mettre les valeurs une fois traitees.

A la place des doublons...

Par exemple
A B C B D E F 0
devient (D est copié en B)
A B C D D E F 0
puis (E est copié en D)
A B C D E E F 0
puis (F est copié en E)
A B C D E F F 0
puis (0 est copié en F)
A B C D E F 0 0

**giggs** · 12/11/2006, 15h02

Emanuel: ta technique marchera uniquement si il connait l'ordre et les valeures du tableau, sinon c'est impossible...

**Emmanuel Delahaye** · 12/11/2006, 15h32

Envoyé par giggs

Emanuel: ta technique marchera uniquement si il connait l'ordre et les valeures du tableau, sinon c'est impossible...

Je pense que ça fonctionne dans tous les cas. Les seules données détruites sont les doublons. Il s'en créée au fur et a mesure, mais c'est pas grave, ils sont éliminés au tour suivant.. Par contre, c'est long.

EDIT Corrigé (La 1ere version, un peu trop simpliste, était buggée)

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
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
69
 
#include <stdio.h>
#include <stdlib.h>
#define NELEM(a) (sizeof (a) / sizeof *(a))
 
static void display (char const *s, int const a[], size_t n)
{
   size_t i;
   printf ("%s: ", s);
   for (i = 0; i < n; i++)
   {
      printf ("%2d", a[i]);
   }
   printf ("\n");
}
 
static size_t clean (int a[], size_t n)
{
   size_t i;
 
   for (i = 0; i < n; i++)
   {
      size_t j;
      int doublon = 0;
 
      for (j = i + 1; j < n - 1; j++)
      {
         if (!doublon)
         {
            doublon = a[j] == a[i];
 
            if (doublon)
            {
               a[j] = a[j + 1];
               display ("    in", a, n);
            }
         }
         else
         {
            a[j] = a[j + 1];
         }
      }
 
      if (doublon)
      {
         n--;
      }
      else
      {
         break;
      }
   }
   return n;
}
 
int main (void)
{
 
   int a[] = { 2, 6, 4, 6, 9, 3, 2, 5 };
 
 
   display ("before", a, NELEM (a));
   {
      size_t n = clean (a, NELEM (a));
      display (" after", a, n);
   }
 
   return 0;
}

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
 
before:  2 6 4 6 9 3 2 5
    in:  2 6 4 6 9 3 2 5
    in:  2 6 4 6 9 3 2 5
    in:  2 6 4 6 9 3 2 5
    in:  2 6 4 6 9 3 2 5
    in:  2 6 4 6 9 3 2 5
    in:  2 6 4 6 9 3 5 5
    in:  2 6 4 6 9 3 5
    in:  2 6 4 9 9 3 5
    in:  2 6 4 9 3 3 5
    in:  2 6 4 9 3 5 5
    in:  2 6 4 9 3 5
    in:  2 6 4 9 3 5
 after:  2 6 4 9 3 5
 
Press ENTER to continue.

**giggs** · 12/11/2006, 15h42

Il est vrai que pour l'exemple que tu vient de donner, cela marche même si c'est un peu long, en revanche si il s'agit par exemple d'un tableau comme ceci:
D A F E C B F
ça risque d'etre encore mille fois plus long pour éliminer les lettres semblables et les remmetre dans l'ordre, et c'est parce que l'on connait l'ordre des lettres, maintenant imaginons que l'on ne connaisse pas l'ordre des lettres on ne pourras pas dire quelle lettre devras remplacer une autre...
Cela dit, c'est une technique comme une autre après il faut voir les contraintes qui sont mise pour le projet...

**Emmanuel Delahaye** · 12/11/2006, 16h14

Envoyé par giggs

Il est vrai que pour l'exemple que tu vient de donner, cela marche même si c'est un peu long, en revanche si il s'agit par exemple d'un tableau comme ceci:
D A F E C B F
ça risque d'etre encore mille fois plus long pour éliminer les lettres semblables et les remmetre dans l'ordre,

Il n'a jamais été question de les remettre dans l'ordre (ou alors j'ai mal lu). Si c'était le cas, on commencerait pas trier le tableau. C'est rien...

J'ai donné du code. Si tu le trouve bizarre ou complexe, dit-le. (en fait, je pense qu'il y a un bug : Corrigé.)

**spongebob1** · 12/11/2006, 16h29

J'ai fait ce petit essai avec un tableau à 6 cases pour voir, mais ça ne marche pas, mon erreur est surement dans la 'double boucle'.

Merci.

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
#include <stdio.h>
#include <stdlib.h>
 
int main(void)
{
   int A[5];
   int i,l,k,j;
 
   for (i=0;i<5;i++)
   { 
      printf("Rentrer la valeur %d du tableau   ",i);
      scanf("%d",&A[i]);
   }
 
   for (k=0;k<5;k++)
   { 
      for(j=0;(j<5)&&(k!=j);j++)
      if (A[j]==A[k]) A[j]=A[j+1] ;
   }
 
 
   for (l=0;l<5;l++)
   {
      printf("%d  .  ",A[l]);
   }
   system("PAUSE");	
   return 0;
}

**spongebob1** · 12/11/2006, 16h40

Desolé, j'ai rectifié une petite erreur mais ça marche toujours pas lol

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
31
32
33
 
#include <stdio.h>
#include <stdlib.h>
 
int main(void)
{
 
int A[5];
int i,l,k,j;
 
for (i=0;i<5;i++)
{
printf("Rentrer la valeur %d du tableau ",i);
scanf("%d",&A[i]);
}
 
for (k=0;k<5;k++)
{
for(j=0;(j<5)&&(k!=j);j++)
if (A[j]==A[k]) A[k]=A[k+1] ;
}
 
 
for (l=0;l<5;l++)
{
printf("%d . ",A[l]);
}
 
 
 
system("PAUSE");
return 0;
}

**Emmanuel Delahaye** · 12/11/2006, 17h24

Envoyé par spongebob1

Desolé, j'ai rectifié une petite erreur mais ça marche toujours pas lol

L'algorithme est un peu plus complexe que ça. Je reprend :

On cherche à éliminer les doublons dans un tableau de n éléments.

Pour ça, on parcours le tableau avec un indice i, et pour chaque valeur de i, on parcours la suite du tableau (donc à partir de i + 1) à la recherche d'un doublon, avec un indice j.

Si il n'y en pas, le travail est terminé.
Si il y en a un, les éléments d'indices i et j sont identiques.

On va alors copier l'élément d'indice j + 1 sur j jusqu'à n-1, puis, comme on 'perdu' un élément, on diminue n de 1, et on recommence avec le i suivant.

**Trap D** · 12/11/2006, 17h36

Je vous propose une autre méthode, qui consiste à parcourir le tableau en regardant si la valeur à déjà été rencontrée, si elle l'a déjà été, on remplace cette valeur par la dernière valeur du tableau, qui est ensuite mise à zéro:
l'algo donne à peu près ceci :

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
31
32
33
34
tab est le tableau de n valeur non nulle (on suppose que tab[n+1] = 0  (la dernière valeur du tableau est nulle, dixit le P.O.)
cur : indice qui parcourt le tableau jusqu'à rencontré une valeur nulle;
max : indice de la dernière valeur non nulle du tableau
 
initialisation
cur <- 2 // la première valeur n'a evidemment jamais été rencontrée déjà
max <- n
 
tant que tab[cur] <> 0 faire
  si valeur_déjà_vue(cur) = vrai alors
    // on remplace la lvauer courante par la dernière valeur du tableau
    tab[cur] <- tab[max]
    // celle-ci est mise à zéro
    tab[max] <- 0
    // et l'indice maximal est décrémenté
    max <- max - 1
  sinon
    cur <- cur + 1
  fin si
fin tant que
 
la fonction  valeur_déjà_vue(x) peux s'écrire
 
fonction valeur_deja_vue(x : entier) : booléen
  i : entier
  retour : booléen
 
  retour <- faux 
  i <- 1
  tant que retour = faux et i < x faire
    retour <- tab[i] = tab[x]
    i <- i + 1
  fin tant que
  retourner retour

**spongebob1** · 12/11/2006, 19h12

C'est encore moi, j'ai essayé de faire la fonction avec les aides proposées, je suis arrivé à cette chose là, essai avec un tableau à 6 valeurs, qqun peut executer la fonction et me dire ce qu'il ne va pas ?

Merci et desolé si je vous embete un peu, je suis un débutant et l'exercice est pour demain, ça fair depuis 15h que je suis desssus.

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
31
32
33
34
#include <stdio.h>
#include <stdlib.h>
 
void main(void)
{
 
int A[6];
int i,l,k,j,m;
int n=6;
 
for(m=0;m<5;m++)
    { 
      printf("Rentrer la valeur %d du tableau   ",m);
      scanf("%d",&A[m]);
      m++ ;
    }
 
for (i=0;i<n;i++)
    for (j=i+1;j<n;j++)
         if (A[i]==A[j])  
             for (k=j;k<n-1;k++)
              A[k]=A[k+1];
              n=n-1;
 
 
for (l=0;l<n;l++)
{
printf("%d . ",A[l]);
}
 
system("PAUSE");
return 0;
 
}

**Emmanuel Delahaye** · 12/11/2006, 19h29

Envoyé par spongebob1

C'est encore moi, j'ai essayé de faire la fonction avec les aides proposées, je suis arrivé à cette chose là, essai avec un tableau à 6 valeurs, qqun peut executer la fonction et me dire ce qu'il ne va pas ?

main() retourne int. Toujours. Si ton prof soutient le contraire, change de prof.

Ton code, une fois correctement indenté, donne ça :

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
 
#include <stdio.h>
#include <stdlib.h>
void main (void)
{
   int A[6];
   int i, l, k, j, m;
   int n = 6;
   for (m = 0; m < 5; m++)
   {
      printf ("Rentrer la valeur %d du tableau ", m);
      scanf ("%d", &A[m]);
      m++;
   }
   for (i = 0; i < n; i++)
      for (j = i + 1; j < n; j++)
         if (A[i] == A[j])
            for (k = j; k < n - 1; k++)
               A[k] = A[k + 1];
   n = n - 1;
   for (l = 0; l < n; l++)
   {
      printf ("%d . ", A[l]);
   }
   system ("PAUSE");
   return 0;
}

C'est normal que n = n -1; soit tout seul comme ça ?

Je conseille de toujours mettre les {} aux structures de code.

**spongebob1** · 12/11/2006, 19h34

en fait n=n-1 est dans la boucle indicée avec k , j'ai bien oublié les accolades ...

En mettant les {} j'ai toujours pas un programme concluant ...

Je doit etre giga nul

**spongebob1** · 12/11/2006, 19h38

PS : il faut enlever m++ dans la boucle en m sinon ça compte de 2 en 2 ...
je commence à comprendre toutes mes erreurs ! le métier rentre !

Tableau et valeurs identiques [Sources]

C

Discussions similaires

Partager

Partager