Тестирование входных чисел свойства палиндрома


3.23 палиндромы

Палиндром-это число, которое читает же вперед и наоборот, как 12321. Написать программа, которая проверяет ввод чисел свойство палиндрома.

Подсказка: это не должно быть сделано с номерами в их вклад (персонажа) в формате.

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

(defun collect-digits (candidate &OPTIONAL (digit-list ()))
  ; make a list out of the digits of the number
  ; example: (= (collect-digits 12321) (1 2 3 2 1)) is true
  (if (< candidate 10) 
    (cons candidate digit-list)
    (multiple-value-call 
      (lambda (sub-candidate onesdigit) 
        (collect-digits sub-candidate (cons onesdigit digit-list)))
      (floor candidate 10))))

(defun reflection-p (candidate-list &OPTIONAL (len (length candidate-list)))
  ; if c-l[first] = c-l[last]
  (and (= (car candidate-list) (car (last candidate-list 1))) 
       ; and the list is 3 or smaller ex. (3 1 3), it is a reflection 
       (if (<= len 3) t 
     ; if longer, keep looking
     (reflection-p (subseq candidate-list 1 (1- len)) (- len 2)))))

(defun palindrome-p (candidate)
    (reflection-p (collect-digits candidate)))

(format t "12321: ~a ~%3456789 ~a ~%" (palindrome-p 12321) (palindrome-p 3456789))


1787
3
задан 18 марта 2011 в 05:03 Источник Поделиться
Комментарии
2 ответа

Это очень просто! Помню обратное-цифры функции? Если номер совпадает с его обратным, тогда это палиндром.

4
ответ дан 18 марта 2011 в 06:03 Источник Поделиться

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

При этом глубина рекурсии будет равна количеству цифр в номере. Так как ваша функция будет вряд ли назовешь с числами, которые имеют более 100 цифр, используя рекурсию-это прекрасно.


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

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


Также примечание по поводу комментариев: конвенции комментируя в Lisp (который тоже принудительно/сильно поощряется поведение, например, в Emacs отступ) выглядит следующим образом:


  1. Комментарий, описывающий одну строку кода следует использовать один запятой и пишется на той же строке как код. Т. е.:

    (format t "hello world") ; Print hello world

    и не

    ; Print hello world
    (format t "hello world")

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

  3. Комментарий документирование функция должна быть написана с тремя точками с запятой.

3
ответ дан 18 марта 2011 в 08:03 Источник Поделиться