zkouska 25.6.09
Re: zkouska 25.6.09
1. priklad v haskellu byl
Mohl by nekdo sem hodit ukazkove reseni
Ja nevim jak to udelat v haskellu
Kód: Vybrat vše
Najdete k zadane konecne posloupnosti cisel nejdelsi rostouci vybranou posloupnost.
Ja nevim jak to udelat v haskellu
-
- Matfyz(ák|ačka) level I
- Příspěvky: 14
- Registrován: 13. 1. 2007 20:48
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: zkouska 25.6.09
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í
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í
Kód: Vybrat vše
{-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