千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2021年8月実施 専門 B12

标签：

• Recursion

Author

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

Description

次の Scheme プログラムで、n は非負整数、x は整数、v は整数のリストとする。

(define (h n u)
  (if (= n 0) '() (cons (car u) (h (- n 1) (cdr u)))))
(define (d u v)
  (if (null? u) '()
      (if (member (car u) v) (d (cdr u) v)
          (cons (car u) (d (cdr u) v)))))
(define (s0 n x)
  (if (= n 0) '() (cons x (s0 (- n 1) (+ x 1)))))
(define (s1 n x v)
  (h n (d (s0 (+ n (length v)) x) v)))
(define (s2 n x v)
  (if (= n 0) '()
      (if (member x v) (s2 イ ロ v)
          (cons x (s2 ハ ニ v)))))

1. (s1 4 1 '(2 4 8)) の値を求めよ。
2. s2 が s1 と同じ結果を返すよう空欄を埋めよ。
3. s2 が停止すると仮定し、同じ結果になる理由を述べよ。
4. s2 が必ず停止する理由を述べよ。

题目描述

对上述 Scheme 程序：(1) 求示例表达式的值；(2) 填写四个递归参数，使 s2 与 s1 等价；(3) 在终止假设下证明等价；(4) 证明 s2 必然终止。

Kai

(1) '(1 3 5 6)。

(2) イ：n、ロ：(+ x 1)、ハ：(- n 1)、ニ：(+ x 1)。

(3) s0 は $x$ から連続する $n+\operatorname{length}(v)$ 個の整数を作り、d は v に含まれる整数を取り除く。取り除かれる異なる整数は高々 $\operatorname{length}(v)$ 個なので、少なくとも $n$ 個残る。h はその先頭 $n$ 個を返す。一方 s2 は $x,x+1,\ldots$ を順に調べ、v に入らないものを $n$ 個選ぶ。従ってどちらも同じ昇順リストを返す。

(4) 各再帰呼出しで $x$ は $1$ 増える。v に含まれる値を飛ばす回数は高々その相異なる要素数であり、それ以外の呼出しでは $n$ が $1$ 減る。従って高々 $n+\operatorname{length}(v)$ 回の再帰の後に $n=0$ となり停止する。