Discussion :

[katrena99]

Bonjour,

ENONCE :
Ecrire un algorithme intitulé K_ppe permettant de déterminer et d'afficher le kième plus petit élément (1<=k<=N), s'il existe, et l'indice de sa première apparition dans un tableau T de N entiers (N>=2)
Remarques:
Si le Kième plus petit élément ne figure pas dans le tableau T, le programme doit afficher le message suivant : "pas de Kième plus petit élément"

Exemple :
Soit le tableau T suivant :
valeurs 5 2 7 2 1 4 9 4 1 1
indices 1 2 3 4 5 6 7 8 9 10

Pour k=3

Le 3ième plus petit élément est 4 et l'indice de sa première apparition est 6.

Fin ENONCE (lol)

La solution que j'ai proposée est de faire un 2e tableau dans lequel les valeurs sont triées dans un ordre croissant. Ensuite une boucle se charge de trouver le kième plus petit élément sachant qu'un même élément peut avoir une fréquence supérieure à 1. Enfin voir si le kième plus petit terme existe en comparant un compteur à N.

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
 
program k_ppe;
uses wincrt;
const n=6;
var
t:array[1..n] of integer;
t2:array[1..n] of integer;
i,e,f:integer; {e : valeur enregistrée pour le tri croissant du tableau}
r,s,k,x:integer;
begin
for i:=1 to n do
       begin
         write('valeur numero ', i,' du tableau : ');
         read(t[i]);
       end;
