OliForum Matematico

Data una sequenza di numeri reali A e un numero reale x, scrivere un algoritmo che stampi tutte le coppie di numeri la cui somma è x. Questo algoritmo deve avere complessità O(nlogn).

Grazie a chiunque mi aiuterà!

Saluti.

Cosa intendi per algoritmo?
Tu sai che qualunque algoritmo non può maneggiare numeri reali e insiemi generici...

MindFlyer ha scritto:Cosa intendi per algoritmo?
Tu sai che qualunque algoritmo non può maneggiare numeri reali e insiemi generici...

Ok! Allora scrivere un programma in pseudocodice, oppure in Java o in C.

Saluti!

Se i numeri sono interi e A è finito, un'idea potrebbe essere questa.

Metti A in ordine crescente in tempo O(nlogn), ad esempio con il quicksort.
Per ogni y in A tale che 2y<=x (O(n)), cerca in A l'elemento z=x-y (in O(logn) con la ricerca binaria). Se lo trovi aggiungi la coppia (y,z) all'output.

etxyz ha scritto:Ok! Allora scrivere un programma in pseudocodice, oppure in Java o in C.

Non ci siamo capiti, parlavo di algoritmi in generale, quindi in particolare di algoritmi in pseudocodice, java o c...
Comunque spero di averti risposto.