[SICP] 問題 1.37 : 連分数

a. 無限の連分数(continued fraction)は
の形の式である. 例えばNiとDiがすべて1の無限連分数展開が1/φになることが示せる. φは(1.2.2節で示した)黄金比. 無限連分数の近似値のとり方の一つは, 与えられた項数で展開を中断することで, そういう中断--- k項有限連分数(k-term finite continued fraction)という---は
の形である. nとdを一引数(項の添字i)で連分数の項のNiとDiを返す手続きとする. (cont-frac n d k)がk項有限連分数を計算するような手続きcont-fracを定義せよ.

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           k)

のkの順次の値で1/φの近似をとり, 手続きを調べよ. 4桁の精度の近似を得るのに, kはどのくらい大きくしなければならないか.

b. cont-fracが再帰的プロセスを生成するなら, 反復的プロセスを生成するものを書け. 反復的プロセスを生成するなら, 再帰的プロセスを生成するものを書け.

連分数を求める手続きを定義します.

;; 再帰的プロセスを生成
(define (cont-frac-r n d k)
  (define (iter i)
    (if (> i k)
        0
        (/ (n i)
           (+ (d i) (iter (+ i 1))))))
  (iter 1))

;; 反復的プロセスを生成
(define (cont-frac-i n d k)
  (define (iter i result)
    (if (= i 0)
        result
        (iter (- i 1)
              (/ (n i)
                 (+ (d i) result)))))
  (iter k 0))

(define (phi-r k)
  (/ 1 (cont-frac-r (lambda (i) 1.0)
                    (lambda (i) 1.0)
                    k)))

(define (phi-i k)
  (/ 1 (cont-frac-i (lambda (i) 1.0)
                    (lambda (i) 1.0)
                    k)))

再帰的プロセスを生成する手続きは, 上の方から計算しています. 反復的プロセスを生成する手続きは, 下の方から計算するようにしています.

黄金比Φの計算をしてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (phi-r 15)
1.6180327868852458
> (phi-i 15)
1.6180327868852458
> 

kの値を15にすれば良さそうです.

[SICP] 問題 1.36 : x^x=1000

問題1.22で示した基本のnewlineとdisplayを使い, 生成する近似値を順に印字するようfixed-pointを修正せよ. 次にx log(1000)/log(x)の不動点を探索することで, xx = 1000の解を見つけよ. (自然対数を計算するSchemeの基本log手続きを使う.) 平均緩和を使った時と使わない時のステップ数を比べよ. ({ fixed-pointの予測値を1にして始めてはいけない. log(1)=0による除算を惹き起すからだ.)

近似値を表示するための処理をfixed-pointに追加しなくてはなりません. 追加する場所は, 内部手続tryが適切でしょう. 修正した手続きは次のとおりです.

(define (average x y)
  (/ (+ x y) 
     2))

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (display guess)
      (newline)
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

x^x=1000を満たすxを求めてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fixed-point (lambda (x) (/ (log 1000) (log x))) 
               2.0)
2.0
9.965784284662087
3.004472209841214
6.279195757507157
3.759850702401539
5.215843784925895
4.182207192401397
4.8277650983445906
4.387593384662677
4.671250085763899
4.481403616895052
4.6053657460929
4.5230849678718865
4.577114682047341
4.541382480151454
4.564903245230833
4.549372679303342
4.559606491913287
4.552853875788271
4.557305529748263
4.554369064436181
4.556305311532999
4.555028263573554
4.555870396702851
4.555315001192079
4.5556812635433275
4.555439715736846
4.555599009998291
4.555493957531389
4.555563237292884
4.555517548417651
4.555547679306398
4.555527808516254
4.555540912917957
4.555532270803653
> (expt 2 3)
8
> (expt 4.555532270803653 4.555532270803653)
999.9913579312362
> 

期待した結果が得られているようです.

平均緩和を使ってみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 
               2.0)
2.0
5.9828921423310435
4.922168721308343
4.628224318195455
4.568346513136242
4.5577305909237005
4.555909809045131
4.555599411610624
4.5555465521473675
4.555537551999825
> 

ステップ数が1/3以下になっています.

[SICP] 問題 1.35 : 不動点の探索による黄金比の計算

(1.2.2節の)黄金比φが変換 x → 1 + 1/x の不動点であることを示し, この事実を使いfixed-point手続きによりφを計算せよ.

黄金比の定義は次のとおりです.
　　φ² = φ + 1
この両辺をφで割ります.
　　φ = 1 + 1/φ
この結果から,
　　変換 x → 1 + 1/x
が得られます.

不動点を求める手続きは次のとおりです.

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

実行してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fixed-point (lambda (x) (+ 1 (/ 1 x)))
               1.0)
1.6180327868852458
> 

p.21から黄金比の値は約1.6180ですから, 求める結果が得られています.

[SICP] 問題 1.34 : (f f)の評価

手続き

(define (f g)
  (g 2))

を定義したとする. その時

(f square)
4

(f (lambda (z) (* z (+ z 1))))
6

解釈系に組合せ(f f)を(意地悪く)評価させるとどうなるか. 説明せよ.

問題文の手続きを定義して実行してみます. 手続きは次の通り.

(define (f g)
  (g 2))

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

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (f square)
4
> (f (lambda (z) (* z (+ z 1))))
6
> (f f)
. . application: not a procedure;
 expected a procedure that can be applied to arguments
  given: 2
  arguments...:
   2
> 

(f f)を評価するとエラーが生じています. その理由を考えます.

手続きfの定義から(f f)を評価した場合の置き換えは次のようになります.

  (f f)
= (f 2)
= (2 2)

「２」は手続きではないのでエラーが生じます.

[SICP] 1.2.6 : expmodでbaseのexp乗をmで割った余りが求まる理由

baseのexp乗をmで割った余りを求める手続きexpmodは次のような定義になります.

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

法演算について馴染みがないと, なぜ, この手続で余りが求まるか分からないと思います. ここで簡単に計算の仕組みを説明します.

