---
# System prepended metadata

title: UVa100 - The 3n + 1 problem
tags: [UVa]

---

# UVa100 - The 3n + 1 problem

## 題目
### 出處
[題目原文](https://onlinejudge.org/external/1/100.pdf)
### 內容
考慮以下的演算法：
```
輸入 n
印出 n
如果 n = 1 結束
如果 n 是奇數 那麼 n=3*n+1
否則 n=n/2
GOTO 2
```

給一個輸入 n ,透過以上的演算法我們可以得到一個數列（1作為結尾）。此數列的長度稱為n的cycle-length。

例如輸入 22, 得到數列： 
```
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
```
cycle length為 16.

對任2個整數i，j我們想要知道介於i，j（包含i，j）之間的數所產生的數列中最大的 cycle length 是多少。

Input
輸入可能包含了好幾列測試資料，每一列有一對整數資料 i，j 。

0< i，j < 1,000,000

Output
對每一對輸入 i, j ，輸出 i, j 和介於 i, j 之間的數所產生的數列中最大的 cycle length。

#### Sample Input
```
1 10
100 200
201 210
900 1000
```
#### Sample Output
```
1 10 20
100 200 125
201 210 89
900 1000 174
```

## 程式碼

實作題意中演算法後，找出輸入範圍中最大的cycle length即可

### C++
```cpp=
#include <iostream>
using namespace std;
int alg(int n){         /*題意中演算法*/
  int t = 1;            /*cycle length*/
  while (n != 1){
    t = t + 1;
    if (n % 2 == 1){
      n = 3 * n + 1;
    }
    else n = n / 2;
  }
  return t;
}

int main() {
  int n, m;
  while( cin >> n >> m ){
    int ans = 1;
    cout << n << " " << m << " ";
    if (n > m){
      int temp = n;
      n = m;
      m = temp;
    }
    for (int i = n; i <= m; i++){
      if (alg(i) >= ans){
        ans = alg(i);
      }
    }
    cout << ans << endl;
  }
}
```
### python
```python=
def alg(n) :
  t = 1
  while n != 1 :
    t = t + 1
    n = 3 * n + 1 if n % 2 == 1 else n / 2
  return t

while True:
  try :  
    n, m = input().split()
    n, m = int(n), int(m)
    ans = 1
    print(n, m, end = " ")
    if n > m :
      n, m = m, n
    for i in range(n, m + 1) :
      if alg(i) >= ans :
        ans = alg(i)
    print(ans)
  except EOFError:
    break
  
```