Bulb Switcher & Nim Game

2015-12-12

问题描述

这两题都是偏脑筋急转弯的，题目还是挺有意思的。

Bulb Switcher

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it\’s off or turning off if it\’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:
Given n = 3.
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].
So you should return 1, because there is only one bulb is on.

Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend

思路

Bulb Switcher

初始状态，所有的n个灯泡（bulb）都是off状态。
对于序号为i的灯泡，当进行第k论转换时，若k是i的约数，则灯泡发生状态转换（toggle），这就意味着每个灯泡（序号为1的灯泡除外）至少要转换两次状态（约数至少含1和本身）。
关键点：在小于n的范围内，对于每个非完全平方数，它都要进行偶数次转换（对称的原理）。例如：48含约数1,2,3,4,6,8,12,16,24,48。偶数次转换后，灯泡一定是off状态。
问题转换为找小于等于n的完全平方数的个数。例如：16含约数1,2,4,8,16,因为16是完全平方数，因为平方根在约数中是相等的，所以完全平方数转换了奇数次，即灯泡一定是on状态。

问题转换为求解在小于等于n的数中，有多少个完全平方数。

Nim Game

这题思路也很清晰，题目也给了提示。因为最少要拿1个，最多只能拿3个，而且拿子的A、B双方是 完全理性 的，所以：

如果总的石子数是4的倍数，那先拿的一方A永远无法胜出，因为每当A取x个子，B只要取4-x个，则最后的石子一定是B取得。
当石子不是4的倍数时，A只要先去 k % 4 个石子（k为石子总数），然后上面的步骤一样，A就能确保自己一定能取得最后的石子。

Code

Bulb Switcher

int bulbSwitch(int n) 
{
    if (0 == n)
        return 0;
    int x = 2;
    int res = 1;
    for (; pow(x, 2) < INT_MAX && pow(x, 2) <= n; ++x)
        ++res;
    return res;
}

也可以一行代码：

int bulbSwitch(int n) 
{
    return (int)sqrt(n);
}

Nim Game

bool canWinNim(int n) {
    return n % 4 ? true : false;
        
}