Одд вопрос, касающийся проекта Euler 72 (шепелявость)

голоса
5

Я признаю, что есть очевидная картина на выходе этого, я просто хочу знать, почему РЕПЛИ lispbox в прерывается, когда я пытаюсь запустить что-нибудь> 52. Кроме того, любые предложения по улучшению кода более чем приветствуются. ^ - ^

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

Все, что я получаю, когда я называю

(count-reduced-fractions 53 53 0)

является

; Оценка прервана

Это не имеет большой смысл для меня, учитывая, он будет работать (и возвращать точный результат) на все числа ниже, что, и что я мог бы (если я захотел) сделать 53 в моей голове, на бумаге, или одна строки в то время в шепелявость. Я даже протестирован на многих различных числах больше, чем 53, чтобы убедиться, что он не был специфичен для 53. Ничего работает.

Задан 10/12/2008 в 01:03
источник пользователем
На других языках...                            


4 ответов

голоса
6

Такое поведение намекает на недостающие оптимизациях хвоста вызова, так что ваша рекурсия сносит стек. Возможной причиной является то, что вы продекламировал оптимизации отладки.

Кстати, вам не нужно , чтобы сделать явный вызов return-from. Поскольку sumявляется самостоятельной оценкой символа, вы можете изменить эту строку

(return-from count-reduced-fractions sum)

в

sum

Редактирование: Объяснение предлагаемого изменения: «Сумма» оценивает свое значение, которое становится возвращаемым значением «если» заявление, которое (так как это последнее утверждение в DEFUN) становится возвращаемым значением функции.

Редактирование: Объяснение продекламировал оптимизации: Вы можете добавить следующие строки в верхний уровень:

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

или использовать то же самое, но с declareвместо в declaimкачестве первого оператора в вашей функции. Можно также попробовать (пространство 3) и (безопасность 0) , если она не работает.

Хвост вызова оптимизация означает, что вызов функции которого возвращаемое значение возвращается непосредственно переводится на замену кадров в стеке (вместо укладки вверх), эффективно «уплощение» вызов рекурсивной функции в цикле, и устраняя рекурсивные вызовы функций. Это делает отладку немного сложнее, потому что нет вызовов функций, где вы ожидаете их, соотв. Вы не знаете, как «глубоко» в рекурсии происходит ошибка (так же, как если бы вы написали цикл, чтобы начать с). Ваша окружающая среда может сделать некоторые декламации по умолчанию, которые вы должны переопределить для включения ТСО.

Редактирование: Просто пересматривает этот вопрос, что такое g? Я думаю , что вы на самом деле хотите

(let ((g (gcd n d)))
  ;; ...
  )
Ответил 10/12/2008 в 01:21
источник пользователем

голоса
3

Я думаю, что есть встроенный предел глубины стека с lispbox. Поскольку Common Lisp не гарантирует хвостовые рекурсии функция использует постоянное пространство стека, вполне возможно, что каждый вызов количество восстановленного-фракций добавляет еще один слой в стеке.

Кстати, SBCL работает этот алгоритм без проблем.

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

* (count-reduced-fractions 100 100 0)
3043
Ответил 10/12/2008 в 01:11
источник пользователем

голоса
1

В самом стиле, вы могли бы сделать d и просуммировать по желанию.

(defun test (n &optional (d n) (sum 0)) .. )
Ответил 10/12/2008 в 01:15
источник пользователем

голоса
0

Вероятно, переполнение стека (хех).

Ответил 10/12/2008 в 01:10
источник пользователем

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