多くのデータから、最大値、または、最小値を求める関数。

たとえば、5個のデータ 1 6 3 8 7 では、最大値は 8、最小値は 1、といった具合。

<関数名>
  maxmin —- n個のデータから最大値および最小値を求める

<形式>
  void maxmin(int *max, int *min, DATA *data, int nmem);

<引数>
  typedef struct {
    int key;    /* 比較のキーとなるフィールド */
    int info;    /* その他のフィールド */
  } DATA;
  max  (出力) キーの値が最大のレコード配列の番号(先頭番号は 0)
  min  (出力) キーの値が最小のレコード配列の番号(先頭番号は 0)
  data  (入力) レコード配列
  nmem (入力) レコード配列の大きさ

<関数値>
  なし

<用例>
  maxmin-test.c

<関数本体>
  maxmin.c

<説明>
  最も簡単なやり方は、最初 n-1 回の比較で最大値 max を見つけ、つぎに残りの n-1 個のデータから n-2 回の比較で最小値 min を見つける方法だ。この場合、計 2n-3 回の比較が必要。
  一方、関数のように、n 個のデータを半分ずつに分け、その各々のグループより最大最小を見つけたとすると、全体の最大値は2つの最大の大きいほう、全体の最小値は2つの最小の小さいほうとなる。この操作を再帰的に各グループの要素が2つになるまで行う。この場合、比較回数は 3/2n – 2 であり、上記の単純比較法のそれよりも小さい。
  ご利用には、データ構造を実際の問題に合わせて修正してほしい。

Comments are closed.

Post Navigation