# zkouska 25.6.09

<{ForumPost(poster="Anonymous", timestamp=2009-06-28 21:21:32)}>
Mohl by nekdo hodit reseni k prikladum ?
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2009-07-01 20:13:59)}>
plosíííííím :)
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2009-07-05 11:19:07)}>
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 :(
<{/ForumPost}>

<{ForumPost(poster="shrill", timestamp=2009-07-07 03:07:26)}>
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](http://ksvi.mff.cuni.cz/~kryl/Avyuka/20089/prikl044/Nejrostv.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


<{/ForumPost}>