← 全部題目
Solved UVa 解題

The 3n + 1 Problem

UVa 100 UVa Online Judge ↗

在 [i, j] 區間內，取每個數最長的 3n+1 序列；特別要注意的是 i 可能大於 j。

Ad Hoc Simulation
Attempts1
First attempt2026-08-17
Solved2026-08-17

Problem

給定一區間 [i, j]，依照題目所給的演算法，求出區間內循環次數 (cycle-length) 最多的數字。

input nprint nn = 1 ?n is odd ?n ← 3n + 1n ← n / 2STOP yesnoyesno

formalization 之後，其實可以寫成數學式：

f(n)={3n+1if n is oddn/2if n is evenf(n) = \begin{cases} 3n + 1 & \text{if } n \text{ is odd} \\[4pt] n / 2 & \text{if } n \text{ is even} \end{cases}

Approach

這題其實只需照著題目給的 pseudocode 刻出來就會過。我們可以設定一個變數以存放最長的循環次數，若大於當前的循環次數，則將變數更新。

  1. 輸出順序：測資可能給出 i>ji > j。此外要先照原本順序印出 ii 和 jj，接著排序 i、ji 、 j 後再進入迴圈（順序印反會 WA）。

  2. 迴圈變數：利用 temp 變數來存放 n 做運算，避免直接更動到迴圈變數，造成無窮迴圈。

Solution

main.cpp
#include <iostream>


using namespace std;


void solve() {
    int i, j;


    while (cin >> i >> j) {
        cout << i << " " << j << " ";


        if (i > j) {
            swap(i, j);
        }


        int max_Cycle = 0;


        for (int k = i; k <= j; k++) {
            int cycle = 1;
            int temp = k;


            while (temp != 1) {
                if (temp % 2 == 1) {
                    temp = temp * 3 + 1;
                } else {
                    temp /= 2;
                }
                cycle++;
            }


            max_Cycle = max(max_Cycle, cycle);
        }


        cout << max_Cycle << '\n';
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    solve();


    return 0;
}

Sample Input

sample.in
1 10
100 200
201 210
900 1000

Sample Output

sample.out
1 10 20
100 200 125
201 210 89
900 1000 174

Pitfalls


錯誤歷程

  1. AC一次直接過#1

See also

  • 考拉茲猜想（Collatz conjecture）