라켓에서 최소값 찾기 더

Question

안녕하세요,

일부 라켓 연습을하고 있습니다. 나는 Racket이 min 함수를 내장하고 있음을 알고 있지만 처음부터 다시 작성하려고합니다. 몇 가지 아이디어를 온라인에서 찾았지만 코드는별로 효율적이지 않습니다. 헬퍼 메서드를 사용해야 할 것입니다. 나는이 코드를 효율적으로 만드는 방법을 조금 더 잃어 버렸다. 테스트 케이스에서이 코드를 실행했는데 너무 길어졌습니다. 작은 테스트 케이스에서는 코드가 올바른 결과를 반환합니다. 어떤 제안이라도 좋을 것입니다. 1.

을 반환

(define (minim lst) 
    (cond 
     ((null? (cdr lst)) (car lst)) 
     ((< (car lst) (minim (cdr lst))) (car lst)) 
     (else 
     (minim (cdr lst))))) 

(미님 '(3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4))

Answer 1

정렬되지 않은 목록을 가정하면 최소값을 찾는 가장 자연스러운 방법은 각 요소를 초기 min 값과 비교하여 전체 목록을 살펴 보는 것이고 요소가 해당 최소값보다 작 으면 요소가 새 값으로 저장됩니다. 분. 결국, list가 비게되면 min이 반환된다 (기본 경우).

예를 들어, 다음을 고려

(define (minimum lst acc) 
    (cond 
    ((null? lst) acc) 
    ((< (car lst) acc) 
    (minimum (cdr lst) (car lst))) 
    (else 
    (minimum (cdr lst) acc)))) 

(define (mymin lst) 
    (if (null? lst) 
     #f 
     (minimum (cdr lst) (car lst)))) 

mymin

n은리스트 내의 요소의 수이다 n-1 비교를 사용하여,리스트에서 최소값을 찾아 O(n) 시간이 걸린다.

당신은 로컬 길고 짧은 목록과이를 테스트 할 수 있습니다

(mymin '(3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 
      3 4 2 9 3 8 7 7 7 7 7 7 7 7 7 8 2 1 3 2 2 2 3 4 -1)) 
=> -1 

Answer 2

코드는 더 이상 때문에 목록의 각 항목에 대해, minim이 테스트 조건에서 cdr에 재귀 적으로 호출 할 필요 이상으로 실행됩니다. 그것은 tree recursion으로 알려져 있습니다.

minim이 두 숫자를 비교하는 간단한 함수를 정의 할 수 있습니다 쓰기보다 "떠들썩한"방법 : 다음 배 그 목록을 통해이 foldl를 사용

(define (min-of-2 x y) 
    (if (< x y) 
     x 
     y)) 

과 :

(define (minim lst) 
    (foldl min-of-2 (first lst) (rest lst))) 

foldl을 사용하는 시간은 목록의 연산이 여기의 경우와 같이 목록의 내용을 기반으로 단일 값을 생성하는 경우입니다.

함수 min-of-2에는 이름을 지정할 필요가 없으며 lamda으로 전달할 수 있습니다. 예 :

(define (minim lst) 
    (foldl 
    (lambda (x y) (if (< x y) x y)) 
    (first lst) 
    (rest lst)))