わだいのたけひこのざっき

■[授業] 最大値の求め方

先週木曜の授業のやりとりを再現してみました．

例題は，授業のものから簡単化しています．最終的な答えを書いていないのは，意図的なものです．

学生と教員の対話は最初から最後まで継続しているのではなく，教員は他の学生の状況を見るため巡回しています．小見出しは，「間」といいますか，一巡してまた気になる学生のところに戻った，とお考えください．

課題

以下は，「10個のint型の値を配列に格納し，その中から最大値を求めるプログラム」になっていない．正しく動作するよう，プログラムを修正しなさい．

#include <stdio.h>

int main(void)
{
  int a[10];
  int n = sizeof(a) / sizeof(a[0]);
  int max;
  int i;

  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }

  for (i = 0; i < n; i++) {
    max = a[i];
  }

  printf("max = %d\n", max);

  return 0;
}

if文でフィルタリング

「先生，これ，for文の中で毎回maxの値が変わるのが，おかしいんですよね?」

　「そうですね．そこが肝心です．で，どうしますか?」

「ええっと，if文を使って…」

  for (i = 0; i < n; i++) {
    if (max > a[i]) {
      max = a[i];
    }
  }

　「はいそんな感じ…って，これはおかしいなあ」

「あれ? 先生の授業で，そうなっていませんでしたっけ?」

　「授業で使用した例題は，最大値と最小値と合計を，一つのforループで求めようとしていたので，紛らわしいですね．この問題では，最大値のみです．…今書いたプログラムは，どんなときにmaxの値が変わりますか?」

「ええっと，maxの値が，a[i]の値よりも大きいときです」

　「はい，そういうときに，maxの値を，a[i]の値に代入するってことですから，その代入によって，maxの値は，大きくなりますか小さくなりますか?」

「あっ!!」

初期化しよう

「先生，条件は修正しました」

　「で，うまく動きます?」

「10個，入力を入れるのが面倒なんですが…」

　「ああそこはですね，当面の間，配列変数の宣言のa[10]を，a[3]くらいにしておくといいよ」

「あ，なるほど!」

　「で，期待する最大値になりましたか?」

「はい，なりました」

　「あれ，おかしいなあ．そのままじゃまずいんだけど」

「何かおかしいですか?」

　「うーん，ちょっとすまんが，不等号の向きを逆にしてくれますか．if文の」

「はい．これで実行ですね」

　「そうすると，入力した中で最小値が求められるはずですが…見事に変な値になっていますね」

「あれ? こんな数字，プログラムに書いてないんですけど」

　「変数の初期化忘れのせいですね*1」

「初期化…?」

　「一度もイコールの左にない，すなわち初期化されていないのに，その変数が式の中で書かれていて値が参照されている，というものがあります．探してみてください」

「分かりました…」

初期値0

「先生，分かりました! maxですね」

　「そう，maxの初期化が必要でした．で，どう対処しました?」

「for文の前に，max = 0;と書きました」

　「うーん，それは望ましくないなあ」

「変数宣言のところで，int max = 0;としないと，ダメですか?」

　「いや，そういう問題ではないです．実はあとあとのことを考えると，forとforの間のほうがいいですよ．…入力がですね，負の値ばかりだったら，どうしますか?」

「マイナスを取り除いて入力してもらう，のはアカンか」

　「言いながら不安になっていくように，それはダメですね．入力する人にとって手間だし，正の値と負の値が混在するときにはうまくいかないし，というか，絶対値が最大のものを求めることになるのは，出題異図ではないので」

「えっと…」

初期値-2147483648

　「んでそうきたか」

「はい，int型の最小値で，初期化しました」

　「max = -2147483648;ですね．いろいろまずいです．規格として，これがint型の最小値であることが，保証されていませんので」

「これ，32ビットの最小値ですよね?」

　「ええ，2の補数表現で，という条件もつきますが．まあそこより気にしないといけないのは，int型が32ビット，すなわち4バイトであるというのが保証されていないことですね」

「じゃあ，intのサイズに依存しないように書かないといけないのですか…」

　「はい，そうです．思っているより，答えは簡単なんですよ」

