OliForum Matematico

bh3u4m ha scritto:E' comunque un algoritmo $ O (N^2) $, se non mi sbaglio (ma due cicli for uno dentro l'altro lo dovrebbero essere).

riguardando l'algoritmo sembra anche a me così. quindi lo zaino non c'entra nulla...

Ah, finalmente ho capito cosa deve fare l'algoritmo!
Però la versione di Pyv va cambiata in vari punti...
In pratica, scorre le tartarughe dalla più in alto alla più in basso, tenendosi il peso minimo delle pile di ogni lunghezza , e questo funziona!!
Ottimo lavoro. :D

un po' come lo zaino ...

l'unico "consiglio" che mi sento di proporre è quello di scrivere algoritmi in pseudo-codice, restando lontani dalle differenze implementative dei vari linguaggi di programmazione. cosa ne dite?

sei sicuro che l'albero come l'hai costruito tu nel caso induttivo sia ancora un albero di decisione?

Di sicuro è vero il viceversa, cioè che un albero di decisione è un albero binario, quindi ho trattato il caso più generale...

Beh sì, un albero di decisione è binario, quindi quello che hai ...

sei sicuro che l'albero come l'hai costruito tu nel caso induttivo sia ancora un albero di decisione? ci sono dei vincoli forti, sugli alberi di decisione per l'ordinamento... non credo che tu possa trattarli come alberi binari qualunque! la mia idea era un'altra, comunque aspetto che qualcun altro ...

interi, numeri che entrano in una word... stiamo passando dal generico a delle particolari sequenze! anche se non sapevo che degli interi si potessero ordinare in n log log n...

comunque, la mia domanda resta la stessa... nessuno si cimenta con questi benedetti alberi di decisione?

Ne approfitto anche io per intavolare una discussione, spero interessante... magari non troppo, in quanto credo sia oggetto di studio di numerosi corsi di Informatica. Però, discuterne e confrontarsi fa sempre bene!

data una generica sequenza di n numeri a_1, a_2, ..., a_n , dimostrare che in ...

Ne approfitto anche io per intavolare una discussione, spero interessante... magari non troppo, in quanto credo sia oggetto di studio di numerosi corsi di Informatica. Però, discuterne e confrontarsi fa sempre bene!

data una generica sequenza di n numeri a_1, a_2, ..., a_n , dimostrare che in media ...

un algoritmo greedy, per essere applicato, richiede (come diceva Mind Flyer) la dimostrazione che la scelta dell'ottimo locale ad ogni iterazione garantisca il raggiungimento della soluzione ottima globale (come ad esempio si può fare per costruire l'albero di copertura minimo di un grafo). credo ...