[sicp][help]задача 1.11

>что почитать по этой теме?
SICP. ЕМНИП нужно написать рекурсивную функцию, которая выполняется итеративно (т.е. с tail call, для этого нужно, чтобы последней операцией функции до выхода был вызов самой себя). Глава перед задачей.

Что надо делать - понятно, глава перечитана раза 4. Непонятно как выделить переменные определяющие состояние. Вообще бядя с матаном =(

ЩИТО? Какой матан? Идёшь итеративно вверх и, очевидно, хранишь последние три.

> Отсюда вопрос - что почитать по этой теме (хотя бы в каком разделе матана искать >_<)?
Если очень хочется «матана», то открой для себя решение линейных рекуррентных соотношений с постоянными коэффициентами.
Но скорее всего в задании речь шла о хвостовой рекурсии.

Пробовал в лоб так и этак - не сходится. Потому и пытаюсь выяснить, есть ли какое-то обобщённое (развёрнутое, для тупых) описание методики. Понимаю что туплю, но спрсить больше негде. Математичка в универе послала, сказав, что в численных методах не разбирается.

Понятно, что там хвостовая рекурсия. Даже понятно, что такое хвостовая рекурсия. Непонятно как выбрать переменные описывающие состояние.

В этой же главе подробнейше обсосана итеративная функция фиббоначи, сделай по образу и подобию.

>Непонятно как выбрать переменные описывающие состояние.

Для вычисления каждого следующего значения нужно знать три предыдущих, вот и состояние. Или что конкретно не так?

> Математичка в универе послала, сказав, что в численных методах не разбирается.
В этом нет никакой математики. Ну почти. Если хочется сформулировать подход с математикой, то у тебя есть вектор {f(3), f(2), f(1)}. Ты его N-3 раза умножаешь слева на матрицу линейного преобразования {{1, 2, 3}, {1, 0, 0}, {0, 1, 0}} и получаешь вектор {f(N), f(N-1), f(N-2)}.

А тебе не нужно это формулировать математически. Просто у тебя есть функция f(N, step, A, B, C). Если N = 1, она равна A, если N = 2, то B, если N = 3, то С. Если N > 3, то если step < N, выдать f(N, step + 1, A+2*B+3*C, A, B), иначе выдать A.

> Просто у тебя есть функция
Соответственно вызывать f(N, 0, 3, 2, 1). Надеюсь, ничего не попутал, но суть все равно по идее ясна.

В Фибоначи 2 переменных состояния - на схеме отчётливо видно 2 типа листьев: 1 и 0 - начальные значения этих переменных. На каждом шаге преобразоваия a -> a+b; b -> a.

В задаче 3 переменных состояния, 3 вида листьев: 2, 1, 0. Так?
Далее пытаюсь перебирать варианты их преобразования (a -> a+b+c; b -> b+c; c -> a и т.п.). Получается другая последовательность на выходе.

Изначально попалась формулировка задачи, где f(n) = f(n - 1) + f(n - 2) + f(n - 3). Что делать с коэффициентами 2 и 3 в f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) не понимаю.

Математики не хочется, но не литейщика же с такими вопросам трясти?)

a->a+2*b+3*c, b->a, c->b

Далее пытаюсь перебирать варианты их преобразования

не надо ничего перебирать, надо просто вывести преобразование, которое осуществлятся на каждом шаге, на предыдущем шаге a=f(n-1), b=f(n-2), c=f(n-3), на следующем шаге хотим получить a=f(n), b=f(n-1), c=f(n-2), а рекурсивная формула для f(n) у нас как раз и дана.

Спасибо.

Отсюда вопрос - что почитать по этой теме?

Внезапно, SICP, эту же главу выше по тексту. По сути в этом случае в качестве параметров функции выступают 3 предыдущих значения, необходимых для вычисления текущего, и счетчик, по которому определяется конец вычислений и возврат.

Да, вот что получилось у меня.

(define (myfun n)
             (define (fiter a b c n)
                          (if (= n 0) c (fiter (+ a (* 2 b) (* 3 c)) a b (- n 1))))
              (fiter 2 1 0 n))

И да, в упражнении 1.11 f(n) = f(n-1) + f(n-2) + f(n-3) же, без коэффициентов. Что, впрочем, особо роли не играет.