相关知识
找假币问题是一个比较简单且典型能够体现计算思维的问题。假设现在有n(n>=2)枚硬币,已知其中一枚为假币,且知道假币的重量是比真币轻的,请思考如何用分治思想解决该问题。
算法原理
本次实验中我们采用二分法解决假币问题。二分法是一个非常典型的分治思想的应用。
如果n是偶数,将n个硬币平均分成两份,直接比较这两份硬币的重量,假币在重量较轻的那份硬币中,继续对重量较轻的那一份硬币使用二分法,直到找出假币;
如果n是奇数,则随意取出一种的一枚硬币,将剩下的n-1枚硬币等分成两份。如果这两份硬币重量相同,则随机取出的那枚硬币即为假币;否则,按照硬币数为偶数是的处理办法继续执行算法。
测试输入:
3(此处省略七个3),2
预期输出 :
position is: 7, weight is: 2.