---
title: 'UVa 100 題解 — C++'
disqus: hackmd
---

# UVa 100 題解 — C++
:::info
:bulb: 此筆記為UVa 100的題目詳解，包含解題思路、C++範例程式碼。
:::

## The 3n + 1 problem (ZeroJudge c039.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=c039)
:::success
考慮以下的演算法：

1. 輸入 n
2. 印出 n
3. 如果 n = 1 結束
4. 如果 n 是奇數 那麼 n=3*n+1
5. 否則 n=n/2
6. GOTO 2

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

據推測此演算法對任何整數而言會終止 (當列印出 1 的時候)。雖然此演算法很簡單，但以上的推測是否真實卻無法知道。然而對所有的n ( 0 < n < 1,000,000 )來說，以上的推測已經被驗證是正確的。

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

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

### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |

### 解題思路
:::warning
這題可以直接暴力解。

有個小地方可以注意一下，因為這題 i、j 並不一定 j > i，因此可以先輸出 i、j，若 i > j 再交換即可。
:::

### 範例程式碼

#include <bits/stdc++.h>
using namespace std;

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int k;
	int i, j;
	
	while (cin >> i >> j) {
		int max = 0;
		
		cout << i << " " << j << " ";
		
		if (i > j)
			swap(i, j);
		
		for (k=i;k<=j;k++) {
			int n = k, l = 1;
			
			while (n != 1) {
				if (n % 2 != 0)
					n = 3 * n + 1;
				else
					n = n / 2;
					
				l++;
			}
			
			if (l > max)
				max = l;
				
		}
		
		cout << max << endl;
	}

	return 0;
}

### 運行結果
<font color="#00BB00">**AC**</font> (13ms, 332KB)

###### tags: `CPE 1星`

:::danger
查看更多資訊請至：https://www.tseng-school.com/
:::