算法-搜狗的一道算法笔试题

算法-搜狗的一道算法笔试题

甜柠檬 发布于 2016-11-25 字数 191 浏览 1170 回复 6

有两个数,A和B,六种操作分别是+12,-12,+7,-7,+5,-5。A经过若干次操作,变成B 是输入任意2个数A和B,要给出变换过程,这其中的操作序列就是一个路径,也就是最少的操作次数 。给出思路和代码

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(6

瑾兮 2017-10-02 6 楼

第一眼:扩展欧几里得算法。
第二眼:枚举情况,常数解决。
三种情况:
A(+12)+B(+7)=C
A(+12)+B(+5)=C
A(+7)+B(-5)=C
其中A>=0, B>=0,并且:
情况一、二中:B<12,情况三中B<7。原因就不必说了吧。:)

在前两种情况中,先算出C对12的余数,这样就能算出B,进而求出A。在第三种情况中类似。

所以总的时间复杂度还是O(1)的。

想挽留 2017-09-18 5 楼

典型的资源搜索算法中的双向Chord算法,建议你可以去看一看

泛泛之交 2017-05-31 4 楼

这个是公约数的变形吧

因为 无论做什么操作都是从这几种操作出发

通过分析可以得出

A+12-7=A+5
所以 如果组合中有12 和7的 完全可以用5代替
而A+12-5=A+7同上 完全可以用7代替
A-12-7=A-19
A+12+7=A+19
A-12-5=A-17
A+12+5=A+17
A-7+5 =A-2
A+7-5 = A+2
可以得到一个序列 -19,-17,-12,-7,-5,-2,2,5,7,12,17,19
然后给出A 和B 相减得到他们的差

然后 选取数字 进行相加 把上面的序列当成数 这里我们只做加法

如果a b相减是个数n 那个查找到离这个n 然后让离他最近的 与数组中的其他数相加得0
例如 a=1 b=8 得到 1-8=-7
找到-7离-7最近 那么 ok 找到7然后就是 1-8=-7
1+7-8=0
1+7=8

在用这种方法做一个 a=13 b=46

13-46= -33
13+33-46=0
13+33=46
所以要求的那个数就是33
如何得到33
离他最近的是19
所以可以看下19+17 =36貌似有点大
那么17丢弃 19+12=31 33-31刚好为2 数组中有2
所以最好的策略就是 19+12+2那么就是 a+12+7+12+2=b

思想是这样的 代码就算了
明天还要上班 恕不能给出代码 你可以自己试着写写

归属感 2017-05-16 3 楼

问题等效于:
求m,n,k使得
7m + 5n + 12k = B-A
使得|m|+|n|+|k|最小。

首先因为12 = 5 + 7,因此有:
7(m+k)+5(n+k) = B-A
设M = m + k, N = n + k
化成一个标准的不定方程

这个不定方程的解集有固定的算法。
首先:
3 * 7 + (-4) * 5 = 1
(可以证明不仅是5和7,任意两个互质的数都可以找到这样一种线性组合使得和为1,这个在数学上称为中国剩余定理)
因此
M = 3*(B-A)
N = -4*(B-A)

是一个可行的解。
对于另一个解M1, N1来说:
7M1 + 5N1 = 7M + 5N
因此
7(M1-M) = 5(N-N1)
设7(M1-M) = 5(N-N1) = V
V % 5 = 0, V % 7 = 0, 因此V是35的倍数,设V = 35 * t
M1 - M = 5*t, N - N1 = 7*t
因此
M1 = M + 5*t
N1 = N - 7*t

结合起来可以得到所有解的表达式:
m + k = 3*(B-A) + 5*t
n + k = -4*(B-A) - 7*t

不妨设B >= A(B<A的时候只要交换A和B就行了),按照t的范围分段讨论:
1.t <= -3*(B-A)/5
2.-3*(B-A)/5 < t < -4*(B-A)/7
3.t >= -4*(B-A)/7

(1) 此时有m + k <= 0, n + k > 0
|n| + |m| + |k| >= |n| + |m| >= n - m = (n+k)-(m+k) = -7*(B-A)-12*t,取极值条件为t = floor(-3*(B-A)/5),k=0
极值为-7*(B-A) - 12*floor(-3*(B-A)/5)
(2) 此时有m + k > 0, n + k > 0