for i:=1 to n do {ici on affiche le tableau avec les valeurs choisies du l'utilisateur}
begin
write(T[i]:6);
T2[i] :=T[i]; {initialisation du 2e tableau, consacré au tri}
end;
 
 
{ici commence le tri croissant du tableau}
for i:=2 to n do 
begin	
	for f:=n downto i do
		begin {condition de changement de deux cases}
		if T2[f-1]>T2[f] then
			begin {changer T[8]  et T[9] de places si T[8] >T[9]}
			e:=T2[f];
			T2[f]:=T2[f-1];
			T2[f-1]:=e;
			end;
		end;
end;
writeln(chr(13),'tableau trié : ');
for i:=1 to n do
	write(T2[i]:6);
writeln(chr(13),' k? ' );
readln(k);
s:=k;
for r:=1 to s do
	begin
	if T2[r] = T2[r+1] then
	S:=S+1;
	end;
X:=T2[s];
if s<=n then
	begin
	writeln('Le ',k,'ième plus petit élément est  ',X);
	end
	else
	writeln('pas de ',k,'ième plus petit élément');
 
 
 
end.

Comme vous l'avez remarqué, je n'ai pas réussi à trouver l'indice du kième plus petit élément. J'ai consacré le 1er tableau à cela. Il me semble qu'il existe une commande qui renverrait l'indice de X, je ne la connais pas.
Merci d'avoir lu.

[Loceka]

en fait, il y'a deux sortes de boucles :
- les boucles inconditionnelles (for) où il n'est généralement pas conseillé de modifier la borne supérieure, et certainement pas le compteur.
- les boucles conditionnelles (while) qui servent à continuer tant que la condition n'est pas établie.

Ici, le mieux pour toi serait de faire une boucle conditionnelle :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
min := T2[1];
nb := 1;
indice := 2;
while ( (nb <> k) and (indice <= length(T2)) ) do
begin
   (* tu augmentes ton compteur si et seulement si ton tableau présente une valeur nouvelle (donc forcément supérieure, vu qu'il est trié). *)
   if (min < T2[indice]) then
   begin
      nb = nb + 1;
      min := T2[indice];
   end;
   indice := indice + 1; (* incrémentation de l'indice de parcours du tableau *)
end;

Bon, il se peut que mon programme ne soit pas syntaxiquement correct, ça fait longtemps que je n'ai pas touché au Pascal.

Pour ce qui est de trouver l'indice de "X" dans le premier tableau, il faut que tu le parcours à la main (avec un while encore), il n'y a pas de fonction toute faite pour ça.

Normalement ça devrait t'aider.

[ALT]

Attention : l'élément cherché peut se trouver plusieurs fois dans le tableau.
Je suppose qu'il faut donc trouver les indices de toutes les occurrences de cet élément. Un parcours complet du tableau est donc nécessaire.

[katrena99]

Bonsoir à tous,

Je n'ai pas compris vos réponses. Cher Loceka, je n'ai pas réussi à comprendre l'objectif de ton code. S'il te plaît explique-moi en langage naturel ton objectif.
Merci de m'avoir consacré autant de temps et excuse-moi de t'en faire perdre encore plus mais, c'est pour la bonnne cause
Je vous remercie.

[Loceka]

@ ALT : d'après son exemple, il s'arrêtait à la première valeur trouvée (ce qui simplifie la tâche quand même).

@ katrena99 :

Tu as testé déjà ?
Enfin, bon, en langage naturel, ça donne :

- Tu as un tableau T2 d'éléments ordonnés (ordre croissant).
- Si tu avances dans T2, soit tu as T[i] = T[i+1] (1), soit tu as T[i] < T[i+1] (2).
- dans le cas (1) tu dois donc passer à la valeur suivante de T2, sans augmenter ton compteur d'éléments (nb dans mon algo)
- dans le cas (2) tu as trouvé un élément différent du précédent. Tu augmente donc nb.
- Quand nb = k, ça veut dire que tu as trouvé ton k_ième plus petit élément. Inutile d'aller plus loin dans ce cas, tu sors de la boucle. De plus la valeur de ce k_ième élément est rangée dans min.

A toi de faire la suite...

[katrena99]

ah d'accord mais j'y suis déjà arrivé dés le premier post, je crois même que mon raisonnement est plus simple bien que ce soit presque la même chose.

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
s:=k; {si les valeurs ne pouvaient pas se repeter il suffirait de prendre T2[k]} 
{mais ce n'est pas le cas alors, je prends un compteur s que j'initialise 
à la valeur de k, }
{(je ne peux pas prendre k lui-même car j'ai besoin de sa valeur 
initiale pour l'affichage plus bas) }
for r:=1 to s do {je prends un autre compteur r de 1 à s}
	begin
	if T2[r] = T2[r+1] then {celle-ci est la condition d'incrémentation de s}
	S:=S+1;
	end;
X:=T2[s];
if s<=n then
	begin
	writeln('Le ',k,'ième plus petit élément est  ',X);
	end
	else
	writeln('pas de ',k,'ième plus petit élément');

Là où j'étais bloqué, c'est pour trouver l'indice de la première apparition du kième plus petit élément. Je pensais qu'il y avait une commande pour renvoyer l'indice d'une valeur dans un tableau. Maintenant, je suis arrivé à tout résoudre peut-être grâce à cette remarque :

Pour ce qui est de trouver l'indice de "X" dans le premier tableau, il faut que tu le parcours à la main (avec un while encore), il n'y a pas de fonction toute faite pour ça.

. X est remplacé par Y dans mon nouveau code que voici :

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
program k_ppe;
uses wincrt;
const n=6;
var
t:array[1..n] of integer;
t2:array[1..n] of integer;
i,e,f:integer; {e : valeur enregistrée pour le tri croissant du tableau}
r,s,k,x,y:integer;
begin
for i:=1 to n do
       begin
         write('valeur numero ', i,' du tableau : ');
         read(t[i]);
       end;
for i:=1 to n do {ici on affiche le tableau avec les valeurs choisies du l'utilisateur}
begin
write(T[i]:6);
T2[i] :=T[i]; {initialisation du 2e tableau, consacré au tri}
end;
 
 
{ici commence le tri croissant du tableau}
for i:=2 to n do 
begin	
	for f:=n downto i do
		begin {condition de changement de deux cases}
		if T2[f-1]>T2[f] then
			begin {changer T[8]  et T[9] de places si T[8] >T[9]}
			e:=T2[f];
			T2[f]:=T2[f-1];
			T2[f-1]:=e;
			end;
		end;
end;
writeln(chr(13),'tableau trié : ');
for i:=1 to n do
	write(T2[i]:6);
writeln(chr(13),' k? ' );
readln(k);
s:=k;
for r:=1 to s do
	begin
	if T2[r] = T2[r+1] then
	S:=S+1;
	end;
x:=T2[s];
y:=0;
repeat
y:=y+1
until
T[y]=x;
if s<=n then
	begin
	writeln('Le ',k,'ième plus petit élément est  ',X, ' et l''indice de sa première apparition est ',y,'.');
	end
	else
	writeln('pas de ',k,'ième plus petit élément');
 
end.

[katrena99]

Bonsoir,
bien que résolu je dois réouvrir le sujet parce qu'apparemment il y a une meilleure solution beaucoup plus courte dont je n'ai aucune idée. Je rappelle l'énoncé:
Ecrire un algorithme intitulé K_ppe permettant de déterminer et d'afficher le kième plus petit élément (1<=k<=N), s'il existe, et l'indice de sa première apparition dans un tableau T de N entiers (N>=2)
Remarques:
Si le Kième plus petit élément ne figure pas dans le tableau T, le programme doit afficher le message suivant : "pas de Kième plus petit élément"

Exemple :
Soit le tableau T suivant :
valeurs 5 2 7 2 1 4 9 4 1 1
indices 1 2 3 4 5 6 7 8 9 10

Pour k=3

Le 3ième plus petit élément est 4 et l'indice de sa première apparition est 6.
________________________________________________________________
Je veux dire qu'il y a une solution sans trier le tableau (je ne la connais pas bien sûr), j'ai pensé à prendre le minimum du tableau, pour k=1 : kppe=minimum, pour k=2 on trouve l'élément qui lui succède directement dans l'ordre croissant et ainsi de suite... exemple : supposons que le minimum du tableau est 3 (il n'y a aucun problème pour le trouver ), on fait une boucle qui vérifie s'il y a 4 dans le tableau, si oui on enlève 1 à k sinon on vérifie s'il y a un 5 ect...
Aidez-moi à trouver un algorithme traduisant ce raisonnement s'il vous plaît, en espérant que l'idée, bien que très mal exprimée, soit passée.

Merci à tous.

[ALT]

Évidemment, tu pourrais passer par une fonction/procédure récursive ou assimilée, mais je ne suis pas sûr que ça améliorerait la lisibilité du code.

je pense à un truc du style :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
i=1
pluspetit=-32768
 
fonction chercher_le_plus_petit_supérieur_à(pp:integer)
begin
    Ah ben tiens je te laisse imaginer la méthode, là. D'ailleurs ce n'est pas compliqué. 8-)
end;
 
répéter
    pluspetit=chercher_le_plus_petit_supérieur_à(pluspetit)
    i=i+1
jusqu'à ce que i=k ou fin de tableau sans résultat

Il y en a sûrement d'autres !

Bon courage

[katrena99]

merci mais je n'ai pas encore fait ça au lycée (fonctions et procédures)...
n'y aurait-il pas un autre moyen avec seulement les boucles itératives et conditionnelles ?

[ALT]

Si.

Il te suffit de tout laisser dans la boucle.
La fonction n'avait d'autre but que d'alléger le code de la boucle.

Donc la méthode reste la même, il te faut simplement imaginer comment rechercher le plus petit élément supérieur au précédent-plus-petit.

C'est, a priori, le plus difficile.
Mais avec un poil de logique & de méthode, tu devrais t'en sortir.

[katrena99]

Grâce à vous et à un peu de musique classique,j'y suis arrivé. Je ne sais pas si c'est meilleur qu'en triant le tableau... Ca fait longtemps et l'enseignante n'a pas encore corrigé l'exercice et je ne pense pas qu'elle aille le faire. J'aimerais quand-même que vous vérifiez que je ne pouvais pas faire 'considérablement' plus court.
Alors voici le nouveau code : (entre temps j'ai appris While en esperant que ça va vous faire sourire)
**plus bas, j'ai écrit la partie la plus interessante seule

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
70
program k_ppe;
uses wincrt;
var t:array[1..100] of integer;
i,e,f,j,c,k,kppe,min,n:integer; cf:boolean;
begin
repeat
writeln('nombre de valeurs du tableau ? (entre 2 et 100) ');
readln(n);
until n in [2..100];
for i:=1 to n do
       begin
       write('valeur numero ', i,' du tableau : ');
       read(t[i]);
       end;
for i:=1 to n do
	begin
	write(T[i]:6);
	end;
 
 
{l'intervalle de définition de k}
CF:=true;	
f:=1;
for i:=1 to n do
	begin
	CF:=true;
	for j:=1 to i-1 do		{vérification que l'élément n'a pas encore été traité}
	if T[j]=T[i] then CF:=false;
	if CF then
		begin
		for c:=(i+1) to n do
			begin
			if T[i]=T[c] then f:=f+1;
			end;
		end;
end;
{k est donc dans [1..n-f]}	
 
 
 
 
writeln('k?');
readln(k);
if k in [1..(n-f)] then
	begin
		{on cherche le minimum}
		min:=T[1];
		for j:=1 to n do
			begin
			if T[j] < min then min:=T[j];
			end;
		kppe:=min-1;
		for j:=1 to k do
			repeat
				kppe:=kppe+1;
				i:=0;
				repeat
				i:=i+1;
				until ((T[i]=kppe) or (i=n));
			until T[i]=kppe;
		{indice}
		i:=1;
		while T[i]<>kppe do
		i:=i+1;  
		writeln('Le ',k,'ième plus petit élément est  ',kppe, ' et l''indice de sa première apparition est ',i,'.');
	end
	else
	writeln('pas de ',k,'ième plus petit élément');
 
end.

Code :

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

1
2
3
4
5
6
7
8
9
kppe:=min-1;
		for j:=1 to k do
			repeat
				kppe:=kppe+1;
				i:=0;
				repeat
				i:=i+1;
				until ((T[i]=kppe) or (i=n));
			until T[i]=kppe;

++