本文共 1995 字，大约阅读时间需要 6 分钟。
X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。比如：16,24,36,54 —— 其等比值为：3/2。 现在，我们随机调查了一些获奖者的奖金数。 请你据此推算可能的最大的等比值。输入格式：
第一行为数字 N (0<N<100)，表示接下的一行包含N个正整数 第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额要求输出：
一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数测试数据保证了输入格式正确，并且最大比例是存在的。 例如，输入：
3 1250 200 32 程序应该输出： 25/4思考：
①首先程序要接收一个数字N，然后再接收N个数字，这N个数字应该是存在数组中的。考虑到N的不确定性(0<N<100)，我们当然可以建立一个大小为100个int的数组，但既然学过vector，索性就建立一个vector向量吧，这是第一步；
②怎样能得到这个比例呢？题目中给出了其中的N个奖金数，将这N个奖金数进行排序，排序后有一点要注意的是：对数组进行去重操作！因为这N个奖金数是随机采访得到的，你不能保证没有同一级别的奖金吧！然后从第二项开始，除以前面的奖金数，最终得到的那个最小的数字，应该就是可能的比例系数；
③这个题目又要求输出分数，这怎么做呢？这时我们应该注意到，上面第二步，如果做简单的相除运算得到的是整数啊！所以这里要找出两个数的最大公约数，两个数分别除最大公约数得到分母分子，最后输出的时候加个/就好了；
④好了，分数知道该怎么表示了，但这些分数的大小又怎么比较呢？这里不用考虑这么复杂。我们可以把所有的分母放在一个数组中，所有的分子防在一个数组中，两个数组相同下标的值取出来就是一个比例分数。该题中，计算出来的所有分数一定是奖金比例的某次方，因此，找到所有分数都是基于哪个数的某次方就好啦（表述不清楚qwq，事实上我认为这段代码也是最难理解的qwq）。
#include#include using namespace std;long long gcd(long long a, long long b) //辗转相除法求a和b的最大公约数{ return b ? gcd(b, a%b) : a;}long long qgcd(long long a, long long b){ if (a == b) { return a; } else { return qgcd(min(b/a, a), max(b/a, a)); }}int main(){ long long a[105], b[105], x[105], N; cin >> N; for (int i = 1; i <= N; ++i) //注意：这里是从1开始给数组x[]赋值的！ { cin >> x[i]; } sort(x+1, x+1+N); //排序 //数组去重 for (int i = 1; i <= N; ++i) { if (x[i] == x[i-1]) { for (int j = i; j <= N; ++j) { x[j] = x[j+1]; } N -= 1; } } //对数组中的数挨个计算比例 for (int i = 2; i <= N; ++i) { a[i] = x[i]; b[i] = x[i-1]; int p = gcd(a[i], b[i]); //p是x[i]和x[i-1]的最大公约数 a[i] /= p; //a[i]存放分子 b[i] /= p; //b[i]存放分母 } int A = a[2], B = b[2]; //第一个分母分子就是从下标为2的地方开始储存的 for (int i = 3; i <= N; ++i) { A = qgcd(A, a[i]); B = qgcd(B, b[i]); } cout << A << '/' << B << endl; return 0;}
1、求最大公约数
通过求最大公约数可以得到一个数与另一个数的比值！
发现原来写过求最大公约数的博客了 →
2、除法如何得到小数
整数除法得到的是一个整数，后面的小数位会直接被舍去。如果想得到小数的话，先要将int型变量转换为double型变量，再进行除法。如果规定输出保留多少位小数，则用cout << setprecision(2) << fixed << ……;其中2表示保留两位小数，要注意seprecision函数的使用要搭配<iomanip>头文件。
转载地址：http://xvtai.baihongyu.com/