文档章节

蓝桥杯 最大比例

李韬_varyshare
 李韬_varyshare
发布于 2017/04/05 11:44
字数 1186
阅读 182
收藏 0

题目描述 

最大比例

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

再例如,输入:

4

3125 32 32 200

程序应该输出:

5/2

再例如,输入:

3

549755813888 524288 2

程序应该输出:

4/1 

思路:

这道题目的是想求等比数列的这个公比最大是多少,既然要求公比的话直接将这个数列任意两个数相除必定是公比的k次方。

所以第一步需要将所有的数都互相除一遍,把所有的公比的k次方求出来,然后再找最小的。怎么找最小的?这个道理很简单,公比是需要所有数都可以整除它,你如果不找最小的那么有些数肯定是整除不了的。但是找到这些整除后的数最小的后还是不一定可以确定公比就是它。 

看到这里可能会有点思路但是还是云里雾里,那么举个列子吧。

题目中输入数据:3125 32 32 200

  1. 将所有数互相整除,获得整除后的结果集合。

3125除32=3125/32
3125除200=125/8
32除32=1/1
32除200=25/4

当然1/1这个不算,整除后数列最小是25/4.那么最终的公比是25/4了吗?当然不是。

等比数列公式Ai=kq^i;所以Ai/Aj=(q^i)/(q^j);而(q^i)/(q^j)=q^m。所以25/4目前只能算是q^m,我们要求公比q。

q可以看做q^1,所以在整除后数列中应该所有数都是公比q的整数次方。

上面这句话用程序怎么表示?下面是伪代码:意思就是x可以一直除公比q直到x=1。如果最后得到x不是1那么证明x不是q的整数次方。比如:9和27的关系,9显然不是27的公比,因为27/9=3,最后的结果不是1。而3和9,9/3/3=1所以3是9的公比。

我们假设的公比25/4不是公比那么怎么求呢?上面这段话给了提示,27/9=3.  9不是公比但是3是啊。所以若最后x不等于1那么x就是公比,我们要更新假设的公比。

int x=25/4;

while(x>q){

   x=x/q;

}

if(x==1)

print("x是q的整数次方");

具体代码


import java.math.BigInteger;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
//用于保存一个分数避免出现除不断情况
class fenshu {
	public BigInteger top;
	public BigInteger below;

	fenshu() {
	}

	fenshu(BigInteger top, BigInteger below) {
		this.top = top;
		this.below = below;
	}
}

public class XMax {
//求最大公约数
	public static BigInteger f(BigInteger a, BigInteger b) {
		if (a.signum() == 0)
			return b;
		return f(b.mod(a), a);
	}
//假设的公比的分子
	public static BigInteger mintop = new BigInteger("1000000000000");
//假设公比的分母
	public static BigInteger minbelow = new BigInteger("1000000000000");
//最小的分子
	public static BigInteger tempmintop;
//保存奖金数值
	public static BigInteger[] digit;
	public static int n;
	public static BigInteger temp;
//保存整除后的数列
	public static Set<fenshu> set = new LinkedHashSet<>();

	public static void fmin(int step) {
		if (step >= n)
			return;
		for (int i = step + 1; i < n; i++) {
			temp = f(digit[step], digit[i]);
			boolean flag = true;
			fenshu t = new fenshu();
			if (digit[step].compareTo(digit[i]) > 0) {
				t.top = tempmintop = digit[step].divide(temp);
				t.below = digit[i].divide(temp);
			} else {
				t.top = tempmintop = digit[i].divide(temp);
				t.below = digit[step].divide(temp);
				flag = false;
			}
			set.add(t);
			if (!tempmintop.equals(BigInteger.ONE)
					&& tempmintop.compareTo(mintop) < 0) {
				mintop = tempmintop;
				if (flag)
					minbelow = digit[i].divide(temp);
				else
					minbelow = digit[step].divide(temp);
			}
		}
		fmin(step + 1);
	}