まず, 整数aをmで割った余りをr, 整数bをmで割った余りをtとします. すると整数aとbは次のように表現できます.

   a = qm + r
   b = sm + t

このaとbの和をmで割った余りを求めます.

   a + b = (qm + r) + (sm + t)
         = (q + s)m + (r + t)

(q + s)mはmで割り切れるので, a + bをmで割った余りはr+tをmで割った余りと等しくなります.

aにある整数cを掛けた値をmで割った余りも求めてます.

   ca = cqm + cr

caをmで割った余りはcrをmで割った余りと等しくなります.

続けて, aとbの積をmで割った余りを求めます.

   ab = (qm + r)(sm + t)
      = qsm^2 + (qt + rs)m + rt

abをmで割った余りはrtをmで割った余りと等しくなります.

積についての結果から,　aのx乗をmで割った余りはrのx乗をmで割った余りと等しくなります.

ここで, 手続きの定義に戻り, baseのexp乗をmで割った余りを考えます.

１）expが偶数のときを考えます.

baseの(exp/2)乗をmで割った余りをrとします. 上で計算した結果から, rの2乗をmで割った余りは, baseのexp乗をmで割った余りと等しくなります.

2) expが奇数のときを考えます.

baseの(exp-1)乗をmで割った余りをrとします. 上で計算した結果から, base*rをmで割った余りは, baseのexp乗をmで割った余りと等しくなります.

これらの結果から, 手続きexpmodによりbaseのexp乗をmで割った余りを求められることが分かります.

[筋トレ] 2014.11.17の週

今週の記録です。
11/1７（月）73.65kg

　プッシュアップ　１７、　４　　（膝をついた状態）
　ナロースタンス　　５、　６　　（両手の間を拳一つ開けた状態）
　アームカール　　１５、１２　　（5kgのダンベル）

11/1８（火）73.65kg

　ジョグ　　　　　3.4km 25'22"

11/1９（水）74.45kg

　ランジ（左）　　１５、　６　　
　ランジ（右）　　１５、１０　　
　リアレイズ　　　１４、　８　　（5kgの鉄アレイ）

　レッグレイズ　　１５、１０

11/２０（木）73.30kg

　プッシュアップ　１７、　７　　（膝をついた状態）
　ナロースタンス　　６、　５　　（両手の間を拳一つ開けた状態）
　アームカール　　１５、１５　　（5kgのダンベル）

11/２１（金）73.65kg

　休み

11/２２（土）74.80kg
　休み

11/２３（日）75.10kg

　ジョグ　　　　　4.1km 29'38"

　ランジ　　　　　４０、３０歩

スクワットが効かないのでランジに変更しました。

娘の相手をしなくても良くなってきたので、ジョギングできるようになりました＼(^o^)／

体を慣らすために、かなりゆっくりペースです。

三菱鉛筆のスタイルフィットを使いやすくする方法

三菱鉛筆のスタイルフィットは、ゲルインクボールペンの中でも使いやすい方だと思います。同じ三菱鉛筆のシグノよりも文字を書いた時の線の広がりが抑えられており、性能が良いように感じています。

しかし、スタイルフィットのホルダーは使いにくい(~_~;)

• ペンを持つところにゴムが付いていないので、手の脂がつくと滑りやすい。
• ちょっとした衝撃でペン先が戻ってしまう。

色々と試した結果、パイロットの4色ボールペンであればスタイルフィットの芯を使えました＼(^o^)／

[SICP] 問題 1.27 : カーマイケル数

脚注47のCarmichael数が本当にFermatテストをだますことを示せ. それには整数nをとり, a < nなるすべてのaで, aⁿがnを法としてaの合同になるかどうか見る手続きを書き, Carmichael数でその手続きを使ってみる.

a < nを満たす正の整数aについて, expmodを用いてaⁿがnを法としてaと合同になるか調べます. 手続きは次のとおりです.

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

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

(define (pass-fermat-test? n)
  (define (loop a)
    (or (= a n)
        (and (= (expmod a n n) a)
             (loop (+ a 1)))))
  (loop 1))

評価してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (pass-fermat-test? 561)
#t
> (pass-fermat-test? 1105)
#t
> (pass-fermat-test? 1729)
#t
> (pass-fermat-test? 2465)
#t
> (pass-fermat-test? 2821)
#t
> (pass-fermat-test? 6601)
#t
> (pass-fermat-test? 6605)
#f
> (pass-fermat-test? 6607)
#t
> 

脚注のカーマイケル数は, フェルマー・テストをパスしています. 間違えて, 必ず#tを返す手続きを実装していては困りますので, 合成数6605では#fが返ってくることを確認しています.

[SICP] 問題 1.26 : expmodの計算に必要なステップ数

