演算子の部分が複合式であるような式の場合、1.5節で説明 した「計算の順序」はどうなるか? 次の関数を例にとって説明せよ。 (define (a-plus-abs-b a b) ((if (> b 0) + -) a b))
(a-plus-abs-b (+ 1 2) (- 1 2)) という式を計算する順序で考える。 正規順序の場合、 1. (a-plus-abs-b (+ 1 2) (- 1 2)) 2. ((if (> (- 1 2) 0) + -) (+ 1 2) (- 1 2))) 3. ((if (> -1 0) + -) (+ 1 2) (- 1 2))) 4. ((if False + -) (+ 1 2) (- 1 2))) 5. (- (+ 1 2) (- 1 2))) 6. (- 3 -1 )) 7. 4 という順序で、また 適用的順序の場合、 1. (a-plus-abs-b (+ 1 2) (- 1 2)) 2. (a-plus-abs-b 3 -1 ) 3. ((if (> -1 0) + -) 3 -1)) 4. ((if False + -) 3 -1)) 5. (- 3 -1)) 6. 4 という順序で行われる。 例を見ると分かるように、a-plus-abs-b への適用の際には、計算の順序が違っ ているが、内側の ((if ...) a b) を適用する際には、どちらも演算子(if ...) の部分を先に計算して - に置換をしている。これは演算子が決まらない限り 置換が行えないので当然と言えば当然である。 (問題がいまいちでした。)
ある数 n の階乗(factorial)は、1 から n までを掛けた数である。より数
学的には、
1 n = 0の場合
n! = {
n・(n-1)! それ以外
のように定義される。
この階乗を求める Scheme の関数を作れ。
> (define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
;Evaluation took 0 mSec (0 in gc) 36 cells work, 47 bytes other
#<unspecified>
> (factorial 100)
;Evaluation took 0 mSec (0 in gc) 397 cells work, 2985 bytes other
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
>
(ほとんど数学的定義そのままですね。)
フィボナッチ数列(Fibonacci numbers)とは、
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
のように、「前 2 つの数の和」で作られる数の列である。
つまり、n 番目のフィボナッチ数は、
Fib(n) = 0 n = 0 の場合
1 n = 1 の場合
Fib(n-1)+Fib(n-2) それ以外
のように定義できる。n 番目のフィボナッチ数を求める関数を Scheme で定
義せよ。ただし、定義は一種類とは限らないので、複数考え付く場合は複数個
提出してよい。
> (define (fibonacci n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fibonacci (- n 1)) (fibonacci (- n 2))))))
;Evaluation took 0 mSec (0 in gc) 50 cells work, 43 bytes other
#<unspecified>
> (fibonacci 10)
;Evaluation took 0 mSec (0 in gc) 537 cells work, 33 bytes other
55
> (fibonacci 20)
;Evaluation took 150 mSec (33 in gc) 65677 cells work, 33 bytes other
6765
> (fibonacci 25)
;Evaluation took 1500 mSec (200 in gc) 728359 cells work, 33 bytes other
75025
>
(これはほんの一例です。)
ある数 n が素数かを調べる関数を定義せよ。(これも方法は一通りとは限ら ないので、複数の定義を提出してよい。) その際、sqrt の例にならって、複数の関数に分割して定義すること。 ヒント: (remainder m n)は、m を n で割った余りを求め る関数である。
;; 定義1:
;; m が n で割り切れるかをテストする
(define (divisible? m n)
(= 0 (remainder m n)))
;; m が n〜(m-1) のどの数でも割り切れないことをテストする
;; n = m であるか、
;; m が n で割り切れず、かつ、
;; m が (n+1)〜(m-1) のどの数でも割り切れない
(define (not-divisible-from m n)
(or (= m n)
(and (not (divisible? m n))
(not-divisible-from m (+ n 1)))))
;; m が素数かどうかを調べる
;; つまり、m が 2〜(m-1)のどの数でも割り切れないことをテストする
(define (prime? m)
(not-divisible-from m 2))
;; 定義2: 上の定義を、局所的な関数定義を使って書き直す
;; m が素数かどうかを調べる
;; つまり、m が 2〜(m-1)のどの数でも割り切れないことをテストする
(define (prime? m)
;; m が n で割り切れるかをテストする
(define (divisible? n)
(= 0 (remainder m n)))
;; m が n〜(m-1) のどの数でも割り切れないことをテストする
;; n = m であるか、
;; m が n で割り切れず、かつ、
;; m が (n+1)〜(m-1) のどの数でも割り切れない
(define (not-divisible-from n)
(or (= m n)
(and (not (divisible? n))
(not-divisible-from (+ n 1)))))
(not-divisible-from 2))
> (prime? 1009)
#t
> (prime? 1011)
#f
> (prime? 1013)
#t
>