Programování - diskusní klub na Lopuchu

Registrace nového uživatele

Návod

Kluby

Archív Lopuchu

Lopuch.cz

Nudou jsi opuch?
Navštiv Lopuch!

Lopuch.cz

	Klub Programování [ŽP: neomezená] (kategorie Programování) moderuje tvx.
	Archiv

Nastavení klubu

Nastavení práv

Homepage

Anketa

[ 857 ]

<Novější <<<Nejnovější Nejstarší>>> Starší>


	31.10.2006 08:03	570
	Dobře hledá! Díky.


	King Born to be king - ... 31.10.2006 01:46	569
	kdo hleda, najde http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements


	King Born to be king - ... 31.10.2006 01:44	568
	ad 1) postavis haldu - N, odebrani vrcholu - okamzite, reorganizace haldy - logN, tedy neni to MN ale N + MlogN ad 2) quicksort v kazde fazi rozdeli pole na dve casti - menis nez pivot a vetsi nez pivot, kdyz vetsich nez pivotu bude alespon 20, nemusis se vbec zabyvat tou druhou skupinou ad 3) NM neni dobra slozitost, linearne jde najit i prostredni prvek, myslim ze by slo ten algoritmus upravit tak, aby nehledal prostredni, ale K-ty (tedy 20), vsech top 20 pak dostanes rovnou v prubehu algoritmu


	31.10.2006 01:31	567
	Výběr nejlepších prvkůdiky za takovou rychlou reakci. 1) Nemám to teď přesně srovnané postavením haldy dostanu nejlepší prvek do kořene, odeberu ho a co dál? Totéž znovu M-krát? čiže náročnost asi O(M*N) 2) Tomu moc nerozumím, jak poznám ty, co mě nezajímají? 3) hmm tomu zatím taky nerozumím, uvidíme co najdeš, ještě bych rozuměl lineárnímu hledání maxima to je O(N) a mohu to provést M-krát To co jsem psal já by mělo mít náročnost do O(N lg2(M)), ale je v tom posuvání těch p-M-2 prvků nějakým memcpy či čím, což není úplně levné, ale zas tak hrozné to pro malé M asi není, nedokážu to posoudit


	King Born to be king - ... 31.10.2006 01:12	566
	moznostico me ted jen napadlo: 1) postav si z toho haldu a odeber 20x vrchol - da se O(N) 2) modifikuj quicksort tak, aby se nesnazil setridit ty zaznamy co te nezajimaji (tady je dulezity vyber pivota - kdyz jich vemes 5 nahodne a vyberes druhy, mohlo by to vypadat slusne) - tady si netroufam na slozitost 3) pouzij neco jako je linearni algoritmus na hledani medianu (zkusim jeste najit)


	31.10.2006 00:39	565
	Výběr nejlepších prvkůAhoj. Mám pole A o N(=400) prvcích různých hodnot(struktura s položkou VALUE typu integer), resp. pointerů na ně. Chci vybrat M (20) nejlepších (podle VALUE) a uložit do cílového pole B. Potřebuju co nejefektivnější algoritmus, protože to budu dělat velmi často. Zatím nejlepší, co mě napadlo je. Napadá vás něco efektivnějšího: 1. Vezmu prvních M prvků pole A a vložím je do B 2. Setřídím B a zapamatuju si hodnotu nejmenšího prvku Vmin 3. Pro ostatní prvky A, tj. i=M..N-1 dělej if a[i].Value>Vmin { půlením intervalu najdi pozici p v poli B, kam prvek patří posuň prvky p..M-1 o jeden doprava na pozici p dej a[i] nastav Vmin=B[M-1] }


	King Born to be king - ... 29.10.2006 18:08	564
	tady hrozne zalezi na tom jakej mas problem, jinak na backtracking existuje spoustu figlu na vylepseni (backjumping, backmarking apod)... holt se musis trochu rozepsat - je jedno v cem to pises, ale neni jedno o jaky problem jde...


	29.10.2006 17:55	563
	AlexDolu jo, ale nahoru je to zajimavejsi... Ja nejsem v programovani moc zbehlej, tak bych nejaky ten napad uvital...


	29.10.2006 12:01	562
	To se snad da delat jednoduchou rekurzi, ne?


	29.10.2006 09:25	561
	Myslim backtracing, to je takova ta metoda nachazeni reseni maticovych a jinych her, dela se to pomoci stromu.


	Kdokoliv Nevidím důvod dělat cokoliv bezdůvodně. - http://kkl2401.wz.cz 29.10.2006 08:09	560
	Aha, to zase koukam neumim cist.


	29.10.2006 01:30	559
	Mozna ale mysli backtracing od slova backtrace a ne backtrack. Ale ja do javy nevidim, takze nevim.


	Kdokoliv Nevidím důvod dělat cokoliv bezdůvodně. - http://kkl2401.wz.cz 28.10.2006 23:08	558
	Backtracking se snad ve vsech nefunkcionalnich jazycich programuje stejne, ne? V tech funkcionalnich teda taky, ale casto je to jenom na jednom radku.


	28.10.2006 14:48	557
	Neprogramoval nekdo z vas nekdy v jave backtracing? Nechce se mi to vymejslet od zakladu...


	7.10.2006 08:48	554
	ja bych zvolil QNX nebo i ten Linux se da.

[ 857 ]

<Novější <<<Nejnovější Nejstarší>>> Starší>


(c) 2001-2011 Lopuch.cz Kontakt