Jun 30

二进制偶矩阵 不指定

felix021 @ 2012-6-30 22:34 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(5380) | 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有一定的限制。

转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: http://www.felix021.com/blog/feed.php
himdd Email Homepage
2012-7-20 11:24
这有另一中解释http://blog.himdd.com/?p=2480
yang_bigarm
2012-7-1 23:58
很遗憾,楼主算错了,我算出来的答案是75个,而不是你的答案。
你的答案没有考虑旋转和对称的情况,事实上这个问题有很多对称的情况,重复的要剔除的哦。

利用等价类(行列置换等价)的方法,可以把所有的情况归结于m1到m5种情况
m1 = {(* four 1s *)
  {1, 1, 0, 0, 0},
  {1, 1, 0, 0, 0},
  {0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0}};
m2 = {(* Eight 1s *)
  {1, 1, 1, 1, 0},
  {1, 1, 1, 1, 0},
  {0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0}};
m3 = {(* Eight 1s *)
  {1, 1, 0, 0, 0},
  {1, 1, 0, 0, 0},
  {1, 1, 0, 0, 0},
  {1, 1, 0, 0, 0},
  {0, 0, 0, 0, 0}};
m4 = {(* Tweleve 1s *)
  {1, 1, 1, 1, 0},
  {1, 1, 1, 1, 0},
  {1, 1, 0, 0, 0},
  {1, 1, 0, 0, 0},
  {0, 0, 0, 0, 0}};
m5 = {(* Sixteen 1s *)
  {1, 1, 1, 1, 0},
  {1, 1, 1, 1, 0},
  {1, 1, 1, 1, 0},
  {1, 1, 1, 1, 0},
  {0, 0, 0, 0, 0}};

Total[EvenMCount /@ {m1, m2, m3, m4, m5}] + 1
得到75种,最后那个加1表示全0的情况。
felix021 回复于 2012-7-4 11:32
这个应该算到问题的扩展里头,因为方向本身也是一种属性。
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]