马上要参加多益的笔试了,所以在网上找了一下多益的笔试题 原文
我感觉我想出了一个更简单的方法(时间复杂度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)),主要是数学推导,这里就不写代码了。