課程名稱︰程式語言 課程性質︰選修 課程教師︰穆信成 開課學院：管理學院 開課系所︰資訊管理學系 考試日期（年月日）︰11/7 (四) 考試時限（分鐘）：9:10-12:10 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : (考試允許攜入任何講義/筆記/參考資料. 原試卷中斜體/程式字以高亮標示) Programming Languages: Midterm Examination Shin-Cheng Mu Nov. 7, 2013 You may assume that knowledge about arithmetic (e.g. ( ×) is associative, multiplication distributes over addition, etc) need no further proof and may be taken as axioms. Algebraic proofs or derivations need not be carried out in glory details -- you may skip some steps that you think are trivial. Do label the important steps, however, especially the step(s) where you use induction. You can use all Haskell functions in the standard prelude, mentioned in the lectures. 1. (10 points) A suffix of a list xs is a consecutive segment of xs that ends at the right end of xs. Define a function lmamrm :: [Int] → Int such that lmamrm xs returns the num- ber of suffixes of xs whose leftmost element is less than or equal to its rightmost element. (The funny name lmamrm stands for ``leftmost-at-most-rightmost".) For example, [4, 3, 9, 3] has two such suffixes: [3, 9, 3] and [3], thus lmamrm [4, 3, 9, 3] = 2. Hints: 1. A one-line definition will do. 2. we have already mentioned a function, in the standard library, that returns all suffixes of a list. 3. A list must be non-empty to have a leftmost and a rightmost element - which could be the same element. There was a function in the standard library check- ing whether a list is empty. If you cannot find it, define your own. 2. (15 points) Prove the property: sum。map (y ×) = (y ×)。sum 3. (15 points) Recall the definition of (!!) such that xs !! n yields the nth element in xs (counting from 0): (!!) :: [a] → Nat → a (x : xs) !! 0 = x (x : xs) !! (1+ n) = xs !! n. Consider the definition below geo :: Int → [Int] geo y = 1 : map (y ×) (geo y). n Prove that geo y !! n = y for all n :: Nat. 4. (15 points) An interleaving of two lists xs and ys is a permutation of the elements of both lists such that the mem- bers of xs appear in their original order, and so does the member of ys. Define interleave :: [a] → [a] → [[a]] such that interleave xs ys is the list of interleaving of xs and ys. For example, interleave [1, 2, 3] [4, 5] yields: [[1,2,3,4,5], [1,2,4,3,5], [1,2,4,5,3], [1,4,2,3,5], [1,4,2,5,3], [1,4,5,2,3], [4,1,2,3,5], [4,1,2,5,3], [4,1,5,2,3], [4,5,1,2,3]]. Hint: I would use an inductive definition. 5. A list ys is a sublist of xs if we can obtain ys by remov- ing zero or more elements from xs. For example, [2, 4] is a sublist of [1, 2, 3, 4], while [3, 2] is not. The list of all sublists of [1, 2, 3] is: [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]. (a) (20 points) Define a function sublist :: [a] → [[a]] that computes the list of all sublists of the given list. Hint: to form a sublist of xs, each element of xs could either be kept of dropped. (b) (10 points) Define a function maximumBy :: (a → Int) → [a] → a such that maximumBy f takes a (non-empty) list xs as its input, and returns an element x such that x is an element of xs and, for all element y in xs, f x ≧ f y. Hint: there are many ways to define maximumBy. I would perhaps go for an inductive definition. (c) (5 points) Let Item be some datatype, representing cer- tain items, for which two functions are defined: value :: Item → Int, weight :: Item → Int. Define two functions valList :: [Item] → Int and weightList :: [Item] → Int that respectively compute the total value and weight, give a list of items. (d) (10 points) Recall the 0-1 knapsack problem: given a list of items, we want to pick a sublist of the items that is as valuable as possible, whose total weight is no more than a weight limit. Give a one-line program knapsack :: Int → [Item] → [Item] knapsack w ... where w is the weight limit, that specifies (or, computes) the 0-1 knapsack problem, using the functions defined above, together with some library functions. It is only a specification, thus it does not matter if it is very slow. (We will learn how to optimise it in later courses.) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.166.61.86 ※ 編輯: suhorng 來自: 118.166.61.86 (11/09 00:26) ※ 編輯: suhorng 來自: 118.166.61.86 (11/09 00:26)