Não tenho ideia de como resolver o exercício 1.11 do SICP

https://stackoverflow.com/questions/2365993

23-09-2019
|

Pergunta

Uma função f é definido pela regra que f(n) = n se n < 3 e f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) se n > 3.Escreva um procedimento que calcule f por meio de um processo recursivo.Escreva um procedimento que calcule f por meio de um processo iterativo.

Implementá-lo recursivamente é bastante simples.Mas não consegui descobrir como fazer isso iterativamente.Tentei comparar com o exemplo de Fibonacci dado, mas não sabia como usá-lo como analogia.Então desisti (que vergonha) e pesquisei no Google uma explicação, e encontrei isto:

(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))))

Depois de lê-lo, entendo o código e como ele funciona.Mas o que não entendo é o processo necessário para passar da definição recursiva da função até isso.Não entendo como o código poderia ter se formado na cabeça de alguém.

Você poderia explicar o processo de pensamento necessário para chegar à solução?

Solução

Você precisa capturar o estado em alguns acumuladores e atualizar o estado a cada iteração.

Se você tem experiência em uma linguagem imperativa, imagine escrever um loop while e rastrear informações em variáveis durante cada iteração do loop.Quais variáveis você precisaria?Como você os atualizaria?Isso é exatamente o que você precisa fazer para fazer um conjunto iterativo (recursivo de cauda) de chamadas no Scheme.

Em outras palavras, pode ajudar começar a pensar nisso como um loop while em vez de uma definição recursiva.Eventualmente, você será fluente o suficiente com transformações recursivas -> iterativas e não precisará de ajuda extra para começar.

Para este exemplo específico, você deve observar atentamente as três chamadas de função, porque não está imediatamente claro como representá-las.No entanto, aqui está o provável processo de pensamento:(em pseudocódigo Python para enfatizar a imperatividade)

Cada etapa recursiva monitora três coisas:

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

Então, preciso de três partes de estado para rastrear o valor atual, o último e o penúltimo valor de f.(aquilo é, f(n-1), f(n-2) and f(n-3).) Chame-os a, b, c.Tenho que atualizar essas peças dentro de cada loop:

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

Então, o que é NOVOVALOR?Bem, agora que temos representações de f(n-1), f(n-2) and f(n-3), é apenas a equação recursiva:

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

Agora só falta descobrir os valores iniciais de a, b and c.Mas isso é fácil, pois sabemos que 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

Isso ainda é um pouco diferente da versão iterativa do Scheme, mas espero que você possa ver o processo de pensamento agora.

Outras dicas

Eu acho que você está perguntando como alguém pode descobrir o algoritmo naturalmente, fora de um 'padrão de design'.

Foi útil para mim olhar para a expansão do f (n) em cada valor 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)

Olhando mais de perto para F (3), vemos que podemos calculá -lo imediatamente a partir dos valores conhecidos. O que precisamos calcular F (4)?

Precisamos pelo menos calcular F (3) + [o restante]. Mas, como calculamos F (3), calculamos também F (2) e F (1), que precisamos de calcular [o restante] de F (4).

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

Portanto, para qualquer número n, posso começar calculando f (3) e reutilizando os valores que uso para calcular F (3) para calcular F (4) ... e o padrão continua ...

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

Como vamos reutilizá -los, vamos dar a eles um nome a, b, c. Subscrito com a etapa em que estamos e percorre um cálculo de f (5):

  Step 1:    f(3) = f(2) + 2f(1) + 3f(0) or f(3) = a₁ + 2b₁ +3c₁

Onde

uma₁ = f (2) = 2,

b₁ = f (1) = 1,

c₁ = 0

Desde f (n) = n para n <3.

Desta forma:

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

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

Então:

uma₂ = f (3) = 4 (calculado acima na etapa 1),

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

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

Desta forma:

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

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

Então:

uma₃ = f (4) = 11 (calculado acima na etapa 2),

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

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

Desta forma:

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

