c087 - 00412 - Pi

🔗 前往 ZeroJudge 原題

題目描述

題目要求根據給定的整數集合，估算 Pi 的值。估算方法是計算集合中所有可能的數對中，互質數對的比例，並根據公式 sqrt(((m*(m-1))/2)*6/count) 計算 Pi 的估計值，其中 m 是集合中元素的數量，count 是互質數對的數量。如果集合中沒有互質數對，則輸出 "No estimate for this data set."。

解題思路

解題思路是首先讀取輸入的整數集合。然後，遍歷所有可能的數對，計算每對數的最大公約數 (GCD)。如果 GCD 為 1，則表示該數對互質，計數器 count 增加。最後，根據公式計算 Pi 的估計值，並輸出結果，保留小數點後 6 位。如果 count 為 0，則輸出 "No estimate for this data set."。GCD 的計算使用遞迴方式實現。

複雜度分析

• 時間複雜度: O(n^2 * log(max_value))，其中 n 是集合中元素的數量，max_value 是集合中最大值的範圍。外層迴圈遍歷 n*(n-1)/2 對數，內層計算 GCD 的時間複雜度為 O(log(max_value))。
• 空間複雜度: O(n)，用於儲存輸入的整數集合。

程式碼

#include <stdio.h>
#include <math.h>
int GCD(int x,int y){
	if(x%y==0)
		return y;
	else
		return GCD(y,x%y);
} 
int main(){
	int n,i,j;
	float m,count;
	while(scanf("%d",&n)>0){
		int a[n];
		if(n!=0){
			for(i=0;i<n;i++)
				scanf("%d",&a[i]);
			for(i=0,count=0;i<n;i++){
				for(j=i+1;j<n;j++)
					if(GCD(a[i],a[j])==1) count++;
			}
			m=n;
			if(count==0)
				printf("No estimate for this data set.\n");
			else
				printf("%.6f\n",sqrt(((m*(m-1))/2)*6/count));
		}
	}
}