計劃拆分操作不起作用

Question

我是新來的計劃，並且在調試我的代碼時遇到了一些麻煩。

; returns number of elements in a list 
(define (length L) 
    (cond ((null? L) 0) 
     (else (+ (length (cdr L)) 1)))) 

; split the list in half: 
; returns ((first half)(second half)) 
(define (split L) 
    (cond 
    ((= (length L) 0) (list L L)) 
    ((= (length L) 1) (list L '())) 
    (else 
     (list (sublist L 1 (/ (length L) 2) 1) 
      (sublist L (+ (/ (length L) 2) 1) (length L) 1))))) 

; extract elements start to end into a list 
(define (sublist L start end counter) 
    (cond ((null? L) L) 
     ((< counter start) (sublist (cdr L) start end (+ counter 1))) 
     ((> counter end) '()) 
     (else (cons (car L) (sublist (cdr L) start end (+ counter 1)))))) 

對我來說，這感覺就像它將一個列表分成兩個子列表。可能有更簡單的方法來做到這一點，所以我很抱歉，如果這看起來很麻煩。

反正結果：

Expected: (split '(1 2 3 4 5)) = ('(1 2) '(3 4 5)) 
Actual: (split '(1 2 3 4 5)) = ('(1 2) '(4 5)) 

很明顯的是，length或split正在失去的中間值，但我一次又一次的檢查，它似乎失去的中間值。這似乎是一個簡單的解決辦法是擺脫(+ (/ (length L) 2) 1)的(+ 1)，但這似乎直覺上我，因爲：

Assume L = '(1 2 3 4 5), (/ (length L) 2) = 2, and (+ (/ (length L) 2) 1) = 3 
(sublist L 1 (2) 1) = '(1 2) 
(sublist L (3) 5 1) = '(3 4 5) 
** I put parens around the 2 and 3 to indicate that they were length calculations. 

顯然，我想提出的假設是錯誤的，或者我忽視的東西微不足道。

在此先感謝！

Answer 1

你知道烏龜和兔子算法嗎？烏龜走單，兔子以雙倍速度跑單子。當兔子到達列表的末尾時，分裂發生在烏龜的位置。這裏是大部分代碼;我會讓你找出其餘部分：

(define (split xs) 
    (let loop ((ts xs) (hs xs) (zs (list))) 
    (if (or (null? hs) (null? (cdr hs))) 
     (values (reverse zs) ts) 
     (loop ...)))) 

這裏TS是項目的剩餘名單由龜進行檢查，HS是項目的剩餘名單由野兔進行檢查，並且ZS是烏龜已經檢查過的物品清單按相反的順序排列。

請注意，您從不需要計算輸入列表中的項目。

Answer 2

我不打算爲你調試你的代碼。取而代之的是，這裏有一個split簡單的定義：

(define (split l) 
    (let ((n (length l))) 
    (list (take (/ n 2) l) 
      (drop (+ (/ n 2) (mod n 2)) l)))) 

讀者練習：實現take和drop。後者只是在n上遞歸，而在遞歸情況下則採用cdr的l;前者在基本情況下（停止條件）稍微花費更多的努力才能得到正確的結果。

Answer 3

這幾乎是你的解決方案（球拍計劃）：

#lang racket 

(define (length lst) 
    (cond [(empty? lst) 0] 
     [else (+ (length (rest lst)) 1)])) 

(define (first-length lst) 
    (quotient (length lst) 2)) 

(define (second-length lst) 
    (- (length lst) (first-length lst))) 

(define (sublist lst start end counter) 
    (cond [(empty? lst) lst] 
     [(< counter start) (sublist (rest lst) start end (+ counter 1))] 
     [(> counter end) '()] 
     [else (cons (first lst) (sublist (rest lst) start end (+ counter 1)))])) 

(define (first-half-of-list lst) 
    (sublist lst 1 (first-length lst) 1)) 

(define (second-half-of-list lst) 
    (sublist lst (second-length lst) (length lst) 1)) 

(define (split lst) 
    (cond 
    [(= (length lst) 0) (list lst lst)] 
    [(= (length lst) 1) (list lst '())] 
    [else (list (first-half-of-list lst) 
       (second-half-of-list lst))])) 

(split '(1 2 3 4 5)) 

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

感謝您良好的腦鍛鍊。關鍵時刻是「第二長度」功能。