スポンサーサイト

一定期間更新がないため広告を表示しています

スポンサードリンク | - | | - | - |

SICPメモ(5) 問題1.11

SICPには練習問題がちょこちょこ出てくるが、気が向いたもののみ解いていく。
問題1.11はある隣接三項間漸化式が与えられていて、それを再帰と反復の両方のアルゴリズムで書けというもの。

〆撞版
(define (f n)
  (cond
    ((< n 3) n)
    (else (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3)))))
  )
)

(f 4)

反復版
(define (calc a b c) (+ (* 3 a) (* 2 b) c))

(define (f-iter count n a b c)
  (cond
    ((< n 3) n)
    ((= count n) (display "end"))
    (else (display a) (display "¥n") (f-iter (+ 1 count) n b c (calc a b c)))
    )
 
  )(define (f n) (f-iter 0 n 0 1 2))
   
 (f 5)
0
1
2
4
11
end


簡単。SICPにも書いてあったと思うが、再帰版は効率こそ悪いものの、定義式そのもので見栄えがいいな。
ジャジャガッチ | LISP | 16:10 | comments(0) | trackbacks(0) |

SICPメモ(4) オイラー法

SCIPに書いてあったわけではないけど、オイラー法実装するの好きなので実装してみた。
今回は
df/dx = f(x)
を解く。f(0)=1とすれば解はexp(x)になる。これを数値的に確かめる。次のようにする。
df/dx = {f(x+dx)-f(x)}/dx = f(x)
より
f(x+dx) = (1+dx)f(x)
つまり
f{n+1} = (1+dx)f{n}
という漸化式になる。計算結果はdisplayで表示できる。

〆撞版
(define Dx 0.01)

(define ( f n)
  (cond
    ((= n 0) 1)
    (else (* (+ 1 Dx) (f (- n 1))))
  )
)

(f 10)
反復版
(define Dx 0.01)

(define (f-iter count value n)
  (cond
   ((= count n) (display value))
   (else (display value) (display "¥n") (f-iter (+ count 1) (* (+ 1 Dx) value) n ))
   )
)

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

(f 10)
1
1.01
1.0201
1.030301
1.04060401
1.0510100501
1.061520150601
1.0721353521070098
1.08285670562808
1.0936852726843609
1.1046221254112045


C言語版は続きから。
続きを読む >>
ジャジャガッチ | LISP | 15:48 | comments(0) | trackbacks(0) |

SICPメモ(3) 1.2あたり 再帰と反復

1.2辺りには再帰と反復は違うよ!って書いてある。
色々なプログラムについて再帰verと反復verが紹介してある。
読んでるだけだとつまんないので簡単なプログラムを実装してみた。
単に0からカウントしていくプログラムだ。

“辛ver
(define (f count n)
  (cond
    ((= count n) n)
    (else (f (+ count 1) n))
    )
)

(f 0 10)
10
∈撞ver
(define (g n)
  (cond
    ((= n 0) 0)
    (else (+ 1 (g (- n 1))))
    )
)

(g 10)
10
再帰verは呼び出し時に値が確定していない戻り値(?)を使って演算している。
(g 10)を呼ぶとその値はg(9)+1になるが、g(9)は確定していない。g(9)はg(8)を呼び・・・、g(0)まで到達するとg(1)、g(2)と値が確定していき、g(10)に戻ってくる。

一方、反復verはcountを使って計算している。このコードの場合、戻り値は特に何の役割も果たしていない。
というか、こういう風に戻り値に対して何の演算もしないで再帰する場合、戻り値を使って値を計算するのは無理だ。
なので、f(0,10),f(1,10)・・・をすべてメモリ上に置いておく必要はない。
Schemeは仕様上このようなコードではf(0,10)等を用が済んだ時点で破棄してしまう。
このため、ループと同じになる。
このようなコードを末尾再帰というらしい。Schemeではループと同じだが、C言語などではf(0,10)などを破棄しないのでループと同じにはならない。
ジャジャガッチ | LISP | 22:03 | comments(0) | trackbacks(0) |

SICPメモ(2) 1.1.7 ニュートン法による平方根の計算

数学における関数とプログラムの関数は違うものだよ、って書いてある。
数学の本にf(x) = √xって書いてあったとしてf(2)がいくつかわかるか、わかんねえだろ。
数学の関数には手続きが書いてねえからわかんねえんだよ。
でもプログラムの関数には手続きが書いてあるから値がちゃんとわかるんだよ、すげえだろ。らしい。
んで、じゃあ√2求めてみようぜ、ってことらしい。

