Exercice sur les tableaux

Version imprimable

Bonjour à tous, voici un exercice que je dois réaliser :

Un tableau à une dimension contient des entiers égaux à 0, 1 ou 2. Ecrire un algorithme qui range les éléments de ce tableau dans un deuxième tableau de manière que les 0 soient rangés en tête, puis les 1 puis les 2. Le premier tableau ne sera parcouru qu'une seule fois. Il sera initialisé à sa déclaration et affiché

Et voici ma solution, mais je ne sais pas si c'est une bonne chose de l'avoir fait de cette manière, merci pour vos remarques.

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
 
Constante MAX = 6
Tableau entier iTableau taille MAX
<* = {0,0,2,1,2,1} *>
Tableau entier iEchange taille MAX
Variable indice iI
 
Début du traitement
 
   /* Boucle : */
   Initialisation
   Compter avec iI de 0 à 5
 
      Afficher iTableau[iI] Tab
 
   Fin de compter
 
   Fin de ligne
   Fin de ligne
 
   /* Boucle : */
   Initialisation
   Compter avec iI de 0 à 5
 
      /* Alternative : */
      Si iTableau[iI] == 0 Alors
 
	 iEchange[0] <- 0
	 iEchange[1] <- 0 
 
	 /* */
      Sinon
 
	 si iTableau[iI] == 1 Alors
 
	    iEchange[2] <- 1
	    iEchange[3] <- 1 
 
	 Sinon
 
	    si iTableau[iI] == 2 Alors
 
	       iEchange[4] <- 2
	       iEchange[5] <- 2 
 
	    Fin de si
	    Fin de si
      Fin de si
 
   Fin de compter
 
   /* Boucle : */
   Initialisation
   Compter  avec iI de 0 à 5
 
      Afficher iEchange[iI] Tab
 
   Fin de compter
 
  Attente 
 
Fin du traitement

Merci pour votre aide.

Michael

05/11/2006, 13h18
borisd

Ton algo ne marche que si tu as deux 0, deux 1 et deux 2. Dans les autres cas, il ne fonctionne pas.

Essaie simplement de faire un programme qui commence par compter le nombre de 0, le nombre de 1, le nombre de 2, puis remplit le tableau de résultat sachant ces nombres.
05/11/2006, 13h39
Hephaistos007

Un algorithme de tri résoud le problème : http://fr.wikipedia.org/wiki/Algorithme_de_tri
05/11/2006, 13h52
millie

Citation:

Envoyé par Hephaistos007

Un algorithme de tri résoud le problème : http://fr.wikipedia.org/wiki/Algorithme_de_tri

IDE demande explicitement que la complexité soit en O(n). Et non en O(n ln n) ou O(n²) tel un algorithme de tri classique. Par contre, un algorithme de tri comptage fonctionne (mais cela revient à ce que borisd disait)

en O(n) par exemple :

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
 
 
const n = 25;
var T_initial, T_final : array[0..n-1] of byte;
procedure ordone;
var i : integer; n1, n2 : integer;
   begin
   for i:=0  to n-1 do T_Initial[i]:=Random(3); // ou mettre les data en question
   n1:=-1; 
   n2:=n;
   for i:=0 to n-1 do
   if T_initial[i]=0 then 
      begin 
      inc(n1); 
      T_final[n1]:=0 
      end
   else
   if T_initial[i]=2 then 
      begin 
      dec(n2); 
      T_final[n2]:=2 
      end;
   if n1 < n2-1 then for i:=n1+1 to n2-1 do 
      T_final[i]:=1;
   end;

05/11/2006, 14h51
IDE

Suite

Merci pour toutes ces réponses, je suis allé sur le suite suivant :

http://fr.wikipedia.org/wiki/Tri_comptage

qui explique se que je voudrais faire mais je ne comprend pas bien l'algorithme, si quelqu'un pourrait me l'expliquer se serait super sympa, merci

Michael
05/11/2006, 15h02
millie

On sait qu'il faudra trier des entiers entre deux bornes (par exemple de 1 et 12) d'un tableau T.

On crée un tableau Compte de taille 12 initialisé à 0. Compte[i] correspondra au nombre de i qu'il y aura dans le tableau à la fin de la première partie.

- Dans un premier temps, il suffit donc de parcourir ton tableau T et incrémenter les bons indices de Compte. Cela revient simplement à incrémenter Compte[T[i]] pour chaque i

- Ensuite, tu connais pour chaque entier entre 1 et 12, leurs nombres d'occurence dans T

- Il suffit de parcourir un nouveau tableau (qui correspondra au tableau trié) et d'écrire les éléments triés (en utilisant le tableau Compte) ce qui se fait simplement en parcourant les éléments de Compte un par un.
05/11/2006, 17h36
HanLee

C'est l'algorithme du drapeau hollandais ton truc non ? ON me l'avait posé en MPSI...

Nous on avait pas le droit de faire du tri par comptage par contre, donc pas le droit de créer un tableau supplémentaire.

