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

标签：

• String-Parsing
• Higher-Order-Functions
• Catalan-Number

Author

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

Description

次の Scheme プログラムについて答えよ。部分文字列は元の文字列と始点・終点（終点を含まない）のリスト (s l h) で表す。

(define (concat ll)
  (if (null? ll) '() (append (car ll) (concat (cdr ll)))))
(define (substr s l h) (list s l h))
(define (str s) (car s))
(define (low s) (cadr s))
(define (high s) (caddr s))
(define (len s) (- (high s) (low s)))
(define (inclow n s) (substr (str s) (+ (low s) n) (high s)))
(define (inchigh n s) (substr (str s) (low s) (+ (high s) n)))
(define (dechigh n s) (substr (str s) (low s) (- (high s) n)))
(define (output r s) (cons r s))
(define (result o) (car o))
(define (next o) (cdr o))
(define (rfun1 r) 1)
(define (rfun2 r1 r2) (+ r1 r2))
(define (a lit)
  (lambda (s)
    (let ((n (string-length lit)))
      (if (and (<= n (len s))
               (string=? (substring (str s) (low s) (+ (low s) n)) lit))
          (list (output (rfun1 lit) (inclow n s))) '()))))
(define (seq p1 p2)
  (lambda (s)
    (let ((f (lambda (rs1)
               (map (lambda (rs2)
                      (output (rfun2 (result rs1) (result rs2)) (next rs2)))
                    (p2 (next rs1))))))
      (concat (map f (p1 s))))))
(define (alt p1 p2) (lambda (s) (append (p1 s) (p2 s))))
(define (pE s) ((alt (seq (a "+") (seq pE pE)) (a "")) s))
(define (run p s)
  (filter (lambda (rs) (= (low (next rs)) (high (next rs))))
          (p (list s 0 (string-length s)))))

(1) ((a "1") '("12" 0 2))、(2) ((seq (a "1") (a "2")) '("12" 0 2))、(3) (run pE "++") の評価結果を記せ。(4) $s_n$ を + が $n$ 個並ぶ文字列とし、$a_n$ を (length (run pE s_n)) の値とする。$a_n$ を $a_i$（$0\le i<n$）で表し、理由を述べよ。

题目描述

阅读上述 Scheme 程序，子串表示为原字符串、起点和不包含的终点所组成的列表。(1)(2)(3) 求给定表达式的结果。(4) 对包含 $n$ 个加号的字符串，令完全解析的结果个数为 $a_n$，用前面的 $a_i$ 写出递推式并说明理由。

Kai

(1)

((1 "12" 1 2))

(2)

((2 "12" 2 2))

(3) pE は文法 $E\to+EE\mid\varepsilon$ の全解析を列挙する。++ には、根の左部分木にもう一つの + がある場合と、右部分木にある場合の二通りがある。いずれも + が2個、空文字が3個で結果値は $5$ なので

((5 "++" 2 2) (5 "++" 2 2))

(4) $a_0=1$。$n\ge1$ では最初の + の後の $n-1$ 個を、左の $E$ に $i$ 個、右の $E$ に $n-1-i$ 個割り当てる。各組の解析は独立に選べるので

$$\boxed{a_n=\sum_{i=0}^{n-1}a_i a_{n-1-i}\quad(n\ge1),\qquad a_0=1}.$$

これは Catalan 数の漸化式である。