Tableau et valeurs identiques

Version imprimable

11/11/2006, 23h56
spongebob1

Tableau et valeurs identiques

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 !
12/11/2006, 00h10
Trap D

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.
12/11/2006, 00h13
Emmanuel Delahaye

Citation:

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.
12/11/2006, 02h26
giggs

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...
12/11/2006, 13h25
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.

Merci.
12/11/2006, 13h43
Emmanuel Delahaye

Citation:

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
12/11/2006, 14h02
giggs

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

Citation:

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:

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:

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.

12/11/2006, 14h42
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, 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...
12/11/2006, 15h14
Emmanuel Delahaye

Citation:

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

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:

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

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

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

12/11/2006, 16h24
Emmanuel Delahaye

Citation:

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.

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:

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

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:

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

Citation:

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:

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.

12/11/2006, 18h34
spongebob1

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 ;)
12/11/2006, 18h38
spongebob1

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 !