Самая длинная убывающая последовательность в Лиспе - PullRequest
Новая
       33

Самая длинная убывающая последовательность в Лиспе

2 голосов
/ 22 декабря 2011

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

(longest '(13 9 3 7 4 7 5 3 2 8 15 11 9 7 3))

Должен возвращать: 

(15 11 9 7 3)

Единственное обязательное требование - это то, что функция должна быть реализована рекурсивно:)

Ответы [ 3 ]

1 голос
/ 22 декабря 2011

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

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

В SICP есть раздел, в котором обсуждается этот стиль подхода: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2

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

1 голос
/ 22 декабря 2011

С непрерывными подпоследовательностями это легко.За исключением того, что я не шучу, поэтому я должен объяснить это словами.

  1. Вызовите рекурсивный помощник с дополнительными аргументами a) самый длинный из найденных до сих пор b) длина этого c) текущая подпоследовательность d)его длина.Первоначально это () 0 () 0.
  2. Пока заголовок списка четный, повторяется на хвосте.
  3. Начинает current с первого встречного нечетного, повторяется на хвосте.
  4. Если головка четная или головка не меньше предыдущего элемента, текущая последовательность останавливается.Сравните его длину с ранее найденной самой длинной последовательностью.Если ток больше, он становится самым длинным, иначе забывает ток.Перейдите к пункту 2.

Когда достигнут конец списка, ответом будет более длинный из двух запомненных списков.

0 голосов
/ 14 января 2013

Алгоритм как в Ответ Даниэля переведен на Хаскелл, с некоторыми изменениями: 

longest_sub xs = g2 xs [] 0 
  where
    g2 [] a _ = a
    g2 (x:t) a i  
         | even x    = g2 t a i 
         | otherwise = g4 t [x] 1
      where
        g4 [] b j = if j>i then reverse b else reverse a
        g4 xs@(x:t) b j            
             | even x || x >= head b
                         = if j>i then g2 xs b j 
                                  else g2 xs a i 
             | otherwise = g4 t (x:b) (j+1)

В Common Lisp: 

(defun longest (xs)
  (prog  ((a nil) (i 0) b j x)                  ; var decls
      G2  (if (null xs) (return (reverse a)))   ; code
          (setf x (car xs) xs (cdr xs))
          (if (evenp x)
              (go G2))
      G3  (setf b (list x) j 1)
      G4  (if (null xs)
              (if (> j i)
                  (return (reverse b))
                  (return (reverse a))))
          (setf x (car xs) xs (cdr xs))
          (when (evenp x)
              (if (> j i) (setf a b i j))
              (go G2))
          (when (>= x (car b))
              (if (> j i) (setf a b i j))
              (go G3))
          (setf b (cons x b) j (+ j 1))
          (go G4)))

В конце концов, вызов функции - это прославленный GOTO, не так ли?

см. Также: prog страница документа .

...