Skip to content

Latest commit

 

History

History
56 lines (46 loc) · 2.25 KB

chapter1.md

File metadata and controls

56 lines (46 loc) · 2.25 KB

#1. マンハッタン距離

2つの整数のペアを受け取り、その2点のマンハッタン距離を返す関数manlenを定義せよ。
ただし、p1 = (a,b)p2 = (c,d)のマンハッタン距離manlen(p1, p2)は次式で定義される。

manlen(p1, p2) = |a - c| + |b - d|

なお、|x|xの絶対値である。
Haskellでは組み込み関数absがあり、これを用いて良い。

manlen :: (Int, Int) -> (Int, Int) -> Int

*Main> abs 1
1
*Main> abs (-1)
1
*Main> manlen (0,0) (1,1) -- x方向での距離1, y方向での距離1
2
*Main> manlen (-1,1) (1,3) -- x方向での距離2, y方向での距離2
4

#2. 整数座標のリスト 非負整数を受け取り、2数それぞれの絶対値がその数以内であるような整数のペアをリストで返す関数pointsを定義せよ。
例として、1が与えられた時には[(x,y) | x ∈ {-1, 0, 1}, y ∈ {-1, 0, 1}] のような集合になる。(xyそれぞれの絶対値が1以下となる全ての整数のペア)
なお、負数が与えられた場合の挙動は考慮しなくて良い。

points :: Int -> [(Int, Int)]

*Main> points 0
[(0,0)]
*Main> points 1
[(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)]

#3. タクシー幾何学における円 非負整数を受け取り、原点(0,0)からのマンハッタン距離がその数であるような整数のペアをリストで返す関数mancircleを定義せよ。
なお、負数が与えられた場合の挙動は考慮しなくて良い。

mancircle :: Int -> [(Int, Int)]

*Main> mancircle 0
[(0,0)]
*Main> mancircle 1
[(-1,0),(0,-1),(0,1),(1,0)]
*Main> mancircle 2
[(-2,0),(-1,-1),(-1,1),(0,-2),(0,2),(1,-1),(1,1),(2,0)]

参考

ユークリッド幾何学ではユークリッド距離√(dx^2 + dy^2)を用いるが、この代わりにマンハッタン距離dx+dyを用いた幾何学をタクシー幾何学という。
円を「原点から等距離にある点の集合」と定義した場合、タクシー幾何学に於ける円は一般的な意味での菱型(より正確には正方形)を成す。
http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%B3%E3%83%8F%E3%83%83%E3%82%BF%E3%83%B3%E8%B7%9D%E9%9B%A2