[TL][小学数学]如何用简洁的代码实现

14 views
Skip to first unread message

Jeff Chen

unread,
Sep 24, 2009, 9:53:19 PM9/24/09
to pon...@googlegroups.com
同事儿子的作业,大概意思是这样:

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

4*4,把其中6个1替换成0,使得横竖1的个数都是偶数,一共有几种,并打印出来.

我自己做了下,写得很烦.有没有高人有简洁一点的代码.

--
My Blog:http://jeffchen.cn

@@

unread,
Sep 24, 2009, 10:16:02 PM9/24/09
to pon...@googlegroups.com
小学的编程题?

2009/9/25 Jeff Chen <sheis...@gmail.com>

Jeff Chen

unread,
Sep 24, 2009, 10:17:42 PM9/24/09
to pon...@googlegroups.com
小学题目,我概括成这样一道编程题,呵呵

2009/9/25 @@ <ask...@gmail.com>

@@

unread,
Sep 24, 2009, 10:19:03 PM9/24/09
to pon...@googlegroups.com
基本就是 每行或者每列要替换的话 只能替换2个。

这样的话总数算算乘法应该就有了

2009/9/25 Jeff Chen <sheis...@gmail.com>

@@

unread,
Sep 24, 2009, 10:24:02 PM9/24/09
to pon...@googlegroups.com
寒。。不过我想摆一个满足条件的都没摆出来

2009/9/25 @@ <ask...@gmail.com>

Jiyong Xu

unread,
Sep 24, 2009, 10:25:01 PM9/24/09
to pon...@googlegroups.com
1111
1100
1010
1001

xxmplus

unread,
Sep 24, 2009, 10:27:59 PM9/24/09
to pon...@googlegroups.com
每行都要换掉两个,所以总有一行是保持4个1,然后有0011,0101,0110,和1100四种情况,剩下的都是对称的
搜索剪枝吧

2009/9/25 @@ <ask...@gmail.com>:

--
Any complex technology which doesn’t come with documentation must be the best
available.
Sent from Sydney, Nsw, Australia

Jeff Chen

unread,
Sep 24, 2009, 10:28:33 PM9/24/09
to pon...@googlegroups.com
嗯,要所有的,并要一共多少种....

2009/9/25 Jiyong Xu <xuji...@gmail.com>
1111
1100
1010
1001

Jiyong Xu

unread,
Sep 24, 2009, 10:30:49 PM9/24/09
to pon...@googlegroups.com
是否可以简化成六个零排成横竖都是偶数的图像呢

@@

unread,
Sep 24, 2009, 10:32:41 PM9/24/09
to pon...@googlegroups.com
有答案吗?不知道算的对不对 8*3*2

2009/9/25 Jeff Chen <sheis...@gmail.com>

Jeff Chen

unread,
Sep 24, 2009, 10:33:16 PM9/24/09
to pon...@googlegroups.com
楼上,不能.如下
1111
1111
1100
0000

2009/9/25 Jiyong Xu <xuji...@gmail.com>
是否可以简化成六个零排成横竖都是偶数的图像呢

Jeff Chen

unread,
Sep 24, 2009, 10:34:31 PM9/24/09
to pon...@googlegroups.com
我跑出来不是8*3*2

关键是还要打印出来

2009/9/25 Jeff Chen <sheis...@gmail.com>

Jiyong Xu

unread,
Sep 24, 2009, 10:35:42 PM9/24/09
to pon...@googlegroups.com
1111
1111
1100
0000

还是下面这个图像吧,每一行可以互换,每一列也可以互换。

1111
1100
1010
1001

2009/9/25 Jeff Chen <sheis...@gmail.com>
1111
1111
1100
0000

Hongzhang Liu

unread,
Sep 24, 2009, 10:46:07 PM9/24/09
to pon...@googlegroups.com
10个1,只可能是4+2+2+2

4行4列中任选出1行和1列,也就是其中的4。按照对称性,只需要考虑三种情况:
1. (1, 1) 第一行与第一列,
2. (1, 2),
3. (2, 2)

对剩下的3行,每行中只能剩下一个1,每个1的列序号都不同,有6组解。

总的解有3*6*4种。

2009/9/25 @@ <ask...@gmail.com>:

Jeff Chen

unread,
Sep 24, 2009, 10:51:23 PM9/24/09
to pon...@googlegroups.com
还是和我print出来的结果不一样啊

2009/9/25 Hongzhang Liu <hongzh...@gmail.com>

Bruce Khereid

unread,
Sep 24, 2009, 11:23:12 PM9/24/09
to pon...@googlegroups.com
不是程序求解的,也没遍历验证,用白话说了,没列定义和公理。不知道有没有错误,请大家纠正:

我换一下词和符号:一个 4x4 的棋盘上放 6 个棋子,使得每个横线(行)和每个竖线(列)上都有 0 个、2 个或 4 个子,问有多少种棋局。

假设某行(列)上有 4 个棋子,那么必然有另一个行(列)上有 2 个,其余两行(列)都是 0 个,这么一来必然有 2 个列(行)有 1 个棋子,不符合题目要求。所以,第一条结论:任何一行和任何一列都不会有 4 个棋子。进而可知,有一行和一列是没有棋子的,其余每行和每列都有 2 个。

如果刨除空行和空列,可以获得 3x3 的子棋盘,要求一样,每行每列 2 个子,共 6 个子。显然是 3 x 2 x 1 种状态。

空行的位置可以区分解(导致不同的解“不同”),所以刨除空行和空列而取得的 3x3 的棋盘中的每个解可以衍生出原问题的 4x4 个解。

总共 96 种。

2009/9/25 Jeff Chen <sheis...@gmail.com>

arri...@gmail.com

unread,
Sep 24, 2009, 11:32:12 PM9/24/09
to pon...@googlegroups.com
暴力验证
ruby 1.8.7
class Array
def sum
self.reduce(0) {|a,b| a+b}
end
end

def check(a) 
0.upto(3) do |i| 
return false if a[i].sum % 2 == 1 || (0..3).to_a.map{|j| a[j][i]}.sum % 2 == 1
end
true
end

count = 0
(0..15).to_a.combination(6).each do |per|
a=[[1,1,1,1], [1,1,1,1], [1,1,1,1], [1,1,1,1]]
per.each {|i| a[i/4][i%4] = 0}
if check(a) 
puts a.map {|e| e.join(' ')}.join("\n"), '-' * 8
count += 1
end
end
puts "count:#{count}"

