module ClassTest1Solutions where
import Data.Char
import Types
Copyright By PowCoder代写 加微信 powcoder
— Question 1
First we define a helper function, which we will use to check if a byte is even.
It calculates the length of the list generated by using filter to obtain all of
the ‘1’s in the input list. If this length is even, then we have an even number
testEven :: String -> Bool
testEven xs = even (length (filter (\c -> c == ‘1’) xs))
The empty case is True, because an empty byte has length divisible by 8, and an
even number of ‘1’s (0 is even).
In the case where we are given a bitstring, we first check that the length of
the list is divisible by 8. If not, we return False. Then we can check if the
first byte in the string has even parity using our helper function testEven.
Using recursion, we also check if every byte in the tail of the list has even
checkParity :: String -> Bool
checkParity [] = True
checkParity xs = if (length xs) `mod` 8 /= 0
then False
else (testEven (take 8 xs)) && checkParity (drop 8 xs)
— Question 2
We first define a helper function which maps letters to their respective letters
(with correct casing) using an uppercase key. Uppercase character are mapped
directly, lowercase characters are mapped to lowercase characters using toLower.
We find the new letter (nl) by using the given function charLabel to given us an
index to look at in the key.
getNewLetter :: Char -> String -> Char
getNewLetter char key = if isUpper char then nl else toLower nl
nl = key !! charLabel char
Now we define substitution using map. We inspect each character and do the
following:
– If the character is a letter, then use the helper function to map to the
corresponding new letter.
– Otherwise, return the character, because it is a space or punctuation.
substitution :: String -> String -> String
substitution plaintext key = map (\x -> if isLetter x then getNewLetter x key else x) plaintext
— Question 3
Chebyshev’s theorem ensures that a prime exists between n and 2n. We can simply
check each value starting from 2n, and searching downwards, returning the first
prime we find. Note that we do not need to exclude 2n, because it is not prime.
By beginning our search from the end of the list, we massively reduce the time
it takes to find the prime.
largestPrimeBetween :: Int -> Int
largestPrimeBetween n = head [p | p <- reverse [n..2*n] , isPrime p]
-- Part ii
First, we define two helper functions which find the next and previous primes of
any integer respectively. In both case, we simply look through values until we
find a prime.
nextprime :: Int -> Int
nextprime n = head [x | x <- [(n+1)..], isPrime x]
prevprime :: Int -> Int
prevprime n | n == 2 = undefined
| isPrime (n-1) = n-1
| otherwise = prevprime (n-1)
Note – largestPrimeBetween can be defined as follows: largestPrimeBetween =
prevprime (2*n)
We need primes whose value is greater than the average of the next previous
primes. Using the helper functons, this can be done using a list comprehension
with boolean guards, finding primes which satisfy the predicate.
strongPrimes :: Int -> [Int]
strongPrimes n = take n [x | x <- [3..], isPrime x &&
x > ((nextprime x + prevprime x) `div` 2)]
— Question 4
The ‘executeCommands’ function repeatedly runs ‘executeCommand’ using foldr as
to obtain a chain of applications
‘executeCommand c_1 (executeCommand c_2 (… executeCommand c_n (x, y)))’
where c_n denotes the nth command in the list ‘cs’.
executeCommands :: [Command] -> (Int, Int) -> (Int, Int)
executeCommands cs (x,y) = foldr executeCommand (x,y) cs
where executeCommand :: Command -> (Int, Int) -> (Int, Int)
executeCommand (MoveUp, d) (x, y) = (x, y+d)
executeCommand (MoveDown, d) (x, y) = (x, y-d)
executeCommand (MoveRight, d) (x, y) = (x+d, y)
executeCommand (MoveLeft, d) (x, y) = (x-d, y)
— Question 5
{-| The function ‘atmChange’ is a greedy algorithm, repeatedly dividing by
current denomination and making a recursive call with the remainder and the rest
of the list of denominations.
atmChange :: Int -> [Int] -> [(Int, Int)]
atmChange 0 [] = []
atmChange n [] = undefined
atmChange n ds = (denom, n `div` denom) : atmChange (n `mod` denom) (reverse (tail revds))
denom = head revds
revds = reverse ds
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com