---
tags: 蘿莉控自學
---
> 蘿莉控的C++自學筆記
# c039-acm: The 3n + 1 problem
連結: https://zerojudge.tw/ShowProblem?problemid=c039
## Sol1. 假解
用DP和遞迴天真
可以AC(測資不夠強)
N開大一點就過了，如果開1000005會RE(記憶體區段錯誤)，因為會讀到範圍外的數字
AC(3ms, 5MB)

#include<bits/stdc++.h>
using namespace std;
const int N = 100000005;
int dp[N] = {0};
int solve(int x){
    if (x == 1) return 1;
    if (dp[x] != 0) return dp[x];
    int len;
    if (x % 2 == 1){
        len = solve(3*x+1) + 1;
    }else len = solve(x / 2) + 1;
    dp[x] = len;
    return dp[x];
}
int main(){
    int i, j;
    while (cin >> i >> j){
        bool note = false;
        if (i > j){
            swap(i, j);
            note = true;
        }
        int max_len = 0;
        for(int k = i;k <= j;k ++){
            max_len = max(max_len, solve(k));
        }
        if (!note) cout << i <<" "<< j <<" "<< max_len << endl;
        else cout << j <<" "<< i <<" "<< max_len << endl;
    }
}

# Sol2.
就是和前面一樣
但在超過1000005的範圍時不查表
這應該很容易就不寫了~~
(好啦還是寫一下)
AC(3ms, 4.2MB)

#include<bits/stdc++.h>
using namespace std;
const int N = 1000005;
int dp[N] = {0};
int solve(int x){
    if (x == 1) return 1;
    if (!(x > 1000000))if (dp[x] != 0) return dp[x];
    int len;
    if (x % 2 == 1){
        len = solve(3*x+1) + 1;
    }else len = solve(x / 2) + 1;
    if (!(x > 1000000))dp[x] = len;
    if (!(x > 1000000))return dp[x];
    else return len;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int i, j;
    while (cin >> i >> j){
        bool note = false;
        if (i > j){
            swap(i, j);
            note = true;
        }
        int max_len = 0;
        for(int k = i;k <= j;k ++){
            max_len = max(max_len, solve(k));
        }
        if (!note) cout << i <<" "<< j <<" "<< max_len << endl;
        else cout << j <<" "<< i <<" "<< max_len << endl;
    }
}

> 回到主頁: https://hackmd.io/C_fY69EtSXeHHPLT1QxUug