2008-11-08

KOF2008に参加しました

午前中は寝坊して、午後からの参加でした。以下、個人的なメモです。間違っているかも。

2008-10-25

SICP勉強会#4に参加しています

http://groups.google.co.jp/group/sicp-in-kansai/web/sicp-4
ごぶさたしています。久し振りにコンピュータ関係の集いに参加しています。

SICPをEmacsでINFOを使って読むと楽らしいとのこと。この辺を参照。http://d.hatena.ne.jp/mahata/20080921/1221958711
1.29は、シンプソンの公式 - Wikipediaより合成シンプソン公式が使われている。問題でヒントが示されている式を使った場合がsimpson、Wikipediaのもうひとつの式を使うとsimpson2。

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
	 (sum term (next a) next b))))

(define (cube n)
  (* n n n))

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))

(integral cube 0 1 0.01)
; gosh> 0.24998750000000042
(integral cube 0 1 0.001)
; gosh> 0.249999875000001

(define (simpson f a b n)
  (define h
    (/ (- b a) n))
  (define (y k)
    (f (+ a (* k h))))
  (define (term i)
    (+ (y (- (* 2 i) 2))
       (* 4 (y (- (* 2 i) 1)))
       (y (* 2 i))))
  (define (next i)
    (+ i 1))
  (/ (* h (sum term 1 next (/ n 2))) 3))

(simpson cube 0.0 1 100)
; gosh> 0.2500000000000001
(simpson cube 0.0 1 1000)
; gosh> 0.25000000000000017

(define (simpson2 f a b n)
  (define h
    (/ (- b a) n))
  (define (x i)
    (+ a (* i h)))
  (define (next i)
    (+ i 1))
  (define (sum1)
    (* 2
       (sum (lambda (j) (f (x (* j 2))))
	    1
	    next
	    (- (/ n 2) 1))))
  (define (sum2)
    (* 4
       (sum (lambda (j) (f (x (- (* j 2) 1))))
	    1
	    next
	    (/ n 2))))
  (/ (* h (+ (f a) (sum1) (sum2) (f b))) 3))

(simpson2 cube 0.0 1 100)
; gosh> 0.25000000000000006
(simpson2 cube 0.0 1 1000)
; gosh> 0.2500000000000002

1.30は普通に末尾再帰にするだけ。のはず。

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
	 (sum term (next a) next b))))

(define (sum2 term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(iter (next a) (+ result (term a)))))
  (iter a 0))

(define (id n) n)

(sum id 1 (lambda (i) (+ i 1)) 10)
(sum2 id 1 (lambda (i) (+ i 1)) 10)

1.31。なんとなくヴォリスの公式ぽいです。参照: 物理講義室・改Ⅱ πについて2(ヴォリスの公式)

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
	 (product term (next a) next b))))

(define (product2 term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(iter (next a) (* result (term a)))))
  (iter a 1))

(define (id n) n)
(define (inc i) (+ i 1))

(product id 1 inc 4)
(product2 id 1 inc 4)

(define (factorial n)
  (product id 1 inc n))

(define (pai n)
  (define (term i)
    (/ (* i (+ i 2.0)) (square (+ i 1.0))))
  (define (next i)
    (+ i 2.0))
  (define (square x) (* x x))
  (* 4.0 (product term 2 next n)))

(pai 1000) ; gosh> 3.1431607055322752

1.32。らぶらぶinjectに誘導されている気がします。

(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(iter (next a) (combiner result (term a)))))
  (iter a null-value))

(define (sum term a next b)
  (accumulate + 0 term a next b))

(define (product term a next b)
  (accumulate * 1 term a next b))

(define (id n) n)
(define (inc i) (+ i 1))

(sum id 1 inc 10)
; gosh> 55
(product id 1 inc 10)
; gosh> 3628800

1.33。prime?とかgcdは過去問から。

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

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

(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 (prime? n)
  (= n (smallest-divisor n)))

(define (filtered-accumulate filter combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(if (filter a)
	    (iter (next a) (combiner result (term a)))
	    (iter (next a) result))))
  (iter a null-value))

(define (sum term a next b)
  (accumulate + 0 term a next b))

(define (inc i) (+ i 1))
(define (id n) n)

(define (f1 a b)
  (filtered-accumulate prime? + 0 square a inc b))

(f1 0 5) ; 1 + 4 + 9 + 25
; gosh> 39

(define (f2 a b)
  (define (gcd a b)
    (if (= b 0)
	a
	(gcd b (remainder a b))))
  (define (filter x)
    (= (gcd x b) 1))
  (filtered-accumulate filter * 1 id a inc b))

(f2 1 10) ; 1 * 3 * 7 * 9
; gosh> 189

1.34。やっとlambdaがでてきました。

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

(define (f g)
  (g 2))

(f square)

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

(f f)
;  -> (f 2)
;  -> (2 2)
gosh> *** ERROR: invalid application: (2 2)
Stack Trace:

2008-09-22

逆ポーランド電卓を実装してみました。

Ruby

第30回Ruby/Rails勉強会に参加しました - サイログ。MiyakoとかRubyとかなんとか＋Miyako ACCESS MAPより。
初級者レッスンで逆ポーランド電卓のお題が出ていたようなので、僕も実装してみました。やっぱりエラーチェックが面倒です…

def rpn(expr)
  result = expr.inject([]) do |stack, e|
    case e
    when :+, :-, :*, :/
      raise "invalid expr." if stack.size < 2
      o2 = stack.pop
      o1 = stack.pop
      raise "divided by 0." if e == :/ and o2.zero?
      stack.push(o1.send(e, o2))
    when Integer
      stack.push(e)
    end
  end
  raise "invalid expr." unless result.size == 1 
  result.first
end

def main(args)
  expr = args.map do |arg|
    case arg
    when /^\d+$/
      arg.to_i
    when '+', '-', '*', '/'
      arg.to_sym
    else
      raise "invalid input #{arg}."
    end
  end
  puts rpn(expr)
end

if __FILE__ == $0
  # main(['1', '2', '+', '3', '4', '+', '*', '10', '-'])
  main(ARGV)
end