選んだ整数は何? （Ｃ＋＋）

質問

１から１００までの整数をＵｓｅｒに選ばせ、Ｕｓｅｒに、「選んだ数字はＸＸ以上ですか？」と質問を繰り返し、最後にＵｓｅｒの選んだ数字を当てるという課題に取り組んでいます。（Ｕｓｅｒはそれに対してＹｅｓ/Ｎｏでしか答えられません。）
たとえば、Ｕｓｅｒが「４５」を選んだとすると、「選んだ数字は50以上ですか？」というダイアログが表示され、「ＮＯ」と答えると、次に「選んだ数字は25ですか？」というダイアログが表示されて、その番号を絞ってくというものです。

これを取り組みはじめましたが、数学が弱いのでどんな式を使うのか混乱しています。数字を２づつ割っていくことはわかるのですが、50を2で割ると25で, 一方はそれを足し（50+25）、一方はそれを50から引いて（50-25）、また次に、たとえば例にだした45の場合なら（50-25+12.5,）(50-25+12.5-6.25）などなど、繰り返してくやり方がわかりません。
これは、switch文でyes/no選択させて、前後に式をいれたりするのでしょうか？
このプログラミングの構成をどうするのかわからないので、ヒントをいただけないでしょうか？

回答No.3

Fooky · ベストアンサー

補足です。

省略して書いたために曖昧になってしまったかも知れませんね。

あのアルゴリズムでは、完全に絞り込まなくても、偶然に当たってしまうことがある
（例えば、ユーザが50を選んだら、初期設定の段階でコンピュータ側の予測が当たって
ますよね）ので、毎回、「当たっているか」を質問し、外れている場合だけ、「上か下か」
の質問をするようになっています。

ステップ１が、当たりかどうか（変数estが選んだ数と同じか）を尋ねる質問です。
ステップ２が、選んだ数が変数estより上か下かを尋ねる質問になっています。

別の手としては、そんなことを考えずに、max == est == minになるまで
ひたすら絞り込む、というのもありです。その場合、ステップ１の質問は不要です。
ステップ１を、以下のように変更すればＯＫです。

ステップ１：
　max == min ならば、estを出力して終了。
　違うなら、ステップ２へ。

数学が苦手ということなので、少し解説すると、ユーザが選んだ数は、min以上
max以下の範囲にあります。で、estはmaxとminの平均なので、max == minならば、
自動的にmax == min == estであり、選んだ数はmin以下max以上であるため、
その数が正解となります。

そうすると、以下のように書き直した方が分かり易いですね。

どちらにしても、ステップ１はいわゆる終了判定（どうなったときにプログラムを
終了させるか、即ち、どうなったら正解とみなすかの判定）です。

初期設定：
　int max = 100;
　int min = 1;

ステップ１：
　int est = (max + min) / 2;

ステップ２：
　min == maxならば、estを出力して終了。
　違うならステップ３へ。

ステップ３：
　est以上ですか？と聞く。
　Yesならステップ４へ。
　Noならステップ５へ。

ステップ４：
　min = est;
　ステップ１へ。

ステップ５：
　max = est - 1;　　//訂正：est以上でない　＝　est - 1以下
　ステップ１へ。　　　　//なので、estから１引いたものをmaxとすべき

お礼

わかりやすいご説明ありがとうございました。頑張って取り組んでみます！　なにぶん初心者なので、ちょっと複雑な課題が出されると、いつも途中でつまずいてわからなくなってしまうので、本当にありがたい限りです。また、なにかあればよろしくお願いします。

回答No.2

Fooky

上限・下限を記憶しておく変数を設ければ良いのでは？
switchかifかはご自由に。Yes/Noみたいな２択
なら普通、if/elseでいいと思いますが。

初期設定：
　int max = 100;
　int min = 1;
int est = 50;

ステップ１：
　estですか？と聞く。
　Yesなら終了。
　Noならステップ２へ。

ステップ２：
　est以上ですか？と聞く。
　Yesならステップ３へ。
　Noならステップ４へ。

ステップ３：
　min = est;
　est += (max - est)/2;
　ステップ１へ。

ステップ４：
　max = est;
　est -= (est - min)/2;
　ステップ１へ。

補足

あほな質問かもしれませんが、「ステップ１でYesなら終了」という部分ですが、もし、Ｕｓｅｒが５０以上の数を選び、たとえば６０を選んだとします。そのＵｓｅｒは一番初めの「50以上ですか？」という質問に対して「Yes」と答えたら、終わってしまうことになるんでしょうか？お返事ください。

回答No.1

y_oku

c++の処理系を持っていないので、perlで同等の構造のものをつくってみました。
c++と違うところは、動作を想像してみてください（＾＾；）
ま、参考にはなるかと……。

12.5になるところでcelr/floor（切り上げと切り捨て）を
数値以上のとき未満のときによって、
うまく使いわけるといいのではないかと思います。
境界条件の設定をあまり考えてないので、
100以上やマイナスになったりしますがご愛敬。

-------------------------------------------------------
use POSIX;

$cur_num=50;
$last_num=100;;

while(1){
print "選んだ数字は",$cur_num,"以上ですか？\n";
$key=<STDIN>;

$tmp_num=$cur_num;
if($key =~ /^y/){
last if($last_num-$cur_num==1); # 抜ける。
$tmp_num += ceil(abs($tmp_num-$last_num)/2);
}else{
$tmp_num -= floor(abs($tmp_num-$last_num)/2);
$tmp_num-- if $cur_num == $tmp_num;
}

$last_num=$cur_num;
$cur_num=$tmp_num;
}

print "答えは", $cur_num, "です。\n";
-------------------------------------------------------

お礼

perlはやったことないのですが、y_oku　さんのご意見参考にさせていただきます。アドバイスありがとうございます。