Решение упражнения 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))))

Comment from bery0za
Date: December 18, 2014, 11:24 am

В процедуре product я бы ещё учёл, что если изначально a > b, то она должна вернуть не 1, а 0

Comment from Irv
Date: January 8, 2016, 11:30 am

(define (multiply-iterative term a next b)
  (define (iter x result)
    (if (> x b)
        result
        (iter (next x) (* result (term x)))))
  (iter a 1))


(define (multiply-recursive term a next b)
  (if (> a b)
      1
      (* (term a) (multiply-recursive term (next a) next b))))

(define (fib n)
  (define (next x) (+ 1 x))
  (define (term x) x)
  (multiply-recursive term 1 next n))

(fib 4)
  
(define (pi n)
  (define (next x) (+ 1 x))
  (define (term x)
    (if (even? x)
        (/ (+ 2 x) (+ 1 x))
        (/ (+ 1 x) (+ 2 x))))
  (* 4.0 (multiply-iterative term 1 next n)))


(pi 10000)

Write a comment