3n+1的递归解

Question

我只是喜欢做简单的递归。对于一个数字，如果它是偶数，它将接近 (number/2)，如果是奇数，则接近 (3*number+1)。达到 1 的次数。

10
10-> 5-> 16-> 8-> 4 -> 2 ->1
总进程 6

long arr[10000];
long dp(int n)  
{ 
    if(n==2|| n==1) return 1;
    if(arr[n]) return arr[n];

    if(n%2==0) return arr[n]=1+dp(n/2);
    else if(n%2==1) return arr[n]=1+dp(3*n+1);
    return arr[n];
}

我已经创建了这样的函数，但对于某些输入，如 999 或 907 会导致分段错误。
我想知道为什么？

如果我增加数组大小，它的输出就会正确。
我也想知道为什么？

为什么它取决于数组大小，因为我已经使用了很长时间的数组元素数据类型，所以它应该为这些输入正确输出？

Answer 1

您正在溢出数组，因为序列值超过 9999。

Answer 2

段错误来自数组溢出。你做下面的事情怎么样？

void rec(int n, int* steps) {
  ++(*steps);
  printf("%d\n", n);
  // termination step if 'n' equals 1
  if(n == 1)
    return;
  if (n % 2 == 0)
    rec(n/2, steps);
  else
    rec(3*n+1, steps);
}

int main(void) {
  int steps = 0;
  rec(10, &steps);
  printf("Steps = %d\n", steps);
  return 0;
}

输出：

10
5
16
8
4
2
1
Steps = 7

此处提供的代码（当然）与 Jarod 的一致。

Answer 3

通过 999，您达到了 11392

通过 907，您达到了 13120

而且这些数字超出范围。

Live example

Answer 4

您对数组的索引越界

对于您正在使用的输入，变量n在执行期间将超过数组大小10000。这会导致程序访问超出其边界的内存，从而导致段错误。
如果您尝试 memoize the function, I'd suggest using std::map instead of a fixed array. This is an associative array which stores key-value pairs——在本例中，每个记忆的输入输出对——并且可以快速检索与给定键关联的值。地图非常适合此应用程序，因为它们可以仅使用实际需要的内存来存储此数据，并根据需要自动增长。
您也可以使用 std::vector，但不推荐这样做。向量就像数组，但它们可以动态调整大小，避免索引越界的问题。这种方法的缺点是对于某些输入，可能需要非常大量的内存，可能是几千兆字节。如果程序被编译为 32 位二进制文件而不是 64 位二进制文件，程序可能会在运行时崩溃，因为它无法为向量分配足够的内存。

使用地图实现

#include <iostream>
#include <map>

using namespace std;

long long dp(unsigned long long);

int main() {
    unsigned long long n;

    while(true) {
        cout << "Enter a number, or 0 to exit: ";
        cin >> n;

        if(!cin) {
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            cerr << "Invalid input, please try again." << endl;
            continue;
        }

        if(n == 0)
            return 0;
        else
            cout << dp(n) << endl;
    }

    return 0; // Unreachable
}


long long dp(unsigned long long n) {
    static map<long long, long long> memo;

    if(n == 2 || n == 1) return 1;
    if(memo[n]) return memo[n];

    if(n % 2 == 0) return memo[n] = 1 + dp(n / 2);
    else if(n % 2 == 1) return memo[n] = 1 + dp(3 * n + 1);
    return memo[n];
}

使用向量实现

#include <iostream>
#include <vector>

using namespace std;

long long dp(unsigned long long);

int main() {
    unsigned long long n;

    while(true) {
        cout << "Enter a number, or 0 to exit: ";
        cin >> n;

        if(!cin) {
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            cerr << "Invalid input, please try again." << endl;
            continue;
        }

        if(n == 0)
            return 0;
        else
            cout << dp(n) << endl;
    }

    return 0; // Unreachable
}


long long dp(unsigned long long n) {
    static vector<long long> arr;

    if(arr.size() <= n)
        arr.resize(n + 1);

    if(n == 2 || n == 1) return 1;
    if(arr[n]) return arr[n];

    if(n % 2 == 0) return arr[n] = 1 + dp(n / 2);
    else if(n % 2 == 1) return arr[n] = 1 + dp(3 * n + 1);
    return arr[n];
}

Answer 5

如果您只想知道它需要的进程数，则不应使用数组存储。

int numProcesses = 0;

int hailstone(int n) {

    if (n == 1) {
        return 1;
    } // base case

    ++numProcesses; // if it wasn't the base case the method will do some work so increment numProcesses

    if (n % 2 == 0) {
        return hailstone(n / 2);
    } // n is even
    else {
        return hailstone(3 * n + 1);
    } // n is odd
}

这是未经测试的，但我认为它应该可以工作，最后 returns numProcesses 应该等于该方法被调用的次数（只要它不是用参数调用的） 1).

3n+1的递归解

Recursive solution for 3n+1

c++

algorithm

dynamic-programming

memoization

您对数组的索引越界

使用地图实现

使用向量实现