練習問題 : リスト構造

練習問題が終わったら、第一回課題 に取り組みましょう。

練習 1 は、重要な問題なので、きちんと解いておいてください。 練習 2 は、補助がないので、余裕があれば解いてみましょう。

1. データ抽象 (参考文献[3]から引用)

二分木をなすモービル(天秤の複合体の様なもので、バランスをとっている、動くオブジェ)は、 left と right の枝をもっている。 各枝には長さがあって、その先に別のモービルか、おもりがついている。 いま、モービルを left, right の枝を用いて、 つぎのように構成するとする(つまりは、要素二つのリストで表現)。

(define (make-mobile left right)
  (list left right))
     

また、枝は length, mobile を用いて以下のように表現される。 但し、 structure には、おもみに対応する数、もしくは、 モービルが対応する。

(define (make-branch length structure)
  (list length structure))
     

a.

モービルに対して、その左・右の枝を返す left-branch, right-branch を定義せよ。また、枝に対して、その length ,structure を返す branch-length, branch-structure を定義せよ。

(define sample-mobile0
    (make-mobile 
     (make-branch 10 (make-mobile 
                      (make-branch 4 8)
                      (make-branch 8 4)))
     (make-branch 4 (make-mobile
                     (make-branch 8 10)
                     (make-branch 4 (make-mobile 
                                     (make-branch 9 5)
                                     (make-branch 3 15)))))))

(define sample-mobile1
    (make-mobile 
     (make-branch 10 (make-mobile 
                      (make-branch 4 8)
                      (make-branch 8 4)))
     (make-branch 4 (make-mobile
                     (make-branch 8 10)
                     (make-branch 4 (make-mobile 
                                     (make-branch 9 5)
                                     (make-branch 2 15)))))))

b.

モービル(もしくは重み)に対して、 その総重量をかえす total-weight を a. の関数をもちいて定義せよ。

> (total-weight sample-mobile0)
42

c.

モービルがバランスしているかどうかを返す、 mobile-balanced? を定義せよ。

> (mobile-balanced? sample-mobile0)
#t
> (mobile-balanced? sample-mobile1)
#f

d.

仮に、モービルのデータ構造を以下の様に変更したとする。

;;; Structure := Mobile | Weight
;;; Mobile := ('Mobile left-structure right-structure)
;;; Weight := ('Weight weight-value)

(define (make-mobile left right) (list 'Mobile left right))
(define (make-weight value)      (list 'Weight value))
  

このとき、プログラムをどのように変更すればよいか考えよ。

解答例

ちなみに、モービル (mobile, stabile) とは？
重りや金属片などを幾重もの天秤状にぶら下げた、動く彫刻のこと。 たとえば、こういうもの 1, 2.

2.

N-Queen パズルの解の個数を返す program を作れ。(ちょっと難しいかも？)
N-Queen パズルとは、N x N の盤の上に Chess の Queen (縦、横、斜め方向に自由に動く) を N 個置き、互いに相手をとることの出来ないような配置を解とする。 但し、前後対称回転対称な盤目も別々の解として数えるものとする。

解答例