Hatena::Groupcsnagoya-sicp

クラなんとかの日記 このページをアンテナに追加 RSSフィード

 | 

2009-06-11準備会

2.34

| 2.34 - クラなんとかの日記 を含むブックマーク はてなブックマーク - 2.34 - クラなんとかの日記 2.34 - クラなんとかの日記 のブックマークコメント

(k_n k_{n-1} ... k_1 k_0) のように項のリストが与えられたとして.

  • T_0 = k_0
  • T_n = k_n + T_{n-1} * x

こんな感じで,前の項をx 倍して,項を足す漸化式を考えればよい.

例えば,(1 3 0 5 0 1) を項のリストとして与えられた場合,以下のように式が変形する.

(ここで,リストとは逆順に項が与えられていくことに注意)

  1. 1
  2. 0 + (1) * x = x
  3. 5 + (x) * x = 5 + x^2
  4. 0 + (5 + x^2) * x = 5x + x^3
  5. 3 + (5x + x^3) * x = 3 + 5x^2 + x^4
  6. 1 + (3 + 5x^2 + x^4) * x = 1 + 3x + 5x^3 + x^5
#!/usr/bin/env gosh
;; -*- coding: utf-8; -*-
; 

;; 準備
(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

;; 答え
(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coefficient higher-term)
                (+ (* higher-term x)
                   this-coefficient))
              0
              coefficient-sequence))

;; 確認
(define x 2)
(define cs (list 1 3 0 5 0 1))

(display x) (newline) ; 2
(display cs) (newline) ; (1 3 0 5 0 1)
(display (horner-eval x cs)) (newline) ; 79 (= 1 + 3x + 5x^3 + x^5 = 1 + 6 + 40 + 32)
 |