Pagina 1 di 2 1 2 ultimoultimo
Visualizzazione dei risultati da 1 a 10 su 11

Discussione: [C] Ricerca del k-esimo elemento minimo

  1. #1
    Utente di HTML.it
    Registrato dal
    Nov 2014
    Messaggi
    54

    [C] Ricerca del k-esimo elemento minimo

    Ciao a tutti!
    devo realizzare un proramma che dao in input un array di n elementi, mi restituisca il k-esimo elemento minimo (dove k è un intero dato in input).

    Io purtroppo non riesco a realizzarlo, ho avuto un idea (cercare k-1 volte l'elemento minimo e sostituirlo all'ultimo elemento dell' array per poi escluderlo decrementando n in modo da trovare il k-esimo minimo appena il ciclo è finito) ma mi sembra un metodo troppo dispendioso e complicato/inutile...

    voi avete altre idee?

  2. #2
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,540
    Applichi k volte il ciclo interno di un bubblesort, l'elemento in posizione k-1 sarà quello che cerchi.
    Utilizzi un heap e fai k estrazioni. Per questo puoi cercare in internet heapsort.

    In sostanza ordini parzialmente l'array.
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  3. #3
    Utente di HTML.it
    Registrato dal
    Nov 2014
    Messaggi
    54
    mi sono dimenticato di precisare: l'algoritmo non deve ordinare l'array... serve qualcosa con complessità non troppo elevata (ordinare l'array è troppo scontato, già ci avevo pensato xD)

  4. #4
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,540
    Non ti ho detto di ordinare l'array, ma ordinarlo parzialmente. Per il k-esimo elemento ti bastano al più k iterazioni del ciclo interno di un bubblesort (meno se non avvengono scambi <=> array già ordinato). Oppure k estrazioni da un heap. Puoi costruire un heap da un array in spazio costante.
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  5. #5
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,540
    Se inoltre n è la lunghezza, se k>n/2 allora puoi invertire il problema e cercare l'(n-k)esimo massimo.
    Ciò riduce il numero di cicli necessari.
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  6. #6
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,540
    Intendevo questo
    codice:
    #include <iostream>
    using namespace std;
    
    
    void swap(int &a, int &b) {
        int t = a;
        a = b;
        b = t;
    }
    
    
    int main() {
        int n;
        cout << "Dimensione: ";
        cin >> n;
        
        int *a = new int[n];
        for(int i = 0; i < n; ++i) {
            cout << i+1 << ") ";
            cin >> a[i];
        }
        
        int k;
        cout << endl
            << "Cercare il minimo numero: ";
        cin >> k;
        bool scambio = true;
        for(int k1 = 0; (k1 < k) && scambio; ++k1) {
            scambio = false;
            for(int i = n-1; i > k1; --i) {
                if(a[i] < a[i-1]) {
                    swap(a[i], a[i-1]);
                    scambio = true;
                }
            }
        }
        cout << a[k-1] << endl;
        return 0;
    }
    Ultima modifica di Scara95; 27-12-2014 a 01:17
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  7. #7
    Utente di HTML.it
    Registrato dal
    Nov 2014
    Messaggi
    54
    devo un attimino documentarmi...ti farò sapere in questo topic se ci son riuscito

  8. #8
    Utente di HTML.it
    Registrato dal
    Nov 2014
    Messaggi
    54
    il problema è che se ci sono elementi che si ripetono, l'algoritmo falla xD

  9. #9
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,540
    Usa un heap e controlla se l'estrazione successiva è uguale a quella precedente.
    Puoi prendere in input gli elementi e poi costruire l'heap oppure costruire l'heap mentre prendi in input gli elementi.
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  10. #10
    ragazzi io ho provato a farlo con un bubble sort parziale ma non mi viene bene potete darmi una mano?

    void bubblesort(int a1[],int n1,int k1)
    {
    int t;
    int i=0,j;

    for(i=0;i<n1;i++)
    {
    for(j=0;j<k1;j++)
    {
    if(a1[j]>a1[j+1])
    {
    t=a1[j];
    a1[j]=a1[j+1];
    a1[j+1]=t;
    }
    }
    }
    }

    ho anche provato a fare un bubble sort inverso xchè mi sembrava più semplice ma niente
    qualcuno mi può illuminare?

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2018 vBulletin Solutions, Inc. All rights reserved.