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

Question

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

Answer 1

第一眼：扩展欧几里得算法。
第二眼：枚举情况，常数解决。
三种情况：
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)的。

Answer 2

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

Answer 3

这个是公约数的变形吧

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

通过分析可以得出

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

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

Answer 4

问题等效于：
求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

代码明天有空的话补上

Answer 5

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

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

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

Answer 6

假设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

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