---
# System prepended metadata

title: The 3n + 1 problem(UVA100)
tags: [CPE一顆星必考題, CPE 一顆星]

---

# The 3n + 1 problem(UVA100)
## [程式繳交區](https://hackmd.io/@Renektonn/rkUTjc5wyx/edit)
## 標籤:模擬
## 題目
[點我](https://onlinejudge.org/external/1/100.pdf)

## 解題系統 
[UVA](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36)
[ZJ](https://zerojudge.tw/ShowProblem?problemid=c039)

## 題意
- 給定i , j，求i到j之間的所有數(包括i,j)的max cycle length
> i可能大於j
- cycle length的定義如下
    - 1. input n
    - 2. if n = 1 then STOP
    - 3. if n is odd then n ←− 3n + 1
    - 4. else n ←− n/2
    - 5. GOTO 2
    - 看n變了幾次，次數+1即為cycle length
- i , j會不斷輸入直到EOF

## 演算法
```
1.輸入整數a b，若沒有，則結束
2.印出a b 
3.找出[a,b]區間的max cycle length，max cycle length要寫成一個函式，輸入n，回傳一個值，並將印出max cycle length印出
4.回到1
```

## 程式碼
```cpp=
/*
0 < a, b < 10000
*/
#include <iostream>
using namespace std;

// 計算單個數字的 cycle length
int cycleLength(int n) {
    int length = 1;
    while (n != 1) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            n = 3 * n + 1;
        }
        length++;
    }
    return length;
}

int main() {
    int a, b;
    while (cin >> a >> b) { // 持續讀入直到無輸入
        cout << a << " " << b << " ";
        int maxLength = 0;
        if (a > b) swap(a, b); // 確保 a <= b

        for (int i = a; i <= b; ++i) {
            int currentLength = cycleLength(i);
            if (currentLength > maxLength) {
                maxLength = currentLength;
            }
        }
        cout << maxLength << endl;
    }

    return 0;
}

```