Louis Reasonerは問題1.24がなかなかうまくいかなかった. 彼の fast-prime?はprime?よりずっと遅いようであった. Louisは友人のEva Lu Atorに助けを求めた. Louisのプログラムを見ていると, squareを呼び出す代りに乗算を陽に使うように変っていた.

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (* (expmod base (/ exp 2) m)
                       (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

「違いが分らん」とLouis, 「分る」とEvaがいった. 「手続きをこのように書き替えたので, Θ(log n)のプロセスをΘ(n)のプロセスにしてしまった.」 説明せよ.

引数expの値に注目して, 手続きが生成するプロセスを図示してみます. まず, squareを用いた場合.

13 -- 12 -- 6 -- 3 -- 2 -- 1 -- 0

まず, squareを用いず, 乗算を用いた場合.

13 -- 12 -- 6 -- 3 -- 2 -- 1 -- 0
       |    |         |
       |    |         + -- 1 -- 0
       |    |
       |    + -- 3 -- 2 -- 1 -- 0
       |              |
       |              + -- 1 -- 0
       |
       + -- 6 -- 3 -- 2 -- 1 -- 0
            |         |
            |         + -- 1 -- 0
            |
            + -- 3 -- 2 -- 1 -- 0
                      |
                      + -- 1 -- 0

このように, squareを用いずに乗算を用いた場合, expの値が偶数の場合, expmodを２回呼び出しています. そのため, Θ(log n)のプロセスをΘ(n)のプロセスにしてしまい, 計算に時間がかかるようになります.

[SICP] 問題 1.25 : expmodの必要性

Alyssa P. Hackerはexpmodを書くのに多くの余分なことをやったと不満で, 結局べき乗の計算法は知っているから

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

と単純に書ける筈だといった. これは正しいか. これも高速素数テストと同じに使えるか, 説明せよ.

テキストp.29の脚注48にあるように, ここでは200桁の整数が素数であるかどうかを問題としています. expmodの引数であるbaseやexpに200桁の整数が与えられるため, fast-exptで計算することは困難であり現実的ではありません. そのため, p.28のexpmodの定義が必要となります.

[SICP] 問題 1.24 : フェルマー・テスト

問題1.22のtimed-prime-test手続きをfast-prime?(Fermat法参照) を使うように変え, その問題で見つけた12個の素数をテストせよ. FermatテストはΘ(log n)の増加なので, 1,000,000近くの素数をテストする時間を1000近くの素数をテストする時間と比べ, どの位と予想するか. データはその予想を支持するか. 違いがあれば説明出来るか.

フェルマーの小定理を用いた素数性のテストをする手続きを定義します. 手続きrandomの引数の範囲に制限があるため, 少し小細工をしています.

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

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))  

(define (rnd n)
  (remainder (* (random (remainder n 4294967087))
                (random (remainder n 4294967087)))
             n))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (rnd (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

;; 素数を求めるために必要な時間を計測する
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (current-milliseconds)))

(define (start-prime-test n start-time)
  (if (fast-prime? n 10000)
      (report-prime (- (current-milliseconds) start-time))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

(define (search-for-primes start end)
  (cond ((< start end)
         (timed-prime-test start)
         (search-for-primes (+ start 1) end))
        (else 
         (newline)
         (display "end"))))
 

素数を求めてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (search-for-primes 100000000000000 100000000000100)
100000000000031 *** 325
100000000000067 *** 344
100000000000097 *** 312
end
> (search-for-primes 1000000000000000 1000000000000200)
1000000000000037 *** 342
1000000000000091 *** 351
1000000000000159 *** 340
end
> (search-for-primes 10000000000000000 10000000000000100)
10000000000000061 *** 390
10000000000000069 *** 375
10000000000000079 *** 366
end
> 

この程度のデータでは, 何も言えそうにありません.

[筋トレ] 2014.11.10の週

今週の記録です。
11/10（月）

　娘の腸炎が伝染って休み

11/11（火）

　休み

11/12（水）72.95kg

　休み

11/13（木）73.40kg
　スクワット　　　２０、２０　　（5kgの鉄アレイ）
　リアレイズ　　　１０、　８　　（5kgの鉄アレイ）
　レッグレイズ　　１５、１０

11/14（金）73.55kg

　プッシュアップ　２０、１０　　（膝をついた状態）
　ナロースタンス　　３、　５　　（両手の間を拳一つ開けた状態）
　アームカール　　１２、　９　　（5kgのダンベル）

11/15（土）74.00kg
　娘の看病のため休み

11/16（日）74.45kg
　スクワット　　　３０、３０　　（5kgの鉄アレイ）
　リアレイズ　　　１２、１０　　（5kgの鉄アレイ）
　レッグレイズ　　１６、１２

娘の腸炎が伝染ってしまい、嘔吐と発熱に苦しめられました(~_~;)

ほぼ２日間、絶食したので体重は減りました。週の後半には順調に回復しました＼(^o^)／

[SICP] 問題 1.23 : 素数性を判定する数を奇数に限定

本節の初めのsmallest-divisorは多くの不要な計算をする: 数が2で割り切れるか調べた後は, より大きい偶数で割り切れるか調べるのは無意味である. test-divisorが使う値は, 2, 3, 4, 5, 6, ...ではなく, 2, 3, 5, 7, 9, ...であるべきだ. この変更を実装するため, 入力が2なら3 を返し, そうでなければ入力に2足したものを返す手続きnextを定義せよ. smallest-divisorを(+ test-divisor 1)ではなく, (next test-divisor)を使うように修正せよ. このように修正した smallest-divisorにしたtimed-prime-testで, 問題1.22で見つけた12 個の素数をテストせよ. この修正はテストのステップを半分にしたので, 二倍速く走ることが期待される. この期待は確められるか. そうでなければ, 得られた二つのアルゴリズムの速度の比はどうであったか. それが2と違う事情を説明せよ.

問題文にあるように手続きを修正します.

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

(define (divides? a b)
  (= (remainder b a) 0))

;; 問題文により追加
(define (next n)
  (if (= n 2)
      3
      (+ n 2)))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next test-divisor)))))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (prime? n)
  (= n (smallest-divisor n)))

;; 素数を求めるために必要な時間を計測する
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (current-milliseconds)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (current-milliseconds) start-time))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

(define (search-for-primes start end)
  (cond ((< start end)
         (timed-prime-test start)
         (search-for-primes (+ start 1) end))
        (else 
         (newline)
         (display "end"))))
 

問題 1.22で求めた12個の素数を判定するための時間を計測します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (search-for-primes 100000000000000 100000000000100)
100000000000031 *** 624  (939)
100000000000067 *** 571  (1397)
100000000000097 *** 598  (949)
end
> (search-for-primes 1000000000000000 1000000000000200)
1000000000000037 *** 1907  (2891)
1000000000000091 *** 1965  (2928)
1000000000000159 *** 1877  (2919)
end
> (search-for-primes 10000000000000000 10000000000000100)
10000000000000061 *** 5925  (9149)
10000000000000069 *** 5887  (9166)
10000000000000079 *** 5887  (9174)
end
> 

