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

14 views

### Jeff Chen

Sep 24, 2009, 9:53:19 PM9/24/09

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

### @@

Sep 24, 2009, 10:16:02 PM9/24/09

2009/9/25 Jeff Chen

### Jeff Chen

Sep 24, 2009, 10:17:42 PM9/24/09

2009/9/25 @@

### @@

Sep 24, 2009, 10:19:03 PM9/24/09

2009/9/25 Jeff Chen

### @@

Sep 24, 2009, 10:24:02 PM9/24/09

2009/9/25 @@

### Jiyong Xu

Sep 24, 2009, 10:25:01 PM9/24/09
1111
1100
1010
1001

### xxmplus

Sep 24, 2009, 10:27:59 PM9/24/09

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

### Jeff Chen

Sep 24, 2009, 10:28:33 PM9/24/09

2009/9/25 Jiyong Xu
1111
1100
1010
1001

### Jiyong Xu

Sep 24, 2009, 10:30:49 PM9/24/09

### @@

Sep 24, 2009, 10:32:41 PM9/24/09

2009/9/25 Jeff Chen

### Jeff Chen

Sep 24, 2009, 10:33:16 PM9/24/09

1111
1111
1100
0000

2009/9/25 Jiyong Xu

### Jeff Chen

Sep 24, 2009, 10:34:31 PM9/24/09

2009/9/25 Jeff Chen

### Jiyong Xu

Sep 24, 2009, 10:35:42 PM9/24/09
1111
1111
1100
0000

1111
1100
1010
1001

2009/9/25 Jeff Chen
1111
1111
1100
0000

### Hongzhang Liu

Sep 24, 2009, 10:46:07 PM9/24/09
10个1，只可能是4+2+2+2

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

### Jeff Chen

Sep 24, 2009, 10:51:23 PM9/24/09

2009/9/25 Hongzhang Liu

### Bruce Khereid

Sep 24, 2009, 11:23:12 PM9/24/09

2009/9/25 Jeff Chen

### arri...@gmail.com

Sep 24, 2009, 11:32:12 PM9/24/09

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}"

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

### 许海斌

Sep 24, 2009, 11:41:46 PM9/24/09
to TopLanguage

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

### @@

Sep 24, 2009, 11:41:31 PM9/24/09

2009/9/25 Bruce Khereid

### Jeff Chen

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

2009/9/25 @@
Message has been deleted

### @@

Sep 25, 2009, 12:08:50 AM9/25/09
java自己写combination就费事不少吧

2009/9/25 Jeff Chen

### Li Yang

Sep 24, 2009, 10:28:54 PM9/24/09
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1

0000
0000
0000
0000

2009/9/25 Jiyong Xu
1111
1100
1010
1001

--
While(!success=try())

### zong

Sep 24, 2009, 10:53:24 PM9/24/09

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

2009/9/25 Hongzhang Liu

--

### Wen YE

Sep 24, 2009, 11:25:33 PM9/24/09
1111
1100
1010
1001

#include <stdio.h>

int allcount = 0;
// check bits in mask fit or not
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
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

Sep 24, 2009, 11:27:01 PM9/24/09

2009/9/25 Wen YE

### Little Push

Sep 25, 2009, 1:33:24 AM9/25/09

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

6×4×2=48

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

0 0 1
0 1 0
1 0 0

C的实现比较烦哎……

--
Push Chen
SNDA
SDO Project Management Department
Curie Rd. 208
Shanghai, China
Mobile: +8613524446040
Tel: 50504740-1796

2009/9/25 @@

### Little Push

Sep 25, 2009, 1:35:05 AM9/25/09

2009/9/25 Li Yang

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

### Little Push

Sep 25, 2009, 1:35:44 AM9/25/09

--
Push Chen
SNDA
SDO Project Management Department
Curie Rd. 208
Shanghai, China
Mobile: +8613524446040
Tel: 50504740-1796

2009/9/25 Wen YE

### Little Push

