FP Cvičení 5

From Marek Běhálek Wiki
Revision as of 10:48, 19 October 2021 by Fai0013 (talk | contribs) (Created page with "* Ve většině případů, pokud je sudé číslo zapsáno jako součet dvou prvočísel, jedno z nich je velmi malé. Budeme hledat případy které tohle pravidlo nesplňuj...")
Jump to navigation Jump to search

Generátory seznamů

Implementujte následující funkce s využitím genrátoru seznamu:

  • Vytvořte funkci, která vygeneruje seznam všech lichých čísel v daném intervalu.
oddList :: Int -> Int -> [Int]
*Main> oddList 1 10   
[1,3,5,7,9]
oddList :: Int -> Int -> [Int]
oddList a b = [ x |x<-[a..b], odd x]
Try it!
  • Vztvořte funkci která odstraní všechna velká písmena z řetězce.
removeAllUpper :: String -> String
*Main> removeAllUpper "ABCabcABC"
"abc"
import Data.Char

removeAllUpper :: String -> String
removeAllUpper xs = [ x |x<-xs, not (isUpper x)]
Try it!
  • Vytvořte funkci která spočítá sjednocení a průnik dvou množin.
union :: Eq a => [a] -> [a] -> [a]
intersection :: Eq a => [a] -> [a] -> [a]
*Main> union [1..5] [3..10]
[1,2,3,4,5,6,7,8,9,10]
*Main> intersection [1..5] [3..10]
[3,4,5]
union :: Eq a => [a] -> [a] -> [a]
union xs ys = xs ++ [y| y<-ys, not (elem y xs)]

intersection ::  Eq a =>  [a] -> [a] -> [a]
intersection xs ys = [y| y<-ys, elem y xs]
Try it!

Komplexnější funkce

  • Vytvořte funkci která spočítá počet výskytů všech znaků v řetězci.
Video logo.png
countThem :: String -> [(Char, Int)]
*Main>countThem "hello hello hello"
[('h',3),('e',3),('l',6),('o',3),(' ',2)]
unique :: String -> String
unique n = reverse(tmp n "") where
  tmp [] store = store
  tmp (x:xs) store | x `elem` store = tmp xs store
                   | otherwise = tmp xs (x:store)

unique' :: String -> String                   
unique' [] = []
unique' (x:xs) = x: unique' (filter (/=x)xs)

countThem :: String -> [(Char, Int)]
countThem xs = let u = unique xs
               in [(x, length (filter (==x) xs)) |x<-u]
Try it!
  • Goldbachova hypotéza říká, že každé kladné sudé číslo větší než 2 lze vyjádřit jako součet dvou prvočísel. Příklad: 28 = 5 + 23. Je to jedna z nejslavnějších hypotéz v teorii čísel, která ještě nebyla dokázána. Vytvořte funkci která pro dané celé číslo spočítá seznam dvojic prvočísel, které splňují Goldbachovu hypotézu.
Video logo.png
goldbach :: Int-> [(Int, Int)]
*Main>goldbach 28
[(5, 23),(11,17)]
isPrime :: Int -> Bool
isPrime n = null [x |x<-[2..ceiling (sqrt (fromIntegral n)::Double)], n `mod` x == 0]

goldbach :: Int-> [(Int, Int)]
goldbach n = let primes = [x |x<-[2..(n `div` 2)], isPrime x]
             in [(x,n-x) |x<-primes, isPrime (n-x)]
Try it!
  • Ve většině případů, pokud je sudé číslo zapsáno jako součet dvou prvočísel, jedno z nich je velmi malé. Budeme hledat případy které tohle pravidlo nesplňují. Vytvořte funkci která má tři parametry. Frvní dva definují interval, kde budeme hledat Goldbachova čísla. Poslední parametr je limit. Pro každé číslo v intervalu nalezněte Goldbachovu dvojici s nejmenším prvočíslem. Pokud je nejmenšé prvočíslo větší než daný limit, přislušná dvojice bude obsažena ve výsledku.
Video logo.png
goldbachList :: Int -> Int-> Int -> [(Int, Int)]
*Main>goldbachList 4 2000 50
[(73,919),(61,1321),(67,1789),(61,1867)]
isPrime :: Int -> Bool
isPrime n = null [x |x<-[2..ceiling (sqrt (fromIntegral n)::Double)], n `mod` x == 0]

goldbach :: Int-> [(Int, Int)]
goldbach n = let primes = [x |x<-[2..(n `div` 2)+1], isPrime x]
             in [(x,n-x) |x<-primes, isPrime (n-x)]

goldbachList :: Int -> Int-> Int -> [(Int, Int)]
goldbachList a b limit = filter (\(x,_)-> x>limit) [head (goldbach x) | x<-[a..b], even x]
Try it!
  • Create a function that generates all combinations of given length from the characters from given string. You can assume, that all character are unique and the given length is not bigger then the length of this string.
Video logo.png
combinations :: Int -> String -> [String]
*Main> combinations 3 "abcdef"
["abc","abd","abe",...]
combinations :: Int -> String -> [String]
combinations 1 xs = [[x]| x<-xs]
combinations n (x:xs) | n == length (x:xs) = [(x:xs)]
                      |otherwise = [[x] ++ y |y<-combinations (n-1) xs ] 
                                    ++ (combinations n xs)
Try it!