d859 - NOIP2001 1.数的计算

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算滿足特定條件的數的個數。給定一個自然數 n，可以通過在它的左邊添加一個小於或等於 n/2 的自然數來擴展這個數。這個過程可以重複進行，直到無法再添加任何自然數。題目要求計算所有可能的擴展數的個數，包括原始數字 n 本身。

解題思路

這道題可以使用深度優先搜尋 (DFS) 或遞迴的方式來解決。遞迴函數 dfs(n) 的作用是計算以 n 為根的樹的節點數量。在每次遞迴中，我們嘗試在 n 的左邊添加一個小於或等於 n/2 的自然數 i，然後遞迴地計算以 i 為根的樹的節點數量。遞迴的終止條件是 n 等於 0。

複雜度分析

• 時間複雜度: O(n^2)
• 空間複雜度: O(n)

程式碼

#include <stdio.h>
int ans=1;
void dfs(int n){
	n>>=1;
	for(int i=1;i<=n;i++){
		ans++;
		dfs(i);
	}
}
int main(){
	int a;
	scanf("%d",&a);
	dfs(a);
	printf("%d",ans);
}