zkouska 25.6.09

Mohl by nekdo hodit reseni k prikladum ?

plosíííííím :)

1. priklad v haskellu byl

   Najdete k zadane konecne posloupnosti cisel nejdelsi rostouci vybranou posloupnost.

Mohl by nekdo sem hodit ukazkove reseni :)
Ja nevim jak to udelat v haskellu :(

Tu podposloupnost jsem nějak zbastlil, ale rozhodně neručím za správnost. Je to v n^2, návod http://ksvi.mff.cuni.cz/~kryl/Avyuka/20 ... jrostv.txt
Mě by zase zajímalo, jak jste dělali tu haldu, stačil by popis algoritmu, alespoň zhruba. Mně tam v té haldě pořád nějak vadila absence oboustranných pointerů v prologu při probublávání :-)

{-vytvori z posloupnosti x dvojici (x, pomocne_pole), kde pomocne_pole obsahuje na indexu odpovidajicim indexu do x jak dlouha je nejdelsi posloupnost zacinajici na tomto indexu. Tvori se ODZADU, posledni prvek ma pomocne_pole[posledni_index] = 1 a pak jdeme na predposledni atd.-}

vytvor_pomocne :: [Int] -> ([Int],[Int])
vytvor_pomocne posl = vytvor_pomocne2 (otoc posl) ([],[])

otoc :: [a] -> [a]
otoc posl = otoc2 posl []

otoc2 :: [a] -> [a] -> [a]
otoc2 [] posl = posl
otoc2 (x:xs) aku = otoc2 xs (x:aku)

{-ve skutecnosti procujeme s akumulatorem, ve kterem se odzadu akumuluji prvky (puvodni_posloupnost, pomocne_pole). Akumulator proto, ze tento prozatimni vysledek potrebujeme k vypoctu zbyleho pomocneho pole a zaroven se nam to akumulovanim zase otoci do puvodniho poradi posloupnosti-}
vytvor_pomocne2 :: [Int] -> ([Int],[Int]) -> ([Int],[Int])
vytvor_pomocne2 [] dvojice_seznamu = dvojice_seznamu	--puvodni posloupnost prazdna, vydame akumulator
vytvor_pomocne2 (x:xs) ([],[]) = vytvor_pomocne2 xs ([x],[1])	--akumulator prazdny, nastartujeme vypocet pridanim posledniho prvku
vytvor_pomocne2 (x:xs) (cast_posl, pom) =vytvor_pomocne2 xs (x:cast_posl, max_cislo:pom)where max_cislo = najdi_max_cislo x cast_posl pom 1
{-najde maximalni cislo, ktere muzeme na tento index do pomocneho pole soupnout. Je to velikost o jedna vetsi, nez ma prvek, ktery muze byt v posloupnosti za nim, a to ta nejvetsi velikost-}
najdi_max_cislo x [] [] prozatimni_max = prozatimni_max
najdi_max_cislo x (prvek: cast_posl) (cislo: cisla) prozatimni_max| ((cislo + 1) > prozatimni_max) && (prvek > x) = najdi_max_cislo x cast_posl cisla (cislo + 1)| otherwise = najdi_max_cislo x cast_posl cisla prozatimni_max

--obycejne vybrani maxima ze seznamu	
najdi_max_delku :: [Int] -> Int
najdi_max_delku [] = 0
najdi_max_delku (x:xs) = najdi_max_delku2 x xs

najdi_max_delku2 :: Int -> [Int] -> Int
najdi_max_delku2 x [] = x
najdi_max_delku2 prozatim_max (x:xs)| prozatim_max < x = najdi_max_delku2 x xs| otherwise = najdi_max_delku2 prozatim_max xs

--vypise prvky podposloupnosti, zacne prvkem, na kterem zacina podposloupnost delky druheho parametru	
vypis :: ([Int],[Int]) -> Int -> [Int]
vypis ([],[]) _ = []
vypis ((x:xs), (p:poms)) delka| p == delka = (x: (vypis (xs,poms) (delka - 1)))|otherwise = vypis (xs,poms) delka

--hlavni funkce
najdi_podposloupnost :: [Int] -> [Int]
najdi_podposloupnost posl =vypis (posloupnost, pom_pole_z_dvojice_seznamu) (najdi_max_delku pom_pole_z_dvojice_seznamu)where (posloupnost, pom_pole_z_dvojice_seznamu) = vytvor_pomocne posl