结果是96
0 0 1 1
0 1 0 1
1 0 0 1
1 1 1 1
--------
0 0 1 1
0 1 0 1
1 1 1 1
1 0 0 1
--------
0 0 1 1
0 1 1 0
1 0 1 0
1 1 1 1
--------
0 0 1 1
0 1 1 0
1 1 1 1
1 0 1 0
--------
0 0 1 1
1 0 0 1
0 1 0 1
1 1 1 1
--------
0 0 1 1
1 0 0 1
1 1 1 1
0 1 0 1
--------
0 0 1 1
1 0 1 0
0 1 1 0
1 1 1 1
--------
0 0 1 1
1 0 1 0
1 1 1 1
0 1 1 0
--------
0 0 1 1
1 1 1 1
0 1 0 1
1 0 0 1
--------
0 0 1 1
1 1 1 1
0 1 1 0
1 0 1 0
--------
0 0 1 1
1 1 1 1
1 0 0 1
0 1 0 1
--------
0 0 1 1
1 1 1 1
1 0 1 0
0 1 1 0
--------
0 1 0 1
0 0 1 1
1 0 0 1
1 1 1 1
--------
0 1 0 1
0 0 1 1
1 1 1 1
1 0 0 1
--------
0 1 0 1
0 1 1 0
1 1 0 0
1 1 1 1
--------
0 1 0 1
0 1 1 0
1 1 1 1
1 1 0 0
--------
0 1 0 1
1 0 0 1
0 0 1 1
1 1 1 1
--------
0 1 0 1
1 0 0 1
1 1 1 1
0 0 1 1
--------
0 1 0 1
1 1 0 0
0 1 1 0
1 1 1 1
--------
0 1 0 1
1 1 0 0
1 1 1 1
0 1 1 0
--------
0 1 0 1
1 1 1 1
0 0 1 1
1 0 0 1
--------
0 1 0 1
1 1 1 1
0 1 1 0
1 1 0 0
--------
0 1 0 1
1 1 1 1
1 0 0 1
0 0 1 1
--------
0 1 0 1
1 1 1 1
1 1 0 0
0 1 1 0
--------
0 1 1 0
0 0 1 1
1 0 1 0
1 1 1 1
--------
0 1 1 0
0 0 1 1
1 1 1 1
1 0 1 0
--------
0 1 1 0
0 1 0 1
1 1 0 0
1 1 1 1
--------
0 1 1 0
0 1 0 1
1 1 1 1
1 1 0 0
--------
0 1 1 0
1 0 1 0
0 0 1 1
1 1 1 1
--------
0 1 1 0
1 0 1 0
1 1 1 1
0 0 1 1
--------
0 1 1 0
1 1 0 0
0 1 0 1
1 1 1 1
--------
0 1 1 0
1 1 0 0
1 1 1 1
0 1 0 1
--------
0 1 1 0
1 1 1 1
0 0 1 1
1 0 1 0
--------
0 1 1 0
1 1 1 1
0 1 0 1
1 1 0 0
--------
0 1 1 0
1 1 1 1
1 0 1 0
0 0 1 1
--------
0 1 1 0
1 1 1 1
1 1 0 0
0 1 0 1
--------
1 0 0 1
0 0 1 1
0 1 0 1
1 1 1 1
--------
1 0 0 1
0 0 1 1
1 1 1 1
0 1 0 1
--------
1 0 0 1
0 1 0 1
0 0 1 1
1 1 1 1
--------
1 0 0 1
0 1 0 1
1 1 1 1
0 0 1 1
--------
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
--------
1 0 0 1
1 0 1 0
1 1 1 1
1 1 0 0
--------
1 0 0 1
1 1 0 0
1 0 1 0
1 1 1 1
--------
1 0 0 1
1 1 0 0
1 1 1 1
1 0 1 0
--------
1 0 0 1
1 1 1 1
0 0 1 1
0 1 0 1
--------
1 0 0 1
1 1 1 1
0 1 0 1
0 0 1 1
--------
1 0 0 1
1 1 1 1
1 0 1 0
1 1 0 0
--------
1 0 0 1
1 1 1 1
1 1 0 0
1 0 1 0
--------
1 0 1 0
0 0 1 1
0 1 1 0
1 1 1 1
--------
1 0 1 0
0 0 1 1
1 1 1 1
0 1 1 0
--------
1 0 1 0
0 1 1 0
0 0 1 1
1 1 1 1
--------
1 0 1 0
0 1 1 0
1 1 1 1
0 0 1 1
--------
1 0 1 0
1 0 0 1
1 1 0 0
1 1 1 1
--------
1 0 1 0
1 0 0 1
1 1 1 1
1 1 0 0
--------
1 0 1 0
1 1 0 0
1 0 0 1
1 1 1 1
--------
1 0 1 0
1 1 0 0
1 1 1 1
1 0 0 1
--------
1 0 1 0
1 1 1 1
0 0 1 1
0 1 1 0
--------
1 0 1 0
1 1 1 1
0 1 1 0
0 0 1 1
--------
1 0 1 0
1 1 1 1
1 0 0 1
1 1 0 0
--------
1 0 1 0
1 1 1 1
1 1 0 0
1 0 0 1
--------
1 1 0 0
0 1 0 1
0 1 1 0
1 1 1 1
--------
1 1 0 0
0 1 0 1
1 1 1 1
0 1 1 0
--------
1 1 0 0
0 1 1 0
0 1 0 1
1 1 1 1
--------
1 1 0 0
0 1 1 0
1 1 1 1
0 1 0 1
--------
1 1 0 0
1 0 0 1
1 0 1 0
1 1 1 1
--------
1 1 0 0
1 0 0 1
1 1 1 1
1 0 1 0
--------
1 1 0 0
1 0 1 0
1 0 0 1
1 1 1 1
--------
1 1 0 0
1 0 1 0
1 1 1 1
1 0 0 1
--------
1 1 0 0
1 1 1 1
0 1 0 1
0 1 1 0
--------
1 1 0 0
1 1 1 1
0 1 1 0
0 1 0 1
--------
1 1 0 0
1 1 1 1
1 0 0 1
1 0 1 0
--------
1 1 0 0
1 1 1 1
1 0 1 0
1 0 0 1
--------
1 1 1 1
0 0 1 1
0 1 0 1
1 0 0 1
--------
1 1 1 1
0 0 1 1
0 1 1 0
1 0 1 0
--------
1 1 1 1
0 0 1 1
1 0 0 1
0 1 0 1
--------
1 1 1 1
0 0 1 1
1 0 1 0
0 1 1 0
--------
1 1 1 1
0 1 0 1
0 0 1 1
1 0 0 1
--------
1 1 1 1
0 1 0 1
0 1 1 0
1 1 0 0
--------
1 1 1 1
0 1 0 1
1 0 0 1
0 0 1 1
--------
1 1 1 1
0 1 0 1
1 1 0 0
0 1 1 0
--------
1 1 1 1
0 1 1 0
0 0 1 1
1 0 1 0
--------
1 1 1 1
0 1 1 0
0 1 0 1
1 1 0 0
--------
1 1 1 1
0 1 1 0
1 0 1 0
0 0 1 1
--------
1 1 1 1
0 1 1 0
1 1 0 0
0 1 0 1
--------
1 1 1 1
1 0 0 1
0 0 1 1
0 1 0 1
--------
1 1 1 1
1 0 0 1
0 1 0 1
0 0 1 1
--------
1 1 1 1
1 0 0 1
1 0 1 0
1 1 0 0
--------
1 1 1 1
1 0 0 1
1 1 0 0
1 0 1 0
--------
1 1 1 1
1 0 1 0
0 0 1 1
0 1 1 0
--------
1 1 1 1
1 0 1 0
0 1 1 0
0 0 1 1
--------
1 1 1 1
1 0 1 0
1 0 0 1
1 1 0 0
--------
1 1 1 1
1 0 1 0
1 1 0 0
1 0 0 1
--------
1 1 1 1
1 1 0 0
0 1 0 1
0 1 1 0
--------
1 1 1 1
1 1 0 0
0 1 1 0
0 1 0 1
--------
1 1 1 1
1 1 0 0
1 0 0 1
1 0 1 0
--------
1 1 1 1
1 1 0 0
1 0 1 0
1 0 0 1
--------



