Counter game
Categories:
Question
Louise and Richard have developed a numbers game. They pick a number and check to see if it is a power of 2
. If it is, they divide it by 2
. If not, they reduce it by the next lower number which is a power of 2
. Whoever reduces the number to wins the game. Louise always starts.
Given an initial value, determine who wins the game.
说明
条件
- 当数字是 2 的指数倍数,则将数字除以 2
- 当数字不是 2 的指数倍数,与小于数字,且最接近的指数倍数的
差
,当作是下一个数字
目前数字 | 下个数字 | 说明 |
---|---|---|
64 | 32 | 是 2 的指数倍数,执行条件 1,(64/2)=32 |
92 | 28 | 不是 2 的指数倍数,执行条件 2,92 以下的 2 的指数数字是 64,(92-64)= 28 |
2 的指数表
2 指数倍数 | 结果 |
---|---|
0 | 1 |
1 | 2 |
2 | 4 |
3 | 8 |
4 | 16 |
5 | 32 |
6 | 64 |
7 | 128 |
8 | 256 |
9 | 512 |
10 | 1024 |
解决问题
- 找出是 2 的指数计算次数
- 找出非 2 的指数计算次数
2 的指数计算
下表为列出 2 的指数的二元表,可以看到当数字为 2 的指数时,除了最前方为 1,后面则都为 0
当遇到 条件 1
,当数字是 2 的指数倍数,则将数字除以 2
所以后面的运算都是除以 2,刚好后面 0 的出现次数
,就是要除以 2 的运算次数
数字 | - | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | - | 除 2 除到 1 运算次数(0 的出现次数) |
---|---|---|---|---|---|---|---|---|---|---|---|---|
256 | - | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | - | 8 |
128 | - | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | - | 7 |
64 | - | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | - | 6 |
32 | - | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | - | 5 |
16 | - | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | - | 4 |
8 | - | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | - | 3 |
4 | - | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | - | 2 |
2 | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | - | 1 |
1 | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | - | 0 |
非 2 的指数计算
以数字 496
为例,可以看到他的二进位数字是 11110000
,以下是所有执行步骤
步骤 | 数字 | - | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | 下个数字 | 谁执行动作 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 496 | - | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 496 - 256 = 240 | Louise |
2 | 240 | - | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 240 - 128 = 112 | Richard |
3 | 112 | - | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 112 - 64 = 48 | Louise |
4 | 48 | - | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 48 - 32 = 16 | Richard |
5 | 16 | - | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 16 / 2 = 8 | Louise |
6 | 8 | - | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 8 / 2 = 4 | Richard |
7 | 4 | - | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 4 / 2 = 2 | Louise |
8 | 2 | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 2 / 2 = 1 | Richard |
9 | 1 | - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 不能除了,输了 | Louise |
在步骤 1 ~ 4
时,因为后面的二进位皆有 1 出现,所以一定非 2 可以整除的数字(非 2 的指数),所以遇到 条件2
,与小于数字,且最接近的指数倍数的差
,当作是下一个数字
在 1 ~ 4
步骤可以刚好看到,那个差值刚好是将二进位数字,最前面的 1 拿掉变为 0,就是这个差值,所以等于是在遇到 2 的指数数字前,1 的数量有多少个
,就是使用 条件2
运算的次数
在步骤 5 ~9
时,可以看到数字变为 2 的倍数了,所以会用条件 1
,当数字是 2 的指数倍数,则将数字除以 2,最后会算出来,输的是 Louise
,赢的是 Richard
计算逻辑拆分 2 种,2 的指数与非 2 的指数
刚刚在上方有提到,当遇到 2 的指数数字,运算的次数就是 后方 0 的数字多寡
,所以等于是使用 条件 1
执行的次数
所以 16(10000)
,后面 0 的数字有 4 个,所以 条件 1
要运算 4 次
步骤 | 数字 | - | 16 | 8 | 4 | 2 | 1 | 下个数字 |
---|---|---|---|---|---|---|---|---|
5 | 16 | - | 1 | 0 | 0 | 0 | 0 | 16 / 2 = 8 |
6 | 8 | - | 0 | 1 | 0 | 0 | 0 | 8 / 2 = 4 |
7 | 4 | - | 0 | 0 | 1 | 0 | 0 | 4 / 2 = 2 |
8 | 2 | - | 0 | 0 | 0 | 1 | 0 | 2 / 2 = 1 |
9 | 1 | - | 0 | 0 | 0 | 0 | 1 | 不能除了,输了 |
当遇到非 2 的指数,使用 条件 2
执行的次数为遇到 2 的指数 1,前面 1 的数量
,就是执行的次数
最后会遇到 2 的指数数字为 16
,所以在 16(10000)
之前 1 出现的次数,496(111110000)
1 出现的次数是 4 次(排除 16 本身的 1)
,所以 条件 2
要运算 4 次
步骤 | 数字 | - | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | 下个数字 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 496 | - | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 496 - 256 = 240 | |
2 | 240 | - | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 240 - 128 = 112 | |
3 | 112 | - | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 112 - 64 = 48 | |
4 | 48 | - | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 48 - 32 = 16 | |
5 | 16 | - | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 16 / 2 = 8 |
统整运算逻辑
条件 1
是 0 出现的次数,条件 2
是 1 出现的次数,为了方便计算,直接将整个数字 -1
,就会从 496(111110000)
变成 495(111101111)
步骤 | 数字 | - | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 496 | - | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | |
1 | 496 | - | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
这样等于 条件 1
是 0 出现的次数就变成 1 出现的次数,那接下来只需要计算所有 1 出现的次数,就可以知道整个游戏玩了几轮,就可以知道谁输谁赢了
条件 | 程式 | 结果 |
---|---|---|
游玩次数为 偶数(even) |
play_game_times % 2 = 0 | Richard 赢 |
游玩次数为 奇数(odd) |
play_game_times % 2 = 1 | Louise 赢 |
Answer
Python
def counterGame(n)
setbits = bin(n-1).count('1')
if setbits%2 == 0:
return 'Richard'
else:
return 'Louise'
PHP
<?php
/*
* Complete the 'counterGame' function below.
*
* The function is expected to return a STRING.
* The function accepts LONG_INTEGER n as parameter.
*/
function counterGame($initial_number)
{
// calculate bit 1 number for play game times
$play_game_times = 0;
$initial_number -= 1;
while($initial_number) {
// if the number is exponent 2(last 1 occur), then the result will be 0, and end the while loop
$initial_number = $initial_number & ($initial_number -1);
$play_game_times++;
}
// calculate play game times to find winner
if ($play_game_times % 2 == 0) {
$winner = 'Richard';
} else {
$winner = 'Louise';
}
return $winner;
}
$fptr = fopen(getenv("OUTPUT_PATH"), "w");
$t = intval(trim(fgets(STDIN)));
for ($t_itr = 0; $t_itr < $t; $t_itr++) {
$n = intval(trim(fgets(STDIN)));
$result = counterGame($n);
fwrite($fptr, $result . "\n");
}
fclose($fptr);
C
int setBits(unsigned long long int n) {
int count = 0 ;
while(n) {
n &= (n-1) ;
count ++ ;
}
return count ;
}
int main() {
int t ;
scanf("%d\n",&t) ;
while(t--) {
unsigned long long int n ;
scanf("%llu\n",&n) ;
if (setBits(n-1) & 1) printf("Louise\n") ;
else printf("Richard\n") ;
}
return 0;
}