|m| + |n| + |k| >= |m+k| + |n| >= |m+k| = 3*(B-A) + 5*t
|m| + |n| + |k| >= |n+k| + |m| >= |n+k| = -4*(B-A) - 7*t

因此3*(B-A) + 5*t < -4*(B-A) - 7*t,即t < -7*(B-A)/12时,
最小值为-4*(B-A) - 7*t,条件为m = 0(此时有n>0);
进一步t = floor(-7*(B-A)/12)时有极值
-4*(B-A) -7*floor(-7*(B-A)/12) >= (B-A)/12
但必须满足floor(-7*(B-A)/12)>-3*(B-A)/5,否则这个区间里没有符合条件的整数t。

t >= -7*(B-A)/12时,
最小值为3*(B-A) + 5*t,条件为n = 0(此时有m>=0);进一步t = ceil(-7*(B-A)/12)时有极值
3*(B-A) + 5*ceil(-7*(B-A)/12) >= (B-A)/12
必须满足ceil(-7*(B-A)/12) < -4*(B-A)/7,否则区间里没有符合条件的整数t。

(3) 此时有m + k > 0, n + k < 0
|m| + |n| + |k| >= |m| + |n| >= m - n = (m+k) - (n+k) = 7*(B-A) + 12*t
t = ceil(-4*(B-A)/7)时有极值
7*(B-A) + 12*ceil(-4*(B-A)/7)
k = 0时等号成立

总结:最后求得的m,n,k为以下四种情况中使得f最小的
(1) t = floor(-3*(B-A)/5), f = -7*(B-A)-12*t, m = 3*(B-A) + 5*t, n = -4*(B-A) - 7*t, k = 0
(2) t = floor(-7*(B-A)/12)且满足5*t>-3*(B-A)f = -4*(B-A) - 7*t, m = 0, k = 3*(B-A) + 5*t, n = -7*(B-A) - 12*t
(3) t = ceil(-7*(B-A)/12)且满足7*t<-4*(B-A)f = 3*(B-A) + 5*t, n = 0, k = -4*(B-A) - 7*t, m = 7*(B-A) + 12*t
(4) t = ceil(-4*(B-A)/7)f = 7*(B-A) + 12*t, k = 0, m = 3*(B-A) + 5*t, n = -4*(B-A) - 7*t

例如:B-A=33时
(1) t = -20, f = 9
(2) t = -20, 不满足条件
(3) t = -19, f = 4
(4) t = -18, f = 15
因此t = -19时有最佳解,解为:n = 0, k = 1, m = 3
即+7 +7 +7 + 12

代码明天有空的话补上

甜柠檬 2016-12-19 2 楼

在结果树空间进行搜索,相信题目的原意也如此。那么我们主要的任务就在搜索算法的考虑上了(剪枝)。在有限的操作集O(+12,-12,+7,-7,+5,-5)上,每一个节点的可对应固定数量的子节点数。例如A=0,那么就有:

A=0 ------------------------------------根节点
+12 -12 +7 -7 +5 -5 ------------------------子节点
....

而B就可能在子孙节点中产生。
我们的限定条件是路径最短,那么在我们的子孙节点中,假如出现了祖先节点中已经出现过的值,这个节点基本就可以排除掉了。结果集中最先出现与B值相等的节点当然就是我们所需要的结果。而一旦我们计算过程中,所有的子节点都被咔嚓掉了,也就说明从A到B不可到达的。
经过以上分析,编程实现也就是一个树的广度优先搜索,相信也难不倒lz。实际处理中,我们需要记录当前的搜索路径,另外建立一张哈希表用以记录所有节点的值用于剪枝。

晚风撩人 2016-12-18 1 楼

假设A=4,B=44
那么 就有(B-A)/12=3,也就是A需要连续加上三次12
此时A=40
而 现在(B-A)/7<0,且(B-A)/7<7,那么就A=A+7,得到A=47,继续往下取5
而 (B-A)/5>0,且(B-A)-5>5,那么就A=A-5,得到A=42,由于(B-A)-5>5仍然成立,A=A-5得到A=37,由于(B-A)-5<5,则向上走取7

由于A+7=B成立,则跳出判断

按照以上方法即可求出用最少操作次数使得A=B

这与九章算术中的更相减损术类似..........................