カッコ内に問題 1.22で計測した時間を書いています. 問題 1.22の結果と見比べると, 時間は短くなっていますが, 半分とまでは言えません. 手続きnextでnが2であるかどうかを判定しているからでしょう.

３歳児が吐いた時の対策

娘が深夜２時頃に吐き出したのに気づき、仕方がないので両手で受けました(T_T)

その後、娘の体調は良くなったのですが、娘が吐き出して４８時間後に私と妻の体調が一気に悪化、嘔吐と発熱に苦しめられました(T_T)

今回学んだこと。

1. 嘔吐物を素手で受けない、処理するときは手袋をはめる。
2. 手袋に加えてマスクもする。
3. 洗面器に新聞で覆っておくと、吐いた時に洗面器を洗わなくて済む。
4. 服などを消毒するときは塩素系の洗剤を使う。アルコールは効かないらしい。
5. 消毒がめんどくさい時は捨てる。
6. ドアノブ、手すりなども消毒する。
7. ポカリスエットを用意する。アクエリアスはダメらしい。

次は感染しないように準備をしておきます＼(^o^)／

[SICP] 問題 1.22 : 素数を求めるために必要な計算量

殆んどのLispの実装には基本手続きruntimeがあり, システムが走った時間を(例えばマイクロ秒で)示す整数を返す. 次のtimed-prime-test手続きは整数nで呼び出されると, nを印字し, nが素数かどうかを調べ, nが素数なら手続きは三つの星印とテストに要した時間を印字する.

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

この手続きを使い, 指定範囲の連続する奇整数について素数性を調べる手続きsearch-for-primesを書け. その手続きで, それぞれ1,000, 10,000, 100,000, 1,000,000より大きい, 小さい方から三つの素数を見つけよ. 素数をテストする時間に注意せよ. テストのアルゴリズムはΘ(√n)の増加の程度だから, 10,000前後の素数のテストは1,000前後の素数のテストの√10倍かかると考えよ. 時間のデータはこれを支持するか. 100,000, 1,000,000のデータは√n予想のとおりだろうか. 結果はプログラムが計算に必要なステップ数に比例した時間で走るという考えに合っているか.

手続きruntimeの代わりにcurrent-millisecondsを使います. 手続きは次のようになります.

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

(define (divides? a b)
  (= (remainder b a) 0))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (prime? n)
  (= n (smallest-divisor n)))

;; 素数を求めるために必要な時間を計測する
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (current-milliseconds)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (current-milliseconds) start-time))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

(define (search-for-primes start end)
  (cond ((< start end)
         (timed-prime-test start)
         (search-for-primes (+ start 1) end))
        (else 
         (newline)
         (display "end"))))

問題文では, 素数を求める範囲を1000から始めていますが, 時間を計測できないため, もっと大きな数字から始めます. 測定結果は次のとおりです. 見やすいように, 不要な結果を削除しています.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (search-for-primes 100000000000 100000000100)
100000000003 *** 45
100000000019 *** 29
100000000057 *** 28
100000000063 *** 29
end
> (search-for-primes 1000000000000 1000000000100)
1000000000039 *** 97
1000000000061 *** 90
1000000000063 *** 90
end
> (search-for-primes 10000000000000 10000000000100)
10000000000037 *** 293
10000000000051 *** 302
10000000000099 *** 307
end
> (search-for-primes 100000000000000 100000000000100)
100000000000031 *** 939
100000000000067 *** 1397
100000000000097 *** 949
end
> (search-for-primes 1000000000000000 1000000000000200)
1000000000000037 *** 2891
1000000000000091 *** 2928
1000000000000159 *** 2919
end
> (search-for-primes 10000000000000000 10000000000000100)
10000000000000061 *** 9149
10000000000000069 *** 9166
10000000000000079 *** 9174
end

結果を見ると, nを１桁増やすと時間は約３倍になっており、 nを２桁増やすと時間は約10倍になっています. このことから, プログラムが計算に必要なステップ数に比例した時間で走るという考えに合っていると言えます.

問題文には, search-for-primesは「指定範囲の連続する奇整数について」とありますが, この条件を満たしていません. 実害はないのでこのままとします.

[SICP] 問題 1.21 : 最小除数の探索

smallest-divisor手続きを使い, 次の数の最小除数を見つけよ: 199, 1999, 19999.

テキストの手続きを入力します.

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

(define (divides? a b)
  (= (remainder b a) 0))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (prime? n)
  (= n (smallest-divisor n)))

評価してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (smallest-divisor 199)
199
> (smallest-divisor 1999)
1999
> (smallest-divisor 19999)
7
> 

[SICP] 問題 1.33 : filtered-accumulate

組み合せる項に フィルタ(filter)の考えを入れることで, accumulate(問題1.32)の更に一般的なものが得られる. つまり範囲から得られて, 指定した条件を満した項だけを組み合せる. 出来上ったfiltered-accumulate抽象は, accumulate と同じ引数の他, フィルタを指定する一引数の述語をとる. filtered-accumulateを手続きとして書け. filtered-accumulateを使い, 次をどう表現するかを示せ.

a. 区間a, bの素数の二乗の和(prime?述語は持っていると仮定する.)
b. nと互いに素で, nより小さい正の整数(つまりi < nでGCD(i, n)=1なる全整数i)の積

フィルターに対応したaccumulateを定義します. 考え方としては, filterが真を返すときはaccumulateと同様の処理をし, 偽を返すときはcombinerを使った計算をしないようにします. 手続きは次のようになります.

(require (lib "racket/trace.ss"))

(define (inc x) (+ x 1))

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

(define (cube x) (* x x x))

(define (divides? a b)
  (= (remainder b a) 0))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (prime? n)
  (= n (smallest-divisor n)))

;; 再帰的プロセスを生成する.
(define (filtered-accumulate-r filter combiner null-value term a next b)
  (cond ((> a b) 
         null-value)
        ((filter a)
         (combiner (term a)
                   (filtered-accumulate-r filter combiner null-value term (next a) next b)))
        (else
         (filtered-accumulate-r filter combiner null-value term (next a) next b))))

