10/19レポート講評
問題
以下のプログラムの(1)-(7)を埋めて，簡単な数当てゲームで遊ぶためのプログラムを完成させなさい．
- プログラムはまず1から10000までの隠した数(整数)を作成する
- 人はその数を推測してキーボードから入力する(1から10000までの数でなくてはいけない)．
- プログラムは人が入力した数が，隠していた数と一致した時は，
何回目で成功したか答える．
- そうでない時は，以下のように答える．
- VERY LOW
- 隠した数の二分の一以下の数が入力された時
- LOW
- 隠した数より小さく，二分の一より大きい数が入力された時
- HIGH
- 隠した数より大きく，二倍以下より小さい数が入力された時
- VERY HIGH
- 隠した数の二倍以上の数が入力された時
- 2から繰り返す．
// 学生証番号: XXXXXXX
// 名前: XXXXXX
import java.io.*; // 入力に関するクラスを使う時は必要
import java.util.*; // Randomを使うので必要
class Kadai1019 {
// throws IOException で内部で入出力エラーが起きる可能性があることを示す
public static void main(String[] args) throws IOException{
System.out.println("Guess a number");
// 入力をするためには，System.inからBufferedReaderを作らなくてはいけない
BufferedReader d=new BufferedReader(new InputStreamReader(System.in));
// Randomクラスのオブジェクトを作る
Random r=new Random();
// answer に1から10000までの乱数を入れる
int answer= (1) ;
// 回答回数を記録する変数
int count=1;
for(;;){
// キーボードからの一行読み込み
String s=d.readLine();
// String(文字列)から整数への型変換
int val= (2) ;
// 正解の時はfor文を終了
if( (3) ) break;
// 正解よりも小さい時
if( (4) ){
// 2倍しても正解以下時
if( (5) ){
System.out.println("VERY LOW");
}
else {
System.out.println("LOW");
}
}
else{ // 正解よりも大きい時
// 正解の2倍以上の時
if( (6) ){
System.out.println("VERY HIGH");
}
else{
System.out.println("HIGH");
}
}
// countを1増やす
(7) ;
}
System.out.println(count);
}
}
講評
- 52名が提出
- answerの範囲が1-10000になっていない人が何人かいた．
- 2倍以上，2倍以下ではなく2倍より大きい，2倍より小さいとなっている人がいた．
- これらのミス(バグ，虫)は，コンパイルが通って一度実行してそれらしく動いたというだけでは発見できないので，プログラムを注意深く見る必要がある．
- メソッド名をスペルミスしたり(Integer.parseIjant)，演算子を書き間違えたり(>=ではなく=>)した解答があった．プログラムはコンパイル実行できるのを確認してから提出すること．
解答例とコメント
// 学生証番号: XXXX
// 名前: XXXX
import java.io.*;
import java.util.*;
class Kadai1019 {
public static void main(String[] args) throws IOException{
System.out.println("Guess a number");
BufferedReader d=new BufferedReader(new InputStreamReader(System.in));
Random r=new Random();
int answer=r.nextInt(10000)+1;
int count=1;
for(;;){
String s=d.readLine();
int val=Integer.parseInt(s);
if(val==answer) break;
if(val< answer){
if(val*2<=answer){
System.out.println("VERY LOW");
}
else {
System.out.println("LOW");
}
}
else{
if(answer*2<=val){
System.out.println("VERY HIGH");
}
else{
System.out.println("HIGH");
}
}
count=count+1;
}
System.out.println("count="+count);
}
}
穴埋めなので，ほとんどの人がこれと同じ解答を書いてくれました．
オプション課題
このゲームの解答側のプログラムを作ってみること．1-10000までのそれぞれが正解であるケースの平均回答回数をなるべく少なくするプログラムに挑戦するのも面白いだろう．
なお，
class Option1019{
public static void main(String[] args){
for(int i=1;i<=10000;i++)
System.out.println(i);
}
}
というのは，冗談としては面白いが，解答としては認めない．
講評
- 6名が解答
- うち1名が冗談プログラム，1名が不正解(質問を作成する際に隠れた数字を使っていた), 4名が正解
- 平均解答回数は11.1625回が最善で，この時，最初の質問は3977．
- 今回紹介しない解答でも同じレベルまで達している解答は加点の対象にする．
解答例(1)
/*
XXXXX XXXX
数当てゲームの解答側のプログラムです．
少なくとも,最初に質問する数が2500以下のとき質問回数の平均が最小とならなければ,
このプログラムでの質問回数の平均(11.1625回)が最小になります.
*/
import java.io.*;
class Option1019{
public static void main(String[] args){
int max = 10000;
int answer= 0 ;
int[] HL;
HL = new int[max];
int[] VHL;
VHL = new int[(max+1)];
int[] klog;
klog = new int[max+1];
HL[0] = 0;
HL[1] = 1;
HL[2] = 3;
VHL[0] = 0;
VHL[1] = 1;
VHL[2] = 3;
klog[1] =1;
klog[2] =2;
for(int i=3;i< max;i++){
if(i%2==0){
HL[i]=HL[(i/2)] +HL[(i/2 -1)]+i;
}
else{
HL[i]= 2*HL[((i-1)/2)] +i;
}
}
for(int j=3;j<=max;j++){
int min=(int)(Math.round(Math.log(max) /Math.log(2)) +1)*max;
for(int k=1;k<=j;k++){
if(k==1){
VHL[j]=VHL[j-1]+j;
}
else if(k==2){
VHL[j]=HL[Math.max(0,(j- 2*k +1))]+j+2;
}
else{
VHL[j]=VHL[(k/2)]+HL[(k-(k/2)-1)]+HL[Math.min((k-1),(j-k))]+HL[Math.max(0,(j- 2*k +1))]+j;
}
if(min > VHL[j]){
min=VHL[j];
klog[j]=k;
}
}
VHL[j]=min;
// System.out.println("VHL["+ j +"]"+ VHL[j]);
// System.out.println("klog["+ j +"]"+ klog[j]);
}
System.out.println("minimum average of "+ max +" = "+ (double)VHL[max]/max);
//ここから実行部
System.out.println("Decide a number (1~"+max+")");
System.out.println("Please answer 'H'(if 'number'>=2*'your number') ,");
System.out.println("'h'(if 'your number' < 'number' < 2*'your number')");
System.out.println("'B'(if 'number' = 'your number')");
System.out.println("'l'(if 'your number'/2 < 'number' < 'your number')");
System.out.println("'L'(if 'number' < your number)");
BufferedReader d=new BufferedReader(new InputStreamReader(System.in));
String str;
int minimum=1;
int maximum=max;
char Ans=' ';
int count=0;
boolean flag=true;
int k=0;
while(true){
if(maximum< 1||minimum>max||minimum>maximum){
flag=false;
break;
}
if(minimum==1){
k=klog[maximum];
}
else{
k=minimum+(maximum-minimum)/2;
}
System.out.print("Your Number is "+k+" ?"+" ->");
try{
str = d.readLine();
Ans = str.charAt(0);
}
catch(Exception e){
continue;
}
if(Ans == 'L'){
count++;
minimum=2*k;
}
else if(Ans == 'H'){
count++;
maximum= (k/2);
}
else if(Ans == 'l'){
count++;
maximum=Math.min(maximum,2*k-1);
minimum=k+1;
}
else if(Ans == 'h'){
count++;
maximum= k-1;
minimum=Math.max(minimum,(k/2)+1);
}
else if(Ans == 'B'){
count++;
break;
}
else{
System.out.println("Prease answer 'H'(if 'number'>=2*'your number') ,");
System.out.println("'h'(if 'your number' < 'number' < 2*'your number')");
System.out.println("'B'(if 'number' = 'your number')");
System.out.println("'l'(if 'your number'/2 < 'number' < 'your number')");
System.out.println("'L'(if 'number' < your number)");
}
}
if(flag){
System.out.println(k+" is O.K. "+"count="+count);
}
else{
System.out.println("You must have made mistakes.");
}
}
}
HIGHとLOWだけしか区別がない場合は，最小回数を実現するプログラムを作る
のは容易(正解の可能性のある区間の中間を質問に選ぶ)なのですが，VERY HIGH,
VERY LOWがあると，表を作って解く必要がありますね．平均質問回数 11.1625回
は最小のはずです．
解答例(2)
/*学生証番号：XXXXX
名前：XXXX
この課題の場合、最初のプレイヤー側の回答によって、答えのあり得る範囲は四つに分けられる。
また、Very High と返され続けた場合のみも、四つに分けられる．
この場合、答えとしてありうる数字のうちどことの高低をきけば要素数の分散が
一番小さくなるかを求めると、要素のうち下から数えて４／１１の位置にある数字であると求められたので、
それをもとに聞くようにプログラムした。
また、それ以外の場合は High or Low しかないので、１／２の位置の数字を聞けば良い。
*/
import java.io.*;
class Kadai1019opt{
static boolean check(String str,String ch1,String ch2){
int N=str.indexOf(ch1);
int M=str.indexOf(ch2);
if(N==-1 && M==-1){return false;}else{return true;}
}
public static void main(String[] args)throws IOException{
System.out.println("Decide a number (1~10000)");
System.out.println("Prease answer 'Very High'(if 'number'>=2*'your number') ,");
System.out.println("'High'(if 'your number' < 'number' < 2*'your number')");
System.out.println("'Bingo'(if 'number' = 'your number')");
System.out.println("'Low'(if 'your number'/2 < 'number' < 'your number')");
System.out.println("'High'(if 'number' < your number)");
BufferedReader d=new BufferedReader(new InputStreamReader(System.in));
int Num = 3636;
String Ans="";
int count=1;
double min=1.0;
double max=10000.0;
boolean flag = true;
while(true){
if(max-min==1)flag=false;
System.out.print("Your Number is "+Num+" ?"+" ->");
Ans = d.readLine();
if(check(Ans,"b","B"))break;
if(check(Ans,"v","V")){
if(check(Ans,"h","H")){
System.out.print("Very High? ");
if(flag){
max=(int)((2.0/11.0)*max);
Num=(int)((7.0*min+4.0*max)/11.0+0.5);
count++;
continue;
}else{
max=(int)(((double)Num)/2.0);
Num=(int)((max+min)/2.0+0.5);
count++;
continue;
}
}else{
if(check(Ans,"l","L")){
System.out.print("Very Low? ");
if(flag){
min=(int)(max*8.0/11.0);
Num=(int)((min+max)/2.0+0.5);
flag=false;
count++;
continue;
}else{
min=Num*2+1;
Num=(int)((min+max)/2.0+0.5);
count++;
continue;
}
}else{
System.out.println("Prease obey me.");
}
}
}else{
if(check(Ans,"h","H")){
System.out.print("High? ");
if(max==Num)Num--;
if(min==Num)Num++;
if(flag){
min=(int)(max*2.0/11+0.5);
max=Num-1;
Num=(int)((min+max)/2.0+0.5);
flag=false;
count++;
continue;
}else{
max=Num-1;
Num=(int)((min+max)/2.0+0.5);
count++;
continue;
}
}else{
if(check(Ans,"l","L")){
System.out.print("Low? ");
if(min==Num)Num++;
if(max==Num)Num--;
if(flag){
min=Num+1;
max=(int)(max*8.0/11.0+0.5);
Num=(int)((min+max)/2.0+0.5);
flag=false;
count++;
continue;
}else{
min=Num+1;
Num=(int)((min+max)/2.0+0.5);
count++;
continue;
}
}else{
System.out.println("Prease obey me.");
}
}
}
}
}
}
最小ではないものの，1を含む区間で全体の4/11を質問に選ぶというのは，良い近似になっています．平均質問回数も11.2109回と最適値11.1625回に近い値を達成しています．