Scheme - 将列表拆分为两个相等的列表

Question

问题:

编写一个函数(split l),它接受一个列表并将其分成两个大小相同(在一个内)的列表,并返回一个对,其car是第一个列表,其cdr是第二个列表.

我的代码:

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

Answer 1

这是使用乌龟和野兔算法的另一种可能的实现:

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

上述解决方案的优点是只遍历列表一次,注意我们不需要知道列表的长度来进行拆分.它被称为"乌龟和野兔",因为我们在列表上保留两个指针:一个缓慢前进,一次一个元素("乌龟"),另一个元素更快,一次两个元素("野兔").当野兔到达输入列表的末尾时,算法停止.

或者,我们可以使用内置过程实现更惯用(尽管更慢)的解决方案.假设您的解释器中有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)