;; 反復的プロセスを生成する.
(define (filtered-accumulate-i filter combiner null-value term a next b)
  (define (iter a result)
    (cond ((> a b) 
           result)
          ((filter a) 
           (iter (next a) (combiner (term a) result)))
          (else
           (iter (next a) result))))
  (iter a null-value))

;; 区間a, bの素数の二乗の和
(define (sum-prime-square a b)
  (filtered-accumulate-r prime?
                         +
                         0
                         square
                         a
                         inc 
                         b))

;; nと互いに素で, nより小さい正の整数の積
(define (product-disjoint n)
  (define (disjoint? x) (= 1 (gcd n x)))
  (filtered-accumulate-r disjoint?
                         *
                         1
                         identity
                         1
                         inc
                         (- n 1)))

区間a, bの素数の二乗の和を求めてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (sum-prime-square 2 10)   
87
> (+ (square 2) (square 3) (square 5) (square 7))
87
> 

2から10の間の素数は, 2, 3, 5, 7ですから, 計算は合っています.

nと互いに素で, nより小さい正の整数の積を求めてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (product-disjoint 10)
189
> (* 1 3 7 9)
189
> 

10よりも小さい正の整数で10と互いに素になる数は, 1, 3, 7, 9ですから, 計算は合っています.

[SICP] 問題 1.19 : Fibonacci数を対数的ステップ数で計算する

Fibonacci数を対数的ステップ数で計算するうまいアルゴリズムがある. 1.2.2 節のfib-iterプロセスで使った状態変数aとbの変換: a ← a + bとb ← aに注意しよう. この変換をTと呼ぶ. 1と0から始め, Tを繰り返してn回作用させると, Fib(n + 1)とFib(n)の対が出来る. いいかえれば, Fibonacci数は対(1, 0)にTⁿ, つまり変換Tのn乗を作用させると得られる. さて, T_pqは対(a, b)をa ← bq + aq + apとb ← bp + aqに従って変換するものとし, Tを変換族T_pqのp = 0とq = 1の特例としよう. 変換T_pqを二回使うとその効果は同じ形式の変換T_p'q'を一回使ったのと同じになることを示し, p'とq'をp, qを使って表せ. これで変換を二乗する方法が得られ, fast-exptのように逐次平方を使い, Tⁿを計算することが出来る. これらをすべてまとめ, 対数的ステップ数の以下の手続きを完成せよ.

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   ＜??＞      ; p'を計算
                   ＜??＞      ; q'を計算
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

変換T_pqは次のような行列として表現できます.

Tpq=	[	p+q	q	]
		q	p

変換T_p'q'はT_pq²となります. T_pq²を計算し整理すると次のようになります.

Tp'q'=	[	(p2+q2) + (2pq+q2)	2pq+q2	]
		2pq+q2	p2+q2

変換T_p'q'とT_pqを見比べると, p'とq'はpとqを用いて次のように表せます.

p'=	p2+q2
q'=	2pq+q2

上で求めたp'とq'を使って手続きを定義すると次のようになります. 計算結果を検証するために, p.22の手続きもfib0として定義します.

(require (lib "racket/trace.ss"))

(define (fib0 n)
  (define (iter a b count)
    (if (= count 0)
        b
        (iter (+ a b) a (- count 1))))
  (iter 1 0 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (* p p) (* q q))
                   (+ (* 2 p q) (* q q))
                   (/ count 2)))
        (else
         (fib-iter (+ (* b q) (* a q) (* a p))
                   (+ (* b p) (* a q))
                   p
                   q
                   (- count 1)))))

(define (fib n)
  (fib-iter 1 0 0 1 n))

;;(trace fib-iter)

