問題文

Using the results of exercises 1.16 and 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.

解答案

まだすぐ反復的プロセスを書けるほどには慣れていない...けど、こういう感じだよね。

(define (even? n)
  (= (remainder n 2) 0))

(define (double x)
  (+ x x))

(define (halve x)
  (/ x 2))

(define (*-iter a b n)
  (cond ((= b 0) n)
        ((even? b) (*-iter (double a) (halve b) n))
        (else (*-iter a (- b 1) (+ a n)))))

(define (* a b)
  (*-iter a b 0))

問題文

The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure:

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.

解答案

こうかな。

(define (even? n)
  (= (remainder n 2) 0))

(define (double x)
  (+ x x))

(define (halve x)
  (/ x 2))

(define (* a b)
  (cond ((= b 0) 0)
        ((even? b) (* (double a) (halve b)))
        (else (+ a (* (double a) (halve (- b 1)))))))

;; テスト
(* 3 1)
(* 3 2)
(* 3 3)
(* 3 4)
(* 3 5)
(* 3 6)

問題文

Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product a is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

解答案

"successive squaring"は日本語版のSICPでは逐次平方と訳されているワードかな。

こんな感じでどうでしょう。

(define (square x) (* x x))

(define (even? n)
  (= (remainder n 2) 0))

(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (expt-iter (square b) (/ n 2) a))
        (else (expt-iter b (- n 1) (* b a)))))

;; テスト
(expt 2 0)
(expt 2 1)
(expt 2 2)
(expt 2 3)
(expt 2 4)
(expt 2 5)
(expt 2 6)
(expt 2 7)
(expt 2 8)

問題文

The sine of an angle (specified in radians) can be computed by making use of the approximation sin x x if x is sufficiently small, and the trigonometric identity

to reduce the size of the argument of sin. (For purposes of this exercise an angle is considered ``sufficiently small'' if its magnitude is not greater than 0.1 radians.) These ideas are incorporated in the following procedures:

(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))

• a. How many times is the procedure p applied when (sine 12.15) is evaluated?
• b. What is the order of growth in space and number of steps (as a function of a) used by the process generated by the sine procedure when (sine a) is evaluated?

解答案

a. の方はtraceすればすぐに分かる。5回。

;; 問題文のコード
(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (sine (/ angle 3.0)))))

;; traceの仕込み
(use slib)
(require 'trace)
(trace p)

;; 実行 (pは5回CALLされる)
(sine 12.15)
;; CALL p 0.049999999999999996
;; RETN p 0.1495
;; CALL p 0.1495
;; RETN p 0.4351345505
;; CALL p 0.4351345505
;; RETN p 0.9758465331678772
;; CALL p 0.9758465331678772
;; RETN p -0.7895631144708228
;; CALL p -0.7895631144708228
;; RETN p -0.39980345741334
;; -0.39980345741334

収束スピードは(1/3)nだからステップ数はlog(n)のオーダで、スペースはステップ数と比例するから、これもやっぱりlog(n)のオーダ...かな。

問題文

Draw the tree illustrating the process generated by the count-change procedure of section 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?

解答案

section 1.2.2のソースは次の通り:

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

これで (count-change 11) を評価する、と。

脳内でツリーを描けているけれど、それをブログに載せられる形式に整えるのが難しいので、この問題は残念ながらパス。ステップ数はで、スペースも...かな。

おまけ

両替コインプログラムをPythonで書いてみたので貼っておく。

def count_change(amount):
    return cc(amount, 5)

def cc(amount, kinds_of_coins):
    if (0 == amount):
        return 1
    elif (amount < 0 or 0 == kinds_of_coins):
        return 0
    else:
        return \
            cc(amount, kinds_of_coins - 1) + \
            cc((amount - first_denomination(kinds_of_coins)), kinds_of_coins)

def first_denomination(kinds_of_coins):
    if (1 == kinds_of_coins):
        return 1
    elif (2 == kinds_of_coins):
        return 5
    elif (3 == kinds_of_coins):
        return 10
    elif (4 == kinds_of_coins):
        return 25
    elif (5 == kinds_of_coins):
        return 50

print count_change(100)

問題文

Prove that Fib(n) is the closest integer to , where . Hint: Let . Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that Fib(n) = .

解答案

ノートに証明を書いたけれど、数式が長くなるので省略。

問題文

The following pattern of numbers is called Pascal's triangle.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. Write a procedure that computes elements of Pascal's triangle by means of a recursive process.

解答案

パスカルの三角形のn行m列目はで表現されるから、コンビネーションを計算するコードを書けばオシマイ。

(define (factorial n)
  (if (< n 2)
      1
      (* n (factorial (- n 1)))))

(define (pt n m)
  (/ (factorial n) (factorial (- n m))))

問題文

A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n>=3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.

解答案

まずは再帰的プロセス。これは楽勝。

(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3))))))

次に反復的プロセス。再帰的プロセス=>反復的プロセスの変換に脳内時間を取られる。

(define (f n)
  (if (< n 3)
      n
      (f-iter 2 1 0 n)))

(define (f-iter a b c n)
  (if (= n 2)
      a
      (f-iter (+ a (* 2 b) (* 3 c))
              a
              b
              (- n 1))))

問題文

The following procedure computes a mathematical function called Ackermann's function.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

What are the values of the following expressions?

(A 1 10)
(A 2 4)
(A 3 3)

Consider the following procedures, where A is the procedure defined above:

(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))

Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n. For example, (k n) computes .

解答案

アッカーマン関数についての問題。アッカーマン関数についての説明はWikipediaの通りで、実際に (f n), (g n), (h n) の意味もWikipediaの通り。

(f n) = 2 * n

(g n) =

(h n) =

問題文

Each of the following two procedures defines a method for adding two positive integers in terms of the procedures inc, which increments its argument by 1, and dec, which decrements its argument by 1.

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5). Are these processes iterative or recursive?

解答案

一つ目の方は再帰的プロセスになる。(inc (+ (dec a) b))のオペランドに+があるから。

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(+ 3 3) ;=> 6
;; (inc (+ 2 3))
;; (inc (inc (+ 1 3)))
;; (inc (inc (inc (+ 0 3))))
;; (inc (inc (inc 3)))
;; (inc (inc 4))
;; (inc 5)
;; 6

２つ目の方は反復的プロセスになる。(+ (dec a) (inc b))のオペレータが+だから。

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

(+ 3 3) ;=> 6
;; (+ 2 4)
;; (+ 1 5)
;; (+ 0 6)
;; 6