跳到主要内容

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

标签：

Recursion

Author

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

Description

Scheme で次の手続きを定義せよ。補助手続きの使用を認める。

同じ長さのリスト $s=(a_1,\ldots,a_n)$ 、 $m=(b_1,\ldots,b_n)$ を受け取り、 $b_i$ が #f でない位置の $a_i$ だけを元の順で返す mask。
リスト s1, s2 を受け取り、s1 が s2 の部分列でなければ #f を返し、部分列なら (equal? s1 (mask s2 m)) が真となる、s2 と同じ長さの真偽値リスト m を返す subseq。

题目描述

用 Scheme 定义：(1) mask：保留列表 s 中掩码 m 对应元素不为 #f 的项，保持顺序；(2) subseq：若 s1 不是 s2 的子序列则返回 #f，否则返回一个布尔掩码，使 (mask s2 m) 等于 s1。

Kai

(1)

(define (mask s m)
  (cond ((null? s) '())
        ((car m) (cons (car s) (mask (cdr s) (cdr m))))
        (else (mask (cdr s) (cdr m)))))

(2)

(define (subseq s1 s2)
  (cond
    ((null? s1) (map (lambda (x) #f) s2))
    ((null? s2) #f)
    ((equal? (car s1) (car s2))
     (let ((r (subseq (cdr s1) (cdr s2))))
       (if r (cons #t r) #f)))
    (else
     (let ((r (subseq s1 (cdr s2))))
       (if r (cons #f r) #f)))))

先頭が一致した場合には、対応する要素を最も早い位置で選んでも、その後で使用できる位置は減らない。この貪欲選択とリスト長に関する帰納法により、存在するときには正しいマスクを返す。空リスト '() は Scheme では真として扱われ、失敗値 #f と区別される。

本页目录

Author
Description
Kai