跳到主要内容

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

标签：

Author​

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

Description​

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

(define (merge-sort-push s ss)
  (cond ((null? ss) (list s))
        ((null? (car ss)) (cons s (cdr ss)))
        (else (cons '() (merge-sort-push (merge s (car ss)) (cdr ss))))))
(define (fold-left f c s)
  (if (null? s) c (fold-left f (f c (car s)) (cdr s))))
(define (merge-sort-sub s)
  (fold-left (lambda (ss x) (merge-sort-push (list x) ss)) '() s))
(define (merge-sort s)
  (fold-left merge '() (merge-sort-sub s)))

(1) 整数リスト二つを受け取り、出現回数を保存して結合し、入力がともに昇順なら出力も昇順となる merge を定義せよ。整数の大小比較回数は両リスト長の和以下とする。(2) (merge-sort-sub '(3 1 4)) と (merge-sort-sub '(3 1 4 1 5 9)) の値を求めよ。(3) 長さ nn の入力に対し、結果が (s1,…,sk)(s_1,\ldots,s_k) となるとき、kk と各 ni=∣si∣n_i=|s_i| を nn で特徴付けよ。

题目描述​

给定上述按二进制进位方式组织的归并排序程序。(1) 实现保存元素重数的归并函数，两个输入有序时输出有序，比较次数不超过总长度。(2) 求两个给定中间结果。(3) 用输入长度刻画返回列表的层数和每层子列表长度。

Kai​

(1)

(define (merge s1 s2)
  (cond ((null? s1) s2)
        ((null? s2) s1)
        ((<= (car s1) (car s2))
         (cons (car s1) (merge (cdr s1) s2)))
        (else
         (cons (car s2) (merge s1 (cdr s2))))))

比較のたびに小さい先頭要素を一つ出力する。従って整列性と各要素の個数が保たれる。各比較で残りの総要素数が1減るので、比較回数は総要素数以下である。

(2)

((4) (1 3))
(() (5 9) (1 1 3 4))

前者は3要素を長さ 1,21,2 に分け、後者は6要素を長さ 0,2,40,2,4 に分けたものである。

(3) n=0n=0 なら k=0k=0。n>0n>0 なら

k=⌊log⁡2n⌋+1,ni=2i−1(⌊n2i−1⌋ mod 2).\boxed{k=\lfloor\log_2n\rfloor+1,\qquad n_i=2^{i-1}\left(\left\lfloor\frac{n}{2^{i-1}}\right\rfloor\bmod2\right)}.

すなわち nn の第 i−1i-1 二進桁が1なら長さ 2i−12^{i-1}、0なら空リストである。新要素は長さ1のリストとして入る。対応する段が空ならそこに置き、既に埋まっていれば同じ長さの二リストを併合して長さを倍にし、次の段へ送る。この動作は二進数への1の加算と一致するため、帰納法で上式が成立する。

本页目录