Yukang's Page

面试:杯子倒水

2010-10-14

前些天纳拓的面试有一道题目:

给你一个3升的杯子和一个5升的(杯子是没有刻度的),要你取4升水来(水可以无限取),请问该如何操作。

这个题目今年面试出现了很多次,不过这次变化了一些。如何抽象出一个模型,如果写程序如何解,如果要求得杯子倒水的过程如何做?

当时并没有一下想出来,看起来有点像取石子那样的游戏,想找规律。然后被提示搜索,对,搜索问题。

搜索得确定状态的表示,状态之间的转移方式,起点和终止状态,如果这些都确定那么就基本完成了。

如果我要求最快的解法,BFS。如果要求所有的解法,递归DFS。这里状态的总数目比较少,如果用一个整数来表示,10位表示A杯子的水量,个位表示B杯子的水量,这样要的空间最大也为60个整数。再想想如果用两个整数,最多64bit,也能表示出状态,能省下空间。

很久没做题了,有些生疏了,看来还得好好补一下。

代码_下载

使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章