d420 - 00694 - The Collatz Sequence

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算 Collatz 數列的長度，直到數列達到 1 或超出給定的上限。Collatz 數列的規則是：如果數列當前項為偶數，則除以 2；如果為奇數，則乘以 3 加 1。

解題思路

使用遞迴函數 step 來模擬 Collatz 數列的生成過程。遞迴函數接收三個參數：當前數列項 a、上限 l 和當前項數 n。如果 a 等於 1，則返回 n，表示數列的長度。如果 a 為偶數，則遞迴調用 step 函數，將 a 除以 2，並將項數 n 加 1。如果 a 為奇數，則檢查 3*a+1 是否超出上限 l，如果超出，則返回 n；否則，遞迴調用 step 函數，將 a 更新為 3*a+1，並將項數 n 加 1。主函數讀取多組輸入，每組輸入包含首項 a 和上限 l，然後調用 step 函數計算數列的長度，並輸出結果。

複雜度分析

• 時間複雜度: O(n)，其中 n 是 Collatz 數列的長度。在最壞的情況下，數列可能需要多次迭代才能達到 1 或超出上限。
• 空間複雜度: O(n)，由於使用了遞迴，遞迴深度最大為 n，因此空間複雜度為 O(n)。

程式碼

#include <iostream>
using namespace std;
long long int step(long long int a,long long int l,long long int n){
	if(a==1){
		return n;
	}
	else if(a%2==0)
		return step(a/2,l,n+1);
	else{
		if(a*3+1>l)
			return n;
		return step(3*a+1,l,n+1);
	}
}
int main(){
	int a,l,i=1;
	while(cin >> a >> l){
		if(a<0&&l<0)break;
		cout << "Case " << i++ << ": A = " << a << ", limit = " << l << ", number of terms = " << step(a,l,1) << "\n";
	}
}