SICP tomada de mudança

Question

Assim; Eu sou um amador que está tentando trabalho através SICP ( é grátis! ) e há um procedimento exemplo no primeiro capítulo que pretende contar as possíveis formas de alterar make com moedas americanas; (Mudança-maker 100) => 292. É implementado algo como:

(define (change-maker amount)
  (define (coin-value n)
    (cond ((= n 1) 1)
          ((= n 2) 5)
          ((= n 3) 10)
          ((= n 4) 25)
          ((= n 5) 50)))

  (define (iter amount coin-type)
    (cond ((= amount 0) 1)
          ((or (= coin-type 0) (< amount 0)) 0)
          (else (+ (iter amount
                         (- coin-type 1))
                   (iter (- amount (coin-value coin-type))
                         coin-type)))))

  (iter amount 5))

De qualquer forma; este é um procedimento de árvore recursiva, e as "folhas como um desafio" autor encontrar um procedimento iterativo para resolver o mesmo problema (espaço ou seja fixo). Eu não tive sorte descobrir isso ou encontrar uma resposta depois de ficar frustrado. Eu estou querendo saber se é um peido de cérebro da minha parte, ou se o autor do enroscando comigo.

Answer 1

A forma geral mais simples / mais para eliminar a recursividade, em geral, é usar uma pilha auxiliar - em vez de fazer as chamadas recursivas, você empurra seus argumentos na pilha, e repita. Quando você precisa o resultado da chamada recursiva a fim de proceder, uma vez mais, no caso geral, isso é um pouco mais complicado, porque você também vai ter que ser capaz de empurrar um "pedido de continuação" (que vai sair o auxiliar empilhar quando os resultados são conhecidos); No entanto, neste caso, uma vez que tudo que você está fazendo com todos os resultados chamada recursiva é um somatório, é o suficiente para manter um acumulador e, cada vez que você obter um resultado número em vez de uma necessidade de fazer mais chamada, adicioná-lo à acumulador.

No entanto, isso, por si só, é não espaço fixo, uma vez que a pilha vai crescer. Então outra idéia útil é: uma vez que esta é uma função pura (sem efeitos colaterais), a qualquer momento você se encontra ter calculado o valor da função para um determinado conjunto de argumentos, você pode memoize a correspondência argumentos de resultado. Isso irá limitar o número de chamadas. Outra abordagem conceitual que leva a muito os mesmos cálculos é programação dinâmica [[aka DP]], embora com DP que muitas vezes o trabalho de baixo para cima "preparando resultados a serem memoized", por assim dizer, em vez de começar com uma recursão e trabalhar para eliminá-lo.

