0

我正在尝试从 Skiena 的书编程挑战中解决一个问题，当提交给在线评委时，一个解决方案通过而另一个失败。

我试图理解为什么一个是可以接受的答案而另一个不是。唯一的区别似乎是一个使用单独的方法，而另一个没有。第二个解决方案在哪个测试中会失败？

问题如下：

3n+1 问题

考虑以下算法来生成数字序列。从整数 n 开始。如果 n 为偶数，则除以 2。如果 n 为奇数，则乘以 3 并加 1。用新的 n 值重复此过程，当 n = 1 时终止。例如，将为 n 生成以下数字序列= 22：

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 推测（但尚未证明）对于每个整数 n，该算法将在 n = 1 处终止。尽管如此，该猜想仍然适用于至少 1、000、000 以内的所有整数。对于输入 n，n 的循环长度是生成的直到 1 并包括 1 的数字的数量。在上面的示例中，循环长度22 是 16。给定任何两个数字 i 和 j，你要确定 i 和 j 之间所有数字的最大循环长度，包括两个端点。

输入

输入将由一系列整数对 i 和 j 组成，每行一对整数。所有整数都将小于 1,000,000 且大于 0。

输出

对于每对输入整数 i 和 j，按照它们在输入中出现的相同顺序输出 i、j，然后是 i 和 j 之间（包括 i 和 j）之间整数的最大循环长度。这三个数字应该用一个空格分隔，所有三个数字都在一行上，每行输入对应一行输出。

样本输入

1 10 100 200 201 210 900 1000

样本输出

1 10 20 100 200 125 201 210 89 900 1000 174

可接受的解决方案如下：

#include <stdio.h>
int cylen(int n){

    int count = 1;
    while (n !=1 ){
        if (n%2 == 0)
            n = n/2;
        else
            n = 3*n +1;
    ++count;
    }
return count;
}
int maxcylen(int s, int e){
int tmp,i,maxcy, sz;

    if(s>e){
        tmp =s;
        s = e;
        e = tmp;
    }

    maxcy = 0;
    for(i=s;i<=e;i++){
        sz = cylen(i);
        if (sz> maxcy)
            maxcy  =sz;
    }
return maxcy;
}
int main(){
int s,e;
while(scanf("%d %d", &s, &e) != EOF){

    printf("%d %d %d\n",s,e,maxcylen(s,e));
}
return 0;
}

不能接受的情况如下：

#include <stdio.h>
int cylen(int n){

int count = 1;
while (n !=1 ){
    if (n%2 == 0)
        n = n/2;
    else
        n = 3*n +1;
    ++count;
    }
return count;
}
int main(){
int s,e, tmp,i,maxcy, sz;
while(scanf("%d %d", &s, &e) != EOF){
    if(s>e){
        tmp =s;
        s = e;
        e = tmp;
    }

    maxcy = 0;
    for(i=s;i<=e;i++){
        sz = cylen(i);
        if (sz> maxcy)
            maxcy  =sz;
    }
    printf("%d %d %d\n",s,e,maxcy);
}
return 0;
}
4

1 回答 1

0

在第一个解决方案中，您有两个变量s，e它们在 main 函数中定义，还有两个单独的变量s，e它们仅在maxcylen函数中定义

这些变量是完全不同的

在第一个解决方案中，您正在修改sand e，但仅在函数内部，因此在输出结果期间显示旧的结果main，这是正确的解决方案

要修复第二个解决方案，您需要这样做：

int s,e, tmp,i,maxcy, sz, originalS, originalE; // note 2 additional variables
while(scanf("%d %d", &s, &e) != EOF){
    originalS = s; // storing of values from file
    originalE = e;
    if(s>e){
        tmp =s;
        s = e;
        e = tmp;
    }

    maxcy = 0;
    for(i=s;i<=e;i++){
        sz = cylen(i);
        if (sz> maxcy)
            maxcy  =sz;
    }
    printf("%d %d %d\n",originalS,originalE,maxcy); // output of variables from file, instead of modified ones
}
于 2013-11-03T06:08:09.960 回答