--
Arrix

许海斌

unread,
Sep 24, 2009, 11:41:46 PM9/24/09
to TopLanguage
有个比较笨的办法,4×4数组其中元素只能为0或者1的情形一共有65536种,然后从中筛选出每行每列加起来是偶数的结果A,再从A中找出6个0的就
是答案了

简洁是够简洁了,就是运算量比较大,呵呵

On 9月25日, 上午11时32分, "arrixz...@gmail.com" <arrixz...@gmail.com> wrote:
> 暴力验证ruby 1.8.7

@@

unread,
Sep 24, 2009, 11:41:31 PM9/24/09
to pon...@googlegroups.com
穷举了下 是96种。。

2009/9/25 Bruce Khereid <bruce....@gmail.com>

Jeff Chen

unread,
Sep 24, 2009, 11:49:46 PM9/24/09
to pon...@googlegroups.com
ruby的代码真简洁啊,我用java写的,同样是暴力求解,复杂多了

2009/9/25 @@ <ask...@gmail.com>
Message has been deleted

@@

unread,
Sep 25, 2009, 12:08:50 AM9/25/09
to pon...@googlegroups.com
java自己写combination就费事不少吧

2009/9/25 Jeff Chen <sheis...@gmail.com>

Li Yang

unread,
Sep 24, 2009, 10:28:54 PM9/24/09
to pon...@googlegroups.com
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
应该也是个解
不过考虑到现在0也终于算是偶数了,所以全0的应该也满足条件
0000
0000
0000
0000

2009/9/25 Jiyong Xu <xuji...@gmail.com>
1111
1100
1010
1001




--
While(!success=try())

zong

unread,
Sep 24, 2009, 10:53:24 PM9/24/09
to pon...@googlegroups.com
在纸上画,参照Jiyong Xu ,给出如下图形

1 0 1 0
1 0 0 1
0 1 0 1
0 1 1 0

且发现确实是每行(列)都替换两个
2009/9/25 Hongzhang Liu <hongzh...@gmail.com>



--
格物,致知;正心,诚意。

Wen YE

unread,
Sep 24, 2009, 11:25:33 PM9/24/09
to pon...@googlegroups.com
1111
1100
1010
1001
对这个矩阵进行的各行进行排列, 总共有 4! = 24 种, 然后调整全 1 的列, 总共有 4 个位置, 再乘 4 得总共有 96 种, 别的情况都和上面这些情况对应, 写了个程序验证, 欢迎指正

#include <stdio.h>

int allcount = 0;
// check bits in mask fit or not
int check(int mask) {
  for (int i = 0; i < 4; ++i) {
    // sh to count i-th row
    // sv to count i-th column
    int sh = 0;
    int sv = 0;
    for (int j = 0; j < 4; ++j) {
      if (mask & (1 << (i*4+j)))
        sh++;
      if (mask & (1 << (j*4+i)))
        sv++;
    }
    if ((sh % 2) || (sv % 2))
      return 0;
  }
  // DEBUG INFO, print the matrix
  printf(" >> [NO.%d] %d (0x%X) >>\n", allcount++, mask, mask);
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j)
      printf("%d", (mask & (1 << (i*4+j)))?1:0);
    printf("\n");
  }
  return 1;
}
int search(int mask, int p, int c) {
  if (p == 16) {
    if ((c == 0) && (check(mask)))
      return 1;
    return 0;
  }
  int count = search(mask, p + 1, c);
  if (c > 0)
    count += search((mask + (1 << p)), p + 1, c - 1);
  return count;
}
int main(int argc, char* argv[]) {
  int sum = search(0, 0, 6);
  printf("%d\n", sum);
  return 0;
}

2009/9/25 Jeff Chen <sheis...@gmail.com>

Wen YE

unread,
Sep 24, 2009, 11:27:01 PM9/24/09
to pon...@googlegroups.com
这个程序里把 1/0 反转了, 只是为了写程序方便, 最后结果都是一样的

2009/9/25 Wen YE <whus...@gmail.com>

Little Push

unread,
Sep 25, 2009, 1:33:24 AM9/25/09
to pon...@googlegroups.com
哎...昨天一小女生跑来问我这个问题,貌似是大二的小孩找来考大一小朋友的……要求用C写....
先贴算法:

1 1 0 0
0 0 1 1
1 1 1 1

这三行,排列组合,共6种情况,然后用1 1 0 0或者0 0 1 1在任意行插入,共4×2种插入方法
6×4×2=48

0 0 1 1
0 1 0 1
1 0 0 1

这四列,排列组合,共24种情况,然后用1 1 1 1插入行,4种插法
由于
0 0 1
0 1 0
1 0 0
是中心对称的,所以,插入过程中会导致出现重复,重复出现次数2
所以24×4 / 2 = 48

总计48 + 48 = 96种

C的实现比较烦哎……

--
Push Chen
SNDA
SDO Project Management Department
Curie Rd. 208
Shanghai, China
Mobile: +8613524446040
Tel: 50504740-1796
Facebook: http://www.facebook.com/littlepush
Twitter: http://twitter.com/littlepush


2009/9/25 @@ <ask...@gmail.com>

Little Push

unread,
Sep 25, 2009, 1:35:05 AM9/25/09
to pon...@googlegroups.com

2009/9/25 Li Yang <myic...@gmail.com>

1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
应该也是个解

俄……这里有8个0了。。所以不对。 

Little Push

unread,
Sep 25, 2009, 1:35:44 AM9/25/09
to pon...@googlegroups.com
这个是错误的,这里面有一半是重复的……


--
Push Chen
SNDA
SDO Project Management Department
Curie Rd. 208
Shanghai, China
Mobile: +8613524446040
Tel: 50504740-1796
Facebook: http://www.facebook.com/littlepush
Twitter: http://twitter.com/littlepush


2009/9/25 Wen YE <whus...@gmail.com>

Little Push

unread,
Sep 25, 2009, 1:38:52 AM9/25/09
to pon...@googlegroups.com
2009/9/25 zong <sunsh...@gmail.com>

在纸上画,参照Jiyong Xu ,给出如下图形

1 0 1 0
1 0 0 1
0 1 0 1
0 1 1 0

且发现确实是每行(列)都替换两个

这样有8个0哎……

Wen YE

unread,
Sep 25, 2009, 1:41:20 AM9/25/09
to pon...@googlegroups.com
原题要求 0 的个数是 6, 然后每行每列有偶数个 1 吧, 你这个有 8 个 0 了

