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

标签：

• 递归

Author

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

Description

次の Scheme 手続きを考える。整数演算のあふれはないものとする。

(define (bl2n bl)
  (if (null? bl) 0
      (+ (if (car bl) 1 0) (* 2 (bl2n (cdr bl))))))

(1) 真偽値のリストに対して返す値を説明せよ。

(2) 任意の非負整数 $n$ に対して (bl2n (n2bl n)) が $n$ になる n2bl を定義せよ。整数除算は quotient, remainder を用いよ。

以下では bl2n, n2bl、数値および数値演算を一切使わずに定義せよ。前問の手続きや補助手続きを使ってよい。

(3) 真偽値リストの表す整数を $1$ 増やす bli。

(4) 二つの真偽値リストの表す整数を加える bla。

(5) 二つの真偽値リストの表す整数を掛ける blm。

题目描述

考虑上面的 Scheme 过程 bl2n，假定整数不溢出。

(1) 说明它对布尔值列表返回什么数。

(2) 定义 n2bl，使任意非负整数 $n$ 满足 (bl2n (n2bl n)) = n，除法使用 quotient 和 remainder。

(3)–(5) 不得使用数值、数值运算以及 bl2n,n2bl；可以使用前问定义和辅助过程。依次定义布尔列表上的加一 bli、加法 bla、乘法 blm。

Kai

(1)

#t を $1$、#f を $0$ とした、最下位ビットから順に並ぶ二進表現の値を返す。リストが $(b_0,\ldots,b_{k-1})$ なら値は $\sum_{j=0}^{k-1}b_j2^j$。空リストは $0$ を表す。

(2)

(define (n2bl n)
  (if (= n 0) '()
      (cons (= (remainder n 2) 1)
            (n2bl (quotient n 2)))))

$n=2\lfloor n/2\rfloor+(n\bmod2)$ より正しく、商が小さくなるので停止する。

(3)

(define (bli a)
  (cond ((null? a) (list #t))
        ((car a) (cons #f (bli (cdr a))))
        (else (cons #t (cdr a)))))

最下位ビットが真なら繰り上がりを上位へ送り、偽なら真に変える。

(4)

(define (bla a b)
  (cond ((null? a) b)
        ((null? b) a)
        ((and (car a) (car b))
         (cons #f (bli (bla (cdr a) (cdr b)))))
        ((or (car a) (car b))
         (cons #t (bla (cdr a) (cdr b))))
        (else (cons #f (bla (cdr a) (cdr b))))))

下位ビットの和が $0,1,2$ の各場合に対応し、和が $2$ の場合だけ上位に bli で繰り上げる。リストの長さに関する帰納法で正しさが従う。

(5)

(define (blm a b)
  (if (null? a) '()
      (let ((shifted (cons #f (blm (cdr a) b))))
        (if (car a) (bla b shifted) shifted))))

$a$ の値を $a_0+2a'$ とすると、積は $a_0b+2(a'b)$ である。cons #f は二倍を表し、下位ビットが真の場合だけ $b$ を加えている。再帰のたびに $a$ の長さが減るので停止する。