この記事の詳しい内容には毎日新聞の「数当てゲーム」ページから有料記事に進むことで読めます。
目次
概要
子どもたち３人が数当てゲームをします。問題を出す男の子は1から20の間の数字を選び、女の子ともう１人の男の子からの質問に、自分が選んだ数よりも「大きい」か「小さい」か、または「当たり」と答えます。
男の子は1から順番に聞いていく方法を取ります。
女の子は少し複雑で、
わたしは真ん中の数を聞くよ。
もし答えが「小さい」なら、聞いた数より小さい数の真ん中の数を聞くよ。
もし答えが「大きい」なら、聞いた数より大きい数の真ん中の数を聞くよ。
これを当たるまで繰り返すよ。
という「真ん中の数を聞く」という方法を取ります。
ここで問題です。問題を出す男の子が7を選んだとき、男の子か女の子か、どちらがとった方法が早く数を当てることができるでしょう？
お題の説明
実はこれは、頭をしゃきっとさせないと理解できないくらいの、手ごわいアルゴリズムに関するお題なので、まずは男の子と女の子がとる方法を具体的に見ていきましょう。
線形探索法
男の子のとる方法は、1から20までの数字を当てるために1から順に聞いていくので、線形探索法(逐次探索法)と呼ばれます。
| 回数 | 聞く男の子 | 答える男の子 |
|---|---|---|
| 1 | 1ですか？ | 大きい |
| 2 | 2ですか？ | 大きい |
| 3 | 3ですか？ | 大きい |
| ・・・ | ・・・ | ・・・ |
| 7 | 7ですか？ | 当たり |
この方法は、探したい対象が一定の決まった順で並んでいない場合に先頭から順番に探していく方法です。今の場合、当てたい対象が7なので、7回めで当てることができます。
この方法には、データがどんな順番で置かれていても必ず見つかるという特徴がある一方で、データ数が増えるほど、探し当てるのに時間がかかるようになる、というデメリットもあります。たとえば1から20,000までの数字を当てる場合、答えが19,999なら、19,999回たずねることになります。
二分探索法
これは、データを文字通り真ん中で二分する方法で、データが小さい順に並んでいる場合に利用できる方法です。答える男の子は「大きい」か「小さい」かを教えてくれるので、正解の範囲を狭めていくことができます。
| 回数 | 聞く女の子 | 答える男の子 |
|---|---|---|
| 1 | 10ですか？ | 小さい |
| 2 | 5ですか？ | 大きい |
| 3 | 7ですか？ | 当たり |
二分探索法を図で追う
さらに理解できるよう、図で二分探索法を追ってみましょう。
(1回め)
女の子は、1-20の真ん中の数は10なので、「10ですか？」と聞く。男の子は、 7 < 10 なので「小さい」と答える
(2回め)
「小さい」場合は、聞いた数(10)以上の数を範囲からはずし、聞いた数より小さい数(1,2,3,4,5,6,7,8,9)の真ん中の数を探す。それは5なので、「5ですか？」と聞く。男の子は、7 > 5 なので「大きい」と答える。
(3回め)
「大きい」場合は、聞いた数(5)以下の数を範囲からはずし、聞いた数より大きな数(6,7,8,9)の真ん中の数を探す。それは7.5なので、切り下げるか切り上げる。切り下げた場合には「7ですか？」と聞く。男の子は、7 = 7 なので「当たり」と答える。
このように、1から20までの数字を当てるとき、答えが7である場合には、線形探索法が７回かかるのに対し、二分探索法では３回で正解にたどり着くことが分かります。
線形探索法のプログラム
線形探索法のプログラムコードでは、forループを使用します。1から20までの数値を入れた配列を作成し、1から順番に調べていきます。
// 数字の配列を作る(小さい順に並べる)
let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20];
// 男の子が選んだ正解
const answer = 7;
function setup() {
noCanvas();
print('答えは: ' + answer);
// 逐次探索
print('-----線形探索法-----');
for (let i = 0; i < numbers.length; i++) {
// iは0から始まるインデックス番号なので、回数を表すには1を足す
print(i + 1 + '回め');
// 男の子に聞くときにもiに1を足す
const boysAnswer = askBoy(i + 1);
if (boysAnswer === '当たり') {
print('答えは :' + numbers[i]);
// 正解が出たのでforループを抜ける
break;
}
}
print('終了');
}
function askBoy(guess) {
// 答えと推測の比較
let boysAnswer;
if (answer < guess) {
print('男の子：小さい');
boysAnswer = '小さい';
}
else if (answer > guess) {
print('男の子：大きい');
boysAnswer = '大きい';
}
else {
print('男の子：当たり');
boysAnswer = '当たり';
}
return boysAnswer;
}上記コードを実行すると、下図の結果が得られます。
forループを使った探索では、目的を達成したらbreakを使ってただちにforループから抜けることが重要です。そうしないと、正解を見つけた後も無駄なループがつづくことになります。
二分探索法のプログラム
二分探索法のプログラムを自力で考えるのは容易ではありません。インターネット上には先人による多くのコードが公開されているので、参考にできます。下記はその一例です。
お題の解決に二分探索法を使ったコードは次のように記述できます。
let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20];
// leftとrightはnumbers配列のインデックス番号を参照する
let left = 0; //
let right = numbers.length - 1;
// 男の子が選んだ正解
const answer = 7;
function setup() {
noCanvas();
print('答えは: ' + answer);
// 二分探索
print('-----二分探索法-----');
// 男の子に聞いた回数を追う変数
let count = 0
while (left <= right) {
count++;
print(count + '回め');
// 真ん中の数
// 最小位置 + (最大位置 - 最小位置) / 2
// floor()は切り下げ
let mid = left + floor((right - left) / 2);
print('mid：' + mid);
// midを使って推測値を得る
let guess = numbers[mid];
// 男の子に聞く
print('女の子：' + guess + 'ですか？');
// 返ってきた答え
let boysAnswer = askBoy(guess);
// '小さい'場合には
if (boysAnswer === '小さい') {
// 範囲の右端を、真ん中より１つ左に移す
right = mid - 1;
// '大きい'場合には
}
else if (boysAnswer === '大きい') {
// 範囲の左端を、真ん中より１つ右に移す
left = mid + 1;
}
else if (boysAnswer === '当たり') {
break; // ループを抜ける
}
print('left :' + left);
print('right :' + right);
print('----------------');
}
print('終了');
}
function askBoy(guess) {
// 答えと推測の比較
let boysAnswer;
if (answer < guess) {
print('男の子：小さい');
boysAnswer = '小さい';
}
else if (answer > guess) {
print('男の子：大きい');
boysAnswer = '大きい';
}
else {
print('男の子：当たり');
boysAnswer = '当たり';
}
return boysAnswer;
}下図は実行結果です。変数midやright、leftは配列numbersのインデックス番号を参照する数値です。それぞれの値の変化を見ると、前の「二分探索法を図で追う」で示した図のように、推測の範囲が狭められているのが分かります。
数当てアプリ
問題を出す男の子が1から100までの整数からランダムに１つ正解を選び、それを男の子が「線形探索法」で解き、女の子が「二分探索法」で解く、視覚的なアプリを考えてみました。
下図の場合、正解は34で、「線形探索法」では34回かかって正解にたどり着いていますが、「二分探索法」ではわずか５回で言い当てています。
下記はそのコードです。
const maxValue = 100;
let numbers = [];
let left, right, answer;
let answerBoy, boy, girl;
let answerBoyMsg = '',
boyMsg = '',
girlMsg = '';
function preload() {
answerBoy = loadImage('images/answerBoy.png');
boy = loadImage('images/boy.png');
girl = loadImage('images/girl.png');
}
function setup() {
createCanvas(400, 300);
background('#DEE8B4');
textSize(13);
// 答えをランダムな値に設定
answer = int(random(1, maxValue + 1));
// numbers配列に数値を入れる
for (let i = 1; i < maxValue + 1; i++) {
numbers.push(i);
}
// 変数の設定
left = 0;
right = numbers.length - 1;
rows = numbers.length;
// [線形探索法]ボタン
const linearButton = setButton('線形探索法', {
x: bx - 10,
y: by + 95
});
linearButton.mousePressed(() => {
linearSearch();
});
// [二分探索法]ボタン
const binaryButton = setButton('二分探索法', {
x: gx - 10,
y: gy + 75
});
binaryButton.mousePressed(() => {
binarySearch();
});
// 3人の発言の初期値
answerBoyMsg = '選んだよ';
boyMsg = '僕は線形探索法で探すよ';
girlMsg = '私は二分探索法で探すわ'
}
// 人物と吹き出しが一体のイメージ上に発言の文字を描くので、
// 各イメージの座標を変数にメモしておくと、文字の描画位置を決めるときに便利
let aBx = 220,
aBy = 200;
let bx = 30,
by = 20;
let gx = 150,
gy = 70;
let infoTxt = ""
function draw() {
background('#DEE8B4');
// ３人のイメージと吹き出しを描画
image(answerBoy, aBx, aBy);
image(boy, bx, by);
image(girl, gx, gy);
// 吹き出しにうまく合う位置に３人の発言を描画
text(answerBoyMsg, aBx + 65, aBy + 37);
text(boyMsg, bx + 57, by + 25);
text(girlMsg, gx + 57, gy + 25);
// 聞いた回数を描画
text(infoTxt, 10, 280)
}
// 男の子が聞いた回数を追う変数
let boyCount = 0;
// [線形探索法]ボタンのクリックで実行される
// Promiseを使ったwaitUntill()関数を使っているので、asyncがいる
async function linearSearch() {
print('-----男の子の探索-----');
for (let i = 0; i < numbers.length; i++) {
print(i + 1 + '回め');
boyCount = i;
if (numbers[i] === answer) {
boyMsg = numbers[boyCount] + 'だね！';
await waitUntill(2000);
answerBoyMsg = '当たり！';
infoTxt = '男の子は' + (boyCount + 1) + '回、聞いた';
print('終了');
break;
}
}
}
// 女の子が聞いた回数を追う変数
let girlCount = 0;
// [二分探索法]ボタンのクリックで実行される
// Promiseを使ったwaitUntill()関数を使っているので、asyncがいる
async function binarySearch() {
print('-----女の子の探索-----');
while (right - left >= 0) {
girlCount++;
print(girlCount + '回め');
let mid = left + floor((right - left) / 2);
let guess = numbers[mid];
await waitUntill(2000);
girlMsg = +guess + 'ですか？';
if (answer < guess) {
await waitUntill(2000);
answerBoyMsg = '小さい';
right = mid - 1;
}
else if (answer > guess) {
await waitUntill(2000);
answerBoyMsg = '大きい';
left = mid + 1
}
else {
await waitUntill(2000);
answerBoyMsg = '当たり';
infoTxt = '女の子は' + girlCount + '回、聞いた';
break;
}
}
print('終了');
}
function setButton(label, pos) {
const button = createButton(label);
button.size(100, 30);
button.position(pos.x, pos.y);
return button;
}
function waitUntill(ms) {
const promise = new Promise(executor);
// Promiseのコンストラクタに渡すexecutor()関数
function executor(resolve, reject) {
if (isNaN(ms)) {
reject('数値でない');
}
else {
// ms秒まったら解決
window.setTimeout(() => {
resolve('成功');
}, ms);
}
}
// というPromiseオブジェクトを返す
return promise;
}ここでは、聞く方と答える方のやりとりの文字が読めるように、Promiseオブジェクトを使っています。waitUntill()関数については「25：くり返しの中にくり返し」の「Promiseの使用」で述べています。