skuska 20.6

Uživatelský avatar
ivo_svk
Matfyz(ák|ačka) level I
Příspěvky: 48
Registrován: 27. 3. 2006 17:03
Typ studia: Informatika Bc.
Bydliště: Hvězda 1/58
Kontaktovat uživatele:

skuska 20.6

Příspěvek od ivo_svk »

priklad 1: nedestruktivny prienik dvoch BVS

priklad 2: mame nejaky pocet minci (<36000 tusim) a mame ich ocislovane od 1.... a funkciu ktora rozhodne ktora z dvoch minci ma vyssiu hodnotu
je zakazane volat tuto funkciu pokial z predchadzajucich vysledkov je dany vztah 2 minci (napr. pokial 1<2 a 2<3 tak sa nesmie funkcia zavolat na mince 1 a 3)
vytup: vypisat po skupinach mince rovnakych hodnot zoradene od najnizsej po najvyssiu
a vypisat pocet zavolani funkcie ohodnocujucej mince
kesy
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 4. 2. 2006 23:19
Typ studia: Informatika Bc.
Bydliště: Nitra
Kontaktovat uživatele:

Příspěvek od kesy »

no a ako sa to malo spravne riesit? ani srnka netusi. ja som to narval do jednej velkej matice (ano, viem, pamatovo zlozite jak svina) a tam som poodvodzoval vztahy ze co sa vyhodnoti a co je v danom okamihu zrejme. bolo k tomu este potrebne pouzit nejaku frontu, ale to je technicky detail. vysledkom bol pomerne kratky algoritmus so 4 vnorenymi cyklami - realne vsak tu zlozitost odhadujem na O(n^2) v priemernom pripade. vyhodou tohto postupu je, ze vam to hned vypluje, ktore mince su rovnako hodnotne - proste si zratate hodnoty v danom riadku matice.
co som pocul, tak skoro fsetci to riesili pomocou stromu (co mne ani nenapadlo :) ) a vyzera to byt hodne efektivnejsie... takze ponaucenie znie: rozmyslajte nad postupom;)
A gun is not a weapon, Marge, it's a tool. Like a butcher knife or a harpoon, or... or an alligator.
Homer Simpson
Uživatelský avatar
ivo_svk
Matfyz(ák|ačka) level I
Příspěvky: 48
Registrován: 27. 3. 2006 17:03
Typ studia: Informatika Bc.
Bydliště: Hvězda 1/58
Kontaktovat uživatele:

Příspěvek od ivo_svk »

optimalne riesenie je vo hviezdach, ale dam svoj postup...v podstate som to riesil podobne ako je quiksort, zobral som jeden prvok s tym porovnal vsetky ostatne, dotal som tri skupiny:
-mensie, s tymi som robil opat to iste (cize rekurzia)
-rovnake, jedna skupina minci
-vacsia - opat sa k slovu prihlasila rekurzia
takze prinajhorsom by to malo mat zlozitost O(n^2) ale ked sa zadari mohlo by to klasnut na O(nlogn)
Jenda
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 20. 1. 2006 22:14

Příspěvek od Jenda »

ja jsem si udelal lin seznam skupin a kazdy prvek jsem porovnal nejdriv s prostredni skupinou z tohodle seznamu,kdyz byl mensi,tak s prostredni skupinou prvni pulky a tak dal... proste pulenim intervalu.kdyz jsem nasel stejnej prvek,jen jsem ho pridal do skupiny,jinak jsem tam vlozil novou skupinu...
takze zarazeni jednoho prvku log(n),prvku n,slozitost by mohla byt n*log(n)
Pavel
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 20. 6. 2006 16:28
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od Pavel »

Nevim, co resite...
proste prvni priklad je sazka do loterie...
a druhy stacilo pouzit libovolny tridici algoritmus (s vyjimkou tech zbytecne zdlouhavych - bublinkoveho trideni, trideni vyberem ci zatridovanim)
vkladani do binarniho stromu bylo take ponekud neprakticke...
... tedy trideni haldou, mergesort, quicksort (s drobnou upravou) jsou vitezne alternativy... krom toho stacily napsat v poli... takze fakt trivka...
Uživatelský avatar
ivo_svk
Matfyz(ák|ačka) level I
Příspěvky: 48
Registrován: 27. 3. 2006 17:03
Typ studia: Informatika Bc.
Bydliště: Hvězda 1/58
Kontaktovat uživatele:

Příspěvek od ivo_svk »

