这道题目的关键在于怎么求两个整数的最大公约数,这里正好复习一下以前的知识,如下:
1.设整数a和b
2.如果a和b都为0,则二者的最大公约数不存在
3.如果a或b等于0,则二者的最大公约数为非0的一个
4.如果b不为0,则使得a=a,b=a%b,转到2重复执行
实现的递归代码如下:
int gcb(int a,int b)
{
if(b==)
return a;
else
return gcb(b,a%b);
}
注:这个算法的证明这里简单说明下:
1.设g为a和b的公约数
2.则存在m和k使得 a=g*m b=g*k
3.同时利用b可表示a a=b*l+r (其中r为余数)
4.合并2、3中的两个式子得出 r=g*(m-l*k) (g!=0)
5.可看出a和b的公约数同时也是b和a%b(取余)的公约数
6.利用反证法我们可以得出结论:如果g是a和b的最大公约数则它也是b和a%b的最大公约数
这样就有了如上算法
这道题目的核心就是这些同时注意运用一些常识:
1.两个偶数不可能互质
2.两个差为1的整数一定互质
见ac代码:
#include <stdio.h>
#include <math.h> int c(int n)
{
return n*(n-)/;
} int gcb(int a,int b)
{
if(b==)
return a;
else
return gcb(b,a%b);
} int myabs(int a)
{
return a<?-a:a;
} int main()
{
int n,num[];
while(scanf("%d",&n)!=EOF&&n)
{
int i,j;
for(i=;i<n;i++)
scanf("%d",&num[i]);
double pairs=double(c(n)); double ncf=;
for(i=;i<n;i++)
{
for(j=i+;j<n;j++)
{
if(num[i]%==&&num[j]%==)
continue;
else if(myabs(num[i]-num[j])==)
{
ncf++;
continue;
}
else
{
if(gcb(num[i],num[j])==)
ncf++;
}
}
} if(ncf==)
printf("No estimate for this data set.\n");
else
printf("%.6lf\n",sqrt(/ncf*pairs));
} return ;
}