计划拆分操作不起作用

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)) 

感谢您良好的脑锻炼。关键时刻是“第二长度”功能。