質問＜３６８１＞２００８／２／６

次のプログラムをBASICで書きたいと思うのですが、
　問）配列にn個の値、,,…,が与えられているとき、このｎ個
　の値の最小値を求めるプログラムを作成する
　どのように作ったらよいのでしょうか？
　どなたかご教授よろしくお願いします

★希望★完全解答★

---

BASICでどう書くかは知りませんが、原則的に一番単純なアルゴリズムは以下のようなものです。
配列,,…,をと表現した時、

1. 変数xに配列の先頭を格納し、残りの配列をとする。


2. プログラム上は、xと配列Aに対して考える。


3. 配列が空の時、変数xが解となる。


4. それ以外の時、配列の先頭を取り出し次の繰り返しを行う。
   
   
   
   1. の時、とし、2番に戻る。
   
   
   2. の時、新しくとし、として2番に戻る
   
   

これで配列内の最小値を探せます。

以上です。

---

では、いつも通り、BASICの課題をSchemeで解題します。
ちなみに、Schemeにはminと言う関数があって、これで数値の最小値を返してくれるんですね。
書式は以下の通り。


(min ＜任意の個数の数字＞)


例えば、3、8、7、6、5、2、9と言う7個の数字があった場合、


(min 3 8 7 6 5 2 9)


とインタプリタに記入すれば結果を返してくれます。



まあ、これは簡単です。
ただし、これでは題意を満たしません。上の計算結果はあくまで「一番小さい数値」を返しているだけで、「配列内の数値ではない」と言うのがミソなんです。
では、配列(Schemeではリスト)内での数値を対象にするにはどうすればいいのでしょうか?
例えばSchemeでは次のように打ってもエラーを返してきます。


(min '(3 8 7 6 5 2 9))


min: expects argument of type ＜real number＞; given (3 8 7 6 5 2 9)
訳:関数minにリスト(3 8 7 6 5 2 9)が与えられていますが、引数は実数じゃないといけません。

とまあ、minの引数は必ず普通の「数」じゃなくてはいけないのです。リスト(配列)じゃマズい。

こんな感じでリストに並べられた数値から最小値を直接返す組み込み関数はSchemeにも存在しないんですが、問題のような質問を見たら、Scheme使ってる人は十中八九次のように高階関数applyを利用して結果を返すと思います。


(apply min '(3 8 7 6 5 2 9))


これだと上手く計算してくれます。
ここで高階関数applyとは、


(apply ＜関数＞ ＜リスト＞)


と言う書式で記述して、＜関数＞を＜リスト＞に適用する作用があります。上の場合はminと言う関数を与えられたリストに適用してるんですね。
リストの最小値を求める関数を使いまわししたい、と言う場合には、次のように新しく関数を定義すれば題意を満たします。

(define (min_of_list ls)
        (apply min ls))

たった二行で終了、ですね(笑)。恐らくScheme使ってる人はこれ以上複雑な事を考えないと思います(笑)。
ただし、以前にも書きましたが、通常のプログラミング言語の場合、高階関数と言う便利な機能はまだまだ実装していないケースが多いのです。よって、一応、本編のような擬似コードをSchemeで書いてみましょう。

(define (min_of_list ls)    ;関数min_of_listを引数lsとして定義
  (let loop ((x (car ls))    ;lsの先頭をxとする
             (ls0 (cdr ls))) ;lsの残りをls0とする
    (if (null? ls0)          ;ls0が空だったら?
        x                    ;xを返す
        (loop (if (<= x (car ls0)) ;xがls0の先頭以下だったら? 
                  x          ;xのまま
                  (car ls0)) ;じゃなかったらls0の先頭とする
              (cdr ls0)))))  ;ls0の残りとする

こんな感じになります。
これも再帰的定義(BASICで言うとDO〜LOOP構文)を使い、ワンパターンで名前付きlet構文で書いたモノです。
局所関数loopを定義して、その第一引数であるxを条件によって書き換えていく、と言う形式ですね(第二引数は条件によらず、書き換わっていく)。
まあ、構造的にはそんなに難しくないので、BASICに訳する事もそんなに難しくはないでしょう。