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

Упражнение 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))))

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

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

Ответы

Ответ 1

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

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

Другими словами, это может помочь начать думать об этом как о цикле 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, но я надеюсь, что теперь вы сможете увидеть мыслительный процесс.

Ответ 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₁ + 2b₁ +3c₁

где

a ₁= f (2) = 2,

b ₁= f (1) = 1,

c ₁= 0

так как f (n) = n для n < 3.

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

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

  Step 2:  f(4) = f(3) + 2a₁ + 3b₁

Итак:

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₂ + 3b₂

Итак:

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}

c _step= b _{step -1}

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

Ответ 3

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

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

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

(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) и счетчика декремента.

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

Ответ 4

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

Проблема с Билл-подход, цитируемый в вашем вопросе, заключается в том, что он не сразу понимает, какой смысл передают переменные состояния, 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, мы закончили.

Ответ 5

Функция 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, поскольку код, который вы цитируете, конечно, полностью эквивалентен.

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