Longest Collatz sequence

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

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

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

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.

1.函数递归调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*思路:简单递归
1.if x == 1, return 1;
2.if x == odd, return (3n + 1);
3.if x == even, return (n / 2);
*/

#include<iostream>
using namespace std;

int func(int x){
    if(x == 1){
        return 1;
    }
    if(x % 2 == 0){
        return func(x / 2) + 1;
    }
    return func(3 * x + 1) + 1;   
}

int main(){
    int ans = 0, mmax = 0;
    for(int i = 1; i <= 1000000; ++i){
        int t = func(i);
        if(t > mmax){
            mmax = t;
            ans = i;
        }
    }
    cout << ans << endl;
    return 0;
}

image-20210412171654270

注意：方法1递归步数太多导致出现爆栈（segmentation fault），原因是递归调用太深

2.利用记忆数组优化递归过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
using namespace std;

//1.建立一个记忆化数组，存储计算过程中的中间值(需要将数组额外开大一些)
long long num[10000005];

long long func(long long x){
    if(x == 1){
        return 1;
    }
    //2.num[x] != 0,发现该数字之前已经计算过，直接返回数值
    if(x < 10000000 && num[x] != 0){
        return num[x];
    }
    long long t;
    //3.num[x] == 0,发现该数字之前没有计算过，进行计算并存入记忆化数组中
    if(x % 2 == 0){
        t = func(x / 2) + 1;
    }else{
        t = func(3 * x + 1) + 1;
    }
    if(x < 10000000){
        num[x] = t;
    }
    return t;
}

int main(){
    int ans = 0, mmax = 0;
    for(int i = 1; i <= 1000000; ++i){
        int t = func(i);
        if(t > mmax){
            mmax = t;
            ans = i;
        }
    }
    cout << ans << endl;
    return 0;
}

image-20210412171654270

补充：当算法优化到极致时，只能是用空间换时间 or 用时间换空间，而记忆化数组就是典型的用空间换时间