Не знаю, как решить упражнение SICP 1.11

Question

Упражнение 1.11 :

Функция f определяется правилом f(n) = n, если n < 3, и f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3), если n > 3. Напишите процедуру, которая вычисляет f с помощью рекурсивного процесса. Напишите процедуру, которая вычисляет f с помощью итеративного процесса.

Реализовать его рекурсивно достаточно просто. Но я не мог понять, как сделать это итеративно. Я попытался сравнить с приведенным примером Фибоначчи, но я не знал, как использовать его в качестве аналогии. Поэтому я сдался (позор мне) и Гуглил для объяснения , и я нашел это:

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

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

После прочтения я понимаю код и как он работает. Но что я не понимаю, так это процесс, необходимый для перехода от рекурсивного определения функции к этому. Я не понимаю, как код мог сформироваться в чьей-то голове.

Не могли бы вы объяснить мыслительный процесс, необходимый для достижения решения?

Answer 1

Вам нужно фиксировать состояние в некоторых аккумуляторах и обновлять состояние на каждой итерации.

Если у вас есть опыт работы с императивным языком, представьте, что вы пишете цикл while и отслеживаете информацию в переменных во время каждой итерации цикла. Какие переменные вам нужны? Как бы вы их обновили? Это именно то, что вам нужно сделать, чтобы сделать итеративный (рекурсивный) набор вызовов в Scheme.

Другими словами, это может помочь начать думать об этом как о цикле while вместо рекурсивного определения. В конце концов вы будете достаточно беглыми с рекурсивными -> итерационными преобразованиями, и вам не понадобится дополнительная помощь для начала работы.

---

Для этого конкретного примера вы должны внимательно посмотреть на три вызова функций, потому что не сразу понятно, как их представить. Тем не менее, вот вероятный мыслительный процесс: (в псевдокоде Python, чтобы подчеркнуть императивность)

Каждый рекурсивный шаг отслеживает три вещи:

f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) 

Итак, мне нужно три элемента состояния для отслеживания текущего, последнего и предпоследнего значения f. (то есть f(n-1), f(n-2) and f(n-3).) Назовите их a, b, c. Я должен обновить эти части внутри каждого цикла:

for _ in 2..n:
    a = NEWVALUE
    b = a
    c = b
return a

Так что же такое NEWVALUE? Хорошо, теперь, когда у нас есть представления f(n-1), f(n-2) and f(n-3), это просто рекурсивное уравнение:

for _ in 2..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

Теперь осталось только определить начальные значения a, b and c. Но это легко, так как мы знаем, что f(n) = n if n < 3.

if n < 3: return n
a = 2 # f(n-1) where n = 3
b = 1 # f(n-2)
c = 0 # f(n-3)
# now start off counting at 3
for _ in 3..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

Это все еще немного отличается от итерационной версии Scheme, но я надеюсь, что теперь вы можете увидеть процесс мышления.

Answer 2

Я думаю, вы спрашиваете, как можно найти алгоритм естественным образом, вне «шаблона проектирования».

Мне было полезно посмотреть на расширение f (n) для каждого значения n:

f(0) = 0  |
f(1) = 1  | all known values
f(2) = 2  |

f(3) = f(2) + 2f(1) + 3f(0)
f(4) = f(3) + 2f(2) + 3f(1)
f(5) = f(4) + 2f(3) + 3f(2)
f(6) = f(5) + 2f(4) + 3f(3)

Если присмотреться к f (3), мы увидим, что мы можем сразу вычислить его по известным значениям. Что нам нужно для вычисления f (4)?

Нам нужно как минимум вычислить f (3) + [остальное]. Но когда мы вычисляем f (3), мы также вычисляем f (2) и f (1), которые нам нужны для вычисления [остатка] функции f (4).

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)

Итак, для любого числа n я могу начать с вычисления f (3) и повторно использовать значения, которые я использую для вычисления f (3), чтобы вычислить f (4) ... и шаблон продолжается ...

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)
            ↘       ↘
f(5) = f(4) + 2f(3) + 3f(2)

Поскольку мы будем их повторно использовать, давайте дадим им имя a, b, c. подписаться с шага мы находимся и пройти через расчет f (5):

  Step 1:    f(3) = f(2) + 2f(1) + 3f(0) or f(3) = a<sub>1</sub> + 2b<sub>1</sub> +3c<sub>1</sub>

, где

a ₁ = f (2) = 2,

b ₁ = f (1) = 1,

с ₁ = 0

, поскольку f (n) = n при n <3. </p>

Таким образом:

f (3) = a ₁ + 2b ₁ + 3c ₁ = 4

  Step 2:  f(4) = f(3) + 2a<sub>1</sub> + 3b<sub>1</sub>

Итак:

a ₂ = f (3) = 4 (вычислено выше в шаге 1),

b ₂ = a ₁ = f (2) = 2,

c ₂ = b ₁ = f (1) = 1

Таким образом:

f (4) = 4 + 2 * 2 + 3 * 1 = 11

  Step 3:  f(5) = f(4) + 2a<sub>2</sub> + 3b<sub>2</sub>

Итак:

a ₃ = f (4) = 11 (вычислено выше в шаге 2),

b ₃ = a ₂ = f (3) = 4,

c ₃ = b ₂ = f (2) = 2

Таким образом:

f (5) = 11 + 2 * 4 + 3 * 2 = 25

