递归栈溢出 C++

Question

我是C++的新手，但我认为解决一些欧拉计划问题会让我熟悉这门语言。

当尝试解决欧拉计划第14题: 最长考拉兹序列时，我的C++解法无法正常工作，但是我的Python解法没有问题...

import time 
start = time.time()
memo = {1:1,2:2}
longest_chain, longest_starting_key = 2, 2

def rec(a):
    global longest_chain, longest_starting_key

    if a in memo.keys():
        return memo[a]    
    if a % 2 == 0:
        memo[a] = rec(a // 2) + 1
    else:
        memo[a] = rec(3 * a + 1) + 1
    if memo[a] > longest_chain:
        longest_chain = memo[a]
        longest_starting_key = a
    return memo[a]    

for i in range(1000000,3,-1): rec(i)

print("starting key", longest_starting_key , ": has length", longest_chain)
print((time.time() - start), "seconds")

并获得

starting key 837799 has length 525
1.399820327758789 seconds

我的C++尝试...（我认为它是等价的...）

#include <iostream>
#include <unordered_map>
std::unordered_map<int, int> mem = { {1,1},{2,2} };
int longest_chain{ 2 }, best_starting_num{ 2 };

bool is_in(const int& i){
    auto search = mem.find(i);
    if(search == mem.end())
        return false;
    else
        return true;
}

int f(int n){
    if(is_in(n))
        return mem[n];
    if(n % 2)
        mem[n] = f(3 * n + 1) + 1;
    else
        mem[n] = f(n / 2) + 1;
    if(mem[n] > longest_chain)
        longest_chain = mem[n];
    return mem[n];
}

int main(){
    for(int i = 3; i < 1000000; i++){
        f(i);
    }
    std::cout << longest_chain << std::endl;
}

在Visual Studio的调试模式下运行时，我遇到了以下错误。

Unhandled exception at 0x00007FF75A64EB70 in
0014_longest)collatz_sequence_cpp.exe: 0xC00000FD: Stack overflow
(parameters: 0x0000000000000001, 0x000000DC81493FE0).

有人告诉我应该使用指针在堆上进行分配，但我对指针的使用经验非常有限...

另一件我不理解的事情是...当我在主循环中使用100'000而不是1'000'000时，它可以运行，但速度非常慢。

- Quantifeye

---

通过 VC++ 调试器运行它会很有帮助。我认为 mem 已经在堆中分配了新元素。 - Jean-François Fabre

当我在我的系统上运行你的C++代码时，我得到了一个489的结果（而不是525）。很明显Python和C++版本并不相等... - Josh Milthorpe

@Barry提供了一个非常好的算法答案，但是你的C++版本中也存在编码错误 - 每当值存在时，你都会进行两次map查找，第一次是为了检测其可用性，第二次才是真正获取它。这不好。 - SergeyA

值得在 Stack Overflow 上搜索单词 Collatz 来获取灵感。 - wally

Answer 1

提示: Collatz序列提供了什么关于n范围的不变量（数学上），你的Python代码满足但你的C++代码不满足？提示：在栈溢出实际发生之前，n的最后几个值是什么？

- Barry

---

啊，这正是我想说的，但提示格式更符合问题背景的教育主题。 :) - wally

我一直盯着它看，但毫无结果。我将Python版本的主循环更改为类似于C++版本（而不是从999,999倒数）。更改了名称，使它们看起来更相似...但我仍然找不到它。 - Quantifeye

@Quantifeye 从 113383 开始。你调用 f 的所有 n 值是什么？ - Barry