c++ - 帮助解决编程挑战

Question

我正在尝试根据 Steven S. Skiena 和 Miguel A. Revilla 编写的书中的编程挑战。

但是我已经遇到了第一个称为“3n+1 问题”的挑战。

挑战可以在这里找到:http://www.programming-challenges.com/english/pdfs/110101.pdf

我想到的解决办法是。

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int CalcCycleLenght(int n)
{
    int t = 1;
    while (n != 1)
    {
        if (n % 2)
        {
            n = 3 * n + 1;
        }else{
            n = n / 2;
        }
        t++;
    }
    return t;
}

int main(int argc, char* argv[])
{
    int i;
    int j;
    vector<int> vi;
    vector<int> vj;
    vector<int> vm;

    int p = 0;

    while (scanf("%d %d", &i, &j) != EOF)
    {
        vi.push_back(i);
        vj.push_back(j);
        int max = 0;
        int n;
        for (int t = i; t <= j; t++)
        {
            n = CalcCycleLenght(t);
            if (n > max)
                max = n;
        }
        vm.push_back(max);
    }

    for (int i=0; i < vi.size(); i++)
    {
        printf("%d %d %d \n", vi[i], vj[i], vm[i]);
    }   

    return 0;
}

它编译正确(虽然我认为我有一个额外的包含)并且根据示例输入和输出答案是正确的。但在线法官说“错误答案”。我认为我的问题是我输入或输出数字的方式。

[编辑]

我解决了。似乎问题是有时我比 j 大。我还删除了 vector 并使代码更高效。这是新的主要功能。

int main(int argc, char* argv[])
{
    int i;
    int j;

    int a;
    int b;

    int max;
    int p;

    while (scanf("%d %d", &i, &j) != EOF)
    {
        if (i < j)
        { a = i; b = j; }
        else
        { a = j; b = i; }   

        max = 0;
        for (int t = a; t <= b; t++)
        {           
            p = CalcCycleLenght(t);
            if (p > max)
                max = p;
        }
        printf("%d %d %d\n",i,j,max);
    }    
    return 0;
}

谢谢

Answer 1

您在每行的末尾输出一个额外的空格。尝试删除此空格，因为自动判断通常会在此类事情上失败。除此之外，您的算法在我看来是正确的。

顺便说一句，没有理由将数字放在 vector 中 - 您可以在计算它们时输出每一行的结果。

编辑:规范中不清楚i>j 是否可能。在这种情况下，您的代码将输出 0，因此如果删除空格没有帮助，您可以尝试在这种情况下交换 i 和 j这样你就有了有意义的输出(只要确保你输出 i 和 j 的顺序与你得到它们的顺序相同)。

编辑 2:这很可能是问题所在:您在计算中使用了一个 int，在大多数平台上它最多可以保存 2147483647 的值。但是计算循环长度将需要大于该值的数字(例如，对于 113383 的初始值)。如果你使用 long long(假设它被支持)你应该没问题。