3
私はC++を初めて使っていますが、いくつかのプロジェクトオイラーの問題に取り組むことで、言語に慣れることができると考えました。再帰スタックオーバーフローC++
Project Euler Problem 14: Longest Collatz sequence
私は仕事に私の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).
を得る誰かが、私は、ポインタを使ってヒープ上に割り当てる必要があることを教えてくれましたが、ポインタでの作業と非常に限られた経験を持っています。..
私が理解できないもう一つのことは...本体のループに1'000'000の代わりに100'000で実行すると動作しますが、非常に遅いです。
vC++デバッガを使用して実行すると多くの手助けをします。私は 'mem'が既にヒープに新しい要素を割り当てていると思います。 –
システムでC++コードを実行すると、結果は489（525ではなく）です。 PythonとC++のバージョンは明らかに同等ではありません... –
@Barryは非常に優れたアルゴリズム的な答えを提供しますが、C++バージョンにもコーディングエラーがあります。可用性、実際にそれを得るために秒。良くない。 – SergeyA