На протяжении вышеупомянутого вычисления мы фиксируем состояние в предыдущем вычислении и передаем его на следующий шаг, particularily:

a _step = результат шага - 1

b _step = a _{step - 1}

с _шаг = b _{шаг -1}

Как только я увидел это, тогда придумать итерационную версию было просто.

Answer 3

Поскольку пост, на который вы ссылались, много описывает решение, я постараюсь дать только дополнительную информацию.

Вы пытаетесь определить хвостовую рекурсивную функцию в Схеме, учитывая (не хвостовое) рекурсивное определение.

Базовый случай рекурсии (f (n) = n, если n <3) обрабатывается обеими функциями. Я не совсем уверен, почему автор делает это; первая функция может быть просто: </p>

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

Общая форма будет:

(define (f-iter ... n)
   (if (base-case? n)
       base-result
       (f-iter ...)))

Замечание: я еще не заполнил параметры для f-iter, потому что сначала нужно понять, какое состояние нужно передавать от одной итерации к другой.

Теперь давайте посмотрим на зависимости рекурсивной формы f (n). Он ссылается на f (n - 1), f (n - 2) и f (n - 3), поэтому нам нужно соблюдать эти значения. И, конечно же, нам нужно само значение n, чтобы мы могли прекратить его повторение.

Так вот как вы придумали хвостовой рекурсивный вызов: мы вычисляем f (n) для использования в качестве f (n - 1), поворачиваем f (n - 1) в f (n - 2) и f (n) - 2) до f (n - 3), и счет уменьшения.

Если это по-прежнему не помогает, пожалуйста, попробуйте задать более конкретный вопрос - очень трудно ответить, когда вы пишете «Я не понимаю», учитывая уже довольно подробное объяснение.

Answer 4

Функция f определяется правилом f(n) = n, if n<3 и f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3), if n > 3. Напишите процедуру, которая вычисляет f с помощью рекурсивного процесса.

Это уже уже написано:

f(n) = n,                                  (* if *)  n < 3
     = f(n - 1) + 2f(n - 2) + 3f(n - 3),   (* if *)  n > 3

Верьте или нет, когда-то был такой язык . Чтобы записать это на другом языке, это просто вопрос синтаксиса. И, кстати, определение, которое вы (неправильно) цитируете, содержит ошибку, которая теперь очень очевидна и ясна.

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

Итерация означает движение вперед ( есть ваше объяснение!) В противоположность рекурсии назад сначала:

f(n)   =  f(n - 1) + 2f(n - 2) + 3f(n - 3) 
       =  a        + 2b        + 3c
f(n+1) =  f(n    ) + 2f(n - 1) + 3f(n - 2)
       =  a'       + 2b'       + 3c'          a' = a+2b+3c, b' = a, c' = b
......

Таким образом, переходы состояния задачи описываются как

 (n, a, b, c)  ->  (n+1, a+2*b+3*c, a, b)

Мы могли бы закодировать его как

g (n, a, b, c) = g (n+1, a+2*b+3*c, a, b)

но, конечно, это никогда не остановится. Поэтому вместо этого мы должны иметь

f n = g (2, 2, 1, 0)
  where
  g (k, a, b, c) = g (k+1, a+2*b+3*c, a, b),    (* if *) k < n
  g (k, a, b, c) = a,                           otherwise 

и это уже в точности как код, о котором вы спрашивали, вплоть до синтаксиса.

Подсчет до n более естественен здесь, следуя нашей парадигме «идти вперед», но обратный отсчет до 0 , как код, который вы цитируете, конечно, полностью эквивалентен.

Угловые кейсы и возможные ошибки не учитываются: упражнение неинтересные технические детали.

Answer 5

Я собираюсь подойти к этому несколько другим подходом к другим ответам здесь, сосредоточенным на том, как стиль кодирования может облегчить понимание мыслительного процесса, стоящего за таким алгоритмом.

Проблема с подходом Билла , процитированным в вашем вопросе, заключается в том, что не сразу понятно, что означает , передаваемое переменными состояния, a, b и c. Их имена не передают никакой информации, и пост Билла не описывает никакого инварианта или другого правила, которому они подчиняются. Мне легче как формулировать, так и понимать итерационные алгоритмы, если переменные состояния подчиняются некоторым документированным правилам, описывающим их отношения друг к другу.

Имея это в виду, рассмотрим эту альтернативную формулировку точно такого же алгоритма, которая отличается от только Билла тем, что имеет более значимые имена переменных для a, b и c и инкрементную переменную-счетчик вместо убывающей один:

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

(define (f-iter n 
                i 
                f-of-i-minus-2
                f-of-i-minus-1
                f-of-i)
    (if (= i n)
        f-of-i
        (f-iter n
                (+ i 1)
                f-of-i-minus-1
                f-of-i
                (+ f-of-i
                   (* 2 f-of-i-minus-1)
                   (* 3 f-of-i-minus-2)))))

Внезапно правильность алгоритма - и мыслительный процесс его создания - просто увидеть и описать. Для расчета f(n):

• У нас есть переменная счетчика i, которая начинается с 2 и увеличивается до n, увеличиваясь на 1 при каждом вызове до f-iter.
• На каждом шаге мы отслеживаем f(i), f(i-1) и f(i-2), что достаточно для расчета f(i+1).
• Как только i=n, мы закончили.