2009/9/25 Li Yang <myic...@gmail.com>

Little Push

unread,
Sep 25, 2009, 2:32:07 AM9/25/09
to pon...@googlegroups.com
还发先一种方法

0000——0
0001——1
0010——2
0011——3
....
这样把16种情况列出来,符合单行偶数个1的有:
0x3, 0x5, 0x6, 0x9, 0xA, 0xC, 0xF共7种(全0的必然不会出现)
其中0xF是必然出现在任何一种组合内的。

这样一共可以得到4种组合方式:
{ 0x3, 0x5, 0x9, 0xF }
{ 0x3, 0x6, 0xA, 0xF }
{ 0x5, 0x6, 0xC, 0xF }
{ 0x9, 0xA, 0xC, 0xF }
然后,每种组合有4 × 3 × 2 ×1 = 24种排列方式,
4种组合就是96种

比较暴力的写法……

#include <stdio.h>
#include <stdlib.h>

// Output.
void outputMatex(char * a, char * b, char * c, char * d)
{
printf("%s\n", a);
printf("%s\n", b);
printf("%s\n", c);
printf("%s\n-------\n", d);
}

int main(int argc, char * argv[] )
{
char * group[4][4] = {
{"0 0 1 1", "0 1 0 1", "1 0 0 1", "1 1 1 1"},
{"0 0 1 1", "0 1 1 0", "1 0 1 0", "1 1 1 1"},
{"0 1 0 1", "0 1 1 0", "1 1 0 0", "1 1 1 1"},
{"1 0 0 1", "1 0 1 0", "1 1 0 0", "1 1 1 1"}
};
// Temp usage
char * a, * b, * c;
int nCount = 0;
for (int _grp = 0; _grp < 4; ++_grp)
{
for (int lv1 = 0; lv1 < 4; ++lv1)
{
a = group[_grp][lv1];
for(int lv2 = 0; lv2 < 4; ++lv2)
{
if (lv2 == lv1) continue;
b = group[_grp][lv2];
for (int lv3 = 0; lv3 < 4; ++lv3)
{
if (lv3 == lv1 || lv3 == lv2) continue;
c = group[_grp][lv3];
for (int lv4 = 0; lv4 < 4; ++lv4)
{
if (lv4 == lv3 || lv4 == lv2 || lv4 == lv1) continue;
outputMatex(a, b, c, group[_grp][lv4]);
++nCount;
}
}
}
}
}

printf("In All: %d\n", nCount);

return 0;
}

--
Push Chen
SNDA
SDO Project Management Department
Curie Rd. 208
Shanghai, China
Mobile: +8613524446040
Tel: 50504740-1796
Facebook: http://www.facebook.com/littlepush
Twitter: http://twitter.com/littlepush


2009/9/25 Little Push <littl...@gmail.com>

Alecs King

unread,
Sep 25, 2009, 4:50:13 AM9/25/09
to pon...@googlegroups.com
On Fri, Sep 25, 2009 at 09:53:19AM +0800, Jeff Chen wrote:
> 同事儿子的作业,大概意思是这样:
>
> 1 1 1 11 1 1 1

> 1 1 1 1
> 1 1 1 1
>
> 4*4,把其中6个1替换成0,使得横竖1的个数都是偶数,一共有几种,并打印出来.
>
> 我自己做了下,写得很烦.有没有高人有简洁一点的代码.
>
> --
> My Blog:http://jeffchen.cn

A Haskell brute force:

import Data.Bits
import Data.List
import Data.Char

main = print (length a) >> mapM_ p a
where a = [ m | n <- [0..2^16-1], let m = get n, sum (map sum m) == 10, ok m, ok . transpose $ m]
get n = [[shiftR (n .&. bit b) b :: Int | y <- [0..3], let b = 4*x+y] | x <- [0..3]]
ok = all (even . sum)
p x = putStrLn "----" >> mapM_ (putStrLn . map intToDigit) x

--
Alecs King

Alecs King

unread,
Sep 25, 2009, 4:51:49 AM9/25/09
to pon...@googlegroups.com
On Fri, Sep 25, 2009 at 09:53:19AM +0800, Jeff Chen wrote:
> 同事儿子的作业,大概意思是这样:
>
> 1 1 1 11 1 1 1
> 1 1 1 1
> 1 1 1 1
>
> 4*4,把其中6个1替换成0,使得横竖1的个数都是偶数,一共有几种,并打印出来.
>
> 我自己做了下,写得很烦.有没有高人有简洁一点的代码.
>
> --
> My Blog:http://jeffchen.cn

#!/usr/bin/python

count = 0
for n in xrange(1 << 16):
m = [[(n & (1 << x*4 + y)) >> x*4+y for y in range(4)] for x in
range(4)]
t = zip(*m)
if sum(map(sum, m)) == 10 and all(sum(m[x]) % 2 == 0 and sum(t[x]) %
2 == 0 for x in range(4)):
for x in range(4):
for y in range(4): print m[x][y],
print
print '-------'
count += 1
print count

--
Alecs King

Jeff Chen

unread,
Sep 25, 2009, 4:55:50 AM9/25/09
to pon...@googlegroups.com
python的没结果...

2009/9/25 Alecs King <al...@perlchina.org>

@@

unread,
Sep 25, 2009, 4:58:00 AM9/25/09
to pon...@googlegroups.com
有呀 估计是你缩进乱了

2009/9/25 Jeff Chen <sheis...@gmail.com>

Wen YE

unread,
Sep 25, 2009, 3:23:15 AM9/25/09
to pon...@googlegroups.com
原题似乎没要求说旋转对称的要去除, 把一个 4*4 的矩阵看成一维的, 然后再对应成二进制, 那不就是 0~65535? (0~2^16) 这个枚举怎么重复来?

2009/9/25 Little Push <littl...@gmail.com>

Li Yang

unread,
Sep 25, 2009, 5:00:07 AM9/25/09
to pon...@googlegroups.com
最里面的循环没东西。。。

2009/9/25 Alecs King <al...@perlchina.org>



--
While(!success=try())

Li Yang

unread,
Sep 25, 2009, 5:02:21 AM9/25/09
to pon...@googlegroups.com
有结果的

2009/9/25 Jeff Chen <sheis...@gmail.com>



--
While(!success=try())

Alecs King

unread,
Sep 25, 2009, 5:33:59 AM9/25/09
to pon...@googlegroups.com
On Fri, Sep 25, 2009 at 04:55:50PM +0800, Jeff Chen wrote:
> python的没结果...

Alecs King

unread,
Sep 25, 2009, 6:34:33 AM9/25/09
to pon...@googlegroups.com
clean up

#!/usr/bin/python

count = 0
ok = lambda m: all(sum(x) % 2 == 0 for x in m)


for n in xrange(1 << 16):
m = [[(n & (1 << x*4 + y)) >> x*4+y for y in range(4)] for x in range(4)]

if sum(map(sum, m)) == 10 and ok(m) and ok(zip(*m)):
for x in m:
for y in x: print y,

Little Push

