Presentazione/Problema

di
BossWolf
il
3 risposte
B
BossWolf
Pochi posts
Iscritto da
giu, 2012
Messaggi:
4

Presentazione/Problema

Ciao a tutti, mi presento sono nuovo del forum e studio informatica all'univeristà.

Cercando su internet ho trovato questo luogo dove si parla di questa materia affascinante ma anche molto complessa (almeno per me ) ,vorrei chiedervi se potevo ricevere aiuto nella risoluzione di alcuni problemi con i quali mi sto scontrando ultimante e non riesco a venirne a capo.
Grazie!

3 Risposte

  • B
    BossWolf
    Pochi posts
    Iscritto da
    giu, 2012
    Messaggi:
    4

    Re: Presentazione/Problema

    Sto cercando di capire come risolvere questo problema, ma non riesco proprio a venirne a capo, qualcuno sa indirizzarmi ad una possibile soluzione?
    Grazie!

    Sia M una matrice k×n di valori distinti. I valori in ognuna delle k righe sono ordinati in modo crescente. Progettare un algoritmo che, presa M, restituisca il valore mediano della matrice, ovvero il valore che, se si considerano in ordine tutti gli elementi della matrice dal piu piccolo al piu grande si trova in posizione ?(nk)/2? + 1.
    L'algoritmo deve avere complessita temporale O(nk log k) e deve usare memoria ausiliaria O(k).
  • Toki
    Toki
    Moderatore
    Iscritto da
    gen, 2001
    Messaggi:
    3887

    Re: Presentazione/Problema

    Ciao e benvenuto.
    Ti anticipo che come da regolamento non svolgiamo esercizi o forniamo soluzioni pronte.
    Quello che facciamo è aiutati a trovare le soluzioni per i problemi quale può essere il tuo algoritmo, aiutarti a migliorare quanto hai fatto, ecc. insomma no pappa pronta.

    Detto questo se come immagino si tratti di C++, fammi un cenno cos'ì sposto il 3d nella sezione più appropriata
  • B
    BossWolf
    Pochi posts
    Iscritto da
    giu, 2012
    Messaggi:
    4

    Re: Presentazione/Problema

    Ciao, in realtà quando ho postato l'esercizio non avevo intenzione di chiedere la pappa pronta ma solo un'idea su una possibile soluzione. Comunque se ho dato questa impressione mi scuso per l'accaduto. Tornando all'esercizio in realtà non devo scrivere il codice completo ma solo lo pseudocodice (che naturalmente poi verrà usato per essere implementato in qualsiasi linguaggio). L'obiettivo consisterebbe nel capire quale struttura dati utilizzare, nella quale inserire gli elementi della matrice messi tutti in ordine crescente (costo O(nk) ) e ricercare/scorrere (costo O(logk) )questa struttura dati fino al punto in cui è stato calcolato il mediano. L'idea che mi era venuta in menta era quella di crearmi tanti array per quante erano le righe della matrice e ricopiarci dentro tutti i valori, poi scorrere in verticale gli array partendo dalla prima posizione e ricercare il minimo tra i valori. Fatto ciò incremento di una posizione l'array dal quale ho selezionato il minimo e ripeto la ricerca del minimo con la stessa procedura. Ripeto il tutto per le volte necessarie calcolate per il mediano.
    Con questa idea credo però di sforare la complessità, e soprattutto avrei poi difficoltà ad immaginarmi il codice per scorrere gli array in modo verticale.

    Grazie
Devi accedere o registrarti per scrivere nel forum
3 risposte