假币问题：12枚金币中存有一假币，且不知假币较轻或较重，给一天枰限称3次找出其中的假币并知其轻重。
# 故事
2012回家过年，在家没事的时候给小弟小妹们出了道以前的有趣的算法题目，题目虽然不难，只要稍微知道其中一点技巧就可解得。出乎我的意料，他们对于这道题目颇为兴趣，虽然一时半会没能得到解答，后来给予一些提示方能想通其中的解法。但是，事后他们都表情露出兴奋，似乎“他们变得聪明了”，哈哈。最后，还要求他们得想清楚用纸笔写出（画出）算法过程如“XXX -> XXX -> XXX -> ... XXX -> X是假币较轻”。
在书写描述的过程，发现他们懂了逻辑但要描写清楚还是比较困难的……想了办法为加深他们对解法的理解，找了12枚硬币继续跟他们解释了遍，再让他们动手去自己演示，然后再去书写描述清楚算法过程……的确，这样下来他们都做得很好（可惜忘记拍图- -！）。哈哈，看到他们的清晰描述时，我当时也有些成就感。
再后来，当我回深开始上班了，我也一时兴致燃起，在空闲时间整理以前的关于这道题的程序（代码放在这里），规范程序解法的输出。结果如下：
# 解法
假币问题：12枚金币中存有一假币，且不知假币较轻或较重，给一天枰限称3次找出其中的
假币并知其轻重。演示如下：
NO.1 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]0 [2]1 [3]1 [4]1 [5]1 [6]1 [7]1 [8]1 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{1 } VS {9 }
假币位置：1 假币较轻！
--- end ---
NO.2 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]0 [3]1 [4]1 [5]1 [6]1 [7]1 [8]1 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{2 } VS {3 }
假币位置：2 假币较轻！
--- end ---
NO.3 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]0 [4]1 [5]1 [6]1 [7]1 [8]1 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{2 } VS {3 }
假币位置：3 假币较轻！
--- end ---
NO.4 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]0 [5]1 [6]1 [7]1 [8]1 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{2 } VS {3 }
假币位置：4 假币较轻！
--- end ---
NO.5 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]0 [6]1 [7]1 [8]1 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{1 } VS {9 }
假币位置：5 假币较轻！
--- end ---
NO.6 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]1 [6]0 [7]1 [8]1 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{6 } VS {7 }
假币位置：6 假币较轻！
--- end ---
NO.7 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]1 [6]1 [7]0 [8]1 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{6 } VS {7 }
假币位置：7 假币较轻！
--- end ---
NO.8 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]1 [6]1 [7]1 [8]0 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{6 } VS {7 }
假币位置：8 假币较轻！
--- end ---
NO.9 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]1 [6]1 [7]1 [8]1 [9]0 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 9 } VS {10 11 }
天枰比较：{10 } VS {11 }
假币位置：9 假币较轻！
--- end ---
NO.10 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]1 [6]1 [7]1 [8]1 [9]1 [10]0 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 9 } VS {10 11 }
天枰比较：{10 } VS {11 }
假币位置：10 假币较轻！
--- end ---
NO.11 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]1 [6]1 [7]1 [8]1 [9]1 [10]1 [11]0 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 9 } VS {10 11 }
天枰比较：{10 } VS {11 }
假币位置：11 假币较轻！
--- end ---
NO.12 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]1 [6]1 [7]1 [8]1 [9]1 [10]1 [11]1 [12]0
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 9 } VS {10 11 }
天枰比较：{1 } VS {12 }
假币位置：12 假币较轻！
--- end ---
NO.13 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]2 [2]1 [3]1 [4]1 [5]1 [6]1 [7]1 [8]1 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{1 } VS {9 }
假币位置：1 假币较重！
--- end ---
NO.14 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]2 [3]1 [4]1 [5]1 [6]1 [7]1 [8]1 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{2 } VS {3 }
假币位置：2 假币较重！
--- end ---
NO.15 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]2 [4]1 [5]1 [6]1 [7]1 [8]1 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{2 } VS {3 }
假币位置：3 假币较重！
--- end ---
NO.16 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]2 [5]1 [6]1 [7]1 [8]1 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{2 } VS {3 }
假币位置：4 假币较重！
--- end ---
NO.17 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]2 [6]1 [7]1 [8]1 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{1 } VS {9 }
假币位置：5 假币较重！
--- end ---
NO.18 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]1 [6]2 [7]1 [8]1 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{6 } VS {7 }
假币位置：6 假币较重！
--- end ---
NO.19 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]1 [6]1 [7]2 [8]1 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{6 } VS {7 }
假币位置：7 假币较重！
--- end ---
NO.20 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]1 [6]1 [7]1 [8]2 [9]1 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 6 7 8 } VS {5 9 10 11 }
天枰比较：{6 } VS {7 }
假币位置：8 假币较重！
--- end ---
NO.21 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]1 [6]1 [7]1 [8]1 [9]2 [10]1 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 9 } VS {10 11 }
天枰比较：{10 } VS {11 }
假币位置：9 假币较重！
--- end ---
NO.22 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]1 [6]1 [7]1 [8]1 [9]1 [10]2 [11]1 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 9 } VS {10 11 }
天枰比较：{10 } VS {11 }
假币位置：10 假币较重！
--- end ---
NO.23 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]1 [6]1 [7]1 [8]1 [9]1 [10]1 [11]2 [12]1
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 9 } VS {10 11 }
天枰比较：{10 } VS {11 }
假币位置：11 假币较重！
--- end ---
NO.24 --- --- --- --- --- --- --- --- --- --- --- ---
[编号]轻重 [1]1 [2]1 [3]1 [4]1 [5]1 [6]1 [7]1 [8]1 [9]1 [10]1 [11]1 [12]2
天枰比较：{1 2 3 4 } VS {5 6 7 8 }
天枰比较：{1 9 } VS {10 11 }
天枰比较：{1 } VS {12 }
假币位置：12 假币较重！
--- end ---
---
回头看来，一道小小算法趣味这样琢磨起来还挺有意思的，至少提提神的作用达到了，让算法思维活跃些了，有益于你继续开始学习其他高深的算法！
最后，完整的C++程序代码放在github，欢迎围观。
没有评论:
发表评论