to pavel:
- triedenie do stromu sa mi prilis neprakticke nezda (navyse jeden znamy to tak urobil a teraz na ustnej mu Kryl povedal ze to ma pekne)
- ak si si nevsimol moje riesenie je vpodstate quiksort, trosku modifikovany
- co je najdolezitejsie funkcia bola tranzitivna, a teda pri pouziti akehokolvek triedenia musis davat pozor kolkokrat zavolas hodnotiacu funkciu a ci nevies vysledok uz predchadzajuceho priebehu vypoctu...aspon pri mergesorte sa mi zda ze tato podmienka nemusi byt splnena a viem najst protipriklad, ale mozno sa mylim :oops:
- navyse je podla mna dost dobre ked sa na fore objavia okrem samotnych zneni pisomiek aj (aspon) naznaky rieseni, podla mna to celkom pomaha pri priprave na skusky
Jakobicek
Matfyz(ák|ačka) level II
Příspěvky: 53
Registrován: 26. 1. 2006 12:42
Typ studia: Informatika Bc.
Bydliště: Praha... VSE/MATFYZ

Příspěvek od Jakobicek »

BVS ma tu neprijemnou vlastnost ze tam neni uplne jasne co s prvky se stejnym klicem... tedy shodnymi prvky... lze je samozrejme vkladat do spojaku.. v tomto pripade zrejme lepsi varianta nez je vkladat na jednu stranu BVS.. pak neni uplne zjevne jak na konci zrekonstruovat ty shodne mince
jinak co se tyce efektivity neni BVS zla volba
slozitost: n*Insert ...prumerne insert o(log(n))
n*(odeberMIN)... taktez o(log(n))//ani se nedelaji zadna porovnani jen primo doleva dokud to jde//
suma sumarum o(nlog(n))
v nejhorsim pripade je to o(n*n) kdyz nam to vadi maji BVS dalsi vyhodu
muzeme je vyvazovat a implementace vyvazovani sice neni uplne snadna ale pohodlne proveditelna
co se tyce merge sortu tak se mi nezda ze by se pri nem opakovali nektere porovnvaci operace... jsou tam vzdy dve monotonni posloupnosti ktere se budou prochazet.. ale je trochu neprijemne ze budeme potrebovat pomocne pole...
jako vzdy existuje vice cest k uspechu a nelze vzdy rici ktera bude lepsi...
mnohdy algoritmy s mizernou teoretickou slozitosti davaji silne nafrak tem ktere maji slozitost podle teorie mnohem lepsi...
Minsk will lead with blade and sword Boo will sort out the details
esk
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 10. 6. 2006 12:06

Příspěvek od esk »

mergesort byl uplne v pohode. teda udelala jsem mergesort spojaku, pokud se pri porovnavani prislo na naky stejny mince, tak jsem jedny z nich zapojila ty zbyly jakoby do retizku, takze se to pak porovnavalo jako celek. tudiz nebyl problem, ze by nastalo naky zbytecny porovnani - pri tom slejvani se pak porovnavaj vzdycky dva prvky, ktery jsou kazdej z jiny uz setrideny casti.
pouziti stromu bylo taky v poradku...
kryl je hodnej a opravdu vam da dost casu na rozmysleni teorie (vezme si dalsiho...)
n-droo
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 8. 6. 2006 21:50

Příspěvek od n-droo »

Já jsem to řešil pomocí binárního stromu. V každém uzlu jsem měl zasobník, kam jsem si vkládal mince stejné hodnoty. Insertoval jsem vsechny mince a pak vytiskl uzly inorder (rekurzí). Je to jednoduché, nemusíte se o nic starat a máte jistotu, že se vám nic nebude porovnávat dvakrát. Jsou zde metody, které nepochybně jsou jak časově, tak prostorově efektivnější než ta moje; já ale myslím, že Kryl k tomu moc nepřihlíží. U ústní zkoušky se mě na žádná vylepšení neptal. Kritizoval jen použití dvojitých pointerů a já mu dal za pravdu, že je to neslušné; ale stejně si myslím, že se mu to skrytě líbilo.
Byl celkem spokojený a tak mi dal jen otázku na virtuální metody:
- co je to VMT
- kolik jich je
- kde sidli odkaz na VMT
- jak se ten odkaz vytvori
a odesel jsem s vybornou.
Kamilko
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 21. 6. 2006 17:38

Příspěvek od Kamilko »

Pisu tu vacsinou ludia, ktory skusku dali. Preto teraz napisem nieco aj ja. Nedal som to. :roll: Smola, no. Prisiel som na ustnu, sadol som si, pozrel do jedenho prikladu, povedal, ze zle. Druhy priklad, algoritmus chapal, napisal som to ako strom, presne ako n-droo, ale nachapal mojim poznamkam, tak ma musel poslat "do dabla", na slimaku, tam. Proste nestaci, ze viete, ako na to, treba to pekne napisat, v reci, ktorej asi nerozumiem. Mozno v cinstine, najlepsie mandarinskej. Potom to asi bude dobre. V kazdom pripade svet nepada, ale je to blbe. Je mily, naozaj, situacie nehrotil, povedal, ze to chcel inak, ze tomu nerozumiem a rozlucil sa. Pre velky uspech opakujem. Co uz, no.
Nakresli mi ovecku.
Odpovědět

Zpět na „PRM044 Programování I“