Понятия не имею, как решить SICP упражнение 1.11

https://stackoverflow.com/questions/2365993

23-09-2019
|

Вопрос

Функция 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))))

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

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

Решение

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

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

Другие советы

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

Мне было полезно посмотреть на расширение 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₁ + 3с₁ = 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

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

a_шаг = результат выполнения шага - 1

b_шаг = a_{шаг - 1}

c_шаг = b_{шаг -1}

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

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

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

Базовый случай рекурсии (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) и уменьшаем счетчик.

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

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

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

Функция 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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow