- アスタリスクの数は難易度です。
- 効率も大事ですが、エレガントな回答を求めます。可能ならばより簡潔で、計算量が少なく、末尾再帰になっている回答を作りましょう。
- Scalaの組み込み関数を使ってもOKです。が、使わないほうが勉強になります。
- 答えが知りたければ、元の英語文書の各問題のリンクをクリックして下さい。
P01 (*) リストの最後の要素を求めよ。
scala> last(List(1, 1, 2, 3, 5, 8))
res0: Int = 8
P02 (*) リストの最後から二番目の要素を求めよ。
scala> penultimate(List(1, 1, 2, 3, 5, 8))
res0: Int = 5
P03 (*) リストのn番目の要素を求めよ。但しリストの最初の要素は0番目とする。
scala> nth(2, List(1, 1, 2, 3, 5, 8))
res0: Int = 2
P04 (*) リストの要素の数を求めよ。
scala> length(List(1, 1, 2, 3, 5, 8))
res0: Int = 6
P05 (*) リストを逆順にせよ。
scala> reverse(List(1, 1, 2, 3, 5, 8))
res0: List[Int] = List(8, 5, 3, 2, 1, 1)
P06 (*) リストが回文になっているか調べよ。
scala> isPalindrome(List(1, 2, 3, 2, 1))
res0: Boolean = true
P07 (**) ネストされたリスト構造を平坦化せよ。
scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))
res0: List[Any] = List(1, 1, 2, 3, 5, 8)
P08 (**) リスト要素の連続した重複物を除去せよ。もしリストの要素で繰り返し要素が含まれていたならば要素一つに置き換えよ。要素の順序は変えてはならない。
scala> compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[Symbol] = List('a, 'b, 'c, 'a, 'd, 'e)
P09 (**) 連続した重複物を子リストに纏めよ。もしリストの要素が繰り返し要素ならば、別々の子リストに分割せよ。
scala> pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))
P10 (*) リストをランレングス・エンコードせよ。P09の結果を用いていわゆるランレングス・エンコーディングによるデータ圧縮法を実装せよ。連続した重複要素はタプル(N,E)にエンコードされる。但しNは要素Eの重複数。
scala> encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))
P11 (*) 修正ランレングス・エンコーディング。P10の結果を修正し、もし要素に重複が無ければ単に要素を結果にコピーせよ。重複している要素だけを(N,E)の形に変換せよ。
scala> encodeModified(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[Any] = List((4,'a), 'b, (2,'c), (2,'a), 'd, (4,'e))
P12 (**) ランレングス・エンコードされたリストをデコードせよ。P10の仕様で生成されたランレングス・エンコードされたリストを元の圧縮されていないものに戻せ。
scala> decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)))
res0: List[Symbol] = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
P13 (**) リストのランレングス・エンコーディング（直接解法）。いわゆるランレングス・エンコーディングを直接実装せよ。すなわち（P09のpackの様な）自分で書いた他のメソッドを使ってはならない。直接書く事。
scala> encodeDirect(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))
P14 (*) リスト要素を重複させよ。
scala> duplicate(List('a, 'b, 'c, 'c, 'd))
res0: List[Symbol] = List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd)
P15 (**) 指定した個数、リスト要素を重複させよ。
scala> duplicateN(3, List('a, 'b, 'c, 'c, 'd))
res0: List[Symbol] = List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd)
P16 (**) 毎N番目の要素を除去せよ。
scala> drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k)
P17 (*) リストを二つに分割せよ。前半の長さは与えられるものとする。結果はタプルで返す。
scala> split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: (List[Symbol], List[Symbol]) = (List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
P18 (**) リストのスライスを抽出せよ。二つの添字 i と j が与えられたとき、スライスとは元のリストの i 番目の要素を含むが j 番目の要素を含まないリストである。要素は0番目から始まるとする。
scala> slice(3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('d, 'e, 'f, 'g)
P19 (**) リストの要素をn個左ローテートせよ。
scala> rotate(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c)
scala> rotate(-2, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res1: List[Symbol] = List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i)
P20 (*) リストのk番目の要素を除去せよ。除去されたリストと除去した要素をタプルで返せ。要素は0番目から始まるとする。
scala> removeAt(1, List('a, 'b, 'c, 'd))
res0: (List[Symbol], Symbol) = (List('a, 'c, 'd),'b)
P21 (*) リストの指定された場所に要素を追加せよ。
scala> insertAt('new, 1, List('a, 'b, 'c, 'd))
res0: List[Symbol] = List('a, 'new, 'b, 'c, 'd)
P22 (*) 与えられた範囲の整数のリストを作れ。
scala> range(4, 9)
res0: List[Int] = List(4, 5, 6, 7, 8, 9)
P23 (**) リストから指定された数だけ値をランダムに選択せよ。（ヒント：P20を使え）
scala> randomSelect(3, List('a, 'b, 'c, 'd, 'f, 'g, 'h))
res0: List[Symbol] = List('e, 'd, 'a)
P24 (*) ロト：1〜Mからn個の異なるランダムな値を選べ。
scala> lotto(6, 49)
res0: List[Int] = List(23, 1, 17, 33, 21, 37)
P25 (*) 要素のランダムな順列を作成せよ。（ヒント：P23を使え）
scala> randomPermute(List('a, 'b, 'c, 'd, 'e, 'f))
res0: List[Symbol] = List('b, 'a, 'd, 'c, 'e, 'f)
P26 (**) n要素数のリストからk個の異なるオブジェクトを取り出す組み合わせを生成せよ。12人から3人の委員会を作る方法は何通りだろうか？答えは C(12,3)=220通り（C(n,k）はよく知られた二項係数）である。数学者にとってはこれで十分であるが、我々は本当に全ての解を生成したい。
scala> combinations(3, List('a, 'b, 'c, 'd, 'e, 'f))
res0: List[List[Symbol]] = List(List('a, 'b, 'c), List('a, 'b, 'd), List('a, 'b, 'e), ...
P27 (**) 集合の要素を、互いに素な部分集合に纏めよ。
a) 9人の人をそれぞれ2,3,4人の３グループに纏める方法は何通りか？全ての組み合わせを生成する関数を書け。
scala> group3(List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida"))
res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David, Evi), List(Flip, Gary, Hugo, Ida)), ...
b) 上の問題を一般化してグループの大きさのリストを与えるとグループのリストを与える様にせよ。グループメンバーの順列は求めていない、すなわち((Aldo,Beat),...)は((Beat,Aldo),...)と同じ解である。しかし、((Aldo,Beat),(Carla,David),...)は((Carla,David),(Aldo,Beat),...)と異なる解である。
scala> group(List(2, 2, 5), List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida"))
res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David), List(Evi, Flip, Gary, Hugo, Ida)), ...
この組み合わせ問題に関して知りたければ離散数学の良い本で「多項係数」について調べよ。
P28 (**) リストのリストを長さでソートせよ。
a) 要素がリストであるリストを考える。そのリストの要素を長さでソートする、すなわち短いリストを前に、長いリストを後にする。
scala> lsort(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o)))
res0: List[List[Symbol]] = List(List('o), List('d, 'e), List('d, 'e), List('m, 'n), List('a, 'b, 'c), List('f, 'g, 'h), List('i, 'j, 'k, 'l))
b) 次に同様にリストを長さでソートするが、今回は長さの頻度でソートする。すなわち稀な長さのものを前に、頻度の高い長さのものを後ろにする。例の場合、長さ４と１のリストはただ１度しか現れない。3番目と4番目は長さ3のリスト２つである。最後に３つの最も頻度の高い長さ２のリストが現れる。
scala> lsortFreq(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o)))
res1: List[List[Symbol]] = List(List('i, 'j, 'k, 'l), List('o), List('a, 'b, 'c), List('f, 'g, 'h), List('d, 'e), List('d, 'e), List('m, 'n))
No comments:
Post a Comment