情報処理演習U 第2回レポート

                            1TE11082P 岩崎 知亮

URL:http://www.s.kyushu-u.ac.jp/~1TE11082P/index.html

課題1  「エラトステネスのふるい」の原理に基づいて100以下の素数を求めるプログラムを以下の手順で作成せよ。

  1. n以下の自然数のリストを生成する関数natintを定義せよ。

(define (natint n) …) ;; natint : number -> (listof number)

関数定義:

(define (natint n)

(cond

[(= n 0) empty]

[else (append (natint (- n 1)) (list n))]))

実行結果:

> (natint 5)

(list 1 2 3 4 5)


  1. 数のリストlからmで割切れるものを除去する関数sieveを定義せよ。

(define (sieve m l) …) ;; sieve : number (listof number) -> (listof number)

関数定義:

(define (sieve m l)

(cond

[(empty? l) empty]

[(= (remainder (first l) m) 0) (sieve m (rest l))]

[else (append (list (first l)) (sieve m (rest l)))]))

実行結果:

> (sieve 2 (list 1 2 3 4 5 6))

(list 1 3 5)


  1. 自然数のリストlを受取り素数のリストを求める関数primeを定義せよ。

(define (prime l) …) ;; prime : (listof number) -> (listof number)

関数定義:

(define (prime l)

(cond

[(empty? l) (append empty)]

[(= 1 (first l)) (prime (rest l))]

[else (append (list (first l)) (prime (sieve (first l) (rest l))))]))

実行結果:

> (prime (natint 100))

(list 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)

感想:この課題は、あまり難しくなかったので、短時間でできた。


課題2 二分木・二分探索木のノードを下のように定義する。

(define-struct valnode (value left right))


(1) 二分木は下の構成的定義に従って定義される。

構成的定義:

[1] empty は二分木である。

[2] 部分木を持つ節を表す valnode 構造体であるとき,

それが持つ左部分木と右部分木が二分木であれば,二分木である。

   また,二分探索木は第11回講義資料の24ページのスライドにあるように,

[a] 左の部分木に含まれる値は,ノードの値(value)より小さい

[b] 右の部分木に含まれる値は,ノードの値(value)より大きい

を満たすものである。

二分探索木であることを判定する関数を定義せよ。          

いくつかの適切な木を入力して,正しく判定できることを確かめよ。

レポートには,入力したテストデータ,そのデータを採用した理由も載せること。


;; BinSearchTree? : any -> boolean

;; (define (BinSearchTree? a-tree) ... )

関数定義:

(define-struct valnode (value left right))


(define (BinSearchTree? a-tree)

(cond

[(empty? a-tree) true]             ;;空ならばtrue

[(not (valnode? a-tree)) false] ;;a-treevalnode型でなければfalse

[(and

(not (empty? (valnode-left a-tree)))

(> (valnode-value (valnode-left a-tree))

(valnode-value a-tree))) false]

[(and

(not (empty? (valnode-right a-tree)))

(< (valnode-value (valnode-right a-tree))

(valnode-value a-tree))) false]

[else

(and

(BinSearchTree? (valnode-left a-tree))

(BinSearchTree? (valnode-right a-tree)))]))





実行結果:

> (BinSearchTree? (make-valnode 35

(make-valnode 21

(make-valnode 13 empty empty)

empty)

(make-valnode 46

(make-valnode 40 empty empty)

(make-valnode 61

empty

(make-valnode 69 empty empty)))))

true

> (BinSearchTree? (make-valnode 35

(make-valnode 13

(make-valnode 21 empty empty)

empty)

(make-valnode 46

(make-valnode 40 empty empty)

(make-valnode 61

empty

(make-valnode 69 empty empty)))))

false

最初の値は第十一回のパワーポイントの中で2分探索木として与えられているものなので、trueとなった。

二回目の値は、一回目の値のうち1321を入れ替えたものである。これは2分探索木の定義を満たしていないので、falseになった。よって、この関数は正しく動いていると考えられる。


(2) 上の(1)に示した二分探索木に登録されている値(value)のうち,

    最小のものを求める関数を定義せよ。                

;; BinSearchTreeMin : any -> number

;; (define (BinSearchTreeMin a-tree) ... )

関数定義:

define (BinSearchTreeMin a-tree)

(cond

[(empty? (valnode-left a-tree)) (valnode-value a-tree)]

[else (BinSearchTreeMin (valnode-left a-tree))]))










実行結果:

> (BinSearchTreeMin (make-valnode 35

(make-valnode 21

(make-valnode 13 empty empty)

empty)

(make-valnode 46

(make-valnode 40 empty empty)

(make-valnode 61

empty

(make-valnode 69 empty empty)))))

13


感想:2分探索木について、まだなれないことが多く、時間がかかってしまった。


課題3-2 二分探索木を描く関数を定義しなさい。


2.1 二分探索木のノードは下の構造体valnodeを使用する。

(define-struct valnode (value left right))

valuesymbolnumberのリストを格納する。ノードの値の大小は

リストのnumberの値で比較する。

このとき,下のvalueのリストから二分探索木を作成し,