Sep 25, 2009, 1:38:52 AM9/25/09
2009/9/25 zong

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

### Wen YE

Sep 25, 2009, 1:41:20 AM9/25/09

2009/9/25 Li Yang

### Little Push

Sep 25, 2009, 2:32:07 AM9/25/09

0000——0
0001——1
0010——2
0011——3
....

0x3, 0x5, 0x6, 0x9, 0xA, 0xC, 0xF共7种（全0的必然不会出现）

{ 0x3, 0x5, 0x9, 0xF }
{ 0x3, 0x6, 0xA, 0xF }
{ 0x5, 0x6, 0xC, 0xF }
{ 0x9, 0xA, 0xC, 0xF }

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

2009/9/25 Little Push

### Alecs King

Sep 25, 2009, 4:50:13 AM9/25/09
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

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

Sep 25, 2009, 4:51:49 AM9/25/09
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

Sep 25, 2009, 4:55:50 AM9/25/09
python的没结果...

2009/9/25 Alecs King

### @@

Sep 25, 2009, 4:58:00 AM9/25/09

2009/9/25 Jeff Chen

### Wen YE

Sep 25, 2009, 3:23:15 AM9/25/09

2009/9/25 Little Push

### Li Yang

Sep 25, 2009, 5:00:07 AM9/25/09

2009/9/25 Alecs King

--
While(!success=try())

### Li Yang

Sep 25, 2009, 5:02:21 AM9/25/09

2009/9/25 Jeff Chen

--
While(!success=try())

### Alecs King

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

### Alecs King

Sep 25, 2009, 6:34:33 AM9/25/09
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

Sep 25, 2009, 5:47:59 AM9/25/09

2009/9/25 Wen YE

### Lyman

Sep 25, 2009, 8:30:00 AM9/25/09
Jeff Chen 写道:
> ruby的代码真简洁啊，我用java写的，同样是暴力求解，复杂多了

#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;
}

>

>
> 穷举了下 是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

Sep 25, 2009, 11:05:53 AM9/25/09
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

Sep 25, 2009, 11:20:32 AM9/25/09

#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

1 1 1 1

### 黑眼猪

Sep 26, 2009, 3:03:39 AM9/26/09

2009/9/25 lostyzd

### raymond

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

2. 现在问题变成了，共有多少种可能的组合呢？就是16个bit中选择6个就行了，配合适当的减枝，速度会很快的。

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

> 1 1 1 11 1 1 1

### xiaosuo

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

Sep 26, 2009, 11:39:17 PM9/26/09
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

### jinhu wang

Sep 27, 2009, 2:00:57 AM9/27/09

1. 递归
2. 利用stl的求组合
3. 利用16bit的数字算法

#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

Sep 27, 2009, 2:12:16 AM9/27/09

2009/9/27 jinhu wang

### Tongliang Zhu

Sep 26, 2009, 11:26:38 PM9/26/09
"1.这个可以归纳为异或运算，4个4bit的数字，如果异或结果为1，就满足了你的要求。"

2009/9/26 raymond

### Wen YE

Sep 26, 2009, 11:50:51 PM9/26/09

2009/9/27 jinhu wang

### Tongliang Zhu

Sep 27, 2009, 4:07:45 AM9/27/09

2009/9/25 Jeff Chen

1 1 1 1

### jinhu wang

Sep 27, 2009, 4:38:32 AM9/27/09

2009/9/27 Wen YE

### Fei Yan

Sep 27, 2009, 8:59:58 AM9/27/09

2009/9/27 Wen YE

### Samuel Ji

Sep 27, 2009, 7:21:25 AM9/27/09

2009/9/25 Jeff Chen

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
>>> import itertools
>>> import functools
>>> N=4

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;

>>> 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

Sep 27, 2009, 11:56:50 AM9/27/09
to TopLanguage

#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;
unsigned char bitpos[3];

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

return 0;
}

### jinhu wang

Sep 27, 2009, 9:39:38 PM9/27/09

#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