시퀀스가 ​​증가하고 있는지 찾는 방법?

Question

이것은 더 큰 작업의 단편이지만이 작업에 정말로 어려움을 겪고 있습니다. scheme/lisp을위한 리소스는 C, Java 및 Python보다 훨씬 제한적입니다.

숫자 목록이 들어있는 var list1을 전달하면 목록이 단조롭게 증가하는 순서인지 여부를 어떻게 알 수 있습니까? 효율성에 문제가없는 경우

Answer 1

목록의 요소가 두 개 미만인 경우 '예'라고 말합니다.

목록에 둘 이상의 요소가있는 경우 첫 번째 요소가 두 번째 요소보다 크면 '아니오'라고 말하고 그렇지 않으면 목록의 뒷부분에서 반복합니다.

Answer 2

, 당신은이 작업을 수행 할 수 있기 때문에 정렬, O(n log n) 솔루션입니다

(equal? list1 (sort list1 <=)) 

합니다. 최적의 솔루션을 얻으려면 각 요소를 다음 요소와 비교하고 현재 요소가 다음 요소보다 작거나 같은지 테스트하십시오. 마지막 요소 (다음 요소가 없음)에주의하십시오. 그러면 O(n) 솔루션이 생성됩니다.

이것은 기능 스타일로 작성해야 할 일에 대한 일반적인 개념입니다. 아직 솔루션을 작성하는 가장 빠른 방법은 아니지만 최소한 O(n)이며 매우 짧습니다. 당신은 처음부터 간단한 해결책을 작성하기위한 기초로 사용할 수 있습니다

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

위의 검사를 각 번호에 대한 lst에서 다음 수 이하의 경우. andmap 절차는 두 목록의 모든 요소 쌍에 대해 <= 조건이 적용되는지 여부를 테스트합니다. 첫 번째 목록은 매개 변수로 전달 된 목록이고 두 번째 목록은 같은 목록이지만 한 위치가 오른쪽으로 이동 한 후 양의 무한 값이 끝에 추가되어 두 목록에서 같은 크기를 유지합니다. 왜냐하면 어떤 숫자가 무한보다 작기 때문입니다. 예를 들어,이 목록 :

(increasing? '(1 2 3)) 

는 위의 프로 시저 호출은 모든 조건이 #t으로 평가하기 때문에 (<= 1 2) 및 (<= 2 3) 및 (<= 3 +inf.0)이 전체 절차는 #t를 반환 확인합니다. 조건 중 하나만 실패한 경우 전체 절차는 #f을 반환했을 것입니다.

Answer 3

(define (monotonically-increasing? lst) 
    (apply < lst)) 

또는, 단조 - 비 감소하려면 :

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

예, 그와 같은 정말 간단합니다. 완전히 O (n)이고 수동 재귀는 필요하지 않습니다.

보너스 : 좋은 측정을 위해 :

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

- P