Tome bottom-up DP sobre esta função, por exemplo. Você sabe que vai repetidamente acabar com "quantas maneiras de fazer a mudança para uma quantidade X com apenas o menor moeda" (como você talhar as coisas para X com várias combinações de moedas do amount original), assim que você começar computar esses valores amount com um simples iteração (f (x) = X / value se X é exatamente divisível pelo valor value menor-moeda, outra 0; aqui, value é 1, então f (X) = X para todo x> 0). Agora você continuar calculando uma nova função g (X), maneiras de fazer a mudança para o X com o dois moedas de menor: novamente uma iteração simples para aumentar X, com g (x) = f (X) + g (X - value) para o value do segundo menor moeda (que será uma iteração simples, porque no momento em que você está computando g (X) que você já computado e f (X armazenado) e todos g (Y) para Y três moedas de menor - h (X) = g (X) + g (X-value) como acima - e de agora em diante você não vai precisar de f (X) mais, para que possa reutilizar que espaço. Tudo dito, isto precisa de espaço 2 * amount - não "espaço fixo" ainda, mas, cada vez mais perto ...

Para dar o salto final para "espaço fixo", pergunte-se: você precisa para se manter em torno de todas valores de duas matrizes em cada etapa (aquela que você última computadorizada e o que você está atualmente computação), ou apenas alguns desses valores, reorganizando seu looping um pouco ...?

Answer 2

A solução que eu vim com é manter a contagem de cada tipo de moeda que você está usando em uma 'bolsa'

O loop principal funciona assim; 'Denom é a denominação atual,' mudou é o valor total de moedas na bolsa, 'dado é a quantidade de mudança que eu preciso fazer e' claro-up-to toma todas as moedas menores do que uma dada denominação fora da bolsa .

#lang scheme
(define (sub changed denom)
  (cond
   ((> denom largest-denom)
    combinations)

   ((>= changed given)
    (inc-combinations-if (= changed given))

    (clear-up-to denom)
    (jump-duplicates changed denom)) ;checks that clear-up-to had any effect.

   (else
    (add-to-purse denom)
    (sub
     (purse-value)
     0
     ))))

(define (jump-duplicates changed denom)
  (define (iter peek denom)
    (cond
     ((> (+ denom 1) largest-denom)
      combinations)

     ((= peek changed)
      (begin
        (clear-up-to (+ denom 1))
        (iter (purse-value) (+ denom 1))))

      (else
       (sub peek (+ denom 1)))))
  (iter (purse-value) denom))

Depois de ler a resposta de Alex Martelli eu vim com a idéia de bolsa, mas apenas tenho tempo para fazê-lo funcionar

Answer 3

Aqui é a minha versão da função, utilizando programação dinâmica . Um vector de tamanho n + 1 é inicializado para 0, excepto que o produto é inicialmente 0'th 1. Em seguida, para cada moeda possível (o laço do exterior), cada elemento do vetor (o laço do interior) a partir do k'th , onde k é o valor da moeda, é incrementado pelo valor no atual índice de menos k.

(define (counts xs n)
  (let ((cs (make-vector (+ n 1) 0)))
    (vector-set! cs 0 1)
    (do ((xs xs (cdr xs)))
        ((null? xs) (vector-ref cs n))
      (do ((x (car xs) (+ x 1))) ((< n x))
        (vector-set! cs x (+ (vector-ref cs x)
          (vector-ref cs (- x (car xs)))))))))

> (counts '(1 5 10 25 50) 100)
292

Você pode executar este programa em http://ideone.com/EiOVY .

Answer 4

Assim, em esta discussão , o consulente original surge a pergunta com uma resposta de som modularização via. Gostaria de sugerir, no entanto, que seu código pode ser facilmente otimizado se você notar que cc-pennies é totalmente supérfluo (e, por extensão, de modo que é cc-nothing)

Veja, o problema com a maneira cc-pennies está escrito é que, porque não há nenhuma denominação menor para ir, tudo o que vai fazer, imitando a estrutura dos procedimentos de valor superior é iterate para baixo de (- amount 1) para 0, e ele vai fazer isso cada vez que você passar uma quantidade do procedimento cc-nickels. Assim, na primeira passagem, se você tentar 1 dólar, você vai ter uma amount de 100, de modo avalia (- amount 1) para 99, o que significa que você vai passar por 99 ciclos supérfluos do ciclo cc-pennies e cc-nothing. Então, níqueis vão passar por você 95 como quantidade, de modo a obter 94 ciclos mais desperdiçados, assim por diante e assim por diante. E isso é tudo antes mesmo de subir na árvore para moedas de dez centavos, ou quartos, ou meias dólares.

Com o tempo você chegar ao cc-pennies, você já sabe que você só quer o acumulador por um, então eu sugiro que esta melhoria:

(define (count-change-iter amount)
    (cc-fifties amount 0))

(define (cc-fifties amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-fifties (- amount 50)
                (cc-quarters amount acc)))))

(define (cc-quarters amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-quarters (- amount 25)
                (cc-dimes amount acc)))))

(define (cc-dimes amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-dimes (- amount 10)
                (cc-nickels amount acc)))))

(define (cc-nickels amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-nickels (- amount 5)
                (cc-pennies amount acc)))))

(define (cc-pennies amount acc)
    (+ acc 1))

Espero que você encontrou este útil.

Answer 5

Você pode resolvê-lo de forma iterativa com programação dinâmica em tempo pseudo-polinomial.