b553 - 4.Collatz 問題

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定正整數 n (2 <= n <= 30000) 經過 Collatz 轉換後，達到 1 需要的步驟數。Collatz 轉換規則如下：如果 n 是偶數，則 n 除以 2；如果 n 是奇數，則 n 乘以 3 加 1。

解題思路

此題的解題思路是直接模擬 Collatz 轉換的過程。使用一個 while 迴圈，只要 n 不等於 1，就根據 n 的奇偶性進行相應的轉換，並記錄轉換的次數。迴圈終止時，記錄的次數就是答案。

複雜度分析

• 時間複雜度: O(n)，在最壞情況下，Collatz 序列可能需要多次迭代才能達到 1。雖然 Collatz 猜想尚未被證明，但對於給定的輸入範圍 (2 <= n <= 30000)，迭代次數不會過多。
• 空間複雜度: O(1)，程式只使用了幾個整數變數，空間使用是常數級別。

程式碼

#include <iostream>
using namespace std;
int main(){
	int a,i;
	while(cin >> a){
		i=0;
		while(a!=1){
			if(a%2==0){
				a/=2;
				i++;
			}
			else if(a%2==1){
				a=a*3+1;
				i++;
			}
		}
		cout << i << endl;
	}
}