	public static void main(String[] args) {
		digit = new BigInteger[] { new BigInteger("549755813888"),
				new BigInteger("524288"), new BigInteger("2") };
		n = digit.length;
		fmin(0);//计算出不同两位数相除得到的商,这些商可能存在公比
		Iterator iter = set.iterator();
		fenshu t = new fenshu();
		while (iter.hasNext()) {
			t = (fenshu) iter.next();
			while (t.top.compareTo(mintop) > 0) {
				t.top = t.top.divide(mintop);
				t.below = t.below.divide(minbelow);
			}
//如果等于1证明能整除,如果不等于1证明mintop/minbelow还不够小,目前的t.top/t.below更小更适合。
			if (!t.top.equals(BigInteger.ONE)) {
				mintop = t.top;
				minbelow = t.below;
			}
		}
		System.out.println(mintop + "/" + minbelow);
	}
}

 

© 著作权归作者所有

李韬_varyshare

李韬_varyshare

粉丝 7
博文 27
码字总数 18588
作品 1
广州
个人站长
私信 提问
蓝桥杯,你怎么看???

蓝桥杯又要报名了,各位大boss们怎么看待蓝桥杯~~~

嘚瑟的小孩
2016/11/29
581
7
我算不算一个程序员

小弟目前大二,主要学习C#(但是我不太喜欢,所以就学的一般),根据学校安排的课程的话最多学完基础,我个人喜欢PHP,从开始学习到目前大约3个月,能够进行基础模块的制作(BBS,在线聊天室...

我是一只小小鸟001
2017/03/21
288
3
【蓝桥杯】2019第十届蓝桥杯B组C++年号字串

小明用字母A 对应数字1,B 对应2,以此类推,用Z 对应26。对于27 以上的数字,小明用两位或更长位的字符串来对应,例如AA 对应27,AB 对 应28,AZ 对应52,LQ 对应329。 请问2019 对应的字符...

Debug客栈
03/27
0
0
请问有没有上学时参加过蓝桥杯的啊。。

学校组织报名蓝桥杯。我报了c++组。想假期时准备准备。但不知到该准备什么?有没有上学时参加过的过来人啊。恳请指点指点。多谢多谢。

solopiggy
2013/01/15
285
2
2019年第十届蓝桥杯B组C++省赛手记

这已经是第二次参加蓝桥杯大赛,之前参加蓝桥杯团队赛项只拿到了国家三等奖(安慰奖),上年编程成绩也是甚不理想,今年吃了上一年的亏,准备了许久,虽然是做的比较基础,但是收获了不少。大...

Debug客栈
03/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

好程序员大数据教程Scala系列之样例类_Option_偏函数

  好程序员大数据教程Scala系列之样例类_Option_偏函数,在Scala中Option类型样例类用来表示可能存在或也可能不存在的值(Option的子类有Some和None)。Some包装了某个值,None表示没有值。 ...

好程序员官网
29分钟前
4
0
zk中ServerCnxnFactory连接管理工厂

作为ServerCnxn的工厂抽象类 属性 ZOOKEEPER_SERVER_CNXN_FACTORY zookeeper.serverCnxnFactory secure 在ServerCnxnFactory中SSL是否启用 sessionMap session管理配置中信息(sessionId,Ser......

writeademo
30分钟前
6
0
【代码审计01】几种常见的漏洞种类以及代码审计工具

前言 代码审计是在经过黑盒测试完毕,也就是检查应用的基本功能是否符合产品业务需求下进行的。需要有一定的编码基础以及对漏洞形成原理的基本认知,通过工具或者经验检测代码中可能出现的b...

北桥苏
31分钟前
5
0
重磅发布 | 全球首个云原生应用标准定义与架构模型 OAM 正式开源

作者: OAM 项目负责人 导读:2019 年 10 月 17 日,阿里巴巴合伙人、阿里云智能基础产品事业部总经理蒋江伟(花名:小邪)在 Qcon 上海重磅宣布,阿里云与微软联合推出开放应用模型 Open A...

阿里巴巴云原生
33分钟前
4
0
【进阶之定义函数】一个查询树结构数据的集合

1、基本定义 delimiter 自定义符号  -- 如果函数体只有一条语句, begin和end可以省略, 同时delimiter也可以省略create function 函数名(形参列表) returns 返回类型  -- 注意是retru...

卯金刀GG
39分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部