一道比较常见的面试题,但至今我没看到有人把这道题说透.
卖油翁油缸里面有10L油, 但他只有两个容量分别为7L和3L的容器,
- 要求写出算法,目标怎么分出5L和5L的油.
答案一般是告诉你:
先这样倒过来, 然后又这样,倒着倒着,到最后, 神奇的事情发生了,答案呼之欲出. (求不吐槽,读者你真的不会想知道具体答案吧,没必要)
不知道有谁有过跟我一样的感觉, 觉得智商被侮辱了.这样的答案简直是莫名其妙. 没错,它是解决了问题,可以我们压根不知道他是怎么解决的. 下次遇到类似的,说不定还是束手无策.就像我们高中看参考答案: …从这里我们明显可以得出.. .
有时候你觉得很简单的结论,因为认知的差别,对于别人就是一道很难迈过去的坎.
扩展欧几里得算法
今天我说说我对这道题的看法,一种更本质的东西.大四上学期,密码学有一节课是讲扩展欧几里得算法的(恩,刚好那节没逃课,捂脸).
扩展欧几里得算法的介绍如链接.
扩展欧几里得算法简单来说,研究的是 aX+bY = Z (其中, X,Y,Z是已知整数)方程中 a,b 是否有整数解的问题.这里我不会具体讲这个算法, 网上很多资料都可以帮你达到这一目的.
当两者相遇
卖油翁问题的解决,在我的潜意识里我一直觉得挺玄乎的,但没有花很大精力去研究. 直到那次的密码课,我突然意识到, 这个问题本质就是 扩展欧几里得算法.这是一种很奇妙的经历,个人人生中少数不多的 AhaMoment. 卖油翁问题我很早就遇到过了,扩展欧几里得初中就学习过了,但两者之间的联系我却是等到一个偶然的情况下才意识到!
你看我们拿容器倒来倒去,其实就是在 加7, 减7, 加3,减3,这几个操作中循环着.那问题就可以变成这样: 给你若干个7和3,只能做加减,怎么得到一个5. 转为算术就是7a+3b=5 ,其中 a,b 为整数是否有解 .这样就跟扩展欧几里得算法一模一样了!知道的这一点,甚至你可以在操作之前就可以判断这样的问题是否有解.
当本质显露之后
看穿本质的人, 一眼就知道这个问题是否有解,最小解集是什么.真正的举一反三. 没看穿的人,只能在那里倒来倒去期待刚好得出答案,有一些没解的说不定会深深的忧郁最后怀疑人生. 我只是借题发挥,这只是一个很小的问题,我感慨的是其他的,我自认为习以为常的东西,说不定在一些人看来,我也只是”身在此山中”.在这里立一个 flag,写一个系列,来自高维度的人类.希望说的就是这样一些人.
PS
小记一下,扩展欧几里得的魅力不仅如此
要是有来自圣经的算法,它当之无愧排名第一. 历史最悠久,坑爹的还是少数的只用到对数 lgN 时间的算法(对分查找也算一个),
重要的一点是,这个算法的平均迭代次数分析,至今我还看不懂:
\begin{aligned}
\frac{12\ln 2 lnN}{\pi^2} + 1.47
\end{aligned}
