Lispの中で最も長い順番の減少シーケンス

Question

私は今後の試験でいくつかの問題に取り組んでおり、このLisp関数についていくつかの助けが必要です。私はCLISPで働いています。 リスト内の奇数だけからなる最長減少シーケンスを見つけなければなりません。 例：

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

返す必要があります。

(15 11 9 7 3) 

唯一の必須要件は、関数が再帰的に実装する必要があります:)連続した部分配列で

Answer 1

ことは、それが簡単だということです。私はlispをしない以外は、言葉で説明しなければなりません。

1. 追加の引数を付け加えて、a）最長発見時間b）現在のサブシーケンスd）の長さ。最初はこれらは（）0（）0
2. リストの頭部が均一である間に、尾部に再発する。
3. current最初の奇数が発生し、末尾に再発します。
4. headが偶数であるか、headが前の要素より小さくない場合、現在のシーケンスは停止します。その長さを以前に発見された最長の配列と比較する。電流がより長い場合は、新しいものが最も長くなり、そうでない場合は電流を忘れる。 2.

リストの末尾に達すると、2つの記憶されたリストのうち長い方が回答になります。

Answer 2

これは再帰を使用して1つの段階で行うことができます（これは私が提案しようとしている方法よりも速い&でしょう）。しかし、すべてを生成すれば読みやすく、モジュール化し、まず有効なソリューションを選択し、有効なものをフィルタリングして、そのソリューションの中で最良のものを返します。

このようにするには、ジェネレータ&マッピング関数が必要です（この問題のために2つのネストされたmaplistを提案します）、フィルタ関数（これを書いてください。 if-not funciton）、およびreduce関数（フィルタリングされたものから最善の解（最長リスト）を返す）を使用します。

アプローチのこのスタイルを論じSICPでのセクションがあります：http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2

信号処理エンジニアが、それは自然 段階のカスケードを流れる信号の面で にこれらのプロセスを概念化するために見つけるだろう。.. 。

Answer 3

いくつかの調整で、ハスケルに翻訳Daniel's answerのようなアルゴリズム：

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) 

012 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 doc page。