e357 - 遞迴函數練習

🔗 前往 ZeroJudge 原題

題目描述

題目定義了一個遞迴函數 F(x)，根據 x 的值，函數的計算方式有三種情況：如果 x 等於 1，則 F(x) 等於 1；如果 x 是偶數，則 F(x) 等於 F(x/2)；否則，F(x) 等於 F(x - 1) + F(x + 1)。題目要求輸入一個正整數 x，並輸出 F(x) 的值。

解題思路

這題的核心在於理解遞迴的定義並正確地實現它。函數 fun(x) 模擬了題目中描述的 F(x) 函數。基本情況是 x == 1，此時返回 1。如果 x 是偶數，則遞迴調用 fun(x/2)。如果 x 是奇數，則遞迴調用 fun(x-1) 和 fun(x+1)，並將結果相加。主函數 main() 讀取輸入的 x 值，調用 fun(x) 計算結果，並輸出結果。由於題目沒有限制輸入數量，因此使用 while(cin >> x) 迴圈來處理多個輸入。

複雜度分析

• 時間複雜度: O(2^n) 在最壞情況下，例如 x 為奇數時，每次遞迴都會產生兩個新的遞迴呼叫，導致指數級的時間複雜度。
• 空間複雜度: O(n) 由於遞迴調用的堆疊，空間複雜度與遞迴深度成正比，最壞情況下遞迴深度為 n。

程式碼

#include <iostream>

using namespace std;

int fun(int x){
	if(x==1){
		return 1;
	}
	else if(x%2==0){
		return fun(x/2);
	}
	else {
		return fun(x+1)+fun(x-1);
	}
}

int main(){
	int x=0;
	while(cin >> x){
		cout << fun(x);
	}
	return 0;
}