[試題] 102-1 穆信成 程式語言 期中考
課程名稱︰程式語言
課程性質︰選修
課程教師︰穆信成
開課學院：管理學院
開課系所︰資訊管理學系
考試日期（年月日）︰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)
→
11/09 00:59, , 1F
11/09 00:59, 1F