c - 3n+1在线评委计划

Question

我编写了一个程序来解决 Online Judge 中的 3n+1 问题 ( Collatz Conjecture )。我注意到一些重要问题，例如第一个输入可能小于第二个输入等。

但是当在线评判时我总是收到错误答案的通知。你能帮我看看我哪里出错了吗？谢谢。

以下是我的程序。注意，我使用了一个数组来存储遍历数的周期。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>


int main(int argc, char const *argv[])
{
    int maxcyc = 0;
    int curcyc;
    int i, min, max;
    unsigned long n;
    int *cach = (int *)malloc(1000000 * sizeof(int));
    if (cach == NULL)
    {
        printf("Memory Allocation Error\n");
    }
    for (i = 0; i < 1000000; ++i)
    {
        cach[i] = 0;
    }
    if (scanf("%d  %d", &min, &max) == 2)
    {
        printf("%d %d ", min, max);
        if (min > max)
        {
            min = min ^ max;
            max = max ^ min;
            min = min ^ max;
        }
        for (i = min; i < max + 1; ++i)
        {
            curcyc = 1;
            n = i;
            while (n != 1)
            {
                if (n < 1000000 && cach[n])
                {
                    curcyc = curcyc + cach[n] - 1;
                    break;
                }
                curcyc++;
                if (n & 0x0001)
                {
                    if (n >= ULONG_MAX / 3)
                    {
                        printf("%d overflow at step %d\n", i, curcyc);
                    }
                    n = 3 * n + 1;
                }
                else
                {
                    n = n >> 1;
                }
            }
            cach[i] = curcyc;
            maxcyc = maxcyc > curcyc ? maxcyc : curcyc;
        }
        printf("%d\n", maxcyc);
    }
    free(cach);
    return 0;
}

PS:该问题的详细描述和说明可以引用http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36

我已经更新了代码，将 n 的类型更改为 unsigned long 并添加了 if 语句以按预期检查以 3 * n + 1 开头的溢出。该程序仍然存在错误，没有通过判断。仍然需要帮助。谢谢。

Answer 1

我对这个方法有一定的信心。它产生的答案与我在最多 100 万条评论中提到的暴力 bc 程序相同(至少，一旦我修改了 bc 程序来计算数字)链中的值而不是转换的数量)。很快就达到100万。当缓存在 1000 万和 1 亿时变得不那么有效时，它会变慢。

示例输出(使用 -DPRODUCTION 编译的代码):

$ j=10; for i in 0 0 0 0 0 0 0; do j="$j$i"; ./collatz-so <<< "2 $j"; done
2 100 119
2 1000 179
2 10000 262
2 100000 351
2 1000000 525
2 10000000 686
2 100000000 950
$

带有为调试而编译的代码的示例输出:

$ ./collatz-so <<< '1 30'
   1:    1
   2:    2
   3:    8
   4:    3
   5:    6
   6:    9
   7:   17
   8:    4
   9:   20
  10:    7
  11:   15
  12:   10
  13:   10
  14:   18
  15:   18
  16:    5
  17:   13
  18:   21
  19:   21
  20:    8
  21:    8
  22:   16
  23:   16
  24:   11
  25:   24
  26:   11
  27:  112
  28:   19
  29:   19
  30:   19
1 30 112
$

代码:

#include <stdio.h>
#include <stdlib.h>

#if defined(PRODUCTION)
#define DEBUG 0
#else
#define DEBUG 1
#endif

static const int debug = DEBUG;

enum { CACHE_SIZE = 1000000 };

int main(void)
{
  int maxcyc = 0;
  int curcyc;
  int i, min, max;
  unsigned long n;
  int *cache = (int *)calloc(CACHE_SIZE, sizeof(int));
  if (cache == NULL)
  {
    printf("Memory Allocation Error\n");
    return 1;
  }

  if (scanf("%d %d", &min, &max) == 2)
  {
    if (min > max)
    {
      min = min ^ max;
      max = max ^ min;
      min = min ^ max;
    }
    for (i = min; i < max + 1; ++i)
    {
      curcyc = 1;
      n = i;
      while (n != 1)
      {
        if (n < CACHE_SIZE && cache[n])
        {
          //printf("%lu: cache[%lu] = %d; c = %d\n", n, n, cache[n], curcyc);
          curcyc += cache[n] - 1;
          break;
        }
        curcyc++;
        if (n & 0x0001)
          n = 3 * n + 1;
        else
          n /= 2;
      }
      if (i < CACHE_SIZE)
      {
        cache[i] = curcyc;
        //printf("cache[%d] = %d\n", i, curcyc);
      }
      if (debug)
        printf("%4d: %4d\n", i, curcyc);
      maxcyc = maxcyc > curcyc ? maxcyc : curcyc;
    }
    printf("%d %d %d\n", min, max, maxcyc);
  }

  free(cache);
  return 0;
}