今天面试了一家XX公司,问了一道盲人分牌的题我没答上来,后来自己用撕了几张纸试了一下,做出来了。类似的题目之前也遇到过一道,也是没做出来,后来也没去想,吃了两次亏了,一定要总结一下。
题目是这样的:一个盲人面前有7张牌,他只知道其中有4张正面朝上的牌,问怎么把牌分成两堆,使得每堆正面朝上的牌一样多?面试时我的回答是:把每张牌对折撕两半,一半放在一堆,这样每堆就有4张正面朝上3张反面朝上的了。面试官呵呵了,说不能把牌弄破。
面完后我用纸片试了一下,把牌直接分两堆,发现一堆3张一堆4张,然后把有4张牌的那堆翻过来,那正面朝上的就一样多了,不管原来分的两堆牌中正面朝上的有几张。
后来想想,这个问题其实可以扩展成一般的问题:一个盲人前面有n张牌,他只知道这n张牌中有m(m为偶数)张是正面朝上的,问怎怎么把牌分两堆,使得每堆正面朝上的牌一样多。解决方法是:把n张牌任意分成两堆,一堆m张,另一堆n-m张,然后把有m张牌的那堆牌全部翻过来即可。这个方法的正确性证明如下:
假设有m张牌的那堆牌中正、反面朝上的牌