PDA

Visualizza la versione completa : [C] Funzione che restituisce elemento più grande dell'array


Skyfall
04-11-2020, 16:30
Sviluppare una function C che, dati come parametri di input un array di int, il suo size eun int k, determina e restituisce come parametro di output il k-imo pi`u grande elementodell’array (N.B.: l’array non deve essere ordinato).
ho gia visto una discussione aperta ma non specificaba che l'array non deve essere ordinato.
Questo sotto è un esercizio simile che chiedeva il secondo massimo. Diciamo che ho saltato il problema azzerando la casella in cui compariva il primo massimo. Vedendo questo di esercizio ho capito che in realtà ci deve per forza essere un'altra soluzione che non preveda azzerare il valore del vettore in quel punto. Vorrei qualche dritta su come poter modificare il codice o se bisogna riscriverlo.
int main()
{
int array[50],i,n,max;
printf("inserisci grandezza array:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("inserisci elemento %d:",i+1);
scanf("%d",&array[i]);
}
max=secondo_massimo(array,n);
printf("il secondo massimo e' %d",max);


return 0;
}
int secondo_massimo(int array[50],int n)
{
int i,indice_max,max=0,max_due=0;
max=array[0];
max_due=array[1];
indice_max=0;
for(i=1;i<n;i++)
{
if(max<array[i])
{
indice_max=i;


}
}
array[indice_max]=0;
for(i=0;i<n;i++)
{
if( max_due<array[i])
max_due=array[i];


}
return max_due;
}

Scara95
06-11-2020, 11:14
Un primo metodo è quello che hai già citato, assegnare il valore minimo possibile alle caselle che contengono i massimi e calcolare il massimo k volte.
Un secondo metodo è effettuare un ordinamento parziale. Ad esempio applicare solo k volte il ciclo interno di un bubble sort, ciò porta i k massimi a posizionarsi all'inizio (o alla fine) dell'array. Oppure costruire una max heap.
In alternativa puoi mantenere un array ordinato di k elementi in cui inserisci gli elementi dell'array originario ad uno ad uno dimenticandoti quelli che strasbordano.
Tutte le soluzioni (assumendo che k << n) sono dominate da n.
La prima che è quella più simile al codice che hai proposto:


#include <stdio.h>
#include <limits.h>


int massimo(int array[50],int n,int k);


int main(void) {
int array[50],i,n,max,k;
printf("inserisci grandezza array:");
scanf("%d",&n);
for(i=0; i<n; i++) {
printf("inserisci elemento %d:",i+1);
scanf("%d",&array[i]);
}
printf("inserisci k:");
scanf("%d",&k);
max=massimo(array,n,k);
printf("il %d massimo e' %d",k,max);
return 0;
}


int massimo(int array[50],int n,int k) {
int j, i, max, max_i;
for(j = 0; j < k; ++j) {
max = INT_MIN;
for(i = 0; i < n; ++i) {
if(array[i] > max) {
max = array[i];
max_i = i;
}
}
array[max_i] = INT_MIN;
}
return max;
}

Skyfall
07-11-2020, 13:35
grazie effettivamente non ci avevo pensato...Ma a questo punto mi chiedo c'è un modo per trovare il k-esimo massimo senza azzerarlo? intendo con un bubble sort non è sempre un tipo di ordinamento ? Grazie ancora per la tua disponibilità.

Scara95
07-11-2020, 15:00
Il bubblesort è un ordinamento, ma non ordini l'array in questo caso, a meno che k e n non coincidano, lo ordini solo parzialmente, quel tanto che ti è neccessario. Puoi vedere qui un esempio: https://ideone.com/IZXRdJ

Skyfall
07-11-2020, 18:43
Grazie ancora, in questo modo posso finalmente riuscire a finire il programma.

Loading