おんがえしの blog

作ったプログラムと調べた技術情報

2008-02-01から1ヶ月間の記事一覧

問題1.22(考察)

1000の場合 guile> (search-for-primes 1000 30) 1001 1003 1005 1007 1009 *** 62 1011 1013 *** 63 1015 1017 1019 *** 62 1021 *** 63 1023 1025 1027 1029 1031 *** 63 1033 *** 47 1035 1037 1039 *** 62 1041 1043 1045 1047 1049 *** 46 1051 *** 63 …

問題1.22

さあ面白くなってきた。素数を求めるのに必要な時間を調べ、考察せよC言語なら単純なforループになるコードだが、Lispだと末尾再帰を使って解く必要がある。 残念ながら自力で書くことは出来なかっので、AnswerBookをコピーしてコード読み。 (define (search…

アクセス解析

なかのひとと、忍者ツールを入れてみました。

問題1.21

199, 1999, 19999の最小除数を求めよ (define (smallest-divisor n) (find-divisor n 2)) (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.20

ちょっと挫折しました...余力があれば後で戻ってくるかも。 AnswerBook一応、作用的順序評価はやってみた。 ; 作用的順序評価 (if (= 40 0) 206 (gcd 40 (remainder 206 40))) (if (= 40 0) 206 (if (= 6 0) 40 (gcd 40 (remainder 40 6)))) (if (= 40 0) 20…

問題1.16

逐次平方の反復的プロセスバージョンを求めよ発想の転換が必要。 b^n = (b^(n/2))^2 = (b^2)^(n/2) b^n = b * b^(n-1) [普通の逐次平方ならばこんな感じ] 2^6 = (2^3)^2 = 8^2 = 8 * 8 = 64 [反復プロセスで行うならばこうする] 2^6 = (2^3)^2 = (2^2)^3 -->…

問題1.15

sinの近似と増加量の計算 (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. (sine 12.5) の評価で、手続きpは何回作用させられたか?5回 (…

両替日本版

両替問題は面白かった。 理屈は分かるけど、解けてしまうことがやっぱり不思議。 せっかくなので日本硬貨での両替計算も作ってみました。 (define (count-change amount) (define (cc amount kinds-of-coins) (cond ((= amount 0) 1) ((or (< amount 0) (= k…

問題1.14

木構造を手で書けうおー、しんどい・・・。 でも練習にはちょうどいいか。 ; 11の場合 (cc 11 5) (cc 11 4) (cc 11 3) (cc 11 2) (cc 11 1) (cc 11 0) -> 0 (cc 10 1) (cc 10 0) -> 0 (cc 9 1) (cc 9 0) -> 0 (cc 8 1) (cc 8 0) -> 0 (cc 7 1) (cc 7 0) -> 0…

問題1.13

Fib(n)が φ^n /√5 に最も近い整数であることを、帰納法を用いて証明せよ。 φ = (1 + √5)/2 ≒ 1.61803398874989 φ^2 = φ + 1 いわゆる黄金比のこと。証明なんて何年ぶりだろう...、自力で解くのは正直無理でしたm(__)m。 AnswerBookを写経しながら、自分の言…

問題1.12

Pascal三角形を計算する関数を作成せよ関数自体は簡単に出来た。 ; 1〜n行, 1〜n列 目のパスカル三角形の値を返す ; 範囲外の場合は0を返す (define (pascals-triangle row col) (cond ((> col row) 0) ((= col 1) 1) ((= row col) 1) (else (+ (pascals-tri…

問題1.19

フィボナッチ数計算の対数ステップ版を作れ 答えを見ながら証明してみましたが、正直理解しきれていないなあ...。 a = bq + aq + ap b = bp + aq a' = (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p = bpq + aq^2 + bq^2 + aq^2 + apq + bpq + apq + ap^2…

問題1.18

1.17の反復プロセス版を作れ (define (fast-mul2 a b) (define (iter a b total) (cond ((= b 0) total) ((even? b) (iter (double a) (halv b) total)) (else (iter a (- b 1) (+ total a))))) (iter a b 0)) (define (double x) (ash x 1)) (define (halv …

問題1.17

掛け算、割り算の無い世界で、足し算を使って掛け算を定義せよ逐次平方はべき乗の高速化だったが、 これは同じような考えで掛け算を定義する。なんとなく、doubleとhalvはシフト演算で定義してみた。 (define (fast-mul a b) (cond ((= b 0) 0) ((even? b) (…

問題1.11

再帰関数を、再帰的プロセス、反復的プロセスで記述せよ ; 答え合わせ用にトレース ; (f 3) ; ==> (+ (f 2) (* 2 (f 1)) (* 3 (f 0))) ; ==> (+ 2 (* 2 1) (* 3 0)) ; ==> (+ 2 2 0) ; ==> 4 ; (f 4) ; ==> (+ (f 3) (* 2 (f 2)) (* 3 (f 1))) ; ==> (+ 4 4 …

問題1.10

Ackermann関数についてそもそもAckermann関数ってなんだ?って話なので、Wikipediaで調べてみる。 アッカーマン関数 - Wikipedia今ひとつ分からないので実際に書いて動かしてみる。 (define (A x y) (cond ((= y 0) 0) ((= x 0) (* 2 y)) ((= y 1) 2) (else …

問題1.9

下記の2つの手続きを、置き換えモデルを用いて図示せよ そのプロセスは反復的か再帰的か? プロセスを図示することが大切。プロセス1 (plus 3 3) ==> (inc (plus 2 3)) ==> (inc (inc (plus 1 3))) ==> (inc (inc (inc (plus 0 3)))) ==> (inc (inc (inc 3))…

run-guile モードで無限ループに入ると停止出来ないや

Meadowでのrun-guileモードはとても便利なんだけど、 何故か無限ループに入るとC-cC-cを押しても止めることが出来ない...。cygwinだと、 guile> (load "question-1_9.scm") ERROR: User interrupt ABORT: (signal) とかで停止出来るんだけど。 run-guileモー…

問題1.8

立方根を求める手続きを作成せよ improveのみ、立方根の手続きに変更すれば良い せっかくなので、good-enough?等はAnswerBook1.7を参考に作ることにした 共通関数は別ファイルにまとめることにした(sicp-lib.scm - おんがえしの日記) (load "sicp-lib.scm") …

問題1.7

1.1.7節で作成した、sqrtの弱点を解析せよ また、その弱点を改良せよ とりあえず、検証用手続きを作る (define (sqrt-test x) (/ (square (sqrt x)) x)) 非常に小さい数の場合、閾値よりも小さい数になると精度が悪くなる。 再帰が少ない回数で終了してしま…

問題1.6

通常版では (sqrt 2) ==> 1.41421568627451 new-if版では ==> ERROR: Stack overflow ==> ABORT: (stack-overflow) ifでは述語がtrueにならない限りelse節が評価されないが、 new-ifはただの手続きのため、呼び出されてすぐにthen節、else節が評価されてしま…

問題1.5

(define (p) (p)) (define (test x y) (if (= x 0) 0 y)) 作用的順序の場合 無限ループする (test 0 (p)) => (test 0 (p)) => (test 0 (p (p (p) (p))))... 正規順序の場合 まず関数testを展開する (test x y) => (if (= x 0) 0 y) ;xを代入する(yはまだ) =>…

問題1.4

とりあえず関数を動かしてみて、どのような振る舞いをするか確かめる a-plus-abs-b は a + abs(b) のことだということは動かせば分かる。 (define (a-plus-abs-b a b) ((if (> b 0) + -) a b)) (a-plus-abs-b 1 2) ; 3 (a-plus-abs-b 1 -2) ; 3 (a-plus-abs-…

はてなダイアリー向けの環境整備

XKeymacsをインストール。 FireFoxをEmacsキーバインドで操作できると便利だなあ。

Meadow+cygwin でのscheme環境構築

Lispは本当に色々な実装があって迷う。 普段はMeadow+cygwinでプログラムしているので、試しにcygwin setupを覗いてみたら、Devel/guile-develを発見。 Meadowとの親和性がよいものがいいので、これを使うことに。id:higepon:20060415:1145108067さんの設定…

問題1.3

三つの数を引数として取り、大きい二つの数の二乗の和を返す手続きを定義せよ。 テキストで出てきた、square, sum-of-squaresを使いまわす ソートする必要は無い、一番小さい数が分かればよい (define (square x) (* x x)) ;(square 5) (define (sum-of-squa…

問題1.2

次の式を前置記法に翻訳せよ とりあえず書いてみる。 実行してみて、動くことを確認。 回答集を見て、同じ答えなことを確認 細かいことだけど、guileは有理数で出力されて、gaucheは小数で出力されるのね (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2)…

問題1.1

式の列がある。それぞれの式が印字する結果は何か。列は示した順に評価するものとする問題1.1はインタプリタの使い方を覚えるのがメイン。 問題を正しく打ち込み、結果を考え記入。インタプリタで結果を答え合わせ。 10 ; 10 (+ 5 3 4) ; 12 (- 9 1) ; 8 (/ …