unread,
Sep 25, 2009, 5:47:59 AM9/25/09
to pon...@googlegroups.com
首先,分解题目,可以理解为6个0, 4×4数组,横向竖向都是偶数个0.
考虑一行4个0,为了保持偶数,则必然需要在余下的3行内为第一行的每个0补充至少1个0。这样就至少需要8个0,于题意不符。
不能4个0,那就2个0,如此一来,即变成有3行是2个0,一行全1,也就是说0xF必然出现。
找到2个0的所有情况:0x3, 0x5 0x6, 0x9, 0xA, 0xC
取3个进行满足题意的组合,然后附带0xF组成一个组,这样的组一共只有4个,之前列出来过了。
然后,每个组内,每行的值可以互换,也就是说,在每组内进行全排,每组共有4 × 3 × 2 × 1 = 24种排列方法,然后对应到4组,就是96种。

不理解你这里说的“枚举”,而且,这样也没有对应成2进制,只是为了描述方便而已。


2009/9/25 Wen YE <whus...@gmail.com>

Lyman

unread,
Sep 25, 2009, 8:30:00 AM9/25/09
to pon...@googlegroups.com
Jeff Chen 写道:
> ruby的代码真简洁啊,我用java写的,同样是暴力求解,复杂多了
暴力法拿 c++ 写起来也不复杂

#include <iostream>
#include <sstream>

int main()
{
char sep[4] = {' ', ' ', ' ', '\n'};
for (int c = 0, i = 0; i < 65535; i++)
{
int zero = 0, x[4] = {0}, y[4] = {0};
std::stringstream ss;
for(int j = 0, t = i; j < 16; ss << (t % 2) << sep[j % 4], j++,
t >>= 1)
if (t % 2)
x[j / 4]++, y[j % 4]++;
else
zero++;
bool b = (zero == 6);
for(int j = 0; j < 4; j++)
b = b && (x[j] % 2 == 0) && (y[j] % 2 == 0);
if (b) std::cout << ++c << ":" << std::endl << ss.str() <<
std::endl;
}
return 0;
}

>
> 2009/9/25 @@ <ask...@gmail.com <mailto:ask...@gmail.com>>


>
> 穷举了下 是96种。。
>
> 2009/9/25 Bruce Khereid <bruce....@gmail.com

> <mailto:bruce....@gmail.com>>


>
> 不是程序求解的,也没遍历验证,用白话说了,没列定义和公理。不知道
> 有没有错误,请大家纠正:
>
> 我换一下词和符号:一个 4x4 的棋盘上放 6 个棋子,使得每个横线
> (行)和每个竖线(列)上都有 0 个、2 个或 4 个子,问有多少种棋局。
>
> 假设某行(列)上有 4 个棋子,那么必然有另一个行(列)上有 2 个,
> 其余两行(列)都是 0 个,这么一来必然有 2 个列(行)有 1 个棋
> 子,不符合题目要求。所以,第一条结论:任何一行和任何一列都不会有
> 4 个棋子。进而可知,有一行和一列是没有棋子的,其余每行和每列都有
> 2 个。
>
> 如果刨除空行和空列,可以获得 3x3 的子棋盘,要求一样,每行每列 2
> 个子,共 6 个子。显然是 3 x 2 x 1 种状态。
>
> 空行的位置可以区分解(导致不同的解“不同”),所以刨除空行和空列而
> 取得的 3x3 的棋盘中的每个解可以衍生出原问题的 4x4 个解。
>
> 总共 96 种。
>
> 2009/9/25 Jeff Chen <sheis...@gmail.com

> <mailto:sheis...@gmail.com>>


>
> 同事儿子的作业,大概意思是这样:
>
> 1 1 1 1
> 1 1 1 1
> 1 1 1 1
> 1 1 1 1
>
> 4*4,把其中6个1替换成0,使得横竖1的个数都是偶数,一共有几种,并
> 打印出来.
>
> 我自己做了下,写得很烦.有没有高人有简洁一点的代码.
>
> --

> My Blog:http://jeffchen.cn <http://jeffchen.cn/>

Alecs King

unread,
Sep 25, 2009, 11:05:53 AM9/25/09
to pon...@googlegroups.com
On Fri, Sep 25, 2009 at 09:53:19AM +0800, Jeff Chen wrote:
> 同事儿子的作业,大概意思是这样:
>
> 1 1 1 11 1 1 1

> 1 1 1 1
> 1 1 1 1
>
> 4*4,把其中6个1替换成0,使得横竖1的个数都是偶数,一共有几种,并打印出来.
>
> 我自己做了下,写得很烦.有没有高人有简洁一点的代码.
>
> --
> My Blog:http://jeffchen.cn

