//di seguito ricopio il testo del primo topic
//adeso spiego//primo topic
Salve ragazzi, tra poco parteciperò alla competizione regionale di informatica e potrei avere bisogno di un algoritmo di ricerca con complessità logaritmica O(log N), cercando in internet ho trovato la binary_search, molto veloce da scrivere e pratica, ma essa non ritorna un valore ma solo un booleano che mi dice se il valore è presente o no, esiste qualche funzione standard C++ o standard C con complessità logaritmica (anche una binary_search) che mi ritorni la posizione dell'elemento trovato, di solito lavoro con int *, quindi non ho bisogno di iteratori.
Se non c'è dovrei scriverla al momento, ma in quel genere di competizioni il tempo è fondamentale, quindi se riesco a trovare la "pappa pronta" sarebbe meglio, come con sort in C++, dato che di problemi ce ne saranno di più grossi e non voglio perdere tempo a scrivere algoritmi.
Grazie mille, spero che esista una soluzione
Le competizioni di informatica sono strutturate in modo che il partecipante non venga "premiato" perchè sa scrivere bene gli algoritmi, altrimenti uno si impara token per token gli algoritmi di ordinamento, etc ed è apposto, ma nell'abilità nel capire se per risolvere un dato problema si può o meno, in che modo e magari con qualche modifica, applicare una serie di algoritmi conosciuti al programmatore.
Come è scritto e consigliato ESPRESSAMENTE nella guida preparativa fornita dall'ORGANIZZATORE dei giochi di informatica in italia:
http://www.olimpiadi-informatica.it/ -> Documentazione -> Syllabus e materiale didattico -> Guida alle selezioni territoriali -> http://81.208.32.83:8080/ioi/files/Guida%20selezioni%20territoriali.pdf
e più precisamente cito i passaggi:
Per questo consigliano di usare le funzioni sort e qsort, che sono nient'altro che "pappa pronta" ma durante una competizione se si ha a disposizione un algoritmo con complessità computazionale O( N log N) e più semplice da implementare di sicuro non si va a perdere tempo con BubbleSort o Inserzione.//guida ufficiale
Dovendo quindi usare un ordinamento durante un problema di gara una soluzione potrebbe essere quella di utilizzare un algoritmo scritto “al volo”; questo però comporterebbe principalmente tre tipi di problemi:
• perdita di tempo per la scrittura dell’algoritmo (anche il più semplice degli algoritmi di ordinamento richiede qualche minuto per essere implementato)
• semplicità dell’algoritmo implementato: probabilmente si ricadrebbe sull’algoritmo bubblesort, che è molto semplice da implementare correttamente, ma ha delle prestazioni non buone, di tipo O ( N^2 )
• possibilità di commettere degli errori: anche un algoritmo semplice come il bubble-sort può comunque essere soggetto a errori di implementazione, dove un algoritmo come il quicksort ha sicuramente buone probabilità di essere scritto male, soprattutto in un contesto come quello delle gare dove si ha poco tempo a disposizione e si è sotto tensione Utilizzare invece le funzioni di libreria permette di evitare questi problemi, al solo costo di impararne il funzionamento.
Per le stesse ragioni, quando si effettua una ricerca, la guida invita ad usare binary_search o bsearch
Quello che però trovo poco utile è che essi ritornano solo un booleano, come detto nel primo topic e chiedo a voi, perchè google non mi ha aiutato, se esiste una funzione simile a binary_search che non abbia una complessità computazionale troppo elevata e che segua la linea di principio proposta dalla guida ossia che IL TEMPO E' PREZIOSO, ci sono infatti 3 quesiti a difficoltà crescente in sole 3 ore, basta sbagliare un carattere e si possono perdere decide di minuti di debug per trovare l'errore.//guida ufficiale riguardo a binary_search
Pur essendo un algoritmo apparentemente semplice, l’implementazione durante una gara potrebbe dare dei problemi: anche in questo caso, se usiamo il C o il C++, ci vengono in soccorso le librerie standard con l’algoritmo bsearch nel caso nel C e con binary_search nel caso del C++.
Se ahimè non esiste chiedo a voi consiglio per scrivere unendo le forze, perchè da solo è difficilino, un'algoritmo che, in accordo col pensiero dell'autore della guida, sia semplice e veloce da implementare.
Spero di essere compreso adesso e sinceramente mi ha dato molto fastidio essere trattato così nel primo topic dato che non mi sembra di aver chiesto tutte queste eresie come sono stato accusato.
Grazie della collaborazione.
Rispondi quotando
