2

これはより大きなタスクの断片ですが、私はこれに本当に苦労しています。スキーム/Lispのリソースは、C、Java、Pythonよりもはるかに制限されています。

数値のリストを含むvarlist1を渡す場合、リストが単調に昇順であるかどうかをどのように判断できますか？

4

3 に答える 3

3

リストの要素が2つ未満の場合は、「はい」と言います。

リストに2つ以上の要素がある場合、最初の要素が2番目の要素よりも大きい場合は「いいえ」と言います。それ以外の場合は、リストの末尾で繰り返します。

于 2012-11-13T03:18:44.523 に答える
1 
(define (monotonically-increasing? lst)
  (apply < lst))

または、単調に減少しないようにしたい場合：

(define (monotonically-non-decreasing? lst)
  (apply <= lst))

はい、それは本当にそれと同じくらい簡単です。完全にO（n）であり、手動で再帰する必要はありません。

ボーナス：適切な測定のために：

(define (sum lst)
  (apply + lst))

:-P

于 2012-11-13T04:47:59.173 に答える
0

効率が問題にならない場合は、次のようにすることができます。

(equal? list1 (sort list1 <=))

O(n log n)ソートのため、これは解決策です。最適なソリューションを得るには、各要素を次の要素と比較し、現在の要素が次の要素以下であるかどうかをテストします。最後の要素（次の要素がない）に注意してください。それでO(n)解決策が得られます。

これは、機能的なスタイルで書かれた、何をする必要があるかについての一般的な考え方です。それでもソリューションを書くための最速の方法ではありませんが、少なくともそれはO(n)非常に短いです。これを、より単純なソリューションを最初から作成するための基礎として使用できます。

(define (increasing? lst)
  (andmap <=
          lst
          (append (cdr lst) '(+inf.0))))

上記は、各番号がlst次の番号以下であるかどうかをチェックします。この手順では、2つのリストの要素のすべてのペアに条件が当てはまるandmapかどうかをテストします。<=最初のリストはパラメーターとして渡されたもので、2番目のリストは同じリストですが、1つ右にシフトされ、両方のリストで同じサイズを維持するために最後に正の無限値が追加されています。これは最後のリストで機能します。任意の数が無限よりも小さくなるため、要素。たとえば、次のリストを使用します。

(increasing? '(1 2 3))

上記のプロシージャ呼び出しは、(<= 1 2)and(<= 2 3)とをチェックします。これは、すべての条件がプロシージャ全体(<= 3 +inf.0)に評価されるためです。条件の1つだけが失敗した場合、手順全体が返されます。#t#t#f

于 2012-11-13T02:35:06.793 に答える