Решение упражнения 1.11 из SICP
Сначала запишем процедуру, вычисляющую 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))))
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) ) ) ))
Write a comment