Il fallait gérer les permutations au fur et à mesure qu'on parcourait le tableau, donc je sais pas si tu peux utiliser les dernières solutions données.

Pour nous la méthode c'était de garder les coordonnées de la fin de la séquence de 0, de la suite des 1, et ta position. Et donc t'en déduisais les permutations à faire...
05/11/2006, 18h06
Jean-Marc.Bourguet

Citation:

Envoyé par HanLee

C'est l'algorithme du drapeau hollandais ton truc non ?

Oui. Voir Dijkstra, a discipline of programming.

Suite

Voici se que j'ai fais mais mon résultat a un petit probleme par apport a ma déclaration de mon tableau et je ne trouve pas mon erreur

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
 
Constante MAX = 5
Tableau entier iTab taille MAX
<* = { 4,8,7,12,1 } *>
 
Variable indice iI,iJ
Variable entiere iTemp
 
Variable entiere iMIN
 
Début du traitement
 
   /* Boucle : */
   Initialisation
 
      iMIN <- iTab[iI]
 
   Compter avec iI de 0 à MAX - 2
 
      /* Boucle : */
      Initialisation
      Compter avec iJ de 1 à MAX - 1
 
	 /* Alternative : */
	 Si iTab[iI] < iTab[iMIN] Alors
 
	    iMIN <- iTab[iI]
 
	 Fin de si
 
      Fin de compter
 
      iTemp <- iTab[iI]
      iTab[iI] <- iTab[iMIN]
      iTab[iMIN] <- iTemp
 
   Fin de compter
 
   /* Boucle : */
   Initialisation
   Compter avec iI de 0 à MAX - 1
 
      Afficher iTab[iI] Tab
 
   Fin de compter
 
   Attente
 
Fin du traitement

et voici mon résultat : 1 4 0 7 8

Merci pour votre aide

Michael

06/11/2006, 11h16
Hephaistos007
Citation:
Envoyé par IDE

Code:

1 2 Tableau entier iTab taille MAX <* = { 4,8,7,12,1 } *>
Je croyais que ton tableau ne contenais que 0,1 ou 2 ?!?

Ensuite, a vu d'oeil ton algorithme ne ressemble pas à un algorithme de tri par comptage.
06/11/2006, 11h32
IDE

Suite

Oui je sais mais j'ai fais des recherches sur le net pour essayer de résoudre mon petit probleme et je suis tombé sur un code en C et je l'ai transformé en pseudo code, mais je dois dire que c'est pas tres bien reussi :lol: , donc voila pourquoi je demandais un peu d'aide pour m'expliquer mon erreur.

Michael
06/11/2006, 12h34
borisd

Je pense que ton erreur c'est de ne pas savoir ce que tu fais.
Ton problème est d'écrire un algorithme qui trie un tableau d'entiers en ne le parcourant qu'une fois, pas de copier bêtement du code trouvé sur internet, code qui ne sert même pas à ce que tu dois faire.
Nous t'avons donné toutes les références nécessaires et même du code pour t'aider. Maintenant, tu peux faire l'effort de réfléchir 10 minutes sur nos réponses.

J'ai enfin trouvé la solution et sa fonctionne très bien, voici le code :

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
 
Constante MAX = 6
Tableau entier iTab taille MAX
<* = { 0,1,1,2,0,0 } *>
Variable entiere iI,iJ,iTemp
 
Début du traitement
Initialisation
Compter avec iI de 0 à MAX - 1
 
   Afficher iTab[iI] Tab
 
Fin de compter
 
   Fin de ligne
   Fin de ligne
 
   /* Boucle : */
   Initialisation
   Compter avec iI de 0 à MAX - 1
 
      /* Boucle : */
      Initialisation
      Compter avec iJ de iI+1 à MAX - 1
 
	 /* Alternative : */
	 Si iTab[iJ] < iTab[iI] Alors
 
	    iTemp <- iTab[iI]
	    iTab[iI] <- iTab[iJ]
	    iTab[iJ] <- iTemp
 
	 Fin de si
 
      Fin de compter
 
      Afficher iTab[iI] Tab
 
   Fin de compter
 
Attente
 
Fin du traitement

Merci pour vos commentaires, c'est vraiment sympa pour votre aide.

Michael.

06/11/2006, 16h59
Hephaistos007
Je n'arrive pas à voir quel algorithme de tri tu as utilisé. :? Ca ressemble vaguement à un tri bulle mais ca n'en est pas un.

Surtout, tu ne respectes pas du tout les consignes de ton exercice :
- Ecrire un algorithme qui range les éléments de ce tableau dans un deuxième tableau ...
- Le premier tableau ne sera parcouru qu'une seule fois
06/11/2006, 19h33
IDE

Suite

Oui tu as raison, mais j'avais envie de changer car de toute maniere je fais les exercices pour moi, je pense que c'est pas plus mal de n'utiliser qu'un seul tableau pour faire le tri, enfin bon je suis loin d'etre un expert en programmation, je ne suis qu'un novice, mais bon mon résonnement fonctionne, passez une très bonne soirée.

Michael