Reverse

新しい再帰呼び出しの形式
• Accumulator(集積変数）を用いた再帰
例：中間結果を保持して計算する
相対距離から絶対距離
（５０４０７０３０３０）から（５０９０１６０１９０２２０）を計算する
相対距
離０
50
40
7０
50
90
160
30
30
190
220
絶対距
離
０
relative-2-absolute
;; relative-2-absolute :
;; (listof number) -> (listof number)
;; 相対的距離を示す値のリストから
;; 絶対的距離を示す値のリストに変換する
;; リストの最初の要素は原点からの距離
relative-2-absolute
(define (relative-2-absolute alon)
(cond
[(empty? alon) empty]
[else (cons (first alon)
(add-to-each
(first alon)
(relative-2-absolute (rest alon))))]))
add-to-each
;; add-to-each : number (listof number) -> (listof number)
;; リストalonの各要素に数nを加える
(define (add-to-each n alon)
(cond
[(empty? alon) empty]
[else (cons (+ (first alon) n)
(add-to-each n (rest alon)))]))
relative-2-absoluteの性能評価
• (define x (relative-2-absolute (list 0 ... N)))
評価にかかる時間がＮに比例しない．それ以上にかかる！
計算のトレース
•
•
•
•
•
•
３，５，２，１，６
６
１，７
２，３，９
５，７，８，１４
３，８，１０，１１，１７
• Ｎの２乗に比例した計算(加算とcons)が必要
問題点
• これまでの値を記憶していない
• 一つ前の値しかわからない
改良
•
•
•
•
•
•
•
•
３，５，２，１，６
３
３＋５＝８
８＋２＝１０
１０＋１＝１１
１１＋６＝１７
これをあわせて，
３，８，１０，１１，１７
rel-2-abs alon accu-dist
(define (rel-2-abs alon accu-dist)
(cond
Accumulator(集積変数)
[(empty? alon) empty]
[else (cons (+ (first alon) accu-dist)
(rel-2-abs (rest alon)
(+ (first alon) accu-dist)))]))
計算のトレース
•
•
•
•
•
= (rel-2-abs (list 3 2 7) 0)
= (cons 3 (rel-2-abs (list 2 7) 3))
= (cons 3 (cons 5 (rel-2-abs (list 7) 5)))
= (cons 3 (cons 5 (cons 12 (rel-2-abs empty 12))))
= (cons 3 (cons 5 (cons 12 empty)))
完成したプログラム
;; relative-2-absolute2 : (listof number) -> (listof number)
;; 相対的距離を示す値のリストから
;; 絶対的距離を示す値のリストに変換する
;; リストの最初の要素は原点からの距離
(define (relative-2-absolute2 alon)
(define (rel-2-abs alon accu-dist)
(cond
[(empty? alon) empty]
[else (cons (+ (first alon) accu-dist)
(rel-2-abs (rest alon) (+ (first alon) accu-dist)))]))
(rel-2-abs alon 0))
Reverse
リストの要素が逆転した新たなリストを作る
;; reverse : (listof X) -> (listof X)
;; to construct the reverse of alox
(define (reverse alox)
(cond
[(empty? alox) empty]
[else (make-last-item
(reverse (rest alox)) (first alox))]))
make-last-item
;; make-last-item : (listof X) X -> (listof X)
;;要素 an-x をリスト alox の最後につける
(define (make-last-item alox an-x)
(cond
[(empty? alox) (list an-x)]
[else (cons (first alox)
(make-last-item (rest alox) an-x))]))
Reverseの問題点
• 再帰を２重に(reverse とmake-last-item ）行って
いる
– (1 2 3 4 5 6)のreverse
•
•
•
•
•
•
()
(6)
(6 5)
(6 5 4)
(6 5 3 2)
(6 5 3 2 1)
; (make-last-item () 6)
; (make-last-item (6) 5)
; (make-last-item (6 5) 4)
…
Accumulatorを用いたreverse
•
•
•
•
•
•
•
•
(1 2 3 4 5 6)のreverse
()
(1)
(2 1)
(3 2 1)
(4 3 2 1)
(5 4 3 2 1)
(6 5 4 3 2 1)
reverse
; reverse : (listof X) -> (listof X)
;; to construct the reverse of alox
(define (reverse alox0)
;; accumulator is the reversed list of all those items
;; on alox0 that precede alox
(define (rev alox accumulator)
(cond
[(empty? alox) ...]
[else
... (rev (rest alox) ....... )
... ]))
(rev alox0 ...))
ACCを用いたreverse ー完成版
;; reverse : (listof X) -> (listof X)
;; to construct the reverse of alox
(define (reverse alox0)
;; accumulator is the reversed list of all those items
;; on alox0 that precede alox
(define (rev alox accumulator)
(cond
[(empty? alox) accumulator]
[else
(rev (rest alox) (cons (first alox) accumulator))]))
(rev alox0 empty))
Accumulatorを用いた再帰に変換
;; sum : (listof number) -> number
;; to compute the sum of the numbers on alon
(define (sum alon)
(cond
[(empty? alon) 0]
[else (+ (first alon) (sum (rest alon)))]))
ACCを用いたsum
;; sum : (listof number) -> number
;; to compute the sum of the numbers on alon0
(define (sum alon)
(define (sum-a alon accumulator)
(cond
[(empty? alon) accumulator]
[else (sum-a (rest alon) (+ (first alon) accumulator))]))
(sum-a alon 0))
計算のトレース：通常の再帰
•
•
•
•
•
•
•
•
(sum (list 10.23 4.50 5.27))
= (+ 10.23 (sum (list 4.50 5.27)))
= (+ 10.23 (+ 4.50 (sum (list 5.27))))
= (+ 10.23 (+ 4.50 (+ 5.27 (sum empty))))
= (+ 10.23 (+ 4.50 (+ 5.27 0)))
= (+ 10.23 (+ 4.50 5.27))
= (+ 10.23 9.77)
= 20.0
計算のトレース：ACCを用いた再帰
•
•
•
•
•
•
(sum (list 10.23 4.50 5.27))
= (sum-a (list 10.23 4.50 5.27) 0)
= (sum-a (list 4.50 5.27) 10.23)
= (sum-a (list 5.27) 14.73)
= (sum-a empty 20.0)
= 20.0
期末試験等
• １１月14日：演習のみ
– 課題の最終締め切りは11月22日（木）
• １１月21日：期末試験
– ３C１１３ 8:40〜11:10
– プログラミングの問題
• これまでの課題と同じ方法で提出
期末試験:注意事項
• 問題は紙で配布
• 個人のノートPCは、使わないこと
• 試験中に実行して良いソフトゥエア
– DrRacket, エディタ, メール送受信のためのソフトウェア
• ネットワークの使用は、解答の送受信に限る
– ウェブの閲覧は禁止（ウェブメールを除く）等

Download Report