第6回　有名なアルゴリズム

繰り返しプログラムを考える際に，気をつけなくてはいけない点をいくつかまとめます。

プログラム全体の流れを考え，どの部分を繰り返すのか決める。
繰り返しの終了は，どのような条件の時か。
回数を数えるためには，カウンタを用いる。
和・積などを求めるときは，変数の初期値に注意。

今週は，いま一度じゃんけんプログラムで，3回先に勝ったらおしまいというプログラム作成で，振り返ってみましょう。

プログラム全体の流れを考える

まずはフローチャートを作成し，プログラム全体がどのような流れになるかを，必ず紙の上で行おう。

自分の手を，キーボードから入力する。グー＝1，チョキ＝2，パー＝3
コンピュータの手を，乱数により発生させる。
勝負
1. 自分の勝ちの場合，自分の勝ち数を＋１
2. コンピュータの勝ちの場合，コンピュータの勝ち数を＋１
3. あいこの場合
どちらかが3勝するまで，繰り返す。

登場するデータを考える

じゃんけんを行うのに必要となるのは，Aの手，Bの手，Aの勝ち数，Bの勝ち数。

データ入力

じゃんけんの手を，キーボードから入力しよう。
「グー」などの入力は面倒なので，グー＝1，チョキ＝2，パー＝3として，数字を入力するようにする。

コンピュータの手は，乱数を使う。


#include <stdio.h>

#include <stdlib.h>

void main()
{
    int b;

	randomize();    /* 乱数発生ルーチンの初期化 */
	b = (rand() % 3) + 1;　　/* 1 ~ 3　の間の数字を発生 */
}

勝負処理

じゃんけんプログラムでは，入力された手を比較して，勝ち負けを判定します。


#include <stdio.h>
#include <stdlib.h>

 
void main()
{
	/* 変数の定義 */
	int a, b;
	int wina, winb;

	/* 初期化 */
	wina =0; winb = 0;
	randomize();

	/* 入　力 */
	printf("あなたの手を入力（グー＝1，チョキ＝2，パー＝3） :");
	scanf("%d", &a);

	b = (rand() % 3) + 1;  

	/* 勝負 */

	printf("あなたの手：%d VS コンピュータの手：%d¥n", a, b);
	if(a == b）{
		printf("あいこです\n");
	}else if((a == 1 && b == 2)||(a == 2 && b == 3)||(a == 3 && b == 1)){
		printf("あなたの勝ち\n"); wina++;
	}else{
		printf("コンピュータの勝ち\n"); winb++;
	}
}

演習課題　（Oh-Meiji で提出）

（１）じゃんけんプログラムを，どちらかが先に3回勝つまで繰り返すようにしよう。繰り返すのは，/* 入力 */ から /* 勝負 */までですね。あとは，どちらかが3回勝つまでというのを，どうやって表現したら良いだろうか。

（２）先週の課題（２）ができなかった人は，これに挑戦しよう。キーボードから，二つの正整数を入力すると，はじめの数÷あとの数　を計算し，商とあまりを求めるプログラムを，引き算だけで実現しなさい。

（３）先週の課題（５）ができなかった人は，かけ算九九を何とか表示するプログラムを作ろう。九九を計算するには，繰り返しを入れ子にして，カウンタを二つ利用する方法が一般的です。

（４）素数の判定：入力した整数が，素数かどうか判定するプログラムを作成しよう。素数とは，１とその数以外では割り切れない数ですね。何かうまい計算方法がありそうですが，ここはコンピュータの力技で，２からその数-1まで，割り切れるかどうか判断してみます（1からではないので注意！）。割り切れるという判断は，もうできますね。できた人は，判断する範囲　「2からその数-1まで」をどこまで狭められるか，数学的に考えてみてください。計算速度の向上につながります。

（５）ユークリッドの互除法に挑戦しよう。２つの整数の最大公約数を求める有名なアルゴリズムです。最大公約数は，これまでどうやって求めてきましたか？これまでに習った素因数分解は，人間の感に頼っている部分がありコンピュータではできません。そこで，考えられたのが次のアルゴリズムです。
「大きい方の数から小さい方の数を引くことを，両者が等しくなるまで繰り返す。等しくなったら，その数が最大公約数。」

こっちを教えてくれればいいのに！と言っていないで，これをプログラムにしてみましょう。

授業終了時までのプログラムと完成した提出用プログラムをoh-meijiシステムを使って提出すること
授業終了時に送るのは出席の確認用である．完成した課題は提出用の回に送ること
（提出用の回に提出しないと，採点を行わない）

第6回 有名なアルゴリズム