412 - Pi
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=353
Professor Robert A. J. Matthews of the Applied Mathematics and Computer Science Department at the University of Aston in Birmingham, England has recently described howthe positions of stars across the night skymay be
used to deduce a surprisingly accurate value of. This result followed from the application of certain theorems in number theory.
Here, we don'thave the night sky, but can use the same theoretical basis to form an estimate for:
Given any pair of whole numbers chosen from a large, random collection of numbers, the probability that the twonumbers have no common factor other than one (1) is
For example, using thesmallcollection of numbers: 2, 3, 4, 5, 6; there are 10 pairs that can be formed: (2,3), (2,4), etc. Six of the 10 pairs: (2,3), (2,5), (3,4), (3,5), (4,5) and (5,6) have no common factor
other than one. Using the ratio of the counts as the probability we have:
In this problem, you'll receive a series of data sets. Each data set contains a set of pseudo-random positive integers. For each data set, find the portion of the pairs which may be formed that have nocommon factor
other than one (1), and use the method illustrated above to obtain an estimate for. Report this estimate for each data set.
Input
The input consists of a series of data sets.
The first line of each data set contains a positive integer value,N, greater than one (1) and less than 50.
There is one positive integer per line for the nextNlines that constitute the set for which the pairs are to be examined. These integers are each greater than 0 and less than 32768.
Each integer of the input stream has its first digit as the first character on the input line.
The set size designator,N, will be zero to indicate the end of data.
Output
A line with a single real value is to be emitted for each input data set encountered. This value is the estimate forfor
the data set. An output format like the sample below should be used. Answers must be rounded to six digits after the decimal point.
For some data sets, it may be impossible to estimate a value for. This occurs when there
arenopairs without common factors. In these cases, emit the single-line message:
No estimate for this data set.
exactly, starting with the first character,"N", as the first character on the line.
Sample Input
5
2
3
4
5
6
2
13
39
0
3.162278
No estimate for this data set.
完整代码:
/*0.109s*/
#include<cstdio>
#include<cmath>
int a[55];
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int n, count, i, j;
while (scanf("%d", &n), n)
{
count = 0;
for (i = 0; i < n; ++i)
scanf("%d", &a[i]);
for (i = 0; i < n - 1; ++i)
for (j = i + 1; j < n; ++j)
if (gcd(a[i], a[j]) == 1) ++count;
if (count) printf("%.6f\n", sqrt(3.0 * n * (n - 1) / count));
else puts("No estimate for this data set.");
}
return 0;
}
分享到:
相关推荐
title: Maximum GCD(最大公约数)categories: [算法题解]传送门:UVA 11827 - Maximum GCD题目大意:给你几组数
uva272
UVA109的题解,经测试完全正确,还附有题解。
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
uva最全ac代码
uva10755 ac 代码,可以随意更改下载
uva357的栈实现版本
UVA 题目,不是很难,试试吧
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
《算法竞赛入门经典》UVa配套题目pdf版完整
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
uva_trilearn2002 源代码
主要是uvaoj习题相关题目 练习题目
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)
PDF试题