반응식 - 동일한 두리스트

Question

으로 목록을 분할

문제점 :

함수 (분할 L)를 작성 개의 동일한 크기 (하나에) 목록으로 목록 및 파티션을 취하고, 그 차가있는 쌍을 반환 첫 번째 목록과 그 cdr 두 번째 목록입니다.

내 코드 :

(define split list) 
    (let ((half (/ (length list) 2) 
    (cons (car half list) 
      (cdr half list)))) 

Answer 1

다음은 tortoise and hare 알고리즘을 사용하여 다른 가능한 구현이다 쪼개다. "거북이와 토끼"라고 불리는 이유는 목록에 두 가지 포인터가 있습니다. 한 번에 한 요소 ("거북이")와 한 번에 두 요소 ("토끼")가 더 빨리 진행됩니다. hare가 입력 목록의 끝에 도달하면 알고리즘이 중지됩니다.

또는 내장 프로 시저를 사용하여보다 관용적 인 (느리지 만) 솔루션을 구현할 수 있습니다. take 및 drop 절차 (안 경우, SRFI-1에서 가져 오기), 이것은 당신이 생각했던 것과 가까운 당신의 통역에서 사용할 수 있다고 가정 :

(define (split lst) 
    (let ((half (quotient (length lst) 2))) 
    (cons (take lst half) 
      (drop lst half)))) 

어느 쪽이든, 그것은 예상대로 작동합니다

(split '(1 2 3 4)) 
=> ((1 2) 3 4) 

(split '(1 2 3 4 5)) 
=> ((1 2) 3 4 5) 

Answer 2

시도 :이 도움이

(split '(1 2 3 4)) => ((1 2) 3 4) 
(split '(1 2 3 4 5)) => ((1 2) 3 4 5) 

희망을 다음과 같이

(define (splitAt n lst) 
    (let loop ((acc '()) (n n) (lst lst)) 
     (if (or (= n 0) (null? lst)) (cons (reverse acc) lst) 
      (loop (cons (car lst) acc) (- n 1) (cdr lst))))) 

(define (split lst) (splitAt (quotient (length lst) 2) lst)) 

의미가 있습니다.

(define (split lst) 
    (let loop ((tortoise lst) (hare lst) (acc '())) 
    (if (or (null? hare) (null? (cdr hare))) 
     (cons (reverse acc) tortoise) 
     (loop (cdr tortoise) 
       (cddr hare) 
       (cons (car tortoise) acc))))) 

위의 솔루션은 목록 한 번만 , 우리가리스트의 길이를 알 필요가 없습니다 통지를 통과하는 장점이 있습니다 :