1

我在 stackoverflow 等上看到了一些关于3n+1 问题的问题，并尝试修复上述提示以使代码正确。例如，现在我检查是否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)
4

1 回答 1

3

对您的代码的一些注释：

您正在阅读aand bas int，尽管long long int在方法中使用它们。那是胡说八道，将它们视为将要使用的类型。

虽然不太可能，但您可能会遇到溢出。为避免这种情况，您可以使用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) + 1as n / 2will evaluate to来计算k。

为什么您的代码不被接受的另一种可能性是输入/输出。您必须遵循平台的确切要求。

您的代码将忽略以下问题描述：

输入将由一系列整数对组成

这可以很容易地修复

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;   
}
于 2013-10-24T10:47:32.633 回答