ニュートン法ならまかせろ!今のところ繰り返し処理とかの特別な構文出てないってことは再帰だろ!ってことで本文読まずにごりごり書いてみた。

(define (myabs x)
  (cond
    ((< x 0) -x)
    (else x)
    )
  )

(define (mysqrt x c)
  (cond
    ((> (abs (- (* x x) c)) 0.001) (mysqrt (- x (/ (- (* x x) c) (* 2 x)) ) c))
    (else x)
  )
 )

(mysqrt 1 2)
1+169/408
一部括弧が大変なことに・・・。てか分数っすか?すげえな。1+169/408=1.4142156・・・なので想定した動作をしている。
ニュートン法について少し復習しておくと、
f(x)を1次までテイラー展開してやると
f(x) = f(x) + f'(x)(x-a)
f(x)=0としてxについて解けば
x = a-f(a)/f'(a)
aに適当な値を入れれば上式で近似解が得られる。そのようにして得られたxを右辺のaに代入して、ってのを繰り返すと近似精度が上がっていく、という仕組み。漸化式だ。
上のコードでは1を初期値にしている。

SICPでは
(define (good-enough? x c) (> (abs (- (* x x) c)) 0.001))
みたいなのとか色々defineして抽象化している。

とりあえず1.1.7までざらっと読んだぞ。まだまだ準備運動かな。
ジャジャガッチ | LISP | 22:36 | comments(0) | trackbacks(0) |

SICPメモ(1)

開発環境はRacket 5.3.6。SICPはSchemeを使っているので。
最初に言語をR5RSに設定する。
実行はCtrl + Rか。

最初は足し算から。
(+ 1 1)
2

こういうのも出来る。
(+ (- 5 2) (+ 3 1) 1)
8
独特だな。

文字に数字を割り当てることも出来る。
(define x 2)
(define y 5)
(+ x y)
7
C言語に慣れているとつい#defineって打ってしまう。

手続きをdefineすることも出来る。
(define (f x) (* x x))
(f 2)
4

条件分岐。
(define (f x)
  (cond
    ((< x 0) -1)
    ((= x 0) 0)
    ((> x 0) 1)
  )
)

orとかもあるよ。
(define (f x)
  (cond
   ((or (< x 0) (> x 0)) 1)
   (else 0)
  )
)
どれも一番左に演算子がくるのね。

今回はここまで。
ジャジャガッチ | LISP | 22:02 | comments(0) | trackbacks(0) |

SICP読み始めた

 SICP = Structure and Interpretation of Computer Program。 計算機科学の古典。
大分前に弟にこの本の存在を教えてもらって原文を印刷したものまでもらったのに放置していた。

Brainf*ckインタプリタを実装していて計算機科学について興味が湧いてきた。
以下、きちんとしたソースにあたったわけではないので間違っている可能性もあります。
Brainf*ckはチューリング完全らしいが、チューリング完全ってのはチューリングマシンで実現可能なアルゴリズムは全て実現出来るということで、それって存在する全てのアルゴリズムを実装できるということとは違うんじゃね?って思って色々調べていた。
実際、チューリングマシンを超える計算機は数学的には考えられるみたい(ハイパーコンピュータ)。
ただ、現実的なモデルとしてはチューリングモデルが最高らしい。
実質的に実現可能なアルゴリズムはチューリングマシンで全て可能と思われているから、チューリング完全ってのは実質的に実現可能なアルゴリズムを全て実現可能ってことか。

チューリングマシンで計算できる関数は「実質的に計算可能な関数」と呼ばれるらしいが、チューリングはチューリングマシンで計算できる関数こそ「計算可能関数」だ、って主張してたみたい(チャーチ=チューリングのテーゼ)。 アルゴリズムって何だ、計算可能って何だ、って問題は結構面倒な問題なのか。

まあ、そんなことを考えていたらそーいえば計算機科学分野にはラムダ計算とかいう面白そうなものがあったな、と思い出したわけです。
1冊評判のよさそうな本を読んでみようと思って注文したところで、そういえばSICPの表紙にはλの文字があるしラムダ計算と戯れることが出来るかな?と思いついたわけです。

前置きが長くなりましたが、そういうわけでSICPを読み始めました。 すぐに飽きてしまう可能性もあるけど、自分で書いたコードや何かをメモしていこうと思っている。
ジャジャガッチ | LISP | 21:40 | comments(0) | trackbacks(0) |
2/2PAGES | << |

07
--
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
--
>>
<<
--
PR
RECOMMEND
RECENT COMMENT
MOBILE
qrcode
OTHERS
Since 2013/09/17
LATEST ENTRY
CATEGORY
ARCHIVE
LINKS
PROFILE
SEARCH