計算結果が正しいことを確認します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (map fib0 '(0 1 2 3 4 5 6 7))
(0 1 1 2 3 5 8 13)
> (map fib '(0 1 2 3 4 5 6 7))
(0 1 1 2 3 5 8 13)
> 

トレースしてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fib 30)
>(fib-iter 1 0 0 1 30)
>(fib-iter 1 0 1 1 15)
>(fib-iter 2 1 1 1 14)
>(fib-iter 2 1 2 3 7)
>(fib-iter 13 8 2 3 6)
>(fib-iter 13 8 13 21 3)
>(fib-iter 610 377 13 21 2)
>(fib-iter 610 377 610 987 1)
>(fib-iter 1346269 832040 610 987 0)
<832040
832040
> 

トレースの結果を見ると, 対数的ステップ数で計算していることが分かります.

[筋トレ] 2014.11.03の週

今週の記録です。
11/03（月）75.30kg

　プッシュアップ　１５、１０　　（膝をついた状態）
　ナロースタンス　　３、　３　　（両手の間を拳一つ開けた状態）
　アームカール　　１５、２０　　（5kgのダンベル）

11/04（火）74.30kg

　休み

11/05（水）74.60kg

　スクワット　　　３０、２５　　（5kgの鉄アレイ）
　リアレイズ　　　１２、　７　　（5kgの鉄アレイ）
　レッグレイズ　　１５、１０

11/06（木）74.85kg

　プッシュアップ　１６、１２　　（膝をついた状態）
　ナロースタンス　　５、　４　　（両手の間を拳一つ開けた状態）
　アームカール　　２０、１７　　（5kgのダンベル）

11/07（金）74.75kg

　休み

11/08（土）75.15kg
　娘の看病のため休み

11/09（日）75.35kg
　娘の看病のため休み

土日もトレーニングをする予定だったのですが、娘が土曜日の午前２時ぐらいから夕食を吐いて、明け方まで何度も吐いたのでトレーニングできませんでした。

日曜の昼過ぎには回復したみたいで、色々と食べれるようになりました。一安心です。

11月3日にボーネルンド KID-O-KIDへ行ってきました＼(^o^)／

１ヶ月ぶりぐらいに娘をボーネルンド KID-O-KIDへ連れて行きました。マンガのような目に遭いました(T_T)

• 11時前に入って、出たのが13時半ぐらい。２時間半も遊ぶとは(~_~;)
• まだ遊び足りないみたいで、地下1Fのボーネルンドのショップで遊び始める。
• ボーネルンドのショップを出たのが14時半ぐらい。
• この時点で予定より1時間以上遅れている(~_~;)
• 15時ちょうどのバスに乗れば、実家の近くで降りられて便利。
• バスに間に合う電車に乗ろうと頑張ったが目の前で電車の扉が閉じる(T_T)
• 実家の最寄り駅に着いたらバスは5分前に出ていた。
• 15時30分のバスに乗れば、実家まで700m程度なので悪くない(^O^)
• 少し離れたバス停から実家へ向けて歩いていたら途中にある公園で娘が遊び始める。
• いつの間にか娘が犬のウンコを踏んでいる。しかも出来たてを踏んだっぽい(T_T)
• 娘を実家へ連れて行き、遅い昼食を食べさせている間に靴を洗う。
• 靴を洗い終わってから、遅い昼食をとる。夕食も近いので軽く。
• いつもなら、父に駅まで車で送ってもらえるのだが、父が酔っ払っているorz
• 17時に駅に向かう最終のバスが出るので、食べ終わったらすぐにバス停へ移動。

ふんだり蹴ったりでした。

この遊び場は、有料で10分延長するごとに100円かかります。こういう場所へ子供を連れてきて、子供を放ったらかしてスマホで何かし続けている親御さんを見かけます。子供より大事なことが書いてあるのでしょう。

[SICP] 問題 1.18 : 対数的ステップ数の乗算手続き（反復的プロセス）

問題1.16, 1.17の結果を使い, 加算, 二倍, 二分による, 対数的ステップ数の, 二つの整数の乗算の反復的プロセスを生成する手続きを工夫せよ.

問題 1.16の結果を参考にして手続きを定義します. 0や負の数をかけた場合の扱いは, ループに入る前に判定してます.

(require (lib "racket/trace.ss"))

(define (double x) (* x 2))

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

(define (fast-mult-iter a b p)
  (cond ((= b 0) p)
        ((even? b) (fast-mult-iter (double a) (halve b) p))
        (else (fast-mult-iter a (- b 1) (+ a p)))))

(define (fast-mult a b)
  (cond ((< b 0) (* -1 (fast-mult-iter a (abs b) 0)))
        ((= b 0) 0)
        (else (fast-mult-iter a b 0))))

(trace fast-mult-iter)

p+a×bを考え, pに計算の途中経過をため込むことにします. pを0から始めます. p + a×bの計算について, 奇数と偶数の場合に分けて, 計算をどのように進めるかを考えます.

1) bが奇数の場合, b = m+1とする. 次の式が成立する.

p + a×(m+1) = (p+a) + (a×m)

(p+a)が次のpとなります.
2) nが偶数の場合, b = 2mとする. 次の式が成立する.

P + a×(2m) = p + double(a)×m

double(a)が次のaとなります.

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fast-mult 3 45)
>(fast-mult-iter 3 45 0)
>(fast-mult-iter 3 44 3)
>(fast-mult-iter 6 22 3)
>(fast-mult-iter 12 11 3)
>(fast-mult-iter 12 10 15)
>(fast-mult-iter 24 5 15)
>(fast-mult-iter 24 4 39)
>(fast-mult-iter 48 2 39)
>(fast-mult-iter 96 1 39)
>(fast-mult-iter 96 0 135)
<135
135
> (fast-mult 4 0)
0
> (fast-mult 5 -8)
>(fast-mult-iter 5 8 0)
>(fast-mult-iter 10 4 0)
>(fast-mult-iter 20 2 0)
>(fast-mult-iter 40 1 0)
>(fast-mult-iter 40 0 40)
<40
-40
> 

トレースの結果から, 反復的プロセスを生成していることが分かります.

[SICP] 問題 1.32 : accumulate

a. sumと(問題1.31の)productは, 一般的なアキュムレーションの関数:

(accumulate combiner null-value term a next b)

を使い, 項の集りを組み合せるaccumulateという更に一般的なものの特殊な場合であることを示せ.
accumulateは引数としてsumや productと同様, 項と範囲指定と, 先行する項のアキュムレーションと現在の項をどう組み合せるかを指定する(二引数の)combiner手続き, 項がなくなった時に使う値を指定するnull-valueをとる. accumulateを書き, sumやproductがaccumulateの単なる呼出しで定義出来ることを示せ.

b. 上のaccumulateが再帰的プロセスを生成するなら, 反復的プロセスを生成するものを書け. 反復的プロセスを生成するなら, 再帰的プロセスを生成するものを書け.

手続きsumとproductを比較すると, 「＋」と「＊」がcombiner, 「０」と「１」がnull-valueに対応します. 手続きを定義すると次のようになります.

(require (lib "racket/trace.ss"))

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

(define (cube x) (* x x x))

;; 再帰的プロセスを生成する.
(define (accumulate-r combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate-r combiner null-value term (next a) next b))))

;; 反復的プロセスを生成する.
(define (accumulate-i combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner (term a) result))))
  (iter a null-value))

;; 総和の定義
(define (sum term a next b)
  (accumulate-r + 0 term a next b))

;; 定積分を求める.
(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))

;; 指定した範囲の関数値の積を求める.
(define (product term a next b)
  (accumulate-i * 1 term a next b))

;; 円周率を求める. 
(define (my-pi n)
  (define (term x) 
    (/ (* x (+ x 2)) (square (+ x 1))))
  (define (next x)
    (+ x 2))
  (* 4.0 (product term 2 next n)))

実行してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (integral cube 0 1 0.01)
0.24998750000000042
> (integral cube 0 1 0.001)
0.249999875000001
> (my-pi 10000)
3.141749705738071
> (my-pi 100000)
3.141608361278168
> 

これまでの問題と同様に計算できています.

[SICP] 問題 1.31 : productの定義

