Powered by SmartDoc

16 関数その2,アルゴリズムの要件

16.1 関数;バリエーション

戻り値がない関数;「List8-3」

関数の名前の付け方

局所変数

リスト 16.1.1 関数定義の例
戻り値の型 関数名(引数の定義,...)
{
  局所変数の定義;

  処理;

  return 戻り値を与える式;
}

複数の引数を取る関数;「List8-4」

16.2 8章の残り

ハイグレード;ヘッダファイル

「練習問題8-1」の解答例

8章の読解練習(ジャンケンプログラム)

16.2.1 ジャンケンプログラムを強くしたい

教科書に載っているプログラムにはlearn()やguess()などの関数のプロトタイプが用意されていて,ジャンケンに強いプログラムを作ろうとした痕跡が残っています.この関数の実体を工夫すれば人間よりジャンケンに強いプログラムを作れるかもしれません.人間がランダムに手を出してくる場合はプログラムをどう工夫しても偶然以外の要素では勝てません.しかし人間が出す手に癖がある場合,その癖をプログラムで学習してそれに対応する手を出せば人間に勝てるはずです.

ではどうすればよいでしょうか?とりあえず考えたのは,人間が出した手の頻度を記憶して,最も多い手に勝てる手を出してみるというものです.

これをプログラムにするためには,このアイデアを明確に記述しなければなりません.それには下記に述べるアルゴリズムの概念が必要ですし,どのようなデータ(変数)を用意すべきかも考えねばなりません.このようにアイデアをプログラムにする場合,アルゴリズムとデータ構造を同時に考える必要があります.

下記の例の場合,人間が出す手の頻度を記録するための変数としてint型の配列であるhandlog[3]を用意しました.また,最も多い手を示す変数として,int型の変数maxhandを用意しました.これらの変数はlearn関数とmain関数の両方で使うので,関数定義の外側で変数を定義しています.プログラムとしては,learn関数で最大頻度の手を求めて,main関数でコンピュータの手を決めるときにその最大頻度の手に勝つ手を出すように変更しました.

ジャンケンプログラム改訂版

ちょっとは強くなったかな?このプログラムの欠点は,人間が出す手の偏りが強くない場合は対応できないということでです.というわけで改良の余地はまだまだありますよ.

16.3 アルゴリズム

アルゴリズム(algorithm);解法の手順.「明確に定義された有限個の規則の集まりであって,有限解適用することにより問題を解くもの.(JISの定義)」

アルゴリズムが満たすべき条件:

正当性(手順に誤りがない);
論理的に矛盾がなく正しい結果を導くこと.手順が間違っていたら問題を解くことなどできない.
一意性(手順が明解);
曖昧なところがなく,詳細に厳密に定義されていること.手順が曖昧であると具体的なプログラムのソースコードに書き下せない.
有限性(手順に終わりがある);
有限なステップで終了すること.有限回で終了しないプログラムは問題を解けないのと同じ.

アルゴリズムを文章で書く例;ボールの入れ替え,ロケット発射のカウントダウン,ソーティング

アルゴリズムは,文章やフローチャートやプログラムの形で表現することができる.

16.4 課題

8章のジャンケンプログラムを強くする方法を考える.Cのプログラムとして実行できるところまで持っていければ最高だがそこまでは求めない.どうやればコンピュータが強くなるのかを考えて,人が読んでもわかるようにそのアイデアをレポートにまとめる.アルゴリズムの条件を満たすように書くこと.つまり,アイデアが曖昧だったり自己矛盾していたりしていてはいけない.またどのような変数を用意しなければいけないかも考えて欲しい.

アルゴリズムとデータ構造を文章で詳細に明解に書くことができれば,それをプログラムにするのは比較的簡単である.アルゴリズムをきちんと考えることができないとそれをプログラムにすることはできない.この課題で論理的に正確に考える練習をする.

レポートはA4用紙に書く.日付け,学生番号,氏名を忘れずに.プログラムとして書けた人はソースコードも印刷し,どこを工夫したかがわかるようにソースコードに赤ペンで注釈を書き込んでください.

まだCの初歩しか学んでいないのでCのプログラムにできなくても構いません.大事なのはどうすれば人間の癖を上手に学習して人間に勝つようにできるかを考えることと,そのアイデアを論理的に正確に曖昧なところなく完全に書き出してプログラムの一歩手前の文章にまで持っていくことです.友達と議論してもよいです.大いに楽しんでください.

このレポートは来週の授業開始前に提出すること.