「えっと…」

上の会話では，「いろいろまずい」のもう一つの理由が書けていません．

「-2147483648」という，値の書き方が不適切です．実際，gcc -Wallでコンパイルすると，「this decimal constant is unsigned only in ISO C90」という警告が出ます．この式はリテラル（これで一つの値）ではなく，単項演算子のマイナスと，整数定数の「2147483648」に分かれ，「2147483648」はint型で表現できる範囲を超えているのです．

どうしてもint型の最小値を書きたければ，そして対象とする処理系ではintが32ビットであり，2の補数表現をとることが分かっているときは，「-2147483647 - 1」としなければならない，というのは私自身も最近知ったノウハウです．むしろ「#include <limits.h>」としてから，INT_MINを使うべきですね．

暫定首位

「先生，maxの初期値に何を書けばいいか，分かりません．アドバイスください」

　「はいはい…そうですね，0オリジンと1オリジンの違いから，攻めますか」

「何ですか，それ?」

　「物事を，0から数え始めるか，1から数え始めるか，です」

「え?」

　「ふたつあるfor文は，ともに，0から数え始めていますね」

「あ，はい」

　「なぜですか?」

「配列が，0から始まるからです」

　「そうですね．正確には，配列の添え字ですが．上のfor文はそのままにして，下のfor文を，1オリジンにすると，どうでしょうね」

「……」

　「うーん，じゃあ，ヒントを変えます．配列の要素数を，a[1]としたら，最大値は何ですか?」

「…1個の要素ってことですよね?」

　「そうです」

「なら，forもifも不要で，a[0]の値です」

　「1個だけの配列なら，そうです．それを，3個でも，100個でも，10000個でも成り立つように，初期値とfor文を定めてください」

「……」

　「まだダメですか．ではまた別のヒントを．テレビはよく観ますか?」

「ええまあ人並みには」

　「でですね，フィギュアスケートを思い浮かべてください．点数をつけて1位を決める競技なら何でもいいのですが」

「あ，はい」

　「実際には2位以下も決めるのですが，1位だけに着目しましょう．最初の演者が終え，点数が出たら，その人は何位ですか?」

「…暫定首位ってやつですか?」

　「そうです．で，次の演者と，暫定首位の人の点数を比べて，新しい人のほうが高ければ，そちらが暫定首位に代わりますね」

「ええ」

　「暫定首位を，このプログラムの変数maxと見ると，何か見えてきませんか?」

「あ，分かった気がします」

a[0]とa[0]を比較している

　「やっと意図通りになりましたね」

「ええ．max = a[0];にすればよかったとは」

　「プログラムは動作しますが，少しだけ無駄がある，と言いますかそのコードでは『暫定首位』の考え方をきちんと理解していない，と思われますので，もう少しだけ，修正しましょう」

「え，ダメですか?」

　「いえ，見た目はほんの小さなことです．scanfがないほうのfor文で，最初は，何と何を比較しますか?」

「maxと，a[0]です」

　「そこに無駄はありませんか?」

「え……」

初期値a[i]

あっちで手を挙げてるよ．はいはい…．

「先生，うまく動かないんですが」

　「はい，じゃあ見てみますか．…あれれ，forとforの間に，max = a[i];ですか」

「初期化してみたんですが」

　「その初期化は，失敗ですねえ」

「ええ」

　「iの値は，いくらですか?」

「はい!? …」

　「forの外でも，今修正したこのプログラムなら，iの値は一つ決まります．ここでは，一つ目のfor文を抜けたときのiの値です」

「n…ですか?」

　「そうですね．i<nが偽になるときですね．まあ，10としておきましょう」

「はい」

　「次に，a[i]は，どんな値ですか?」

「配列の，10番目の値…じゃないや」

　「a[10]って何だ? ですね．あとは考えてみてください」

「分かりました．とりあえず（forとforの間の，max = a[i];を）消します」

　「え! いやいや，安直なコピーは間違いのもとだけど，そこは丸ごと消さなくても，ちょっとした修正で，正解に近づくんですよ」

ツイートする

Permalink | コメント(0) | トラックバック(4) | 05:58