Hatena::ブログ(Diary)

babanbanの日記

2008-11-19

SICPの宿題

| 19:42

問題1.19

Tをn回作用させた時のa, bを a_{n}, b_{n}とすると a_{n+1}, b_{n+1}

 a_{n+1} = b_{n}q + a_{n}q + a_{n}p

 b_{n+1} = b_{n}p + a_{n}q

となる。

さらに、もう一回Tを作用させたとき a_{n+2}, b_{n+2}

 a_{n+2}

 = b_{n+1}q + a_{n+1}q + a_{n+1}p

 = (b_{n}p + a_{n}q)q + (b_{n}q + a_{n}q + a_{n}p)q + (b_{n}q + a_{n}q + a_{n}p)p

 = b_{n}(2pq + q^{2}) + a_{n}(2pq + q^{2}) + a_{n}(p^{2} + q^{2})

 b_{n+2}

 = b_{n+1}p + a_{n+1}q

 = (b_{n}p + a_{n}q)p + (b_{n}q + a_{n}q + a_{n}p)q

 = b_{n}(p^{2} + q^{2}) + a_{n}(2pq + q^{2})

これから

 p’ = p^{2} + q^{2}, q’ = 2pq + q^{2}

とすると、 T_{pq}を2回作用させるのは、 T_{p’q’}を1回作用させるのと同じになる。

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

(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
                   (+ (square p) (square q)) ;; p'
                   (+ (* 2 p q) (square q))  ;; q'
                   (/ count 2))]
        [else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1))]))

実行結果

gosh> (fib 3)
2
gosh> (fib 4)
3
gosh> (fib 5)
5
gosh> (fib 6)
8
gosh> (fib 7)
13
gosh> (fib 8)
21

2008-11-09

SICPの宿題

| 22:36

問題1.14がワカラナイヨ。

明日の答え合わせで教えてもらおう。

問題1.16

;; if n is even, procedure returns true, otherwise false.      
(define (even? n)
  (= (remainder n 2) 0))

;; ex1.16 procedure "fast-expt and fast-expt-iter"                                         
(define (fast-expt x n)
  (fast-expt-iter x n 1))

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

問題1.17

;; double                                                      
(define (double n)
  (+ n n))

;; halve                                                       
(define (halve n)
  (/ n 2))

;; ex1.17 procedure "fast-mult"                                
(define (fast-mult x n)
  (cond [(= n 0) 0]
        [(= n 1) x]
        [(even? n) (fast-mult (double x) (halve n))]
        [else (+ x (fast-mult x (- n 1)))]))

問題1.18

;; ex1.18 procedure "fast-mult and fast-mult-iter"             
(define (fast-mult x n)
  (fast-mult-iter x n 0))

(define (fast-mult-iter x n a)
  (cond [(= n 0) a]
        [(even? n) (fast-mult-iter (double x) (halve n) a)]
        [else (fast-mult-iter x (- n 1) (+ x a))]))

clairvyclairvy 2008/11/11 01:08 普通に合ってる気がするけど,何が問題なんでしたっけ?

babanbanbabanban 2008/11/15 22:02 なんか自信なかっただけだと思います><
clairvyさんの答えと一緒だったんで安心しました。

2008-10-30

問題1.13

| 21:14

gabuchan : 「さあ、証明するのだ」

babanban : 「yes master」


証明スタート

 ¥phi = (1 + ¥sqrt{5})/2,  ¥psi = (1 - ¥sqrt{5})/2 として

 Fib(n) = (¥phi^{n} - ¥psi^{n})/¥sqrt{5}が0を含む全ての自然数について成り立つことをnに関する数学的帰納法をつかって証明する。

基底

n = 0 のとき

Fib(0) = 0

 (¥phi^{0} - ¥psi^{0})/¥sqrt{5} = 0 より成り立つ

n = 1 のとき

Fib(1) = 1

 (¥phi^{1} - ¥psi^{1})/¥sqrt{5} = 1 より成り立つ

帰納段階

Fib(n) = Fib(n-1) + Fib(n-2)

ここで帰納法の仮定を使って

Fib(n-1) =  (¥phi^{n-1} - ¥psi^{n-1})/¥sqrt{5}

Fib(n-2) =  (¥phi^{n-2} - ¥psi^{n-2})/¥sqrt{5}

がいえる。

Fib(n)

= Fib(n-1) + Fib(n-2)

=  ¥frac{¥phi^{n-1} - ¥psi^{n-1}}{¥sqrt{5}} + ¥frac{¥phi^{n-2} - ¥psi^{n-2}}{¥sqrt{5}}