Just for fun. A c++ version. This is different from the haskell or the
python version. Since # of 1s is fixed, we can just check those
possible permutations (# of which is 8008) instead of doing no-brainer
2^16 (65536) checkings.


#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

inline bool ok(vector<int> &a)
{
for (int i = 0; i < 4; i++) {
int r = 0, c = 0;
for (int j = 0; j < 4; j++) {
r += a[i * 4 + j];
c += a[j * 4 + i];
}
if (r & 1 || c & 1)
return false;
}
return true;
}

inline void print(vector<int> &a)
{
for (int i = 0; i < 16; i++)
printf("%d%c", a[i], (i + 1) % 4 == 0 ? '\n' : ' ');
printf("-------\n");
}

int main()
{
vector<int> a(16, 1);
for (int i = 0; i < 6; i++)
a[i] = 0;
int count = 0, all = 0;
do {
all++;
if (ok(a)) {
count++;
print(a);
}
} while (next_permutation(a.begin(), a.end()));
printf("%d ok out of %d\n", count, all);
return 0;
}

--
Alecs King

lostyzd

unread,
Sep 25, 2009, 11:20:32 AM9/25/09
to pon...@googlegroups.com
无聊了我
#include <stdio.h>
int main()
{
int a[16];
int i,j,k,l,m,n;
int tot=1;
for (i=0;i<16;i++) 
a[i]=1;
for (i=0;i<16;i++)
for (j=i+1;j<16;j++)
for (k=j+1;k<16;k++)
for (l=k+1;l<16;l++)
for (m=l+1;m<16;m++)
for (n=m+1;n<16;n++)
{
a[i]=0;a[j]=0;a[k]=0;a[l]=0;a[m]=0;a[n]=0;
if (!(
(a[0]+a[1]+a[2]+a[3])%2||
(a[4]+a[5]+a[6]+a[7])%2||
(a[8]+a[9]+a[10]+a[11])%2||
(a[12]+a[13]+a[14]+a[15])%2||
(a[0]+a[4]+a[8]+a[12])%2||
(a[1]+a[5]+a[9]+a[13])%2||
(a[2]+a[6]+a[10]+a[14])%2||
(a[3]+a[7]+a[11]+a[15])%2
)
)
{
printf("%d\n",tot++);
for (int i=0;i<16;i+=4)
printf("%d%d%d%d\n",a[0+i],a[1+i],a[2+i],a[3+i]);
}
a[i]=1;a[j]=1;a[k]=1;a[l]=1;a[m]=1;a[n]=1;
}
}

2009/9/25 Jeff Chen <sheis...@gmail.com>
同事儿子的作业,大概意思是这样:

1 1 1 1

黑眼猪

unread,
Sep 26, 2009, 3:03:39 AM9/26/09
to pon...@googlegroups.com
单就这道题来说,可以归纳为8皇后问题×排列组合

2009/9/25 lostyzd <los...@gmail.com>

raymond

unread,
Sep 26, 2009, 10:48:15 AM9/26/09
to TopLanguage
1.这个可以归纳为异或运算,4个4bit的数字,如果异或结果为1,就满足了你的要求。
比如
1 1 1 1
1 0 0 1
0 0 1 1
0 1 1 1
异或为1 1 1 1。
2. 现在问题变成了,共有多少种可能的组合呢?就是16个bit中选择6个就行了,配合适当的减枝,速度会很快的。

具体可以使用单一的数据类型,比如short,加上小心的记录位置来实现。

On 9月25日, 上午9时53分, Jeff Chen <sheismyl...@gmail.com> wrote:
> 同事儿子的作业,大概意思是这样:
>

> 1 1 1 11 1 1 1

xiaosuo

unread,
Sep 26, 2009, 11:02:55 PM9/26/09
to TopLanguage


On 9月26日, 下午10时48分, raymond <shiqu...@gmail.com> wrote:
> 1.这个可以归纳为异或运算,4个4bit的数字,如果异或结果为1,就满足了你的要求。
> 比如
> 1 1 1 1
> 1 0 0 1
> 0 0 1 1
> 0 1 1 1
> 异或为1 1 1 1。
> 2. 现在问题变成了,共有多少种可能的组合呢?就是16个bit中选择6个就行了,配合适当的减枝,速度会很快的。
>
> 具体可以使用单一的数据类型,比如short,加上小心的记录位置来实现。
#include <stdio.h>

void print_row(unsigned char matrix, int colum)
{
int i, ci;

ci = 0;
for (i = 0; i < 4; i++) {
if (i == colum)
printf(" 1");
else
printf(" %d", (matrix >> (ci++)) & 1);
}
printf("\n");
}

void print_instance(unsigned char *matrix, int row, int colum)
{
int i, ri;
static int count = 0;

printf("\nnumber: %d\n", ++count);
ri = 0;
for (i = 0; i < 4; i++) {
if (i == row)
printf(" 1 1 1 1\n");
else
print_row(matrix[ri++], colum);
}
}

void print_matrix(unsigned char *matrix)
{
int i, j;

for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++)
print_instance(matrix, i, j);
}
}

int main(int argc, char *argv[])
{
int i, j, k;
unsigned char matrix[3];

for (i = 0; i < 3; i++) {
matrix[0] = 1 << i;
for (j = 0; j < 3; j++) {
matrix[1] = 1 << j;
for (k = 0; k < 3; k++) {
matrix[2] = 1 << k;
if ((matrix[0] ^ matrix[1] ^ matrix
[2]) == 7)
print_matrix(matrix);
}
}
}
}

jinhu wang

unread,
Sep 26, 2009, 11:39:17 PM9/26/09
to pon...@googlegroups.com
c++的
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>

#include <algorithm>
using namespace std;
int tmp[16]={0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1};
#define IS_EVEN_H(i) (tmp[i*4+0]^tmp[i*4+1]^tmp[i*4+2]^tmp[i*4+3]==0)
#define IS_EVEN_V(i) (tmp[i+0]^tmp[i+4]^tmp[i+8]^tmp[i+12]==0)
#define IS_EVEN() IS_EVEN_H(0)&&IS_EVEN_H(1)&&IS_EVEN_H(2)&&IS_EVEN_H(3)&&IS_EVEN_V(0)&&IS_EVEN_V(1)&&IS_EVEN_V(2)&&IS_EVEN_V(3)
#define PRT_LINE(i) cout<<tmp[i*4+0]<<","<<tmp[i*4+1]<<","<<tmp[i*4+2]<<","<<tmp[i*4+3]<<endl;
#define PRT(i)  cout<<"___"<<i++<<"____"<<endl;PRT_LINE(0);PRT_LINE(1);PRT_LINE(2);PRT_LINE(3)
void myapproach()
{
 int i=0;
 do {
  if(IS_EVEN())
  {
   PRT(i);
  }
  }while(next_permutation(tmp,tmp+16));
}
int main()
{
  myapproach();
 return 0;
}


 

2009/9/27 xiaosuo <xia...@gmail.com>

jinhu wang

unread,
Sep 27, 2009, 2:00:57 AM9/27/09
to pon...@googlegroups.com
我这里列了3种暴力方法:
  1. 递归
  2. 利用stl的求组合
  3. 利用16bit的数字算法
方法1和2区别在于求矩阵的方式。判断矩阵合法性的方式都一样
方法3是利用bit运算求矩阵及判断矩阵合法性
 
#include <iostream>
#include <bitset>

#include <algorithm>
using namespace std;

#define IS_EVEN_H(tmp,i) (tmp[i*4+0]^tmp[i*4+1]^tmp[i*4+2]^tmp[i*4+3]==0)
#define IS_EVEN_V(tmp,i) (tmp[i+0]^tmp[i+4]^tmp[i+8]^tmp[i+12]==0)
#define IS_EVEN(tmp) IS_EVEN_H(tmp,0)&&IS_EVEN_H(tmp,1)&&IS_EVEN_H(tmp,2)&&IS_EVEN_H(tmp,3)&&IS_EVEN_V(tmp,0)&&IS_EVEN_V(tmp,1)&&IS_EVEN_V(tmp,2)&&IS_EVEN_V(tmp,3)
#define PRT_LINE(tmp,i) cout<<tmp[i*4+0]<<","<<tmp[i*4+1]<<","<<tmp[i*4+2]<<","<<tmp[i*4+3]<<endl;
#define PRT(tmp,i)  cout<<"___"<<i++<<"____"<<endl;PRT_LINE(tmp,0);PRT_LINE(tmp,1);PRT_LINE(tmp,2);PRT_LINE(tmp,3)
//1递归
void recursiveApproach(int n, int m, int *p,int*pb)
{
 static int i=0;
 if(n==0)
 {
  for(int j=0;j<m;++j)
  {
   *(p+j)=1;
  }
  if(IS_EVEN(pb))
  {
   PRT(pb,i);
  };
  return;
 }
 for(int i=0;i<m-n+1;i+=1)
 {
  for(int j=0;j<i;++j)
  {
   *(p+j)=1;
  }
  *(p+i)=0;
  recursiveApproach(n-1,m-1-i,p+1+i, pb);
 }
 
}

