python - 这段 C++ 代码和这段 Python 代码有什么区别？

Question

回答

感谢@TheDark 发现溢出。新的 C++ 解决方案也非常有趣。这是非常多余的:

if(2*i > n && 2*i > i)

替换了旧的代码行 if(2*i > n)。

背景

我在做this problem on HackerRank ，尽管问题可能并不完全与这个问题有关。如果您看不到该网页，或者必须创建一个帐户但又不想这样做，问题将在下面以纯文本形式列出。

问题

我的 C++ 代码超时，但我的 Python 代码没有。我首先怀疑这是由于溢出，但我使用 sizeof 来确保 unsigned long long 可以达到 2^64 - 1，问题的上限。

我实际上是将我的 C++ 代码直接翻译成 Python 以查看是否是我的算法导致了超时，但令我惊讶的是我的 Python 代码通过了每个测试用例。

C++代码:

#include <iostream>

bool pot(unsigned long long n)
{
    if (n % 2 == 0) return pot(n/2);
    return (n==1); // returns true if n is power of two
}

unsigned long long gpt(unsigned long long n)
{
    unsigned long long i = 1;
    while(2*i < n) {
        i *= 2;
    }
    return i; // returns greatest power of two less than n
}

int main()
{    
    unsigned int t;
    std::cin >> t;
    std::cout << sizeof(unsigned long long) << std::endl;
    for(unsigned int i = 0; i < t; i++)
    {
        unsigned long long n;
        unsigned long long count = 1;
        std::cin >> n;
        while(n > 1) {
            if (pot(n)) n /= 2;
            else n -= gpt(n);
            count++;
        }
        if (count % 2 == 0) std::cout << "Louise" << std::endl;
        else std::cout << "Richard" << std::endl;
    }
}

Python 2.7 代码:

def pot(n):
    while n % 2 == 0:
        n/=2
    return n==1

def gpt(n):
    i = 1
    while 2*i < n:
        i *= 2
    return i

t = int(raw_input())
for i in range(t):
    n = int(raw_input())
    count = 1
    while n != 1:
        if pot(n):
            n /= 2
        else:
            n -= gpt(n)
        count += 1
    if count % 2 == 0:
        print "Louise"
    else:
        print "Richard"

对我来说，这两个版本看起来是一样的。我仍然认为我在某种程度上被愚弄了，并且实际上在我的 C++ 代码中溢出，导致超时。

问题

路易丝和理查德玩游戏。他们有一个计数器设置为 N。路易丝得到第一个回合，然后交替进行。在游戏中，他们执行以下操作。

如果 N 不是 2 的幂，他们将计数器减去小于 N 的最大 2 的幂。

如果 N 是 2 的幂，他们将计数器减去 N 的一半。

结果值是新的 N，它再次用于后续操作。

当计数器减到 1 时游戏结束，即 N == 1，最后一个做出有效移动的人获胜。

给定 N，你的任务是找到游戏的赢家。

输入格式

第一行包含一个整数 T，测试用例的数量。T线跟随。每行包含 N，计数器中设置的初始数字。

约束

1≤T≤10

1 ≤ N ≤ 2^64 - 1

输出格式

对于每个测试用例，在新行中打印获胜者的姓名。所以如果 Louise 赢了比赛，打印“Louise”。否则，打印“Richard”。 (引号是为了清楚起见)

示例输入

1

6

示例输出

理查德

解释

由于 6 不是 2 的幂，Louise 将 2 的最大幂减少到小于 6，即 4，因此计数器减少到 2。

由于 2 是 2 的幂，Richard 将计数器减去 2 的一半，即 1。因此计数器减为 1。

当我们达到 N == 1 的终止条件时，理查德赢得了比赛。

Answer 1

当n大于2^63时，你的gpt函数最终会将i作为2^63，然后乘以2^63乘以 2，给出溢出和 0 值。这将以无限循环结束，每次将 0 乘以 2。