a. sum手続きは高階手続きとして書ける, 同様な数多い抽象の最も単純なものに過ぎない.51 与えられた範囲の点での関数値の積を返すproductという似た手続きを書け. productを使って, factorialを定義せよ. また式

π　　２・４・４・６・６・８・・・
−＝−−−−−−−−−−−−−−− 
４　　３・３・５・５・７・７・・・

によってπの近似値を計算するのにproductを使え.
b. 上のproductが再帰的プロセスを生成するなら, 反復的プロセスを生成するものを書け. 反復的プロセスを生成するなら, 再帰的プロセスを生成するものを書け.

与えられた範囲の関数値の積を求める手続きproductを定義します. 和を積に変えているだけなので, sumの定義を利用できます. 手続きは次のようになります.

(require (lib "racket/trace.ss"))

(define (inc x) (+ x 1))

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

;; p.18のfactorialの定義
(define (factorial-0 n)
  (if (= n 1)
      1
      (* n (factorial-0 (- n 1)))))

;; productの定義. 再帰的プロセス
(define (product-r term a next b)
  (if (> a b)
      1
      (* (term a)
         (product-r term (next a) next b))))

;; productを用いたfactorialの定義
(define (factorial n)
  (product-r identity 1 inc n))

;; 反復的プロセスを生成
(define (product-i term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* (term a) result))))
  (iter a 1))

;; 円周率を求める. nが大きくなれば精度が良くなる.
(define (my-pi n)
  (define (term x) 
    (/ (* x (+ x 2)) (square (+ x 1))))
  (define (next x)
    (+ x 2))
  (* 4.0 (product-i term 2 next n)))

変更内容は, 「＋」を「＊」に, 初期値を0から1に変えているぐらいです. factorialの定義には再帰的プロセスを生成するproductを使用し, 円周率の計算には反復的プロセスを生成productを使用しています.

また, 円周率を計算する式は, 次のようにカッコをつけると見やすくなります.

π　　２・４　　　４・６　　　６・８
−＝（−−−）・（−−−）・（−−−）・・・
４　　３・３　　　５・５　　　７・７

計算してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (factorial-0 6)
720
> (factorial 6)
720
> (my-pi 10)
3.2751010413348074
> (my-pi 100)
3.1570301764551676
> (my-pi 1000)
3.1431607055322663
> (my-pi 10000)
3.1417497057380523
> (my-pi 100000)
3.1416083612781764
> 

実行結果から, 円周率を計算できていそうです.

[筋トレ] 2014.10.27の週

今週の記録です。
10/27（月）74.90kg

　腰痛のため休み

10/28（火）74.70kg

　腰痛のため休み

10/29（水）74.85kg

　腰痛のため休み

10/30（木）74.60kg

　腰痛のため休み

10/31（金）74.65kg

　腰痛のため休み

11/01（土）75.30kg
　スクワット　　　２０、２０　　（5kgの鉄アレイ）
　リアレイズ　　　１０、　０　　（5kgの鉄アレイ）
　レッグレイズ　　１５、１０

11/02（日）75.35kg
　寝過ごしたので休み

腰痛のため、トレーニングはほぼ休みとしました。

週末には腰痛もよくなったので、ぼつぼつと再開します。

自滅する中国（エドワード・ルトワック 著、芙蓉書房出版）

自滅する中国（エドワード・ルトワック 著、芙蓉書房出版）

タイトルだけを見るとよくある嫌中本のようですが、別物であると考えています。
（よくある嫌中本を読んだことがないので、本当のところは判断できないのですが）

「別物」と判断した理由は、次の２つです。

Ａ．著者の経歴
　解説によると、著者のエドワード・ルトワックは、アメリカ政府・軍事機関で顧問を務めているだけでなく、日本の防衛省防衛研究所をはじめとして、世界中の軍事関係機関で招聘講師を務めている。

Ｂ．インタビューした相手
　第14章で日本について書いてあり、2011年3月にインタビューした相手の名前が書いてあります。安倍晋三、中曽根康弘など、見たことのある名前が挙がっています。また、2014年10月29日の朝刊によると、10月28日に著者が首相官邸を訪れています。

この本の副題は「なぜ世界帝国になれないのか」となっており、中国の戦略的な不味さを説明しています。著者の主張は次のとおりです。

１．中国は自国の行動が他国にどのような影響をあたえるか分かっていない。
　中国に限らず、アメリカやロシアのような大国について言えることです。国が大きくなれば、それに応じて国内問題も増えます。しかし、人間の認識能力は国の大きさに関係ありません。その結果、外交に対する関心が低下します。

２．「中華思想」や「華夷秩序」が染み付いている。
　中国は、黄河流域の文明や文化は最高のものであり、アメリカのような野蛮人もいずれは中国の文化に取り込まれると考えています。これは、漢の時代に匈奴を取り込んだ経験に基づいています。しかし、清の時代、支配者であった女真族は民族の文化を頑なに守り通したことを忘れているようです。このように、他国の文化を見下しているため、他国の理解はより低くなります。

３．「孫子」を生み出した漢民族は戦略的に優れていると勘違いしている。
　「孫子」に代表される兵法書は、春秋戦国時代に生み出されました。この時代は、同じ価値観を持つ同一の文化圏内で、同じ民族が離合集散を繰り返していました。しかし、現代の国際社会は、異なる文化や価値観を持った国家や民族間で利害を争っており、「孫子」が成立したときと条件が異なっています。これを理解せずにそのまま「孫子」を持ち出しても、利益よりも害の方が大きくなります。

　また、過去1000年の歴史を振り返ると、漢民族が中国全土を支配できた期間はわずか200年（？）に過ぎず、このような事実からも戦略的に優れていると判断することは間違いです。

４．中国の軍事力が増大すると周辺国は脅威を感じ、反中国的な行動を取る。
　中国が軍事力を増大させる理由は、国際的な影響力を強めるためることがその一つであると考えられます。しかし、中国の軍事的な圧力が高まると、親中国的な国は中立的な行動を取り、中立的であった国は反中国的な同盟を組むようになります。その結果、中国の影響力は相対的に低下します。

