5

我目前正在解决Project Euler 问题 14：

为正整数集定义了以下迭代序列：

n → n/2 (n is even)
n → 3n + 1 (n is odd)  

Using the rule above and starting with 13, we generate the following sequence:
               13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1  

Which starting number, under one million, produces the longest chain?

我设计了以下算法来解决这个问题：

  • 我没有为每个数字单独查找序列，这将包含大量冗余计算，而是尝试从 1 向后开发序列。也就是说，从数字开始并预测它之前的元素。
  • 由于可以生成多个系列，因此使用链表存储所有系列的最近编号。（这个想法是只存储那些具有较长系列的元素。）
  • 我将循环这个，直到找到所有低于给定限制的数字；限制下的最后一个数字将具有最长的系列。

这是我的代码： 

void series_generate(long num)
{
    long n = 1;
    addhead(n);             //add 1 to list.
    while (n < num) 
    {
            series *p;
            for (p = head; p != NULL; p = p->next)
            {
                    long bf = p->num - 1;
                    if (p->num%2 == 0 && bf != 0 && bf%3 == 0) {
                            bf /= 3;
                            if (bf != 1)
                                    addhead(bf);
                            if (bf < num)
                                    n++; 
                    }
                    p->num *= 2;
                    if ( p->num < num)
                            n++;

            }       
    }       
}

这是完整代码的链接。 但是，我没有得到预期的答案。谁能解释为什么这个算法不起作用？

4

1 回答 1

9

您正在尝试逐级构建 Collat​​z 树。因此k，在内部循环的第 - 次迭代之后，列表包含（虽然没有发生溢出）所有需要精确k步骤才能在其 Collat​​z 序列中达到 1 的数字。

这种方法有两个严重的问题。

  1. 级别的大小呈指数增长，大小大约每三个级别增加一倍。您没有足够的内存来存储不超过 100 的级别。
  2. 级别中最大的成员k是 2 k。根据num成员使用的类型，您会在级别 31、32、63 或 64 处溢出。然后，如果您使用有符号类型，您将有未定义的行为，可能是列表中的负数，并且一切都变得混乱。如果您使用无符号类型，您的列表包含一个 0，并且一切都变得混乱。

由于 27 需要 111 步才能达到 1，所以你有溢出时num > 27，因此你得到错误的结果。

于 2012-07-04T18:44:26.567 回答