=  ¥frac{¥phi^{n-2}(¥phi + 1) - ¥psi^{n-2}(¥psi + 1)}{¥sqrt{5}

( ¥phi^{2} = ¥phi + 1, ¥psi^{2} = ¥psi + 1 より)

=  ¥frac{¥phi^{n-2}*¥phi^{2} - ¥psi^{n-2}*¥psi^{2}}{¥sqrt{5}}

=  ¥frac{¥phi^{n} - ¥psi^{n}}{¥sqrt{5}}

よって成り立つ

証明終了

(一口メモ)

今回は帰納法の仮定を使うときにn-1とn-2が必要になるので基底ではn=0とn=1の2つの場合が成り立つことを証明しなくちゃいけない。

2008-10-27

SICPの宿題

| 22:48

こつこつやろうということで今日は問題1.13を解きました。

証明問題だからちょっとあせったけど、ヒント通りにやればできました。というかヒントなしじゃできませんでした。

答えを書こうとしたけど、tex記法フォントが気に入らなかったのでやめました。

gabuchangabuchan 2008/10/29 00:52 答え書かないと意味ないじゃんw

2008-10-12

CSNagoyaの宿題

| 17:03

皆さんがんばって実装しているみたいなので僕も、今回smlでスキャナを実装した。

Gaucheは後回し。すいません。

でも、関数型で実装するイメージはこれでだいぶつかんだと思う。

TextIOモジュールのlookaheadは先読みする関数なので、これを使えば1文字ずつ読み込んでいくスタイルでも難なく実装できた。

とはいえ、けっこう手抜きなところがあって申し訳ないですが。

次回の勉強会ではパーサの実装に入る予定なので、それまでに、Gaucheスキャナを実装せねば。。。

datatype token =
    EOF
  | IDENT of string    | NUMBER of string
  | STR of string
  | MODULE of string   | BEGIN of string
  | END of string      | VAR of string
  | INTEGER of string  | STRING of string
  | IF of string       | THEN of string
  | ELSE of string     | WHILE of string
  | DO of string
  | OPEN    | CLOSE  | PERIOD
  | COMMA   | COLON  | SEMICOLON
  | EQ      | MINUS  | PLUS
  | MULT    | DIV    | LT
  | LE      | GT     | GE
  | NE      | MYASSIGN
  | UNKNOWN


structure T = TextIO
fun skipSpaces ins =
    case T.lookahead ins of
        SOME c => (if Char.isSpace c
                        then (T.input1 ins;skipSpaces ins)
                   else ())
      |  _     => ()

fun getID ins =
    let fun getRest s =
        case T.lookahead ins of
            SOME c => (if Char.isAlphaNum c then getRest (s ^ T.inputN(ins,1))
                       else s)
          | _ => s
    in IDENT(getRest "")
    end


fun isReserved (IDENT(str)) =
    case str of
        "MODULE"  => MODULE(str)
      | "BEGIN"   => BEGIN(str)
      | "END"     => END(str)
      | "VAR"     => VAR(str)
      | "INTEGER" => INTEGER(str)
      | "STRING"  => STRING(str)
      | "IF"      => IF(str)
      | "THEN"    => THEN(str)
      | "ELSE"    => ELSE(str)
      | "WHILE"   => WHILE(str)
      | "DO"      => DO(str)
      | _         => IDENT(str)


fun getNum ins =
    let fun getRest s =
        case T.lookahead ins of
            SOME c => (if Char.isDigit c then getRest (s ^ T.inputN(ins,1))
                       else s)
          | _ => s
    in NUMBER(getRest "")
    end
fun getStr ins =
    let fun getRest s =
        case valOf(T.input1 ins) of
            #"\"" => s
          | c => getRest(s ^ str c)
    in STR(getRest "")
    end

fun lex ins =
    (skipSpaces ins;
     if T.endOfStream ins then EOF
     else let val c = valOf(T.lookahead ins)
          in if Char.isDigit c then getNum ins
             else if Char.isAlpha c then isReserved(getID ins)
                  else case valOf (T.input1 ins) of
                      #"+"  => PLUS
                    | #"-"  => MINUS
                    | #"*"  => MULT
                    | #"/"  => DIV
                    | #"="  => EQ
                    | #"<"  => LT
                    | #">"  => GT
                    | #":"  => COLON
                    | #";"  => SEMICOLON
                    | #","  => COMMA
                    | #"("  => OPEN
                    | #")"  => CLOSE
                    | #"."  => PERIOD
                    | #"\"" => getStr ins
                    | _ => UNKNOWN
          end)


fun toString (IDENT(str)) = "ID(" ^ str ^ ")"
  | toString (NUMBER(str)) = "NUMBER(" ^ str ^ ")"
  | toString (STR(str)) = "STR(" ^ str ^ ")"
  | toString (MODULE(str)) = "MODULE(" ^ str ^ ")"
  | toString (BEGIN(str)) = "BEGIN(" ^ str ^ ")"
  | toString PLUS = "PLUS"
  | toString MINUS = "MINUS"
  | toString MULT = "MULT"
  | toString DIV = "DIV"
  | toString EQ = "EQ"
  | toString LT = "LT"
  | toString RT = "RT"

fun testLex () =
    let val token = lex TextIO.stdIn
        in case token of
            EOF => ()
          | _ => (print (toString token ^ "\n"); testLex())
    end