SICP по-русски

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))))

Comment from Elvis
Date: August 13, 2012, 10:53 am

Неужели cond непредсказуема?

Странная вещь

(define (f-rekursion n)
(cond ((< n 3) n)
(else (+
(f (- n 1))
(f (- n 2))
(f (- n 3))))))


Выдает:

> (f-rekursion 3)
6
> (f-rekursion 4)
12

Посмотрел на Ваш ответ, а у Вас if. Думаю может дело в том что и в задании 1.6 сначала cond вычисляет else и выдает результат прежде чем просчитает (< n 3). Просчитал else на бумаге выходит 3, а не 6, странно. Затем просматривал еще раз и запустил программу еще раз.
Выдает:

> (f-rekursion 3)
3
> (f-rekursion 4)
6

прислал бы скриншот, но тут картинки не добавляются.

Неужели cond непредсказуема?

Comment from Elvis
Date: August 13, 2012, 11:01 am

Прошу прощение за флуд предыдущее сообщение можно удалить ошибка видна не вооруженным глазом.

Comment from filimon
Date: September 10, 2012, 12:53 pm

Вариант Сергея не работает с отрицательными числами, это да. Но особо усложнять ничего не нужно. Можно просто добавить одну лишнюю переменную, то есть, вызывать f-iter с пятью аргументами. Тогда просто введём ещё одну проверку на завершение, а, значит, вместо if используем cond. По-большому счёту изменения минимальны. Просто лишняя проверка и лишняя переменная.


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


Comment from filimon
Date: March 13, 2013, 12:51 pm

Решил тут давеча перерешать задачки из SICP ещё разок. Заметил, что моё предыдущее решение этого упражнения получилось чуть большего размера, чем новое.. Так что вот.. Этот вариант работает и с отрицательными числами, и вообще работает правильно..

(define (f n)
(define (f-iter a b c count)
(cond ((and (< count 3) (= c 3)) count)
((and ( c 3)) c)
(else (f-iter b c (+ a b c) (- count 1)))))
(f-iter 1 2 3 n))


Comment from filimon
Date: March 13, 2013, 12:55 pm

Чёрт.. коряво вставил код.. жаль, нельзя пост удалить.. вот..

(define (f n)
(define (f-iter a b c count)
(cond ((and (< count 3) (= c 3)) count)
((and ( c 3)) c)
(else (f-iter b c (+ a b c) (- count 1)))))
(f-iter 1 2 3 n)


Comment from filimon
Date: March 13, 2013, 12:56 pm

Короче, чёта не хочет оно правильно вставляться.. тупо пропускает половину строки.. не понимаю, почему.. 🙁

Comment from Evgeniy
Date: November 20, 2013, 8:41 am

У меня окончательная версия такая вышла, хотя признаюсь, обшлифовал идеями которые проскакивали выше.
(define (f n)
(define (f-iter a b c counter)
(cond
((= counter n) c)
(else (f-iter b c (+ a b c) (+ counter 1)))
))
(if (< n 3)
n
(f-iter 0 1 2 3))
)

Comment from Evgeniy
Date: November 20, 2013, 8:42 am

Простите

(define (f n)
(define (f-iter a b c counter)
(cond
((= counter n) c)
(else (f-iter b c (+ a b c) (+ counter 1)))
))
(if (< n 3)
n
(f-iter 0 1 2 3))
)


Comment from filimonix
Date: January 6, 2014, 6:25 pm


(define (f-iter n a b c)
(if (< n 3)
c
(f-iter (- n 1) b c (+ a b c))))
(define (f n)
(if (< n 3)
n
(f-iter n 0 1 2)))


Comment from Hahatsker
Date: January 13, 2015, 6:34 pm

Не обязательно count сравнивать с 0… он не успеет дойти до него)
Вот моё решение:

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

Comment from Vladimir
Date: January 8, 2016, 5:48 pm

просто добавить cond и все нормально работает

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