//2利用stl的next_permutation
void myapproach(int *p)
{
 int i=0;
 do {
  //++ncount2;
  if(IS_EVEN(p))
  {
   PRT(p,i);
  }
 }while(next_permutation(p,p+16));
}
//3数字运算
int count_bits(unsigned short n)
{
    //0xAAAAAAAA,0x55555555分别是以“1位”为单位提取奇偶位
    n = ((n & 0xAAAA) >> 1) + (n & 0x5555);

    //0xCCCCCCCC,0x33333333分别是以“2位”为单位提取奇偶位
    n = ((n & 0xCCCC) >> 2) + (n & 0x3333);

    //0xF0F0F0F0,0x0F0F0F0F分别是以“4位”为单位提取奇偶位
    n = ((n & 0xF0F0) >> 4) + (n & 0x0F0F);

    //0xFF00FF00,0x00FF00FF分别是以“8位”为单位提取奇偶位
    n = ((n & 0xFF00) >> 8) + (n & 0x00FF);

    return n;
}
bool is_even_h(unsigned short n)
{
    n = ((n & 0xAAAA) >> 1) ^ (n & 0x5555);
    n = ((n & 0xCCCC) >> 2) ^(n & 0x3333);
    return (n==0);
}
bool is_even_v(unsigned short n)
{
    n = ((n & 0xF0F0) >> 4) ^ (n & 0x0F0F);
    n = ((n & 0xFF00) >> 8) ^ (n & 0x00FF);
    return (n==0);
}
bool is_even(unsigned short n)
{
 return is_even_h(n)&&is_even_v(n);
}

void W2Matrix()
{
 int i=0;
 for(int n=0x3ff;n<=0xff30;++n)
 {
  if(count_bits(n)==10
      &&is_even(n))
  {


   cout<<"___"<<i++<<"____"<<endl;

   cout<<bitset<4>(n>>12)<<endl<<bitset<4>(n>>8)<<endl<<bitset<4>(n>>4)<<endl<<bitset<4>(n)<<endl;
  }
 }
}
int main()
{


 int tmp[16]={0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1};

 int tmp2[16]={0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1};
  freopen("recursiveApproach.txt", "w", stdout);
 recursiveApproach(6,16,tmp,tmp);

  freopen("myapproach.txt", "w", stdout);
  myapproach(tmp2);
  freopen("countresult.txt", "w", stdout);
 W2Matrix();
 return 0;
}

jinhu wang

unread,
Sep 27, 2009, 2:12:16 AM9/27/09
to pon...@googlegroups.com
数字的那个int count_bits(unsigned short n)这个可以用bitset<16>(n).count()代替。又可以省几行代码。

2009/9/27 jinhu wang <wangji...@gmail.com>

Tongliang Zhu

unread,
Sep 26, 2009, 11:26:38 PM9/26/09
to pon...@googlegroups.com
"1.这个可以归纳为异或运算,4个4bit的数字,如果异或结果为1,就满足了你的要求。"
 
应该是异或结果为0吧。

2009/9/26 raymond <shiq...@gmail.com>

Wen YE

unread,
Sep 26, 2009, 11:50:51 PM9/26/09
to pon...@googlegroups.com
这样难以阅读的代码, 除了短, 哪里够的上 "简洁" 二字?
难道现在的公司里都喜欢这样 tricky 满地难以维护的代码风格了?

2009/9/27 jinhu wang <wangji...@gmail.com>

Tongliang Zhu

unread,
Sep 27, 2009, 4:07:45 AM9/27/09
to pon...@googlegroups.com
这几天一直在看大家对这个问题的解法,我也一直在思考,今天终于有了一个完整的思路,拿出来和大家分享下,如果有问题请多多指教。
 
我的思路是这样的,把每一行看成一个数,它的取值范围是0(0000) - 15(1111)。
要满足题目条件,有如下几条结论:
第一,每行1的个数为偶数个,这可以划分为3类:全0 - 0(0000),两个0两个1(0011,0101,0110,1001,1010,1100),全1 - 15(1111)
第二,必须有一行是全1-15(1111),因为只能替换6个1。
第三,因为要求每列1的个数为偶数,可以排除全0(0000)。
第四,综合前三条结论,发现最终只需要对 两个0两个1(0011,0101,0110,1001,1010,1100)这些数选择3个进行组合(但每个数可以重复选择),对组合后的结果求异或,结果为1的即满足要求。
第五,考虑全1行与第4中求出的3个数,可以有4中不同的位置组合(第4求出的3个数的相对位置不变)。所以在4中的结果数再乘以4就是所有的情况了。
 
思路清楚了,代码其实就非常简单了:
一个包含6个数的数组(0011,0101,0110,1001,1010,1100),进行3层嵌套循环,求异或。
2009/9/25 Jeff Chen <sheis...@gmail.com>
同事儿子的作业,大概意思是这样:

1 1 1 1

jinhu wang

unread,
Sep 27, 2009, 4:38:32 AM9/27/09
to pon...@googlegroups.com
是不是打印那个宏有点多余。其它的也说不上tricky吧。


 
2009/9/27 Wen YE <whus...@gmail.com>

Fei Yan

unread,
Sep 27, 2009, 8:59:58 AM9/27/09
to pon...@googlegroups.com
妙处在于next_permutation的应用,其它的都是宏,我觉得还是值得称道的。

起码一眼看过去知道大体是怎么来的,细节之处,只需要看宏就可以。
宏的名字起得也算比较清晰

2009/9/27 Wen YE <whus...@gmail.com>

Samuel Ji

unread,
Sep 27, 2009, 7:21:25 AM9/27/09
to pon...@googlegroups.com


2009/9/25 Jeff Chen <sheis...@gmail.com>
同事儿子的作业,大概意思是这样:

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

4*4,把其中6个1替换成0,使得横竖1的个数都是偶数,一共有几种,并打印出来.

我自己做了下,写得很烦.有没有高人有简洁一点的代码.

Python 3.1 (r31:73574, Jun 26 2009, 20:21:35) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> import itertools
>>> import functools
>>> N=4
因为每行0的个数是偶数个,
所以每行0的个数的排列应该是0,0,2,4或者0,2,2,2
又如果有两行全为1,一行全为0,则剩余一行中1所在列1的个数为奇数,所以可以排除
我们就可以先计算2,2,2的排列组合:
1.计算所有可能导致0的个数为2的组合
>>> def make_line1():
list=[]
for x in range(N):
for y in range(x+1,N):
list.append(1<<x | 1<<y)
return list

>>> lines = make_line1()
>>> lines
[3, 5, 9, 6, 10, 12]
2.第二行0的位置不能跟第一行全部相同,否则第三行上需要4个1;
也不能完全相反,否则第三行需要4个0
>>> def make_line2(x):
return [y for y in lines if y not in [x, 0b1111 & ~x]]

>>> make_line2(3)
[5, 9, 6, 10]
3.三行的异或结果必须为0b1111
>>> def make_line3(x, y):
return [z for z in lines if not functools.reduce(int.__xor__, (x,y,z), 0b1111)]

>>> make_line3(3,5)
[9]
4.生成所有可能的三行2,2,2组合
>>> def make_three_lines():
list = []
for x in lines:
for y in make_line2(x):
for z in make_line3(x, y):
list.append([x,y,z])
return list

