使用矢量时的分段故障 [英] Segmentation Fault when using Vectors

问题描述

我想从projecteuler.net http://projecteuler.net/problem=14

I am trying to solve a problem from projecteuler.net http://projecteuler.net/problem=14

这是问题：

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

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

n→n / 2（n为偶数）
n→3n + 1（n为奇数）

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

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

Using the rule above and starting with 13, we generate the following sequence:

13→40→20→10→5→16→8→4→2 →1
可以看出，这个序列（从13开始并在1结束）包含10个项。虽然尚未被证明（Collat​​z问题），但是认为所有起始数字都在1处结束。

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

哪个起始号码低于一百万，产生最长的链？

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

注意：一旦链条开始，条款允许超过一百万。

NOTE: Once the chain starts the terms are allowed to go above one million.

递归的解决方案，但是在100,000左右的迭代后，出现了分割错误。所以我做了一个迭代的解决方案，希望能解决这个问题。分段故障发生在同一点。我看了堆栈跟踪，发现问题出现时，一个值被添加到向量我标记下面的行。我认为矢量会自动调整大小，所以我真的很困惑这个问题。谢谢你的帮助。这里是代码：

I first used a recursive solution, but after 100,000 or so iterations there was a segmentation fault. So I made an iterative solution hoping that would solve the problem. A segmentation fault occurred at the same point. I looked at the stack trace and found that the problem showed up when a value was added to the vector I marked the line below. I thought the vector would automatically resize so I'm really confused about this problem. Thanks for your help. Here's the code:

#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

推荐答案

进行以下观察：

1. 单个最小链只包含数字1.其长度为1。


2. 长链只能通过 x 前缀到尾链形成c $ c> x / 2 （如果 x 为偶数）或 3x + 1 （如果 x 是奇数）。长链的长度为1加上其尾部的长度。


3. 一旦链条开始，条款允许超过一百万。

1. The single smallest chain consists of just the number 1. Its length is 1.
2. Long chains can only be formed by prepending x to a tail chain that begins at either x/2 (if x is even) or 3x+1 (if x is odd). The length of a long chain is 1 plus the length of its tail.
3. Once the chain starts the terms are allowed to go above one million.
4. Negative numbers are not really needed to solve this problem.
5. No chain has length 0.

p>我们得到以下结论：

And we arrive at the following conclusions:

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。

1. From observations 1 and 2: Once we find the length of a chain beginning at x, we must memoize it. This avoids recomputing the lengths of tails. Furthermore, we can interpret a chain length being 0 (which results by default-constructing a std::size) as "this length has not been computed yet".
2. From observation 3: For any x > 1000000, if we eventually need to compute the length of the chain beginning at x, nothing guarantees we will be interested in the length of every chain beginning at a y such that x > y >= 1000000. So we should use an associative data structure (such as std::map), not std::vector, for storing the memoized lengths:
3. From observations 3 and 4: We shall use an unsigned integral type as big as possible. Without going as far as using a bignum library (such as GMP), the type we want is std::uint64_t.
4. From observation 5: We can use a chain length value of 0 to denote "this chain length has not been computed yet". This is particularly convenient because C++'s associative containers default-construct a value when using operator [] with a key that does not exist in the container, and a default-constructed value of an integral type is initialized to 0.

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

The resulting program, written using C++11 constructs for convenience, is this:

#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;
}

这篇关于使用矢量时的分段故障的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！