Forum » Loža » Izziv : Srednja plastenka
Izziv : Srednja plastenka
NejcSSD ::
Imamo pribiližno 100 plastenk v katerih je različna količina vode (v vsaki je drugačna količina). Plastenke so take, da ne vidimo koliko je v njih vode, recimo take:
Radi bi poiskali tisto plastenko v kateri je toliko vode, da je v pol plastenkah manj vode, v pol pa več vode (ok, če je plastenk skupaj sodo (recimo 100), poiščemo tako, da je v 49 ih manj , v 50 pa več vode).
Edini pripomoček, ki ga imate na voljo, je nagibna tehtnica brez uteži
Kdo zna sestaviti postopek, ki s kar se da malo tehtanji pride do rešitve.
Plastenka
Radi bi poiskali tisto plastenko v kateri je toliko vode, da je v pol plastenkah manj vode, v pol pa več vode (ok, če je plastenk skupaj sodo (recimo 100), poiščemo tako, da je v 49 ih manj , v 50 pa več vode).
Edini pripomoček, ki ga imate na voljo, je nagibna tehtnica brez uteži
Tehtnica
Kdo zna sestaviti postopek, ki s kar se da malo tehtanji pride do rešitve.
jernejl ::
Recimo quickselect, ki deluje na enakem principu kot quicksort.
Ima časovno zahtevnost O(n), če imaš smolo z izbiro pivota pa O(n^2).
Quickselect @ Wikipedia
Ima časovno zahtevnost O(n), če imaš smolo z izbiro pivota pa O(n^2).
Quickselect @ Wikipedia
technolog ::
Jernejl, obstaja tud algoritem, ki ima O(n) worst-case.
http://cs.stackexchange.com/questions/1...
p.s.: Rekurzija ni algoritem.
http://cs.stackexchange.com/questions/1...
p.s.: Rekurzija ni algoritem.
Zgodovina sprememb…
- spremenil: technolog ()
jernejl ::
Jernejl, obstaja tud algoritem, ki ima O(n) worst-case.
Te optimizacije so zanimive, saj podobne zadeve obstajajo tudi pri algoritmih sortiranja (ali pa alternative, npr. heapsort, mergesort).
Samo boljša worst-case časovna zahtevnost še ne pomeni, da bo v povprečju tisti algoritem hitrejši.
Tukaj je ponavadi trade-off med tem, koliko časa si "on average" pripravljen izgubiti, da bi izboljšal worst-case scenarij.
V zgornjem primeru bi zato raje izbral preprost quickselect, ker je vseeno večja verjetnost, da bom s takim postopkom zaključil hitreje kot če bi se lotil optimizacije določanja pivota (overhead).
Če bi imel nekaj smole, bi pa lahko bil quickselect tudi počasnejši.
Zgodovina sprememb…
- spremenil: jernejl ()
Meizu ::
Jernejl, obstaja tud algoritem, ki ima O(n) worst-case.
http://cs.stackexchange.com/questions/1...
p.s.: Rekurzija ni algoritem.
Postopek ni vedno enako algoritmu. Pa ravno nekdo je gor objavu video demšarja, ki z rekurzijo lepo pokaže "postopek" rekurzivnega izločanja različno polnih plastenk.
technolog ::
Algoritem je postopek, ki se konča. Edina razlika.
1. Demšar sortira, tukaj pa iščemo mediano, kar je lažji problem.
2, Vsak rekurziven algoritem se da napisat iterativno.
1. Demšar sortira, tukaj pa iščemo mediano, kar je lažji problem.
2, Vsak rekurziven algoritem se da napisat iterativno.
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | enojno povezan seznam -izpis nazajOddelek: Programiranje | 3271 (2811) | Randomness |
| » | Identifikacija s pomočjo glasu je težavnaOddelek: Novice / Zasebnost | 4330 (2117) | poweroff |
| » | It means business (strani: 1 2 3 4 5 6 7 8 )Oddelek: Znanost in tehnologija | 27249 (13248) | Thomas |
| » | [ Teorija ] "premature optimization is the root of all evil"Oddelek: Programiranje | 1791 (1040) | BlueRunner |
| » | C++ vs. C (strani: 1 2 )Oddelek: Programiranje | 6594 (5585) | rokpok |