Решение упражнения 1.31 из SICP

18 October, 2007 (21:11) | Решения упражнений

Упражнение по написанию процедуры, вычисляющей произведение полезное, но несложное, так как аналогии с суммированием просматриваются очень легко. Все понимают, что роль операции + из суммирования в умножении выполняет операция *. Роль нуля выполняет единица. Те, кто изучал линейную алгебру, вообще особой разницы между сложением и умножением не видят :)

Итак, процедуру product можно записать так (порождается рекурсивный процесс):

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

либо так (порождаемый процесс итеративен):

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

Факториал вычисляется следующим образом:

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

Для вычисления π product можно использовать так (здесь параметр n - это количество элементов в разложении плюс один):

(define (pi n)
  (define (pi-term k)
    (/ (* (- k 1) (+ k 1)) (square k)))
  (define (pi-next k)
    (+ k 2))
  (* 4 (product pi-term 3 pi-next n)))

Как видим, все очень просто и удобно.

Comments

Comment from hub
Date: September 25, 2008, 3:13 pm

А как насчет следующей реализации:


(define (my-pi n)
(define (pi-term x)
(if (odd? x)
(/ (+ x 1) (+ x 2))
(/ (+ x 2) (+ x 1))))
(define (pi-next x) (+ x 1))
(* 4.0 (product pi-term 1 pi-next n)))

Comment from meduza
Date: October 20, 2008, 8:29 am

у меня так:

(define (product f a b next)
  (define (iter a result)
    (if (> a b)
      result
      (iter (next a) (* (f a) result))))
  (iter a 1))  

(define (pi n)
  (define (sqr x) (* x x))
  (define (f n) (/ (+ 1 n) n))
  (define (next n) (+ 2 n))
  (define p (product f 1 n next))
  (* (/ 2.0 n) (sqr p)))

мне кажется в квадрат возводить лучше в самом конце, может быть я ошибаюсь

Pingback from Упражнение 1.31 | Записки сумасшедшего
Date: May 14, 2011, 3:51 pm

[…] версию можно улучшить еще в 2 раза, но этот метод я подсмотрел и поэтому решил не постить […]

Comment from vladimir
Date: November 3, 2011, 3:53 am

а если знаешь формулу Валлиса то намного легче

Comment from ivan
Date: February 3, 2012, 5:17 am


(define (pi n)
(define (next-pi a)
(+ a 2))
(/ (* 2 (product square 4 next-pi n))
(* (+ n 1) (product square 3 next-pi n))))

Write a comment