多益网络校招笔试题

2023-10-27

马上要参加多益的笔试了,所以在网上找了一下多益的笔试题  原文

我感觉我想出了一个更简单的方法(时间复杂度O(1)),如果有问题希望大家及时指正。

题目如下:

给定一个数x(x>5),找到该数与3、4之间的关系。

关系如下:x=3*n+4*m,然后找到|n-m|的最小值。(应该规定了m,n,x都为正整数)

其中:6=3*2+4*0

7=3*1+4*1

8=3*0+4*2

9=3*3+4*0

分析:假如x=3*n+4*m,且n-m=y(y>0)(n和m是其中的一个解,但不一定是最优解)。我们此时的目的就是让y尽可能的小,要让y减小必须减小n,增大m。n每次减小至少要减4,同时让m加3才能让等式继续成立(假设n减少k,m增加s,必须让3k=4s,等式才能继续成立,最小整数解:k=4,s=3)

改变之后的差值(>0)为(n-4)-(m+3)=y-7 或者(m+3)-(n-4)=7-y

若y大于7可以一直执行此操作直到y<7,再执行一次结果就变成了7-y,在y和7-y中找一个最小值就是答案了,由此可知最优解<=3,且无法再优化。

若x%7==0     |n-m|的最小值为0(3和4的个数一样)

x%7==1     |n-m|的最小值为2(4比3多2个)

x%7==2     |n-m|的最小值为3(3比4多3个)

x%7==3     |n-m|的最小值为1(3比4多1个)

x%7==4     |n-m|的最小值为1(4比3多1个)

x%7==5     |n-m|的最小值为3(4比3多3个)

x%7==6     |n-m|的最小值为2(3比4多2个)

(如果不容易想到的话可以拿具体值进行计算,只要结果<=3即是最优解)

上面的结果都是最优解且无法继续优化,所以上面的结果就是最小值。

代码只用判断x%7等于几并输出对应答案就行,时间复杂度(O(1)),主要是数学推导,这里就不写代码了。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

多益网络校招笔试题 的相关文章

随机推荐