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

标签：

• Recursion

Author

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

Description

Scheme または OCaml で次の手続きを定義せよ。添字は $0$ から始める。補助手続きの使用を認める。

1. 単項述語 p とリスト items に対し、p を満たす最小の添字を返し、なければ $-1$ を返す index。
2. p を満たすすべての添字を昇順リストで返す indices。
3. 二項述語 p に対し、$i<j$ かつ $p(a_i,a_j)$ を満たすすべての添字対 $(i,j)$ を辞書式昇順で返す indices2。Scheme では対を (i . j) で表す。

例：(index odd? '(2 7 1 8 2)) は 1、indices は '(1 2)、(indices2 < '(2 7 1 8 2)) は '((0 . 1) (0 . 3) (1 . 3) (2 . 3) (2 . 4)) を返す。

题目描述

用 Scheme 或 OCaml 编写：(1) 找到满足谓词的最小索引，无则返回 $-1$；(2) 返回所有满足条件的索引，升序排列；(3) 对二元谓词返回全部满足 $i<j$ 且 $p(a_i,a_j)$ 的索引对，按字典序排列。

Kai

Scheme を用いる。

(1)

(define (index p items)
  (let loop ((xs items) (i 0))
    (cond ((null? xs) -1)
          ((p (car xs)) i)
          (else (loop (cdr xs) (+ i 1))))))

(2)

(define (indices p items)
  (let loop ((xs items) (i 0))
    (cond ((null? xs) '())
          ((p (car xs))
           (cons i (loop (cdr xs) (+ i 1))))
          (else (loop (cdr xs) (+ i 1))))))

(3)

(define (indices2 p items)
  (define (row a i ys j)
    (cond ((null? ys) '())
          ((p a (car ys))
           (cons (cons i j) (row a i (cdr ys) (+ j 1))))
          (else (row a i (cdr ys) (+ j 1)))))
  (let loop ((xs items) (i 0))
    (if (null? xs) '()
        (append (row (car xs) i (cdr xs) (+ i 1))
                (loop (cdr xs) (+ i 1))))))

各手続きはリストを先頭から走査するので、(1) では最小の添字を、(2) では添字の昇順を得る。(3) は第一添字 $i$ の昇順に、各行を第二添字 $j$ の昇順で連結するため辞書式順序となる。各再帰で残りのリスト長が減少するので必ず停止する。