[CPE一星49題] UVA100 - The 3n + 1 problem 題目解析與實作

編輯製作： 蔡豐聲、李心潔

單位： 中國醫藥大學醫療資訊學系程式俱樂部

YT： https://youtu.be/LQs6xlgkgUE

## 題目資訊

題目名稱： The 3n + 1 problem

編號： CPE10400, UVA100

相關平台： Zero Judge, Online Judge

## 題目解析

這是一個關於數列規律的問題。對於任何一個正整數 $n$，我們定義一套運算規則：

如果 $n$ 是奇數，則下一步變為 $3n + 1$。
如果 $n$ 是偶數，則下一步變為 $n/2$。
如此循環直到 $n = 1$ 為止。

Cycle Length（循環長度）： 指的是從 $n$ 開始到 $1$ 所經過的數字個數（包含 $n$ 與 $1$）。

目標： 給定兩個整數 $i$ 和 $j$，找出在 $i$ 與 $j$ 範圍之間（含 $i, j$）所有數字中，最大的循環長度是多少。

## 輸入說明

每組測試資料包含一對整數 $i$ 和 $j$。

輸入直到檔案結束 (EOF)。

## 輸出說明

對於每對輸入 $i$ 和 $j$，輸出原始的 $i, j$ 順序，以及在該區間內最大的循環長度。

## 範例測試

輸入：

1 10
100 200

輸出：

1 10 20
100 200 125

## 解題思路

處理輸入順序： 題目給予的 $i$ 和 $j$ 不一定是由小到大，因此在進入迴圈計算前，需判斷並確保範圍起始點。

計算個別循環長度：

使用 while 迴圈計算直到數字變為 1。
記錄過程中出現的數字個數。

找出最大值：遍歷區間內每個數字，並用一個變數（如 max_steps）更新最大循環長度。

## 實作程式碼 (Python)

def solve(n):
    steps = 1
    while n != 1:
        if n % 2 == 1:
            n = 3 * n + 1
        else:
            n //= 2
        steps += 1
    return steps

while True:
    try:
        i, j = map(int, input().split())
        small, big = min(i, j), max(i, j)
        max_steps = 0
        for k in range(small, big + 1):
            steps = solve(k)
            max_steps = max(max_steps, steps)
            
        print(i, j, max_steps)
        
    except:
        break

---
本著作採用創用 CC 姓名標示-非商業性-禁止改作 3.0 台灣授權條款授權。
本部落格的免責聲明。

程式俱樂部YT頻道 https://www.youtube.com/@tsai-cai

搜尋此網誌

中國醫藥大學蔡豐聲