---
# System prepended metadata

title: 'CPE 解題分享 - UVa 100 - The 3n + 1 problem '
tags: [UVA, c++., CPE]

---

# 題目
* 考慮以下的演算法：

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* 是多少。

# 思路
利用 *C++* 容器 *vector* 儲存元素並且運用 *.size()函式* 計算每個數列的長度，最終將長度回傳和 *max* 比較，如果大於 *max* 則取代 *max* 否則不變。 

# Code
```C++=1
#include <iostream>
#include <vector>
#include <algorithm>

class The3nproblem{
private:
  int range(int n){
    return (n%2?3*n+1:n/2);
  }

  int len(int k){
    std::vector<int> vec;
    int r=k;
    while(r!=1){
      vec.push_back(r);
      r=range(r);
    }
    return static_cast<int> (vec.size())+1;
  }
  
public:
  int _length(int i, int j){
    int max=0;
    for(int k=i;k<=j;++k){
      int le=len(k);
      max=(le>max?le:max);
    }
    return max;
  }
}__3n;

int main()
{ 
  int i, j;
  
  while(std::cin>>i>>j)
    std::cout<<i<<" "<<j<<" "<<__3n._length(std::min(i,j),std::max(i,j))<<"\n";
}
```