本文主要是介绍蓝桥杯最大比例java实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最大比例X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。比如：
16,24,36,54
其等比值为：3/2
现在，我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。
输入格式：
第一行为数字N(N < 100)，表示接下的一行包含N个正整数
第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额
要求输出：
一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数
测试数据保证了输入格式正确，并且最大比例是存在的。
例如，输入：
3
1250 200 32
程序应该输出：
25/4
再例如，输入：
4
3125 32 32 200
程序应该输出：
5/2
再例如，输入：
3
549755813888 524288 2
程序应该输出：
4/1
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms
需要知识：
1.辗转相除法：
static long gcd(long a, long b) {return b == 0 ? a : gcd(b, a%b);}
2.更相减损法：
static long check(long a, long b) {while (a != b) {// 保证 a > bif (a < b) {long temp = a;a = b;b = temp;}long temp = a / b;a = b;b = temp;}return a;} 补充：等比数列是等比相等
题目思路：
先把输入的数用优先队列存，或者排序，目的是把数按 由小到大 的顺序处理。
依次处理队列中两个相邻的数 a1 a2，a2 a3, a3 a4......
假设最大比例系数为 b ，则 a2 / a1 = b^n1，a3 / a2 = b^n2， a4 / a3 = b^n3......。
要求的是 等比数列 中的最大比例系数，
若 n1 n2 n3 n4......的最大公因数为n，则解最大比例系数为 b^n 。
那么怎么求出 b^n 呢？
此时 b 未知，n1 n2 n3....也为未知，
但是 已知 b^n1 b^n2 b^n3...，且他们有相同的底数，则 b^n2 / b^n1 = b^(n2-n1)
所以可以通过 更相减损法 两两求 b^n1 b^n2， b^n2 b^n3...中最大公因数 n 时的 b^n。
例如： 2^4 = 16 2^6 = 64
2^6 / 2^4 = 2^2 -> 6 - 4 = 2
2^4 / 2^2 = 2^2 -> 4 - 2 = 2（减数和差相等，结束）
结果为 2^2 = 4。
完整代码：
package test;import java.util.*;/*** LQ 最大比例* Created by jingtao on 2017/2/20.*/
public class Main {// 辗转相除static long gcd(long a, long b) {return b == 0 ? a : gcd(b, a%b);}// 相减static long check(long a, long b) {while (a != b) {// 保证 a > bif (a < b) {long temp = a;a = b;b = temp;}long temp = a / b;a = b;b = temp;}return a;}static long[] arr;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();arr = new long[n];Queue<Long> queue = new PriorityQueue<>((o1,o2) -> o1 > o2 ? 1 : -1);for (int i = 0; i < n; i++) {queue.add(scanner.nextLong());}long a = 1, b = 1; // 分别保存分子，分母boolean first = true;long left = queue.poll();while (!queue.isEmpty()) {long right = queue.poll();// 输入会有相等的数，所以队列中两数相等时跳过if (left != right) {// 后一个数除前一个数，并进行约分long temp = gcd(right, left);long nexta = right / temp;long nextb = left / temp;if (first) {a = nexta;b = nextb;left = right;first = false;continue;}a = check(a, nexta);b = check(b, nextb);}// 向右滑动队列left = right;}System.out.println(a + "/" + b);}
}
这篇关于蓝桥杯最大比例java实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
