PPT

情報処理Ⅱ
2004年11月16日（火）
レポート課題1の解説
一言で表現
する訓練を！
解説（１）

これは何をするプログラムか?

二つのコップから，決められた量の水をくみ取るプログラム
Cup A
Cup B
0L
0L
7L
0L
2L
5L
2L
0L
0L
2L
1L
5L
2
解説（２）

宣言されている変数の意味・用途は何か?






max_a: カップAの容積
max_b: カップBの容積
goal: くみ取りたい水の量
a: カップAに入っている水の量．a == goalとなれば成功
b: カップBに入っている水の量
tmp: max_aとmax_bの値を交換するための一時変数
3
解説（３）

変数の初期値をどのようにしたときに「There is no
answer.」と出力するか?


以下のいずれかを満たすとき
• max_a < goal && max_b < goal が真
• goalが，max_aとmax_bの最大公約数の倍数でない
例
• max_a = 15; max_b = 9; goal = 18; ⇒
「There is no answer.」
• max_a = 15; max_b = 9; goal = 4; ⇒
「There is no answer.」
• max_a = 15; max_b = 9; goal = 3; ⇒
「Cup A holds exactly 3L.」
4
解説（４）

if (max_a < max_b) { ... } は何をしているか?
これがないと，どんなとき(変数の初期値)に不都合が起こる
か?


max_aとmax_bの値を交換している．
これがないと，max_a < goal && goal <= max_bが真
のとき（例えばmax_a = 5; max_b = 7; goal = 6;）に
も，a == goalが真になることはなく，「There is no
answer.」と出力してしまう．
5
解説（５）

breakを使うことなく，同じ動作をするよう書き換えることは
できるか?

変更前： while (1) {
if (a == goal) {
break;
} else if (a == 0) {

変更後： while (a != goal) {
if (a == 0) {
6
他の答案

「There is no answer.」の条件



× a = b ≠ goal に途中でなるもの
× a,bが偶数，goalが奇数
× max_aがmax_bの倍数であり，goalがmax_bの倍数でな
いとき
7
他の答案

max_aとmax_bの値交換の必要性




△ max_a = 0のとき不都合
△ max_a < max_bのとき不都合が起こる
× max_a < max_bのとき，カップAの中身がカップBに入り
切らない
• max_a = 5; max_b = 7; とし，交換のif文を除去し
てコンパイル・実行すれば，不都合ないことがわかる
！ max_a = 0のときに無限ループを回避できる
• max_aやmax_bが０以下の場合は，このプログラムでは考
慮していなかった！
8
他の答案

break除去の方法



○ goto文を使用する
○ break; を消して，print(...); exit(0);
• いずれも「同じ動作」になるが，行儀のよい使い方ではない
× while (1) {
if (a == goal) {
break;
}
while (a != goal) {
elseを消し
忘れている！
9
気になったレポート


提出年月日がない
長い１段落のみで記述している


１枚のレポートにステープラ（の針）をつけている




１枚なら不要
ステープラ（の針）２つで綴じる


段落を分け，見出しをつけるなどしてわかりやすい「文章」を
１つで十分．失敗したのなら，取り除いておく
配布資料を添付している
「ゴール」と書いたのだろうが「ブール」に見える
goal=○;

丸印（「任意の値」の意味と思われる）が数字の0に見える
10
ここから先を読む人への注意

ここから先は数学的記述が多く，情報処理Ⅱという科目の趣
旨を越えている．「問題に隠された数学的性質」が気になる
人や，上記の解説で納得いかない人だけが読んで自習して
ほしい．
11
解説（３）の補足

最大公約数に関する準備など




max_aとmax_bの最大公約数を，以下ではgcdと書く．
max_aとmax_bが互いに素 ⇔ gcd == 1 ⇔
1,2,...,max_aの任意の量をくみ取れる
「0」は，「任意の正の整数」の倍数である．ゆえに，
「0」と「任意の正の整数n」との最大公約数は，nである．
goalが，gcdの倍数でないならば，goalの分量をくみ取れ
ない．これは数学的帰納法で証明できる．その帰納段では，
「aとbの値（カップAとカップBの水量）が変わるとき，変わる
前のaとbがそれぞれgcdの倍数ならば，変わった後のaとb
もそれぞれgcdの倍数である」ことを示せばよい．
12
解説（３）の補足

max_aとmax_bの値を固定し，goalを様々な値にして実行
すると，くみ取れる値は，gcd, 2*gcd, ..., max_aで
あり（max_aもgcdの倍数であることに注意），それ以外には
ない．これは，次の二つの事実と，数式処理の能力（高校レ
ベル）があれば証明できる．


「Fill Cup A.」の回数をα，「Empty Cup B.」の回数をβと
すると，a+b == α*max_a-β*max_bが成り立つ．
「拡張ユークリッドの互助法」と呼ばれるアルゴリズムを用いる
と，X*max_a+Y*max_b == gcdを満たす整数XとYを求める
ことができる．
13

Download Report