加载中…盲人分牌问题
(2016-09-19 13:38:43)
标签：
盲人分牌两堆正面朝上一样多 |
分类： 面试题 |
今天面试了一家XX公司，问了一道盲人分牌的题我没答上来，后来自己用撕了几张纸试了一下，做出来了。类似的题目之前也遇到过一道，也是没做出来，后来也没去想，吃了两次亏了，一定要总结一下。
题目是这样的：一个盲人面前有7张牌，他只知道其中有4张正面朝上的牌，问怎么把牌分成两堆，使得每堆正面朝上的牌一样多？面试时我的回答是：把每张牌对折撕两半，一半放在一堆，这样每堆就有4张正面朝上3张反面朝上的了。面试官呵呵了，说不能把牌弄破。
面完后我用纸片试了一下，把牌直接分两堆，发现一堆3张一堆4张，然后把有4张牌的那堆翻过来，那正面朝上的就一样多了，不管原来分的两堆牌中正面朝上的有几张。
后来想想，这个问题其实可以扩展成一般的问题：一个盲人前面有n张牌，他只知道这n张牌中有m（m为偶数）张是正面朝上的，问怎怎么把牌分两堆，使得每堆正面朝上的牌一样多。解决方法是：把n张牌任意分成两堆，一堆m张，另一堆n-m张，然后把有m张牌的那堆牌全部翻过来即可。这个方法的正确性证明如下：
假设有m张牌的那堆牌中正、反面朝上的牌数分别为x，y（很显然
x+y=m），那么另一堆牌中正、反面朝上的牌数为m-x，n-m-y。此时，把有m张牌的那堆牌全部反面，那么该堆牌中正、反面的牌数就变为了y，x张。由于x+y=m，所以y=m-x，其中y为第一堆中正面朝上的牌，m-x为第二堆中正面朝上的牌，即此时两堆正面朝上的牌数一样多了。
喜欢
0
赠金笔
前一篇：股神