[題解] 考拉茲猜想路徑長

#include <iostream>
#include <vector>

using namespace std;

int dp[200000]={};

int find(long int a,int b){
    int ans=1;
    while(a>1&&ans<=b){
        if(a%2==0){
            a=a/2;
            ans++;
        }else{
            a=3*a+1;
            ans++;
        }
    }
    if(ans<=b){
        return ans;
    }else{
        return 0;
    }
}

int main(){
    int a;
    for(int i=1;i<100000000;i++){
        a=find(i,64);
        if(a) dp[a]++;
    }
    for(int i=0;i<=64;i++){
        cout<<i<<": "<<dp[i]<<endl;
    }

}

0: 0
1: 2
2: 1
3: 1
4: 1
5: 1
6: 2
7: 2
8: 4
9: 4
10: 6
11: 6
12: 8
13: 10
14: 14
15: 18
16: 24
17: 29
18: 36
19: 44
20: 58
21: 72
22: 91
23: 113
24: 143
25: 179
26: 227
27: 287
28: 365
29: 459
30: 577
31: 718
32: 911
33: 1098
34: 1407
35: 1793
36: 2061
37: 2656
38: 3071
39: 3778
40: 4917
41: 5045
42: 6674
43: 8808
44: 8606
45: 11531
46: 10433
47: 14263
48: 19391
49: 16738
50: 23227
51: 20488
52: 26417
53: 37038
54: 28511
55: 40841
56: 58054
57: 42904
58: 62295
59: 42972
60: 63683
61: 93517
62: 62378
63: 93572
64: 71605

Process returned 0 (0x0)   execution time : 26.438 s
Press ENTER to continue.

#include <bits/stdc++.h>

using namespace std;

int dp[20000]={};

void test(long int a,int b){
    if(b<64){
        if((a-1)%3==0&&a%2==0){
            //dp[b]++;
            test((a-1)/3,b+1);
        }
        dp[b]++;
        test((2*a),b+1);
    }
}



int main()
{
    dp[1]=1;
    dp[2]=1;
    dp[3]=1;
    test(8,4);
    for(int i=0;i<64;i++) cout<<i<<": "<<dp[i]<<endl;
    //for(int i=0;i<64;i++) cout<<dp[i]<<", ";
    return 0;
}

0: 0
1: 1
2: 1
3: 1
4: 1
5: 1
6: 2
7: 2
8: 4
9: 4
10: 6
11: 6
12: 8
13: 10
14: 14
15: 18
16: 24
17: 29
18: 36
19: 44
20: 58
21: 72
22: 91
23: 113
24: 143
25: 179
26: 227
27: 287
28: 366
29: 460
30: 578
31: 732
32: 926
33: 1174
34: 1489
35: 1879
36: 2365
37: 2988
38: 3780
39: 4788
40: 6049
41: 7628
42: 9635
43: 12190
44: 15409
45: 19452
46: 24561
47: 31025
48: 39229
49: 49580
50: 62680
51: 79255
52: 100144
53: 126542
54: 159930
55: 202085
56: 255455
57: 322869
58: 408002
59: 515542
60: 651407
61: 823238
62: 1040490
63: 1315036

Process returned 0 (0x0)   execution time : 0.054 s
Press ENTER to continue.