chapter3.md

#1. トリボナッチ数列

トリボナッチ数列の定義

以下のような数列を考える。

• 最初の2つの数字は0
• 3つめの数字は1
• 4つめ以降の数字は、直前の3つの数の和

このような数列をトリボナッチ数列という。
例として、最初の10項は

0, 0, 1, 1, 2, 4, 7, 13, 24, 44

となる。

問

トリボナッチ数列のn番目の数を計算する関数を、以下の名前と方法で定義せよ。

1. tri_pattern : パターンマッチを用いる
2. tri_guard : ガードを用いる
3. tri_case : case式を用いる。

ただし一番最初の数を0番目とする。
また負数を与えた場合の挙動は考慮しなくて良い。

例

*Main> :t tri_pattern
tri_pattern :: Int -> Int
*Main> take 10 [tri_pattern n | n <- [0..]]
[0,0,1,1,2,4,7,13,24,44]

*Main> :t tri_guard
tri_guard :: Int -> Int
*Main> take 10 [tri_guard n | n <- [0..]]
[0,0,1,1,2,4,7,13,24,44]

*Main> :t tri_case
tri_case :: Int -> Int
*Main> take 10 [tri_case n | n <- [0..]]
[0,0,1,1,2,4,7,13,24,44]

#2. タプル数

タプル数の定義

有理数を、分子と分母を表す整数の二つ組で表すことにする。
以下、この表現による数をタプル数と呼ぶことにする[註1]。
例えば、2/5は(2,5)のようにタプル数で表現できる。

以下に注意すべき点を挙げる。

• 分子、分母ともに負数を許す。2/5は(2,5)とも(-2,-5)とも表現できる。
• 既約でない表現を許す。2/5は(4,10)とも(20,50)とも表現できる。
• 分母が0であるタプル数は存在しない。このようなタプル数に対して関数を適用した場合、実行時例外とする。

問

以下の関数を定義せよ。なお、オーバーフローが起こるような、極端に大きな数を与えた際の挙動は考慮しなくて良い。

1. qadd : 2つのタプル数を受け取り、その和を返す関数(既約でなくても良い)
2. qequal : 2つのタプル数を受け取り、有理数としての値が等しいかの真偽値を返す関数
3. qlist : 1つのタプル数を受け取り、そのタプル数と等しいすべてのタプル数をリストで返す関数
   　 ただし、順序は分母の絶対値の小さい順とし、絶対値が同じ場合は分母が正の物が先になるようにする。
   　 Haskellには最大公約数を求める関数gcdがあり、これを用いて良い。

例

*Main> :t qadd
qadd :: (Int, Int) -> (Int, Int) -> (Int, Int)
*Main> qadd (1,2) (3,4)
(10,8)
*Main> qadd (1,1) (-2,-5)
(-7,-5)
*Main> qadd (1,1) (-2,0)
*** Exception: second of tuple number is 0

*Main> :t qequal
qequal :: (Int, Int) -> (Int, Int) -> Bool
*Main> qequal (1,2) (-2,-4)
True
*Main> qequal (1,3) (-2,-4)
False
*Main> qequal (1,0) (-2,-4)
*** Exception: second of tuple number is 0

*Main> :t qlist
qlist :: (Int, Int) -> [(Int, Int)]
*Main> take 10 (qlist (4,6))
[(2,3),(-2,-3),(4,6),(-4,-6),(6,9),(-6,-9),(8,12),(-8,-12),(10,15),(-10,-15)]
*Main> take 10 (qlist (3,-5))
[(-3,5),(3,-5),(-6,10),(6,-10),(-9,15),(9,-15),(-12,20),(12,-20),(-15,25),(15,-25)]
*Main> take 10 (qlist (1,0))
*** Exception: second of tuple number is 0

※註1. タプル数は便宜上定義した語であり、一般的な用語ではない。