５．周辺国の反発を避ける唯一の道は軍事力の削減である。
　中国が周辺国の反発を受けずに、国際的な影響力を強める唯一の手段は軍事力を削減することです。しかし、歴史的な恨みから中国は国の規模に応じた軍事力を保持する事を望んでおり、また、軍事力を増大させることで利益を得る人たちもいることから、軍事力を削減することはできそうにありません。

６．経済成長をこのまま続け、軍事力で圧倒するしかない。
　中国の経済成長率は年に7%程度あり、アメリカなどを圧倒しています。このペースで経済成長を続け、それに応じて軍事力を増大させれば、中国に立ち向かえる国は無くなります。しかし、反中国的な同盟を組んだ国が中国の経済成長を妨げるような行動を取るため、現在の成長率を維持することは難しくなります。また、中国は多くの国内問題を抱えており、それらが原因で経済成長が止まる可能性があります。経済成長が止まると、中国国内の矛盾が一気に噴出します。その時、中国は持ちこたえられるでしょうか？

この本の約半分のページは、リーマン・ショック以降の中国の行動に対する周辺国（オーストラリア、日本、ベトナム、韓国、モンゴル、インドネシア、フィリピン）の行動を説明しています。ほとんどの国が反中国的な行動を取っており、反中国同盟と呼べるものです。例外は、韓国ぐらいでしょうか。

著者は各国の要人と意見を交換できる立場にありますが、この本に書いてある中国や周辺国の行動は、ニュースなどで確認できるものばかりです。読みやすい本ではありませんが、この本を読むとニュースの見方が変わるかも＼(^o^)／

[SICP] 問題 1.30 : 反復的プロセスを生成する総和

上のsumの手続きは線形再帰を生成する. 総和が反復的に実行出来るように手続きを書き直せる. 次の定義の欠けているところを補ってこれを示せ:

(define (sum term a next b)
  (define (iter a result)
    (if ＜??＞
        ＜??＞
        (iter ＜??＞ ＜??＞)))
  (iter ＜??＞ ＜??＞))

総和を求める手続きが反復的プロセスを生成するように修正します. 内部手続iterの引数resultに計算の途中経過を蓄積するようにします. 手続きの定義は次のようになります.

(require (lib "racket/trace.ss"))

(define (cube x) (* x x x))

(define (inc x) (+ x 1))

;; 再帰的プロセスを生成
(define (sum-r term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum-r term (next a) next b))))

;; 反復的プロセスを生成
(define (sum-i term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ (term a) result))))
  (trace iter) ;; 内部手続きをトレースする.
  (iter a 0))

(trace sum-r)

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (sum-r identity 1 inc 10)
>(sum-r #<procedure:identity> 1 #<procedure:inc> 10)
> (sum-r #<procedure:identity> 2 #<procedure:inc> 10)
> >(sum-r #<procedure:identity> 3 #<procedure:inc> 10)
> > (sum-r #<procedure:identity> 4 #<procedure:inc> 10)
> > >(sum-r #<procedure:identity> 5 #<procedure:inc> 10)
> > > (sum-r #<procedure:identity> 6 #<procedure:inc> 10)
> > > >(sum-r #<procedure:identity> 7 #<procedure:inc> 10)
> > > > (sum-r #<procedure:identity> 8 #<procedure:inc> 10)
> > > > >(sum-r #<procedure:identity> 9 #<procedure:inc> 10)
> > > > > (sum-r #<procedure:identity> 10 #<procedure:inc> 10)
> > > >[10] (sum-r #<procedure:identity> 11 #<procedure:inc> 10)
< < < <[10] 0
< < < < < 10
< < < < <19
< < < < 27
< < < <34
< < < 40
< < <45
< < 49
< <52
< 54
<55
55
> (sum identity 1 inc 10)
>(iter 1 0)
>(iter 2 1)
>(iter 3 3)
>(iter 4 6)
>(iter 5 10)
>(iter 6 15)
>(iter 7 21)
>(iter 8 28)
>(iter 9 36)
>(iter 10 45)
>(iter 11 55)
<55
55
> 

トレースの結果からも反復的プロセスを生成していることが分かります.

ダメな４星人

先日、会社で中小企業診断士の先生による研修を受けました。その中で、コンサルタントとして上手くいかない人の特徴を「ダメな４星人」と名づけて紹介していました。次の４星人です。

1. ダメダメ星人
2. デモデモ星人
3. クレクレ星人
4. グルグル星人

もう少し詳しく書きます。

１．ダメダメ星人
　人の話を聴いた時に、とりあえず否定するところから入る人です。もちろん、ダメなものはダメと言わないといけないのですが、言った方としては否定され続けると意見する気が無くなります。その結果、ダメダメ星人には情報が集まらなくなるので、コンサルタントとしてやっていくのは難しそうです。

２．デモデモ星人
　プラカードを持って抗議活動をする人ではありません。何をするにしても、「でもでも」と、できない理由を探す人です。もちろん、何かを始めるときには、最悪の場合に備えて計画を立てるべきですが、実行すると決めたのなら最善を尽くすべきです。

３．クレクレ星人
　仕事をまわして欲しいと、それだけを人に依頼する人です。そもそも、仕事がなく、暇そうにしているコンサルタントは、仕事ができなさそうに見えるので仕事を依頼したいと思いません。「くれくれ」と言うのは逆効果でしょう。世の中、ギブ・アンド・テイクといいます。まず、与えること、相手の利益を考えることを考えるぐらいで、ちょうど良いのでしょう。

４．グルグル星人
　ちょっと分かり難いのですが、思考がグルグルと同じことを回っている人です。何か新しく始めようとして計画を立てても、実行の段階で、ああでもない、こうでもない、と考えて行動に移さない人です。私もよくあります。少しずつでも行動を起こして、前に進めていかないと、何も変わりません。

この４星人にならないようにしなくては(~_~;)