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

20 August, 2007 (00:15) | Решения упражнений

Сначала запишем процедуру, вычисляющую f с помощью рекурсивного процесса. Это делается весьма прямолинейно:

(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1))
         (f (- n 2))
         (f (- n 3)))))

Теперь запишем решение с помощью итеративного процесса. Для этого будем использовать следующую трансформацию :

a <- a + b + c
b <- a
c <- b

Сама же функция будет выглядеть так (кстати, сравните, насколько она эффективнее предыдущего варианта, вычислив функции с аргументами 30 и 40):

(define (f n)
  (f-iter 2 1 0 n))
(define (f-iter a b c count)
  (if (= count 0)
      c
      (f-iter (+ a b c) a b (- count 1))))

Comments

Comment from Sergey Khenkin
Date: August 20, 2007, 12:25 am

Важный момент!
По какой-то неочевидной причине в русском переводе книги условие упражнения 1.11 было изменено.

В русскоязычном варианте функция f задается как
f(n) = f(n-1) + f(n-2) + f(n-3), n>=3.

В то же время в оригинале f задается несколько иначе:
f(n) = f(n-1) + 2*f(n-2) + 3*f(n-3), n>=3.

Выше приведены решения для русского варианта. Решения для оригинала получаются абсолютно аналогично. Можете подсмотреть у Кена Дика, только лучше берите не его решение, а предложенное вот в этом комментарии.

Comment from Roman Zhukov
Date: September 24, 2008, 12:55 pm

Предложенная ункция f, использующая итеративный процесс не будет работать с отрицательными n. Вот мой вариант: (define (f n)
(define (f-iter n0 fn1 fn2 fn3)
(if (= n0 n)
(+ fn1 fn2 fn3)
(f-iter (+ n0 1) (+ fn1 fn2 fn3) fn1 fn2)))
(if (< n 3)
n
(f-iter 3 (f 2) (f 1) (f 0))))

Comment from Nickolay
Date: October 6, 2008, 7:51 pm

Когда делал это упражнение для итеративного процесса, исходил из следующих рассуждений. У нас есть послед-ть 0,1,2,3,6,11,20 и т.д. по условию на ф-цию. Т.к. итеративный процесс обладает переменными состояния и правилом перехода из одного состояния в другое, то логично для описания состояния “таскать” за собой три последних члена последовательности, ну а правило простое - 1-й член выкидваем, сдвигаем на его место следующие два, а третий считаем по ф-ции. Отсюда решение:

(define (f-iter n)
  (define (f-iter-iter a b c count)
    (cond ((= count 0) a)
	  (else (f-iter-iter b c (+ a b c) (- count 1)))))

  (f-iter-iter 0 1 2 n))

Comment from синдикат
Date: January 21, 2010, 3:51 pm

Роман Жуков правильно заметил насчёт отрицательных, поэтому моя программа получилась так:


(define (fib3 n)
(if (< n 3)
n
(fib3-iter 2 1 0 n)))

(define (fib3-iter a b c count)
(if (= count 0)
c
(fib3-iter (+ a b c) a b (- count 1))))

Comment from Anonymous
Date: July 12, 2010, 11:31 pm

Или так, без 2 лишних итераций:
(define (f n)
(if (< n 3)
n
(f_iter 2 1 0 n)))

(define (f_iter a b c n)
(if (= n 2)
a
(f_iter (+ a b c) a b (- n 1))))

Write a comment