c002 - 10696 - f91

🔗 前往 ZeroJudge 原題

題目描述

題目定義了一個遞迴函數 f91(N)，如果 N 小於等於 100，則 f91(N) = f91(f91(N+11))，否則 f91(N) = N-10。題目要求計算給定正整數 N 的 f91(N) 值。

解題思路

這題的核心在於理解遞迴的終止條件和遞迴的過程。由於 N <= 100 時的遞迴呼叫，我們可以觀察到 f91(N) 的值最終會收斂到 91。當 N > 100 時，f91(N) = N - 10。因此，我們可以利用這個特性來簡化計算。

對於 N <= 100 的情況，f91(N) = f91(f91(N+11))。由於 N+11 > 100，所以 f91(N+11) = (N+11) - 10 = N+1。因此，f91(N) = f91(N+1)。 繼續遞迴，直到 N > 100，此時 f91(N) = N - 10。

實際上，可以發現 f91(N) 在 N <= 100 的情況下，最終會計算出 f91(101) = 101 - 10 = 91。

複雜度分析

• 時間複雜度: O(N)
• 空間複雜度: O(N)

程式碼

#include <stdio.h>
int f91(int N){
	if(N<=100)
		return f91(f91(N+11));
	return N-10; 
}
int main(){
	int a;
	while(scanf("%d",&a)!=EOF){
		if(a==0)
			break;
		printf("f91(%d) = %d\n",a,f91(a));
	}
}