c++ - UVA 3n+1 (prob 100) 错误答案但所有测试用例都通过了

Question

我看到了一些关于 3n+1 problem 的问题在 stackoverflow 等上，并尝试修复提到的提示以使代码正确。例如现在我检查是否 a > b 。或者我使用 long long 而不是简单的 int。但仍然得到错误的答案。我的回答有什么问题？

我的代码:

#include <iostream>
using namespace std;

int count_steps(long long int num)
{
    int counter = 1;
    while(num != 1)
    {
        if (num % 2 == 1)
            num = 3*num + 1;
        else
            num /= 2;

        counter++;
    }

    return counter;
}

int max_between(long long int a , long long int b)
{
    int max=0,step;
    for(long long int i = a; i <= b; i++)
    {
        if ((step = count_steps(i)) > max)
            max = step;
    }
    return max;
}

int main()
{
    int max=0,a,b,step;
    cin >> a;
    cin >> b;
    if (a >= b)
        cout << a << ' ' << b << ' ' << max_between(b,a) << endl;
    else
        cout << a << ' ' << b << ' ' << max_between(a,b) << endl;
    return 0;   
}

测试用例:

1 10 (input)
1 10 20 (output)
900 1000 (input)
900 1000 174 (output)
1 1000000 (input)
1 1000000 525 (output)
1000000 1 (input)
1000000 1 525 (output)

Answer 1

对您的代码的一些评论:

虽然在方法。那是废话，把它们当作它们将要使用的类型来阅读。

虽然不太可能，但您可能会遇到溢出。为避免这种情况，您可以使用 unsigned long long 将整数范围加倍。

从数学上讲，你做的太多了。

对于奇数 n = 2 k + 1，结果 3 n + 1 将始终为偶数:3 n + 1 = 3(2 k + 1) + 1 = 6k + 4。因此，您可以将奇数 n 的情况与以下除以二结合起来。其结果将是 3 k + 2，即 k + 1 大于 n。在 C++ 中使用整数运算，这可以用 n += (n/2) + 1 计算，因为 n/2 将计算为 k.

您的代码未被接受的另一种可能性是输入/输出。您必须严格遵守平台的要求。

---

您的代码忽略了问题描述的以下部分:

The input will consist of a series of pairs of integers

这很容易解决

int main()
{
    int max=0,a,b,step;
    while ( cin >> a >> b )
    {
       std::cout << a << ' ' << b << ' ';
       if (a >= b)
       {
           std::cout << max_between(b,a);
       }
       else
       {
           std::cout << max_between(a,b);
       }
       std::cout << std::endl;
    }
    return 0;   
}