Info:

twitter

Ultimi commenti: Comment feed

Tags:

Sponsor:

Archivio 2018:

Giu Mag Feb Gen

Archivio 2017:

Dic Nov Ott Mag Apr Mar Feb Gen

Archivio 2016:

Dic Nov Ott Ago Mag Mar Feb Gen

Archivio 2015:

Nov Ott Set Mar Gen

Archivio 2014:

Dic Nov Ott Set Lug Giu Mag Apr Gen

Archivio 2013:

Dic Nov Set Ago Lug Giu Mag Apr Feb Gen

Archivio 2012:

Dic Nov Ott Set Ago Giu Mag Apr Mar Feb Gen

Archivio 2011:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2010:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2009:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2008:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2007:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2006:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

LunedìQuìz–serie 2012 #2

Implementare la seguente funzione:

bool SumExists(int[] data, int sum)

che restituisce true se esistono due elementi nell’array data la cui somma è sum e definirne la complessita in notazione O.

-quack

P.S. titolo leggermente alterato per arginare l’eventuale ondata spam

Potrebbero interessarti anche:
Commenti (11):
1. crossbower
martedì 21 febbraio 2012 alle 6:07 PM - Opera 11.51 Linux
   

Salve a tutti!

 Come promesso ho installato monodevelop per scrivere la soluzione in c#, in modo da essere compilabile (si spera :D) anche con visual studio.

La soluzione si trova all'url: http://pastebin.com/Hczs2mYw (scusate eventuali grossolanità ma é la prima volta che uso c#)

La complessità computazionale dell'algoritmo é O(n), ma l'algoritmo richiede un array ordinato di interi.

Considerando quest'ultima cosa, partendo da un array disordinato bisogna aggiungere la complessità dell'algoritmo per il riordino. Usando quicksort tutto l'ambaradam diventa O(nlogn). 

   
2. Paperino
martedì 21 febbraio 2012 alle 6:43 PM - chrome 17.0.963.56 Windows 8
   

@crossbower:

bene. Però:

1. si può fare di meglio con una soluzione iterativa anziché ricorsiva (con un array ordinato)

2. con un array disordinato (sciusciato direbbero dalla mie parti) si può fare di meglio usando memoria aggiuntiva (hint troppo grosso)

   
3. crossbower
martedì 21 febbraio 2012 alle 7:08 PM - Opera 11.51 Linux
   

Umm, il secondo hint mi sta già facendo venire qualche idea...

Una curiosità (non necessariamente attinente): in genere preferisco scrivere algoritmi usando ricorsioni, ottimizzabili attraverso tail-call optimization.

La funzione-soluzione che ho dato sopra é ottimizzabile, perche' l'ultima operazione eseguita prima del return é una chiamata a se stessa.

Il compilatore c/c++ mi espanderebbe quindi il codice ricorsivo che ho scritto sopra come algoritmo iterativo.

Dalla tua esperienza ti é mai capitato di fare la stessa cosa in c#? Sai se il compilatore c# supporta tail-call optimizations?

   
4. Giuseppe
martedì 21 febbraio 2012 alle 8:00 PM - IE 9.0 Windows 7
   

buttata giù in 5 minuti, non l'ho provata.

bool SumExist(int[] data, int sum)
{
    QuickSort(data);  
    for (int i = 0; i < data.Length / 2; i++)  
    {
        int search = sum-data[i];   
        bool b = BinarySearch(data,search);   
        if (b) return true;  
    }
    return false; 
}

Dovrebbe essere O(n log(n)) (quicksort oppure n [mezzi] volte binary search)

   
5. crossbower
martedì 21 febbraio 2012 alle 10:03 PM - Opera 11.51 Linux
   

@Paperino:

2. con un array disordinato (sciusciato direbbero dalla mie parti) si può fare di meglio usando memoria aggiuntiva (hint troppo grosso)

Ed array sciusciato sia!

Dato che, a parte miglioramenti costanti (cioe' che lasciano sempre il codice a O(n*log n), anche se un po' piu' efficiente), non sono a migliorare asintoticamente il codice (a partire da un array disordinato), ho preso alla lettera il tuo consiglio...

Voila', un algoritmo O(n) che non richiede array ordinati: http://pastebin.com/ePcwjvuR

Hehe, di memoria in effetti ne usa un po' di piu' (in teoria 128Mb), pero' é O(n)

Gli interi nell'array devono essere interi signed di 32bit.

Utilizzo due serie di slots (uno slot é in sostanza una maschera di bit) per tenere traccia dei numeri positivi e negativi che ho gia' incontrato. In questo modo basta scorrere l'input array una sola volta.

Una piccola considerazione: ho detto che "in teoria" occupa 128Mb di memoria dinamica durante l'esecuzione, ma i sistemi operativi moderni utilizzano tecniche di "copy on write" e altre ottimizzazioni varie, quindi sono sicuro che gli si possa far occupare una quantità di memoria minima con le dovute ottimizzazioni.

Commenti?

   
6. crossbower
martedì 21 febbraio 2012 alle 10:04 PM - Opera 11.51 Linux
   

PS: Naturalmente non userei questo algoritmo in un programma normale...

   
7. Beppe
giovedì 23 febbraio 2012 alle 4:46 PM - IE 9.0 Windows 7
   

@Giuseppe

Non puoi fare una ricerca fino a data.Length / 2, cosi' facendo presupponi che l'addendo minore della somma sia necessariamente nella prima meta' dell'array

   
8. Paperino
giovedì 23 febbraio 2012 alle 4:57 PM - chrome 17.0.963.56 Windows 7
   

Dalla tua esperienza ti é mai capitato di fare la stessa cosa in c#? Sai se il compilatore c# supporta tail-call optimizations?

Non ti so dire, ma a parità di complessità algoritmica per esperienza preferisco soluzioni più "leggibili" e, purissima opinione personale, nel caso in questione la soluzione ricorsiva mi sembra più complicata da leggere.

Soluzioni

array ordinato: http://pastebin.com/Lit8Xqr3

array non ordinato: http://pastebin.com/FtdwNXsa

@crossbower, la soluzione proposta è buona per array molto grandi. Quella proposta è preferibile per array più "normali"

   
9. Giuseppe
giovedì 23 febbraio 2012 alle 8:48 PM - IE 9.0 Windows 7
   

@ Beppe
la ricerca infatti è fatta su tutto l'array. Gli elementi da cercare invece sono presi solo dalla prima metà (tanto la somma è commutativa)

   
10. Supercazzola
mercoledì 15 maggio 2013 alle 9:06 AM - firefox 22.0 Windows 8
   

Zio can che spammata.

   
11. Paperino
mercoledì 15 maggio 2013 alle 6:27 PM - chrome 26.0.1410.64 Windows 8
   

Maledizione, però vista la rarità.....

   
Lascia un commento:
Commento: (clicca su questo link per gli smiley supportati; regole di ingaggio per i commenti)
(opzionale, per il Gravatar)