>>> all_three_lines = make_three_lines()
>>> len(all_three_lines)
24
5.往每个可能的三行组合中任意插入一行1111就是一个符合条件的四行结果
>>> def make_all_lines():
list = []
for three_lines in all_three_lines:
for i in range(N):
temp = three_lines[:]
temp.insert(i, 0b1111)
list.append(temp)
return list

>>> all_lines = make_all_lines()
>>> len(all_lines)
96
6.打印处所有组合
>>> def print_all_lines():
for lines in all_lines:
print('{0:04b}, {1:04b}, {2:04b}, {3:04b}'.format(*lines))

>>> print_all_lines()
1111, 0011, 0101, 1001
0011, 1111, 0101, 1001
0011, 0101, 1111, 1001
0011, 0101, 1001, 1111
1111, 0011, 1001, 0101
0011, 1111, 1001, 0101
0011, 1001, 1111, 0101
0011, 1001, 0101, 1111
1111, 0011, 0110, 1010
0011, 1111, 0110, 1010
0011, 0110, 1111, 1010
0011, 0110, 1010, 1111
1111, 0011, 1010, 0110
0011, 1111, 1010, 0110
0011, 1010, 1111, 0110
0011, 1010, 0110, 1111
1111, 0101, 0011, 1001
0101, 1111, 0011, 1001
0101, 0011, 1111, 1001
0101, 0011, 1001, 1111
1111, 0101, 1001, 0011
0101, 1111, 1001, 0011
0101, 1001, 1111, 0011
0101, 1001, 0011, 1111
1111, 0101, 0110, 1100
0101, 1111, 0110, 1100
0101, 0110, 1111, 1100
0101, 0110, 1100, 1111
1111, 0101, 1100, 0110
0101, 1111, 1100, 0110
0101, 1100, 1111, 0110
0101, 1100, 0110, 1111
1111, 1001, 0011, 0101
1001, 1111, 0011, 0101
1001, 0011, 1111, 0101
1001, 0011, 0101, 1111
1111, 1001, 0101, 0011
1001, 1111, 0101, 0011
1001, 0101, 1111, 0011
1001, 0101, 0011, 1111
1111, 1001, 1010, 1100
1001, 1111, 1010, 1100
1001, 1010, 1111, 1100
1001, 1010, 1100, 1111
1111, 1001, 1100, 1010
1001, 1111, 1100, 1010
1001, 1100, 1111, 1010
1001, 1100, 1010, 1111
1111, 0110, 0011, 1010
0110, 1111, 0011, 1010
0110, 0011, 1111, 1010
0110, 0011, 1010, 1111
1111, 0110, 0101, 1100
0110, 1111, 0101, 1100
0110, 0101, 1111, 1100
0110, 0101, 1100, 1111
1111, 0110, 1010, 0011
0110, 1111, 1010, 0011
0110, 1010, 1111, 0011
0110, 1010, 0011, 1111
1111, 0110, 1100, 0101
0110, 1111, 1100, 0101
0110, 1100, 1111, 0101
0110, 1100, 0101, 1111
1111, 1010, 0011, 0110
1010, 1111, 0011, 0110
1010, 0011, 1111, 0110
1010, 0011, 0110, 1111
1111, 1010, 1001, 1100
1010, 1111, 1001, 1100
1010, 1001, 1111, 1100
1010, 1001, 1100, 1111
1111, 1010, 0110, 0011
1010, 1111, 0110, 0011
1010, 0110, 1111, 0011
1010, 0110, 0011, 1111
1111, 1010, 1100, 1001
1010, 1111, 1100, 1001
1010, 1100, 1111, 1001
1010, 1100, 1001, 1111
1111, 1100, 0101, 0110
1100, 1111, 0101, 0110
1100, 0101, 1111, 0110
1100, 0101, 0110, 1111
1111, 1100, 1001, 1010
1100, 1111, 1001, 1010
1100, 1001, 1111, 1010
1100, 1001, 1010, 1111
1111, 1100, 0110, 0101
1100, 1111, 0110, 0101
1100, 0110, 1111, 0101
1100, 0110, 0101, 1111
1111, 1100, 1010, 1001
1100, 1111, 1010, 1001
1100, 1010, 1111, 1001
1100, 1010, 1001, 1111
 

xiaosuo

unread,
Sep 27, 2009, 11:56:50 AM9/27/09
to TopLanguage
提前剪枝的算法,确实就是3皇后问题加便利print

#include <stdio.h>

void print_row(unsigned char bitpos, int colum)
{
int i, ci;

ci = 0;
for (i = 0; i < 4; i++) {
if (i == colum || (ci++) == bitpos)
printf(" 1");
else
printf(" 0");
}
printf("\n");

}

void print_instance(unsigned char *bitpos, int row, int colum)
{
int i, ri;
static int count = 0;

printf("\nnumber: %d\n", ++count);
ri = 0;
for (i = 0; i < 4; i++) {
if (i == row)
printf(" 1 1 1 1\n");
else
print_row(bitpos[ri++], colum);
}
}

void print_matrix(unsigned char *bitpos)
{
int i, j;

for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++)
print_instance(bitpos, i, j);
}
}

int main(int argc, char *argv[])
{
int i, j, k;
int mask;
unsigned char bitpos[3];

for (i = 0; i < 3; i++) {
bitpos[0] = i;
mask = 1 << i;
for (j = 0; j < 3; j++) {
if (mask & (1 << j))
continue;
bitpos[1] = j;
mask |= 1 << j;
for (k = 0; k < 3; k++) {
if (mask & (1 << k))
continue;
bitpos[2] = k;
print_matrix(bitpos);
}
mask &= ~(1 << j);
}
}

return 0;
}

jinhu wang

unread,
Sep 27, 2009, 9:39:38 PM9/27/09
to pon...@googlegroups.com
又想到一个方法,还是用c++:
这个的思路是每个存储单元是1个字节,则连续的字节可以作为一个long。竖向累加的时候可以直接把四个long型变量直接进行运算得结果,横向的计算没有想到好办法,直接用的bitset算bit位。
#include <numeric>
#include <iostream>
#include <bitset>

#include <algorithm>
using namespace std;

void prtbt(unsigned char b)
{
 printf("%d ",b);
}
void prtdw(unsigned long dw)
{
 unsigned char*pbt =(unsigned char*)&dw;
 for_each(pbt,pbt+4,prtbt);
 printf("\n");
}
void ByteDwordSolution()
{
 int count = 0;

 unsigned char v1[16]={0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1};
 unsigned long *pdw =(unsigned long *)v1;

 do {
  if((pdw[0]^pdw[1]^pdw[2]^pdw[3]==0)
      &(bitset<32>(pdw[0]).count()%2==0)
      &(bitset<32>(pdw[1]).count()%2==0)
      &(bitset<32>(pdw[2]).count()%2==0)
      &(bitset<32>(pdw[0]).count()%2==0))
  {
   cout<<"......."<<++count<<"...."<<endl;
   for_each(pdw,pdw+4,prtdw);
  }

 }while(next_permutation(v1,v1+16));
 
}


2009/9/27 Wen YE <whus...@gmail.com>

jinhu wang

unread,
Sep 27, 2009, 10:06:49 PM9/27/09