欧拉计划第14题

Question

欧拉计划第14题

5

The following iterative sequence is defined for the set of positive integers:

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++;

            }       
    }       
}

这是完整代码的链接。然而，我没有得到我期望的答案。有人能解释一下为什么这个算法不起作用吗？

- mohit

6

你的算法返回了什么？它与你的期望有何不同？ - gary

你应该使用调试器逐行执行程序，以找到第一行行为与你预期不符的地方。 - Oliver Charlesworth

我使用暴力算法计算出了问题的答案。我期望的结果是837799。 - mohit

顺便说一下：这是Collatz循环序列。 - wildplasser

1

@nhahtdh：链中最大的值接近570亿，需要36位。这个问题需要64位整数类型。 - Blastfurnace

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Fischer · Accepted Answer

你正在尝试按层级反向构建科拉兹树。因此，在内部循环的第 k 次迭代之后，该列表（在没有溢出的情况下）包含所有需要恰好 k 步才能在其科拉兹序列中达到 1 的数字。

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

1. 层级大小呈指数增长，大小大约每三个级别加倍。您没有足够的内存来存储超过100个级别的内容。

2. 第 k 级中最大的成员是 2^k。根据 num 成员所使用的类型，您在级别 31、32、63 或 64 处会发生溢出。然后，如果使用带符号的类型，则会出现未定义的行为，可能会在列表中出现负数，并且所有内容都变得混乱。如果使用无符号类型，则列表将包含0，所有内容都变得混乱。

由于27需要111步才能到达1，当 num > 27 时就会发生溢出，因此您会得到错误的结果。