Problème: Calcul du kième plus petit élément d'un tableau

bonjour, s.v.p j'essaie de résoudre un problème pascal
g arrive a écrire une solution qui me parait raisonnable en faisant une exécution manuelle mais l'exécution sur machine donne un résultat erroné.
énonce:
soit un tableau t de n entiers positifs(on suppose que n >=2), on veut déterminer et afficher le k-ieme plus petit élément (1<=k<=n) et l'indice de sa première apparition dans le tableau.
exemple: soit le tableau t suivant:
5 2 7 2 1 4 9 4 1 1

le programme doit afficher: le 3ème élément minimal est 4 et l'indice de sa première apparition est 6.

voila le code que g trouvé:

Code:

program ex2;
uses wincrt;
type tab=array[1..100] of integer;
var n,nb,pos,k:integer;
t:tab;
procedure saisie(var n,k :integer; var t:tab);
var i :integer;
begin
repeat
write('n='); readln(n);
until n>=2;
writeln('**** les elements de t ****');
repeat
for i:=1 to n do readln(t[i]);
until t[i]>=0;
 
write('k='); readln(k);
end;

function cherche_min(t:tab; n:integer):integer;
var
min,i:integer;
begin
min:=1;
for i:=1 to n do
begin
if (t[i] <> -1)then
min:=i;
end;
cherche_min:=min;
end;

procedure recherche( t:tab; n,k:integer;var nb,pos:integer);
var m,j:integer;
begin
nb:=0;
repeat
m:=cherche_min(t,n);
for j:=1 to n do if t[j]=t[m] then t[j] :=-1;
nb:=nb+1;
until (nb=k)
 pos:=m;
 end;
 procedure affiche(nb,pos:integer; t:tab);
 begin
 if nb=k then
 writeln('le', k,'eme plus petie element est: ',t[pos], ' et la positionde sa premiere apparitionest ', pos)
 else writeln('pas de ',k,' eme element minimal');
  end;
begin
saisie(n,k,t);
recherche(t,n,k,nb,pos);
affiche(nb,pos,t);
end.

Bien que l'idée de ton algorithme soit intuitive et logique, ce dernier n'est pas correct. Il ne traite pas tous les cas. Il devrait te retourner de faux résultats dans certains cas.

Soit par exemple un tableau t=[1, 1, 1], alors quel est le 2ème minimum?!

Par contre, l'idée la plus simple (mais pas nécessairement la meilleure!) consiste à trier le tableau dans l'ordre croissant en éliminant les doublons. Soit "tR" ce tableau, et "m" le nombre d'éléments qu'il contient. Alors, le "k"-ième minimum de "t" est "tR[k]" avec "k<=m".

Cette méthode est sûre, mais pour les doués d'algorithmique et surtout ceux qui cherchent non pas "un algorithme qui marche" mais plutôt le "meilleur algorithme" en terme de complexité, il existe d'autres méthodes plus élaborées et plus dures que les deux propositions qu'on a citées jusqu'à maintenant.

A toi de creuser d'avantage d'abord...

Par contre, l'idée la plus simple (mais pas nécessairement la
meilleure!) consiste à trier le tableau dans l'ordre croissant en
éliminant les doublons. Soit "tR" ce tableau, et "m" le nombre
d'éléments qu'il contient. Alors, le "k"-ième minimum de "t" est
"tR[k]" avec "k<=m".

il faut plutôt stocker le numéro de l'indice

"sasouki":

si ton tableau "t" est rempli de "-1" par la procédure "recherche"... alors, la fonction "cherche_min" que va-t-elle retourner ??

L'algorithme proposé par "Sasouki", même s'il fonctionne pour quelques cas, il doit échouer pour dans d'autres. Mais c'est une bonne tentative.

Tu es encore intéressé par la solution? il faut participer dans la discussion au moins !!!

sasouki a écrit:bonjour, svp j'essaie de résoudre un problème pascal
g arrive a écrire une solution qui me parait raisonnable en faisant une exécution manuelle mais l'exécution sur machine donne un résultat erroné.
enonce:
soit un tableau t de n entiers positifs(on suppose que n >=2), on veut determiner et afficher le k ieme plus petit element (1<=k<=n) et l'indice de sa premiere apparition dans le tableau.
exemple: soit le tableau t suivant:
5 2 7 2 1 4 9 4 1 1

le programme doit afficher: le 3 ème élément minimal est 4 et l'indice de sa première apparition est 6.

voila le code que g trouvé:

Code:

program ex2;
uses wincrt;
type tab=array[1..100] of integer;
var n,nb,pos,k:integer;
t:tab;
procedure saisie(var n,k :integer; var t:tab);
var i :integer;
begin
repeat
write('n='); readln(n);
until n>=2;
writeln('**** les elements de t ****');
repeat
for i:=1 to n do readln(t[i]);
until t[i]>=0;
 
write('k='); readln(k);
end;

function cherche_min(t:tab; n:integer):integer;
var
min,i:integer;
begin
min:=1;
for i:=1 to n do
begin
if (t[i] <> -1)then
min:=i;
end;
cherche_min:=min;
end;

procedure recherche( t:tab; n,k:integer;var nb,pos:integer);
var m,j:integer;
begin
nb:=0;
repeat
m:=cherche_min(t,n);
for j:=1 to n do if t[j]=t[m] then t[j] :=-1;
nb:=nb+1;
until (nb=k)
 pos:=m;
 end;
 procedure affiche(nb,pos:integer; t:tab);
 begin
 if nb=k then
 writeln('le', k,'eme plus petie element est: ',t[pos], ' et la positionde sa premiere apparitionest ', pos)
 else writeln('pas de ',k,' eme element minimal');
  end;
begin
saisie(n,k,t);
recherche(t,n,k,nb,pos);
affiche(nb,pos,t);
end.

c'est juste comme solution, mais répondant au commentaire de Mr Nabil que je remercie, on peut remplir le tableau T par des éléments distincts pour remédier a ce problème et avoir une solution optimale.

la fonction cherche_min cherche les minimum autre que -1 (a condition que t[i] soit différent de -1)

salut, pardon si g pas participe a la discussion mais c juste paske j'avais pas de connexion, mr nabil merci pour la réponse g déjà pensé a ca mais c pas la methode demandee, et puisque le programme ne doit pas prendre en consideration le cas des doublons alors g supposé moi que les elements du tableaux sont positifs et remplacer tous les elements egaux au minimum par -1, et la fonction cherche_min quand elle cherche le min:
function cherche_min(t:tab; n:integer):integer;
var
min,i:integer;
begin
min:=1;
for i:=1 to n do
begin
if (t[i] -1)then
min:=i;
end;
cherche_min:=min;
end;
anisi pour l'exemple que g donné et a la premiere iteration la fonction doit trouver le min est 1 a la position 5
par la suite le prog remplacera les 1 par -1
et dans la deuxieme iteration la fonction doit retourner le min 2 a la position 2 et ainsi de suite jusk'a ce ke le nb=k,
le probleme c ke le programme ne remplace que le premier 1 par -1 et ne modifie pas les autres de telle sorte que la fonction kan elle cherche le min pour la deuxieme fois elle va retouner le 2 eme 1 du tableau et la troisieme iteratio elle retournera le 3 eme 1 dans le tableau et ainsi de suite
je sais en plus que g pas traite ts les cas des tableaux, j'essaierai encore une fois

"si ton tableau "t" est rempli de "-1" par la procédure "recherche"... alors, la fonction "cherche_min" que va-t-elle retourner ??"
g pas de reponse exacte mais il faut dans ce cas prevoire 2 resultats pour la fonction selon le cas, si ts les elements du tab sont des -1 dans ce cas elle retournera par exemple une valeur negative et kan la fonction retourne cette valeur la boucle repeter s'arrete
et enfin pour afficher le resultat on teste si nb=k alors on affiche le k ieme element minimal, sinon afficher que il n'existe pas de k ieme element dans t
c logique non?

sasouki a écrit:"si ton tableau "t" est rempli de "-1" par la procédure "recherche"... alors, la fonction "cherche_min" que va-t-elle retourner ??"
g pas de reponse exacte mais il faut dans ce cas prevoire 2 resultats pour la fonction selon le cas, si ts les elements du tab sont des -1 dans ce cas elle retournera par exemple une valeur negative et kan la fonction retourne cette valeur la boucle repeter s'arrete
et enfin pour afficher le resultat on teste si nb=k alors on affiche le k ieme element minimal, sinon afficher que il n'existe pas de k ieme element dans t
c logique non?

Effectivement.

Est-ce que vous êtes encore intéressés par la correction de cet excellent exercice ?

bien sure que oui, en fait g une idee de ce que je dois faire mais l'execution sur machine ca ne marche tjrs pas

c'est un exercice dur... mais faisable. Il existe plusieurs versions simplifiées de ce problèmes sur Internet.