ログイン
kid's world

最大値を求める

最大値を求める

では,ここからは実際に行われることの多い処理を実現するアルゴリズムについて考えていこう。

最初に考えるのは,最大値を求めるアルゴリズムである。これはさまざまな場面で利用されるだろう。たとえば最大値を求める例としては,「50人の生徒のテストの点数が配列に入っているとき,最高点は何点なのかを調べる」というのがすぐに思いつく。また,その最高点の生徒は誰なのかを調べるのも,ほとんど同じアルゴリズムが利用できる。

では,50個の数値の入ったaという名前の配列の中から「最大値」と「その最大値を持つ要素の番号」を求めるアルゴリズムを考えてみよう。テストの点数の例に置き換えれば,それぞれは最高点と出席番号と考えられる。あなたならどのように表の中から最高点を探すだろうか?

おそらく,ほとんどの人が表の先頭から視線を動かしていくだろう。60点,50点,65点……となぞりながら,あなたは今まで見た中での最高点と,その人の名前を記憶しておくだろう。そして,それよりも高い点数に出くわしたら,今までの点数を忘れて高いほうの点数を記憶するだろう。もしかしたら,忘れないようにそのときの最高点の部分を指で押さえておくかもしれない。すると,最後まで見終わったときに覚えている点数(指で押さえている部分)が最高点となる。

フローチャートに変換する

この作業を忠実にフローチャートに描いてみると,Fig. 5のようになる。このフローチャートの開始時には,配列aに50個の数値データがあらかじめ入っているものとして読んでいただきたい。

Fig.5: 最大値を求めるアルゴリズム

/c/algorithm-fig5.png

フローチャートでは,指の位置(最大値を持つ要素の番号)を変数mで表している。最初は先頭にあるので,0にしておく。そして,50個の要素を順々に検索していく。視線(今何番目を検索しているのか)は変数iで表している。最初は視線も先頭にあるので,iは0としたくなるところだが,1にしても大丈夫だ。というのは,0番目と0番目を比較することは無意味だからだ。

次に,iが50未満かどうかを見る。iは49以下の範囲になければならないので,もしそうでない場合は終了する。もし範囲内にあった場合は,m番目の値よりもi番目の値のほうが大きいかどうかを調べる。すなわち,指の位置の点数よりも大きい点数を見たかどうかに相当する。もしi番目のほうが大きければ,mにiを書き込む。これは,視線の位置に指を合わせるという意味になるわけだ。そしてiを1つ増やして視線を次に移し,同じことを繰り返す。

こうして49番目までの値を検索したときの「変数mの指す位置」が,「最大値の入った要素」ということになるわけだ。

C言語に変換する

それでは,このようにしてできあがったアルゴリズムをC言語で書いてみよう。

変数名についてはフローチャートのものをそのまま利用しよう。配列aの型はint型としておくが,大小関係が比較できるのであればとくに型の種類に制限はない。配列aにデータを入力しておく必要があるが,これについては,input_dataという関数を作ることにする。関数の中身については割愛するので,実際に試すときは各自のやり方でデータ入力のコードを書いていただきたい。キーボードから入力しても,ファイルから読み込んでもけっこうである。もちろん,

data[0]=50;
data[1]=20;
data[2]=79;
data[3]=98;
…

というように直接代入してもよい。50個のデータを検索する繰り返し部分は,for文で書くのが適切だろう。for文の中でif文を使って最大値に関する比較を行い,変数mを更新していけばよいことになる。フローチャートが細かく描かれているので,そんなに違和感なくC言語に直すことができるだろう。例をList 1に示す。実行例はFig. 6を参照していただきたい。

List 1: 最大値を表示するプログラム

#include <stdio.h>

void input_data(int data[]);

void input_data(int data[])
{
  /* データ入力を行う(省略) */
}

void main()
{
  int i, m, a[50];
  
  input_data(a);
  
  for(i=1,m=0; i<50; i++){
    if(a[m]<a[i])
      m=i;
  }
  
  printf("最大値は%d、番号は%d\n", a[m], m);
}

Fig.5: List 1の実行例

/c/algorithm-fig5.png

いかがだろうか。何らかの問題を解決しようとするとき,自分ならいったいどのような行動をとるのかを細かく観察し,そのとおりに忠実にフローチャートを描いて整理しながらアルゴリズムを構築し,それをC言語で書けば,コンピュータがあなたの考え方と同じように動いて,その問題を解決してくれるようになるのである。

コンピュータの行う処理の出来/不出来は,アルゴリズムにこそかかっているといっても過言ではない。何かトラブルが起きるときは,コンピュータが誤動作するのではなく,ほとんどの場合,考えついたアルゴリズムが間違っているのだ。プログラミングをいきなり始める前に,アルゴリズムを吟味する必要があるのである。

ちなみに,最小値を求めるアルゴリズムは,最大値を求めるアルゴリズムとほとんど同じだ。どこが変わって,どこが変わらないのかを考えてみよう。また,自分で実際にプログラムを作ってみよう。


データを整理する」へ進む

広告


©Toshio Koide 1996-2007.

目次

リンクについて

リンクは御自由にどうぞ。

メール

mail.gif

広告