g256 - 考拉茲猜想

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算對於給定的正整數 n，依照考拉茲猜想的規則（奇數乘以 3 加 1，偶數除以 2）運算，直到 n 變成 1 需要多少次迭代。輸入為多個正整數，直到輸入結束。

解題思路

此題的解題思路非常直接，就是根據考拉茲猜想的規則進行模擬。對於每個輸入的 n，我們進入一個迴圈，判斷 n 是奇數還是偶數，如果是奇數則執行 n = n * 3 + 1，如果是偶數則執行 n = n / 2。每次迭代都將計數器 ans 加 1。迴圈持續進行，直到 n 等於 1。最後輸出 ans 的值。由於題目限制 n 的範圍不大 (n <= 10^6)，因此這種模擬方法是可行的。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入的數字。在最壞的情況下，考拉茲猜想的序列可能很長，需要多次迭代才能達到 1。
• 空間複雜度: O(1)，因為我們只使用了幾個變數來儲存 n 和計數器 ans，空間使用是固定的。

程式碼

#include <iostream>
using namespace std;
long long n;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> n){
		long long ans=0;
		while(n!=1){
			if(n%2)
				n=n*3+1;
			else
				n/=2;
			++ans; 
		}
		cout << ans << "\n";
	}
}