[supersaibal]
Originariamente inviato da jaromil
Se il sudoku vi ha stufato, risolvete e postate questi rompicapi.
Il gioco è da ritenersi concluso con successo quando io passerò questa merda di esame...
Data una sequenza di n numeri interi x1, ..., xn diciamo che (xi, xi+1) sono una coppia di numeri consecutivi se xi + 1 = xi+1. Ad esempio nella sequenza (12, 13, 24, 25, 26, 35, 67) ci sono 3 coppie di numeri consecutivi: (12, 13), (24, 25) e (25, 26). Scrivere un algoritmo ricorsivo che utilizzi la tecnica divide-et-impera e che calcoli quante coppie di numeri consecutivi sono contenute in una sequenza di n numeri interi x1, ..., xn ricevuta in input. Valutare in ordine di grandezza il costo computazionale dell’algoritmo proposto. Vietato usare il Master Theorem !!!
----------------------
Scrivere un algoritmo che ordina n numeri compresi tra 0 e n 2 − 1 in tempo O(n). Suggerimento: combinare counting-sort e radix-sort. Motivare le risposte.
----------------------
E possibile ordinare un Heap in tempo o(n log n) ?
---------------------
Sia G = (V, E) un grafo non orientato pesato tale che per ogni e ∈ E : W(e) ∈ {1, 2, 3, 4}. Sia s ∈ V . Scrivere un algoritmo che calcoli l’albero dei cammini minimi da s a tutti gli altri nodi in tempo O(|V | + |E|). Suggerimento: Applicare BFS su un grafo G
---------------------
Sia V un vettore di n numeri interi positivi. Definiamo i seguenti due problemi computazionali: min-gap (differenza minima): determinare una coppia di indici 1 ≤ i < j ≤ n tali per cui per ogni 1 ≤ k < h ≤ n : |V [i] − V [j]| ≤ |V [k] − V [h]|. max-gap (differenza massima): determinare una coppia di indici 1 ≤ i < j ≤ n tali per cui per ogni 1 ≤ k < h ≤ n : |V [i] − V [j]| ≥ |V [k] − V [h]|.
---------------------
e ne ho altri bellissimi... [/supersaibal]