判断假币比真币重还是轻?

更轻或者更重?

你有n>2个外观相似的硬币和一个没有砝码的天平。其中一枚为假币,但并不知道它比真币重还是轻。设计一个 θ(1)的算法来确定假币比真币重还是轻。

看《算法设计与分析基础》,习题2.2里面的一道题,还挺有意思的。

问题第一眼看上去并不算难,很快就能想出一些解法。

第一种解法

直观上,既然只有一枚假币,那其他都是真币,那其他真币,随便拿两个放在天平上,肯定天平是平衡的。如果不平衡,那里面一定有一个是假币。

根据上面的想法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
随意从n>2中取出两枚硬币,分别为y1,y2

if y1=y2
//y1和y2相等,那么y1,y2都是真币
while(true) {
//再从所有硬币中取出一枚硬币y3
if y1=y3
continue
else if y1>y2
//假币更轻
break
else
//假币更重
break
}
else
//再从所有硬币中取出一枚硬币y3
if y1=y3
//y2就是假币
if y1!=y3
//y1就是假币

第一种解法,显然是一个O(n)时间复杂度的算法,最差情况下,比较到最后一个硬币才能发现假币。当然,最好情况,可以只需要两次。不过依然是一个O(n)时间复杂度的算法,并不符合题目的要求。

不过,这是一种直观的解法,研究一个算法,就普通人来说,没法做到像大牛一般,一下就能想到很合适,很优雅的算法。可能就是从最粗暴的暴力硬撸算法开始,不过在这思考中间,有可能就能想到更好的思路。我一开始学习算法,做算法题时,就很有挫败感,感觉看别人的答案,都是很精妙的解法,甚至连代码都写的很优雅,都是十行java搞定xxx一行python解决xxx,不过这背后付出了多少努力,我们是看不见的。记得在 霸王别姬里面有一幕,小赖子看到唱京戏的名角儿,底下人声鼎沸,叫好声一片,小豆子抹着眼泪大哭:“我什么时候能成角儿啊?这得挨多少打呀?”

写远了。

第二种解法

要想做到θ(1)的时间复杂度,那必须在固定步骤中就能解出结果,那就必然不能在某一个硬币上面纠结,如果一个一个去比较,那必定是要到O(n)的。既然不能一个一个,那就一堆一堆咯?这是我当时最直观的想法。一堆一堆怎么比较?

分成两堆

如果n%2=0,把n分成两等份,必然一堆重,一堆轻,然而好像没什么卵用,没法确认假币轻还是重,因为我们不知道假币在哪堆。

灵感来了,我们要怎么知道假币在哪堆呢?

分成三堆

分成三堆,假币一定会在其中一堆里面,那其他两堆都是真币,两堆同样数量的真币重量也一定相等!确定了两堆真币,和一堆含有一个假币的,这样就变的很简单了!两堆真币拿出和假币堆一样数量的真币,和假币堆一比较,轻重的结果就出来了!

关键点:

  • 分成三堆,其中两堆加起来一定要大于或者等于余下的那一堆,否则最后没法做比较
  • 三堆加起来等于全部的硬币数量,不要剩余什么零头,否则就多了可能性,自然算法的步骤就增多了

那三堆到底可以分成多大?其实根据上面两个关键点已经可以推出来了

$$ f(n)= \begin{cases} 2x+y=n \newline 2x>=y \end{cases} $$

由于 n 是已经确定的,其实就是解一个2元一次方程,求出x,y的范围,也就知道怎么分配堆的大小了

数学真奇妙o( ̄▽ ̄)d

今天这道题就写这么多啦~

白了个白~