Em todo o cálculo acima, capturamos o estado no cálculo anterior e o passamos para a próxima etapa, particularmente:

uma_degrau = resultado da etapa - 1

b_degrau = a_{passo 1}

c_degrau = b_{passo 1}

Uma vez que vi isso, depois criar a versão iterativa foi direta.

Como a postagem a que você vinculou descreve muito sobre a solução, tentarei fornecer apenas informações complementares.

Você está tentando definir uma função recursiva da cauda no esquema aqui, dada uma definição recursiva (não cauda).

O caso base da recursão (f (n) = n se n <3) é tratado por ambas as funções. Não sei ao certo por que o autor faz isso; A primeira função pode ser simplesmente:

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

A forma geral seria:

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

Observe que eu ainda não preencheu os parâmetros para o F-TITER, porque você primeiro precisa entender o que o estado precisa ser passado de uma iteração para outra.

Agora, vejamos as dependências da forma recursiva de f (n). Ele faz referências F (n - 1), F (n - 2) e F (n - 3), por isso precisamos manter -se em torno desses valores. E é claro que precisamos do valor de N em si, para que possamos parar de iterar sobre ele.

Então é assim que você cria a chamada Recursiva a cauda: Calculamos f (n) para usar como f (n - 1), gire f (n - 1) para f (n - 2) e f (n - 2) para f (n - 3) e contagem de decréscimo.

Se isso ainda não ajudar, tente fazer uma pergunta mais específica - é realmente difícil responder quando você escrever "eu não entendo", dada uma explicação relativamente completa já.

Vou abordar isso com uma abordagem um pouco diferente das outras respostas aqui, focada em como o estilo de codificação pode tornar o processo de pensamento por trás de um algoritmo como esse mais fácil de compreender.

O problema com Abordagem de Bill, citado na sua pergunta, é que não está imediatamente claro o que significado é transmitido pelas variáveis de estado, a, b, e c.Seus nomes não transmitem nenhuma informação, e a postagem de Bill não descreve nenhuma regra invariante ou outra regra que eles obedeçam.Acho mais fácil formular e compreender algoritmos iterativos se as variáveis de estado obedecerem a algumas regras documentadas que descrevem suas relações entre si.

Com isso em mente, considere esta formulação alternativa exatamente do mesmo algoritmo, que difere do de Bill apenas por ter nomes de variáveis mais significativos para a, b e c e uma variável de contador incremental em vez de uma variável decrescente:

(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)))))

De repente, a correção do algoritmo – e o processo de pensamento por trás de sua criação – é simples de ver e descrever.Calcular f(n):

Temos uma variável contadora i que começa em 2 e sobe até n, incrementando em 1 em cada chamada para f-iter.
A cada passo do caminho, acompanhamos f(i), f(i-1) e f(i-2), o que é suficiente para nos permitir calcular f(i+1).
Uma vez i=n, acabamos.

Uma função f é definido pela regra que f(n) = n, if n<3 e f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3), if n > 3. Escreva um procedimento que calcule f por meio de um processo recursivo.

Isto é já escrito:

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

Acredite ou não, houve uma vez tal idioma. Escrever isso em outro idioma é apenas uma questão de sintaxe. E, a propósito, a definição como você (mis) cita ela tem um bug, que agora é muito aparente e claro.

Escreva um procedimento que calcule f por meio de um processo iterativo.

Iteração significa indo frente (há sua explicação!) Em oposição à recursão para trás inicialmente:

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
......

Isso descreve as transições de estado do problema como

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

Poderíamos codificá -lo como

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

Mas é claro que nunca iria parar. Então devemos ter

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

E isso já é exatamente como o código que você perguntou, até a sintaxe.

Contando até n é mais natural aqui, seguindo nosso paradigma de "daqui para frente", mas contando 0 Como o código que você cita, é claro, é totalmente equivalente.

Os casos de canto e possíveis erros fora por um são deixados de fora como ~~exercício~~ técnicos não interessantes.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow