PDA

Visualizza la versione completa : Chi ha voglia di giocare con gli algoritmi?


jaromil
06-02-2006, 14:57
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...

bakuryu
06-02-2006, 14:59
:sonno:

IbraSoft
06-02-2006, 15:01
ma che lingua stai parlando? :confused:

Metallica
06-02-2006, 15:02
io ODIO, con tutta l'anima, gli algoritmi ricorsivi.
Iterativo SEMPRE :D

darkkik
06-02-2006, 15:07
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...

http://www.emotioneric.com/horror.jpg

scimmietta1
06-02-2006, 15:11
m vai a giocare intangenziale va :rollo:

jamesev
06-02-2006, 15:15
visto il successone che ne dici di non postare gli altri? :D

GattoBastardo
06-02-2006, 15:18
Originariamente inviato da Metallica
io ODIO, con tutta l'anima, gli algoritmi ricorsivi.
Iterativo SEMPRE :D

ma questo e' perche' sei un niubbo :D

jaromil
06-02-2006, 15:20
dico che è una buona idea.
anche quella della tangenziale.

PinguinoGoloso
06-02-2006, 15:46
Fondamenti di Informatica I/II :D ?

Loading