# [競程] 3n+1 問題
###### tags: `競程`

## 問題
* ZeroJudge: [c039](https://zerojudge.tw/ShowProblem?problemid=c039)

給定一個正整數 $n$，如果 $n$ 是偶數，則把 $n$ 除以2；如果 $n$ 是奇數，則把 $n$ 乘以 3 再加上 1。如此不斷對新的數重複這個程序，最後到1的時候停止，例如輸入 22，得到的數列為：

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 

據推測此演算法對任何整數而言會終止。雖然此演算法很簡單，但以上的推測是否真實卻無法知道。然而對所有的 $0 < n < 1000000$ 來說，以上的推測已經被驗證是正確的。

我們把得到的數列長度稱為 $n$ 的 cycle length。以上面的例子來說，22 的 cycle length 為 16。

問題來了：對任2個整數 $i$ 和 $j$，我們想要知道介於 $i$ 和 $j$ 之間（包含 $i$ 和 $j$）的數中，最大的 cycle length 是多少。

## 暴力解
照著題目的流程直接算過一次，我們就可以得到想要的答案：

def three_n_plus_one(i, j):
    if i > j:
        i, j = j, i
    max_count = -1 
    for num in range(i, j + 1):
        count = 0
        while num != 1:
            count += 1
            if num % 2 == 0:
                num = num / 2
            else:
                num = 3 * num + 1
        max_count = max(count + 1, max_count)
    return max_count

## 動態規劃解
使用動態規劃解可以省去重複計算的時間。注意到這邊我們可以選擇由上而下或由下而上建置一個dict，這邊我們選擇使用由上而下的方式，方法如下：

def three_n_plus_one_top_down(i, j):
    if i > j:
        i, j = j, i   
    dp = {}
    for k in range(i, j + 1):
        num = k
        count = 0
        while num != 1:
            if num in dp:
                count += dp[num]
                break
            else:
                count += 1
                if num % 2 == 0:
                    num = num / 2
                else:
                    num = 3 * num + 1
        dp[k] = count

    return max(dp.values()) + 1