pergunta estranha relacionada com Euler projeto 72 (língua presa)

votos
5

Eu reconheço que há um padrão óbvio na saída para isso, eu só quero saber por que REPL do lispbox aborta quando tento executar qualquer coisa> 52. Além disso, quaisquer sugestões para melhorar o código são mais do que bem-vindo. ^ - ^

(defun count-reduced-fractions (n d sum)
  (setf g (gcd n d))
  (if (equal 1 d)
      (return-from count-reduced-fractions sum)
      (if (zerop n)
          (if (= 1 g)
              (count-reduced-fractions (1- d) (1- d) (1+ sum))
              (count-reduced-fractions (1- d) (1- d) sum))
          (if (= 1 g)
              (count-reduced-fractions (1- n) d (1+ sum))
              (count-reduced-fractions (1- n) d sum)))))

Tudo que eu vejo quando eu chamo

(count-reduced-fractions 53 53 0)

é

; Avaliação abortada

Não faz muito sentido para mim, considerando que vai correr (e devolver o resultado exato) em todos os números abaixo disso, e que eu poderia (se eu queria) fazer 53 na minha cabeça, no papel, ou uma linha em um momento em Lisp. Eu mesmo testado em muitos números diferentes superiores a 53 para se certificar de que não era específico para 53. Nada funciona.

Publicado 10/12/2008 em 01:03
fonte usuário
Em outras línguas...                            


4 respostas

votos
6

Este comportamento sugere uma otimização de chamada de cauda ausente, para que seu recursão sopra a pilha. Uma possível razão é que você declamou otimização depuração.

By the way, você não precisa fazer uma chamada explícita para return-from. Desde sumé um símbolo de auto-avaliação, você pode alterar esta linha

(return-from count-reduced-fractions sum)

para

sum

edit: Explicação da mudança proposta: "sum" avaliada como o seu próprio valor, que se torna o valor de retorno do "if", que (uma vez que esta é a última declaração no defun) torna-se o valor de retorno da função.

edit: Explicação de otimização declamado: Você poderia adicionar o seguinte ao seu nível mais alto:

(declaim (optimize (speed 3)
                   (debug 0)))

ou usar o mesmo, mas com declareem vez de declaimcomo a primeira instrução na sua função. Você também pode tentar (espaço 3) e (segurança 0) se ele não funciona.

chamada de cauda otimização significa que uma chamada de função cujo valor de retorno é diretamente retornado é traduzido em um substituto quadro na pilha (em vez de empilhar), de forma eficaz "achatamento" uma chamada de função recursiva para um loop, e eliminando as chamadas de função recursiva. Isso faz com que a depuração de um pouco mais difícil, porque não há chamadas de função onde você espera deles, resp. você não sabe como "profunda" em uma recursão ocorre um erro (como se você tivesse escrito um loop para começar). Seu ambiente pode fazer algumas declamações padrão que você tem que substituir para permitir TCO.

edit: Apenas revisitar esta questão, o que é g? Eu acho que você realmente quer

(let ((g (gcd n d)))
  ;; ...
  )
Respondeu 10/12/2008 em 01:21
fonte usuário

votos
3

Meu palpite é que há um limite de profundidade da pilha embutida com lispbox. Desde Lisp comum não garante funções cauda-recursivo usar espaço de pilha constante, é possível que cada invocação de redução de contagem de frações acrescenta outra camada na pilha.

By the way, SBCL corre esse algoritmo, sem problema.

* (count-reduced-fractions 53 53 0)
881

* (count-reduced-fractions 100 100 0)
3043
Respondeu 10/12/2008 em 01:11
fonte usuário

votos
1

Por uma questão de estilo, você poderia fazer d e soma opcional.

(defun test (n &optional (d n) (sum 0)) .. )
Respondeu 10/12/2008 em 01:15
fonte usuário

votos
0

Provavelmente um estouro de pilha (heh).

Respondeu 10/12/2008 em 01:10
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more