Jun 30

二进制偶矩阵 不指定

felix021 @ 2012-6-30 22:34 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(7478) | Via 本站原创
这是2012年百度实习招聘非技术类的某道笔试题。

给一个5×5的矩阵,每个元素只能是0或者1。

请问,有多少种不同的矩阵,能够满足每一行、每一列都有偶数个1?

==== 分割线 ====

乍看这个题目,觉得是数学题。画了个5*5的矩阵,试图填几个数字进去看看是否可以推出一些结论。果断失败。

然后想了下,这题如果枚举的话,也就是2的25次方,大约3200万这个规模,不是很夸张。于是决定暴力搞一下。

最简单的做法就是
for (i = count = 0; i < 2<<25 - 1; i++) check_even(i) && count++;
这个check_even(i)里头把 i 当成一个25bit的二进制数字,并转换为对应的5*5矩阵,判断其每一行和每一列是否满足要求。(p.s. whusnoopy的做法是直接使用位运算,更简单,不过思路就断了。。)

一个不难想到的优化是,在for之前先把每一行给枚举了,这样就不需要在check_even里面每次进行转换,只需要从 i 中取出对应的bits,就可以直接找到每一行。

更进一步,由于题目要求每一行都是偶数个1,所以可以进行剪枝——在枚举的时候只需要保留有偶数个1的情况就行了,枚举出5行,然后判断每个列。很容易计算,每行5个bit,偶数个1的情况是2^4=16种。于是需要枚举的矩阵数量降至16^5。

再进一步剪枝——题目要求所以列是偶数,那么在已经确定前4行的情况下,第5行是可以直接推出来的,需要枚举的矩阵数量降至16^4。但还需要做的事情是,判断第5行是否有偶数个1。

到了这一步,豁然开朗——因为很容易证明,第5行必然是偶数个1:
  1) 每一列都是偶数个1(ABCDE都是偶数),所以矩阵中必然有偶数个1(F=A+B+C+D+E为偶数)
  2) 前4行都是偶数个1(HIJK都是偶数),所以第5行必然是偶数个1(L=F-H-I-J-K为偶数)
  (p.s. 这个证明是WHUMSTC群里某同学给出的,非常清晰,所以我就不给我自己那个很挫的证明过程了)

于是开头的直觉获胜,问题的答案就是:16^4,也就是(2^4)^4。

==== 分割线 ====

扩展:

1. 如果矩阵的大小是 N×N ,甚至是 M×N 呢?

    根据上述结论,很容易推知,对于M*N的矩阵,结果是2^((M-1) * (N-1))。

2. 如果要求满足每一行、每一列都有奇数个1呢?(whusnoopy提出)

    这个结论就不那么直接了,对M*N有一定的限制。
分页: 1/1 第一页 1 最后页 [ 显示模式: 摘要 | 列表 ]