1

したがって、次の場合、4 つの数値のセットから最小値を返します。

(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 を比較してその 2 つの最小値を見つけ、次に c と d を比較し、それらの最小値を見つけ、それら 2 つの最小値を比較して実際の最小値を見つけるように書きたいと思います。 . 私が書いたことがわかりにくい場合は、a が b と「対戦」し、勝者が c と d の間で他の勝者と対戦するトーナメント ブラケットのようなものだと考えてください。助けてくれてありがとう！

4

2 に答える 2

2

これを行う1つの方法は次のとおりです。

(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

これを行うには 2 つの方法があります。reduce最初の を使用した方がはるかに慣用的だと思いますが、同じ数の比較を使用していますが、トーナメント スタイルの構造を行っていません。トーナメント スタイルの構造を行う 2 つ目は、実際には、一般化されたマージ ソートの特殊なケースにすぎません。比較回数が同じなのは、トーナメント形式の比較では、

最小(a、b、c、d) =最小(最小(a、b)、最小(c、d))

そしてreduce定式化では、

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

どちらも最低レベルの min プロシージャを 3 回呼び出す必要があります。

ベースのreduceアプローチ

この解決策は(私の経験では Lisp 言語でfoldより一般的に呼ばれます) を使用します。reduceスキーム (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項が含まれています(まあ、実際には少なくとも 1 つの引数が必要です。少なくとも 1つの項です) 。これは、バイナリ関数として既に機能することminを意味します。minでは、最初minに行うだけです。(min a b c d)したがって、完全を期すために、min2正確に 2 つの引数を受け入れる a を次に示します。

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

次に、n 項はmin*単純にmin2初期値とリストの縮小です。引数リストの表記を使用して.、これを少なくとも 1 つの引数を必要とする可変引数関数にすることができます。(min* x) => xこれは、より典型的な多引数呼び出しに加えて、を実行できることを意味します。

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

例えば：

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

マージソートに基づく真のトーナメントスタイルのソリューション

適切なトーナメント スタイルは、実際にはマージ sortminと同形です。マージソートは、長さ 1 のリストが生成されるまで、リストを再帰的に半分に分割します (これは、リストを実際に新しいリストに分割するのではなく、元のリストのインデックスを使用してその場で行うことができます)。次に、隣接するリストがマージされます長さ 2 のリストを生成します。次に、隣接する長さ 2 のリストがマージされて、長さ 4 のリストが生成され、ソートされたリストが 1 つだけになるまで、というように繰り返されます。(入力リストの長さが 2 の累乗でない場合、ここでの数値は常に完全に機能するとは限りませんが、同じ原則が当てはまります。) マージ関数をパラメーターとして受け取るマージソートの実装を作成すると、次に、より小さい値を含む 1 つの要素リストを返すようにすることができます。

まず、リストを左右に分割する関数が必要です。

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

まだマージ手順が必要です。2 つのリストを取り、それらのソートされた要素のリストを返す標準的なものではなく、2 つのリストを取り、それぞれが最大 1 つの要素を持ち、リストの最大 1 つが空である可能性があるものを必要とします。いずれかのリストが空の場合、空でないリストが返されます。両方のリストが空でない場合は、要素が小さい方が返されます。私はそれを呼んだmin-list。

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

この場合、マージ プロシージャが であるmin*を呼び出すように定義できます。マージソートは 1 つの要素を含むリストを返すため、リストからその要素を取得する必要があります。merge-sortmin-listcar

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

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