为向量中足够大的输入获得负输出

Question

我正在为如下问题编写算法：

Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this until n is one. For example, the sequence for n=3 is as follows: 3→10→5→16→8→4→2→1

可以找到原题here

我为它写的算法如下：

#include <iostream>
#include<vector>
using namespace std;
void check(long int n, vector<int> &arr);
int main(){
    long int n;
    cin>>n;
    vector<int> arr; //Vector to store values of n
    check(n,arr);
    for(unsigned int i=0;i<arr.size();i++){
      cout<<arr[i]<<' ';    //Printing the final values of n
    }
    return 0;
}

void check(long int n,vector<int> &arr){
    arr.push_back(n);
    if(n%2==0){   //if n is even
      n=n/2;
      if(n!=1){
        check(n,arr);
      }
      else if(n==1){
        arr.push_back(1);
      }
    }
    else{         //if n is odd
      n=(n*3)+1;
      if(n!=1){
        check(n,arr);
      }
      else if(n==1){
        arr.push_back(1);
      }
    }
    return;
}

我的解决方案适用于 n 的较小值。然而，当 n 变得足够大时——尤其是在 138367 附近的某个地方（根据编译器，这是第一个答案出错的测试用例），最后打印的 n 的值也会开始包含一些'negative numbers'，有点不合理

例如，如果我一开始输入n=986089625，那么最后输入的下一个数字就是-1336698420。而正确的数字应该是2958268876。令人惊讶的是，紧随其后的下一个数字是正确的，但在某些（随机）间隔内，数字会变为负数。

我知道算法可以进一步简化，但我无法理解这个算法的问题。我想我遗漏了一些微妙的东西！

Answer 1

典型的int（带符号的 32 位长）最多只能存储 2,147,483,647（2**31 - 1）的数字，而数字 2958268876 超出了这个限制。

您正在使用 long int 进行计算，因此您也应该将其用于 vector 的元素。

也就是说三个vector<int>应该换成vector<long int>.

Answer 2

您可以通过这个简单的例子了解它是如何工作的

#include <limits.h>
#include <iostream>

int main()
{
    int n = INT_MAX;
    std::cout << "n=" << n << '\n';
    std::cout << "n+1=" << n + 1 << '\n';

    unsigned m = UINT_MAX;
    std::cout << "m=" << m << '\n';
    std::cout << "m+1=" << m + 1 << '\n';
}

给予

n=2147483647
n+1=-2147483648
m=4294967295
m+1=0

当达到限制时，回绕到 INT_MIN 或零，具体取决于整数类型的符号。

当然，相反的方向也会发生同样的情况，从 INT_MIN 到 INT_MAX 或从零到 UINT_MAX.

为向量中足够大的输入获得负输出

Getting negative outputs for large enough inputs in vector

c++

algorithm

vector

unsigned-integer