c++ - 使用 vector 时出现段错误

Question

我正在尝试解决来自 projecteuler.net http://projecteuler.net/problem=14 的问题

问题是:

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

n → n/2(n 为偶数) n → 3n + 1(n 为奇数)

使用上述规则并从 13 开始，我们生成以下序列:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 可以看出，这个序列(从 13 开始到 1 结束)包含 10 个项。尽管尚未证明(Collat​​z Problem)，但认为所有起始数字都以 1 结尾。

哪个起始数(小于一百万)产生最长的链？

注意:一旦链开始，条款就可以超过一百万。

我首先使用递归解决方案，但在 100,000 次左右的迭代后出现了段错误。所以我做了一个迭代解决方案，希望能解决问题。在同一点发生段错误。我查看了堆栈跟踪，发现当一个值被添加到我在下面标记的行的 vector 时，问题就出现了。我以为 vector 会自动调整大小所以我真的很困惑这个问题。感谢您的帮助。这是代码:

#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
 int ITERATIONS=100000;

int main()
{
vector<int> maxArray;
vector<int> newArray;
int max_size = 0;
int n = 2;
int collatz = n;
while(n <= ITERATIONS){

#Stack trace error# 
newArray.push_back(collatz);
#Stack trace error#

if(collatz == 1){
++n;
if(newArray.size() > max_size){
maxArray.clear();
for(vector<int>::const_iterator i = newArray.begin(); i < newArray.end(); ++i){
maxArray.push_back(*i);
}
max_size = newArray.size();
}
newArray.clear();
collatz = n;
}
else if(collatz%2 == 0)
collatz = collatz/2;
else
collatz = 3*collatz+1;
}
for(vector<int>::const_iterator i = maxArray.begin(); i < maxArray.end(); ++i){
cout << *i << " "; 
}
cout << "\n" << max_size;
}

堆栈跟踪:

#0  0x00132416 in __kernel_vsyscall ()
#1  0x002641df in raise () from /lib/i386-linux-gnu/libc.so.6
#2  0x00267825 in abort () from /lib/i386-linux-gnu/libc.so.6 #3  0x001e013d in __gnu_cxx::__verbose_terminate_handler() ()  from /usr/lib/i386-linux-gnu/libstdc++.so.6
#4  0x001dded3 in ?? () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#5  0x001ddf0f in std::terminate() ()  from /usr/lib/i386-linux-gnu/libstdc++.so.6
#6  0x001de05e in __cxa_throw () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#7  0x001de67f in operator new(unsigned int) () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#8  0x08049362 in __gnu_cxx::new_allocator<int>::allocate (this=0xbffff214, 
__n=536870912) at /usr/include/c++/4.6/ext/new_allocator.h:92
#9  0x0804923c in std::_Vector_base<int, std::allocator<int> >::_M_allocate (
this=0xbffff214, __n=536870912)   at /usr/include/c++/4.6/bits/stl_vector.h:150
#10 0x08048e7f in std::vector<int, std::allocator<int> >::_M_insert_aux (
this=0xbffff214, __position=..., __x=@0xbffff220: -91)
at /usr/include/c++/4.6/bits/vector.tcc:327
#11 0x08048bdd in std::vector<int, std::allocator<int> >::push_back (
this=0xbffff214, __x=@0xbffff220: -91)
at /usr/include/c++/4.6/bits/stl_vector.h:834
#12 0x08048897 in main () at iterativeCollatz.cpp:16

Answer 1

我们做出以下观察:

1. 单个最小链仅由数字 1 组成。它的长度为 1。
2. 长链只能通过在 prepending x 到从 x/2 开始的tail 链来形成>(如果 x 是偶数)或 3x+1(如果 x 是奇数)。长链的长度是其尾部长度的 1。
3. 一旦链开始，条款就可以超过一百万。
4. 解决这个问题并不是真的需要负数。
5. 没有链的长度为 0。

我们得出以下结论:

1. 根据观察 1 和 2:一旦我们找到从 x 开始的链的长度，我们就必须记住它。这避免了重新计算尾部的长度。此外，我们可以将 0 的链长度(默认构造 std::size 的结果)解释为“尚未计算此长度”。<
2. 来自观察 3:对于任何 x > 1000000，如果我们最终需要计算从 x 开始的链的长度，没有什么能保证我们会对从 y 开始的每条链的长度使得 x > y >= 1000000。所以我们应该使用关联数据结构(例如 std::map)，而不是 std::vector，来存储内存长度:
3. 根据观察 3 和 4:我们将使用尽可能大的无符号整数类型。无需使用 bignum 库(例如 GMP)，我们需要的类型是 std::uint64_t。
4. 根据观察 5:我们可以使用链长值 0 来表示“此链长尚未计算”。这特别方便，因为 C++ 的关联容器在使用 operator [] 和容器中不存在的键时默认构造一个值，并且整数类型的默认构造值被初始化为 0 .

为方便起见，使用 C++11 构造编写的结果程序是这样的:

#include <iostream>
#include <map>
#include <set>
#include <stack>

int main()
{
  typedef std::uint64_t num;

  // ys[x] is the length of the chain starting at x.
  // xms is the set of numbers that yield the longest chains.
  // ym is the length of the longest chain so far.
  std::map<num, num> ys = {{1,1}};
  std::set<num> xms = {1};
  num ym = 1;

  for (num i = 2; i < 1000000; ++i)
  {
    std::stack<num> xs;
    num x = i, y = ys[x];

    // Compute successive chain elements until
    // a base element is reached whose chain
    // length has already been memoized.
    while (!y)
    {
      xs.push(x);
      x = (x & 1) ? (3*x + 1) : (x/2);
      y = ys[x];
    }

    // The lengths of the newly computed elements
    // can be found by repeatedly incrementing
    // the base element's chain length.
    while (!xs.empty())
    {
      x = xs.top();
      ys[x] = ++y;
      xs.pop();
    }

    // Keep track of which number(s)
    // yield the longest chain(s).
    if (y >= ym)
    {
      if (y > ym)
      {
        xms.clear();
        ym = y;
      }
      xms.insert(x);
    }
  }

  for (num xm : xms)
    std::cout << xm << ' ';

  return 0;
}