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

标签：

• 递归

Author

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

Description

次の Scheme 手続きを定義せよ。補助手続きを用いてよい。

(1) リストの長さを返す length。

(2) 整数 $x$ と整数リスト $l$ に対して、$x$ がなければ #f、あれば最初の $x$ から始まる部分リストを返す mem=。例えば (mem= 1 '(3 1 4 1)) は (1 4 1)。

(3) 副作用のない整数値関数 $f$、整数 $x$、非負整数 $n$ を受け取り、$f^i(x)=f^j(x)$（$0\le i<j\le n$）となる最小の $i$ を返し、そのような組がなければ #f を返す find-loop。

例えば、定数関数 $f(x)=1$ に対して (find-loop f 1 0) は #f、(find-loop f 1 1) は $0$。$f(x)=x^2\bmod10$ に対する初期値 $2,n=10$ では $2$。$f(x)=\lfloor x/2\rfloor$、初期値 $255$ では $n=8$ なら #f、$n=9$ なら $8$。

题目描述

用 Scheme 定义以下过程，可使用辅助过程。

(1) length：返回列表长度。

(2) mem=：查找整数，若不存在返回 #f，否则返回从首次出现处开始的子列表。

(3) find-loop：输入无副作用的整数函数 $f$、初值 $x$ 和非负整数 $n$，返回满足 $f^i(x)=f^j(x)$、$0\le i<j\le n$ 的最小 $i$；若无则返回 #f。

例如常值函数 $1$、初值 $1$ 在 $n=0,1$ 时分别返回 #f,0；$x\mapsto x^2\bmod10$、初值 $2,n=10$ 返回 $2$；$x\mapsto\lfloor x/2\rfloor$、初值 $255$ 在 $n=8,9$ 时分别返回 #f,8。

Kai

(1)

(define (length l)
  (if (null? l) 0 (+ 1 (length (cdr l)))))

(2)

(define (mem= x l)
  (cond ((null? l) #f)
        ((= x (car l)) l)
        (else (mem= x (cdr l)))))

先頭から検索するため、最初に一致した位置からの部分リストを返す。

(3)

(define (orbit f x n)
  (if (= n 0) (list x)
      (cons x (orbit f (f x) (- n 1)))))

(define (scan-loop l i)
  (cond ((null? l) #f)
        ((mem= (car l) (cdr l)) i)
        (else (scan-loop (cdr l) (+ i 1)))))

(define (find-loop f x n)
  (scan-loop (orbit f x n) 0))

orbit は $x,f(x),\ldots,f^n(x)$ を順に並べる。scan-loop は $i=0,1,\ldots,n$ の順で、現在の値がそれより後に現れるかを mem= で判定する。従って条件を満たす最小の $i$ が返り、全て不一致なら #f が返る。