跳到主要内容

千葉大学 理学研究科 基盤理学専攻 数学・情報数理学コース 2016年8月実施 専門 B12

标签：

Author​

祭音Myyura (co-authored with GPT 6 Astra)

Description​

次の Scheme プログラムを考える。

(define (enumerate-tree tree)
  (cond ((null? tree) '())
        ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))
(define t0 (list 1 (list 2 (list 3 4) 5)))

(1) (enumerate-tree t0) の値を記せ（答えのみ）。

(2) この評価中に (a) list 経由、(b) append 経由で呼ばれる cons の回数を理由とともに答えよ。list は引数の個数だけ、append は第 11 引数の長さだけ cons を呼ぶとする。

(3) 数値・空リスト・対からなるデータ tt と数値リスト ll に対し、(prepend-leaves t l) が (append (enumerate-tree t) l) と等しくなる手続きを定義せよ。(prepend-leaves t '()) の cons 回数は (2)(a) と同じ葉数に等しく、対を変更する副作用を使わないこと。

题目描述​

考虑上述将树的叶子依次列出的 Scheme 程序。

(1) 求 (enumerate-tree t0) 的值，不必解释。

(2) 计算本次求值经由 list、append 调用 cons 的次数并解释。假定 list 每个参数使用一次 cons，append 使用次数为首参数列表长度。

(3) 定义 prepend-leaves，将树 tt 的所有数值叶子按相同顺序置于列表 ll 前。要求结果等于 (append (enumerate-tree t) l)，cons 总次数等于树的叶数，且不得修改已有的对。

Kai​

(1)​

(1 2 3 4 5)

(2)​

(a) 数値の葉が五つあり、各葉で (list tree) が一回呼ばれて cons を一回使うので、合計 55 回。

(b) 各対について、第 11 成分の葉の数だけ append が cons を呼ぶ。外側の二つの対の寄与は 1,41,4、リスト (2 (3 4) 5) 内の三つの対では 1,2,11,2,1、リスト (3 4) 内の二つの対では 1,11,1。従って

1+4+1+2+1+1+1=111+4+1+2+1+1+1=11

回。

(3)​

(define (prepend-leaves t l)
  (cond ((null? t) l)
        ((not (pair? t)) (cons t l))
        (else (prepend-leaves
               (car t)
               (prepend-leaves (cdr t) l)))))

空リストでは何も追加せず、数値ではその葉を一回の cons で追加する。対ではまず後半の葉を ll の前に置き、その前に前半の葉を置くので順序も正しい。構造に関する帰納法で要求された等式が成立する。

cons は数値の葉に対してだけ一回ずつ呼ばれ、既存の対への変更は行わない。従って残りの二条件も満たす。

本页目录