それを描画する関数を定義せよ。                  

(list (list 'A 61)

(list 'B 28)

(list 'C 89)

(list 'D 16)

(list 'E 77)

(list 'F 96)

(list 'G 12)

(list 'H 25)

(list 'I 98)

(list 'J 37)

(list 'K 21)

(list 'L 22)

(list 'M 88)

(list 'N 90)

(list 'O 100)

(list 'P 76)

(list 'Q 35)

(list 'R 1))

2.2 作成した二分探索木の木の高さを求め,

それをルートノードの右に表示するように変更しなさい。      

関数定義:

(define-struct node (sn pn left right))

(define list-of-valnode

(list (list 'A 61)

(list 'B 28)

(list 'C 89)

(list 'D 16)

(list 'E 77)

(list 'F 96)

(list 'G 12)

(list 'H 25)

(list 'I 98)

(list 'J 37)

(list 'K 21)

(list 'L 22)

(list 'M 88)

(list 'N 90)

(list 'O 100)

(list 'P 76)

(list 'Q 35)

(list 'R 1)))


;;to set the canvas' size

(define width 700)

(define height 730)

;;to set the disk's radius and color

(define disk-radious 5)

(define disk-color 'blue)

(define line-color 'black)

;;to set root position

(define TopMargine 30)

(define root-pos

(make-posn (/ width 2)

(+ disk-radious TopMargine)))


;; draw-node : node posn -> boolean

;;to draw a disk and a string at a-posn position

(define (draw-node a-node a-posn)

(and

(draw-solid-disk a-posn disk-radious disk-color)

(draw-solid-string a-posn (number->string (node-sn a-node)))

))


;;to draw-line: node posn posn -> true

(define (draw-line a-node a-posn1 a-posn2)

(cond

;;if a-node = empty -> the branch will not be drawn.

[(empty? a-node) true]

[else

(draw-solid-line a-posn1 a-posn2 line-color)]))



(define N (length list-of-valnode));;num of "fusi"

(define DP (/ (- height TopMargine) (- N (log N))));;length between fusi


;;get-next-left-posn : posn number -> posn

(define (get-next-left-posn a-posn width)

(make-posn (-(posn-x a-posn) width)

(+ (posn-y a-posn) DP)))


;;get-next-right-posn : posn number number -> posn

(define (get-next-right-posn a-posn width)

(make-posn (+ (posn-x a-posn) width)

(+ (posn-y a-posn) DP)))


(define Interval-Time 0.5);;to wait time between make brance etc...

;; draw-node-and-branches : node posn number -> true

(define (draw-node-and-branches node a-posn width)

(and ;;to draw node

(draw-node node a-posn)

(sleep-for-a-while Interval-Time)

;;to draw left and right branches

(draw-line (node-left node) a-posn

(get-next-left-posn a-posn (/ width 2)))

(sleep-for-a-while Interval-Time)

(draw-line (node-right node) a-posn

(get-next-right-posn a-posn (/ width 2)))

))


;;to make the tree

(define (draw-tree node a-posn width)

(cond

[(empty? node) true]

[else

(and

;;to draw node and edges

(draw-node-and-branches node a-posn width)

;;to traverse left and right nodes

(draw-tree (node-left node)

(get-next-left-posn a-posn (/ width 2)) (/ width 2))

(draw-tree (node-right node)

(get-next-right-posn a-posn (/ width 2)) (/ width 2))

)]))


;; add-node : node (listof number symbol) -> node

(define (add-node bt alosp)

(cond

[(empty? bt)

(make-node (first (rest alosp))(first (rest alosp)) empty empty)]

[else

(cond

[(= (node-sn bt) (first (rest alosp))) bt]

[(> (node-sn bt) (first (rest alosp)))

(make-node (node-sn bt) (node-pn bt)

(add-node (node-left bt) alosp)

(node-right bt))]

[else

(make-node (node-sn bt) (node-pn bt)

(node-left bt)

(add-node (node-right bt)alosp))])]))


;;create-btree : node (lof (lof symbol number))->node

(define (create-btree bt lof-alosp)

(cond

[(empty? lof-alosp) bt]

[else

(create-btree

(add-node bt (first lof-alosp))

(rest lof-alosp))]))



(define Root-Pos

(make-posn (/ width 2) (+ disk-radious TopMargine)))


(start width height)


(draw-tree (create-btree empty list-of-valnode) Root-Pos (/ width 3))



;; height-2 : tree -> number

;;to measure the height of a tree

(define (height-2 abt)

(cond

[(empty? abt) 0]

[else (+ 1

(max (height-2 (node-left abt))

(height-2 (node-right abt))))]))


(define Root-Pos-2

(make-posn (+ (/ width 2) (* 4 disk-radious)) (+ (* 2 disk-radious) TopMargine)))


(draw-solid-string Root-Pos-2 (number->string (height-2 (create-btree empty list-of-valnode))))

実行結果:






























全体の感想:

すごく難しかったが、なんとか理解しながらすることができた。しかし、提出期限を過ぎてしまった。もう少し早く書けるようになりたい。