1

因此，如果我有以下内容，它将返回一组四个数字中的最小值：

(define (minimum2 a b c d)
  (cond ((and (< a b) (< a c) (< a d)) a)
        ((and (< b c) (< b d)) b)
        ((< c d) c)
        (else d)))

但是，我想写它，以便我比较 a 和 b 并找到这两者之间的最小值，然后比较 c 和 d，并找到它们之间的最小值，然后将这两个最小值一起比较以找到实际的最小值. 如果我写的东西很难理解，可以把它想象成一个锦标赛括号，其中 a “玩” b，获胜者在 c 和 d 之间扮演另一个获胜者。预先感谢您的帮助！

4

2 回答 2

2

这是一种方法：

(define (min4 a b c d)
  (define (min2 x y)
    (if (< x y) x y))
  (min2 (min2 a b) (min2 c d)))

如果您不想使用内部函数，另一种方法是：

(define (min4 a b c d)
  (let ((min-ab (if (< a b) a b))
        (min-cd (if (< c d) c d)))
    (if (< min-ab min-cd) min-ab min-cd)))
于 2013-09-25T08:27:46.987 回答
2

这里有两种方法可以做到这一点。我认为第一个使用reduce更加惯用，但它没有使用锦标赛风格结构，尽管它使用相同数量的比较。第二个是锦标赛风格的结构，实际上只是广义合并排序的一个特例。比较次数相同的原因是在锦标赛风格比较中，

min(a,b,c,d) = min(min(a,b),min(c,d))

在reduce配方中，

min(a,b,c,d) = min(min(min(a,b),c),d)

两者都需要三个调用最低级别的 min 过程。

基于的reduce方法

此解决方案使用 a （根据我的经验，在 Lisp 语言中fold更常见）。reduceScheme (R 5 RS) 不包含reduce也不折叠，但它很容易实现：

(define (reduce function initial-value list)
  (if (null? list)
      initial-value
      (reduce function (function initial-value (car list))
              (cdr list))))

左关联折叠是尾递归且有效的。给定一个二元函数f、一个初始值i和一个列表 [ x 1 ,…, x n ]，它返回 f(f(…f(f( i , x 1 ), x 2 )…), x n - 1 ), x n )。

在这种情况下，二元函数是min2。R5R5 实际上已经包含一个n元（嗯，它实际上需要至少一个参数，它是至少一个元）min，这意味着它min已经可以作为一个二进制函数工作，但是如果你想使用内置的在 中min，您(min a b c d)首先要做的是。因此，为了完整起见，这里的 amin2正好接受两个参数。

(define (min2 a b)
  (if (< a b)
      a
      b))

那么我们的n元min*只是一个min2初始值和一个列表的约简。我们可以使用.参数列表中的符号来使它成为一个至少需要一个参数的可变参数函数。这意味着(min* x) => x除了更典型的多参数调用之外，我们还可以做 。

(define (min* a . rest)
  (reduce min2 a rest))

例如：

(min* 4 2 1 3)
;=> 1

基于归并排序的真正锦标赛式解决方案

一个合适的锦标赛风格min实际上是同构的merge sort。合并排序递归地将列表分成两半（这可以使用原始列表的索引就地完成，而不是将列表实际拆分为新列表），直到生成长度为 1 的列表。然后合并相邻的列表生成长度为 2 的列表。然后，合并长度为 2 的相邻列表以生成长度为 4 的列表，依此类推，直到只有一个排序列表。（如果输入列表的长度不是 2 的幂，这里的数字并不总是完美的，但同样的原则也适用。）如果你编写一个以合并函数作为参数的合并排序实现，然后你可以让它返回包含较小值的一个元素列表。

首先，我们需要一个函数来将列表分成左右两边：

(define (split lst)
  (let loop ((left '())
             (right lst)
             (len (/ (length lst) 2)))
    (if (< len 1)
        (list (reverse left) right)
        (loop (cons (car right) left)
              (cdr right)
              (- len 1)))))

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

合并排序现在很容易实现：

(define (merge-sort list merge)
  (if (or (null? list) (null? (cdr list))) 
      list
      (let* ((sides (split list))
             (left (car sides))
             (right (cadr sides)))
        (merge (merge-sort left merge)
               (merge-sort right merge)))))

我们仍然需要合并过程。我们需要一个可以接受两个列表的标准，而不是接受两个列表并返回其排序元素列表的标准，其中每个列表最多有一个元素，并且最多有一个列表可能是空的。如果任一列表为空，则返回非空列表。如果两个列表都不为空，则返回具有较小元素的列表。我已经调用它了min-list。

(define (min-list l1 l2)
  (cond
    ((null? l1) l2)
    ((null? l2) l1)
    (else (if (< (car l1) (car l2))
              l1
              l2))))

在这种情况下，您可以定义min*调用merge-sort，其中合并过程是min-list。合并排序将返回一个包含一个元素的列表，因此我们需要car从列表中获取该元素。

(define (min* a . rest)
  (car (merge-sort (cons a rest) min-list)))

(min* 7 2 3 6)
;=> 2
于 2013-09-25T13:17:43.977 回答