ジャンケンで決着がつくまでの回数(1)

例えば、10人でジャンケンしたら、何回で1人が残るだろうか。


まず、ジャンケンをシミュレートしてみよう。
グーを1、チョキを2、パーを4とする。
すなわちビットを立てる。
乱数を使いJavaScriptでこんな具合に実装する。


// 2.8s
for(var i = 0; i < 1000000; i++) {
var a;
var r = Math.random() * 3;
if(r < 1)
a = 1;
else if(r < 2)
a = 2;
else
a = 4;
}

ifを使わなくても書けるが、
ふつうに考えると、Math.floorあたりを使わなければいけないので、
結局遅くなる。


// 4.0s
for(var i = 0; i < 1000000; i++) {
var a;
var r = Math.random() * 3;
a = 1 << Math.floor(r);
}

でも、こうしたら?


// 2.5s
for(var i = 0; i < 1000000; i++) {
var a;
var r = Math.random() * 3;
a = 1 << r;
}

ビットシフトのときに自動的に整数になって、正しい値になる。
しかも速い。


勝負の判定は、すべてのビットごとのORをとる。
例えば、グーばかりなら、1となり、
すべてそろえば、7となる。
1か2か4か7ならあいこ、そうでなければ誰かが負けたことになる。
3ならグーとチョキなので、グーの人だけ残る。
グーの人だけ数えると、残った人の数となる。



// ジャンケンで何人残ったかを返す
function judge(a) {
var b = 0;
var length = a.length;
for(var i = length - 1; i >= 0; i--) {
b |= a[i];
if(b == 7) // あいこ
return length;
}

if(b == 1 || b == 2 || b == 4)
return length;

var c; // 勝った手
if(b == 3) // g, c
c = 1;
else if(b == 5) // g, p
c = 4;
else
c = 2;

var counter = 0;
for(var i = length - 1; i>= 0; i--) {
if(a[i] == c)
counter++;
}

return counter;
}