在Top Languange上看到：
同事儿子的作业，大概意思是这样:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 14*4,把其中6个1替换成0,使得横竖1的个数都是偶数,一共有几种，并打印出来.
偶用的穷举法，答案是96。 以下是Python代码：
N = 4
def int2b(n, bit=N*N):
return [(n >> i) & 1 for i in range(bit)[::-1]]
def check(L):
for i in range(N):
if sum(L[i::N]) % 2 or sum(L[i*N:i*N+N]) % 2:
return 0
return 1
count = 0
for i in xrange(1<<N*N):
L = int2b(i)
if sum(L) == 10 and check(L):
print '\n'.join([' '.join(map(str,L)[i::N]) for i in range (N)])
print '-------'
count += 1
print count
看到有人写的Python代码只要300多字符，我写的为啥要400+，伤心了。。
以下文章也许和本文有点关系：
那年今天:- 2008 ： 两种编程-兼论生物背景研究生物信息学的优势
- 2008 ： Advanture on the Chesapeake Bay
(还没人喜欢）
Loading ...
7条留言 跳到评论框
过来学习。呵呵。。我试试用Perl写一个看看
[回复这条留言]
好复杂阿~~ 真是要花心思了。！
[回复这条留言]
其实就是个排列组合问题，不用脑的话就穷举吧
[回复这条留言]
(1)6个0分布于四行,只能是4+2+0+0或2+2+2+0=>必有一行全为1;
(2)同理,必有一列全为1.
(1)(2)=>只能是2+2+2+0.
先剔除全为1的行和列,要保证每行/列只有一个1:
1 1 1 1 0 0
1 1 1 –> 0 1 0
1 1 1 0 0 1
第3列的位置的1由前两列决定,
所以一共A(3,2)=6种;
再插入一行和一列全1, 共4*4=16种.
所有一共6*16=96种:)
ps:本文中代码的行宽超过了的宽度…在firefox3.5.3和IE8下面都是越界显示,有点乱,怎么让它们自动换行而不产生歧义呢,嘿嘿 :p
[回复这条留言]
偶把代码改了下。。
ms没有自动转换的好方法，因为python代码如果一行写不下要在行尾加 \
[回复这条留言]
你肯定不是用的firefox或者你的显示屏很大^_^
[回复这条留言]
我用的firefox，22寸显示屏
[回复这条留言]
数值赋值比穷举运算会快很多,如:
#!/usr/bin/perl -w
use strict;
my @a=(0,1,2,3);
my @matrix=([0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]);
my @combo=([1,0,0],[0,1,0],[0,0,1]);
my @D=([0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]);
my $count=0;
foreach my $i (@a) {
foreach my $j (@a) {
my @out=@matrix;
@{$out[$i]}=(1,1,1,1);
map{$_->[$j]=1}@out;
my @B=@a;
my @C=@a;
splice(@B,$i,1);
splice(@C,$j,1);
for (my $k=0;$k<@D ;$k++) {
my $m=0;
foreach my $x(@B) {
my $y=$D[$k][$m];
$m++;
@{$out[$x]}[@C]=@{$combo[$y]};
}
$count++;
print “——– $count\n”;
foreach (@out) {
print join ” “,@$_,”\n”;
}
}
}
}
[回复这条留言]
快得多到没有啊
我的代码运行只要0.2秒左右
[回复这条留言]
这个算法的时间复杂度2^(N*N)，还是相当恐怖的
时间短是因为N的数很小
[回复这条留言]
那倒是。。N=5我猜要运行个几天了。。
[回复这条留言]
for i in xrange(1<<N*N):
这句的<<是什么意思呢?
有个问题想不通~~
[回复这条留言]
其实就是移位运算，相当于二进制的1后面加上N*N个0，就是2的N*N次方
啥问题想不通？
[回复这条留言]
~ 已经有人把perl的贴出来了~
虽然思路不大一样。。先去借鉴学习先~~ 再想不通再来问你阿。
呵呵
[回复这条留言]
我也想做一个你这样的个人博客网站。
能教教我吗？
怎么申请域名之类？
[回复这条留言]
你要先去买个域名，通常10美元一年，然后再买个空间，最好买国外的。。
或者你可以用我们的空间，只要买个域名就好。
再或者，你不介意的话，可以用我这个站的子域名，xxx.azpala.com这种。
[回复这条留言]
我找到了一个申请域名的网站，需要paypal才能付款。我没有visa的卡，还得去申请一个visa。
请问你们的空间是哪里买的？你们几个人合用吗？像你们这样的空间大约要花多少费用呢？
如果加入你们的空间或者用你的子域名，管理方不方便呢？比如密码之类的？
[回复这条留言]
我们是lunapages的空间，我和我老公以及几个朋友在用，一年100多美元，独立IP，无限空间，无限流量，只是CPU有限制。
你可以免费加我们的空间，想个用户名就行，你可以自己改密码的。
visa卡应该满好申请的，建设银行，招商银行都有学生信用卡。
[回复这条留言]
lunapages的,速度不错哦~~价格也满便宜哦
我过段时间也换国外的了,MediaTemple的
[回复这条留言]
好的，明天去申请一个visa的。
[回复这条留言]
今天去申请visa被打击了。招商貌似五万起存。其它银行都得出示收入证明，至少也要父母的签字。
VISA被银联打击得好厉害啊。
如果我通过国内的代理商（如万网）申请一个域名，解析到国外的空间速度会受影响吗？
[回复这条留言]
速度不是很清楚, 但如果你以后想把域名转出的话 用国内代理会非常麻烦(貌似有人被千方百计阻挠过). 我个人是很不信任国内代理的. Godaddy这种提供商, 无论是域名转出或是续费, 或是添加记录到blogger等目前被x的网站上都非常方便. 现在这种环境下, 说不给你解析了, 你一点办法都没有. 最好是找个周围有信用卡的朋友帮你买, 一时麻烦, 以后省事.
[回复这条留言]
return [(n >> i) & 1 for i in range(bit)[::-1]]
这句话是什么意思呢?
如何保证不重复呢?
[回复这条留言]
这个函数就是输入一个整数，转换成二进制整数各个位置构成的一个链表，保留最后N=bit位
比如 int2b(4,6)，就是把整数4转换成有6位的二进制整数，结果是[0,0,0,1,0,0]
[回复这条留言]
这个好强大~ 原来你都是用二进制的. 不错..我也先去学习一下perl的这方面内容先..
[回复这条留言]
这个是受到原帖里面一个人贴的python代码的启发，不过这道题题目里只有0,1，还是很容易想到二进制的
[回复这条留言]
那是,呵呵.我这笨脑袋才没想到.. 多亏了你的帮助,我已经用perl的穷举法解答出来了. 还是实践一下才能学得快阿
[回复这条留言]
1 条Trackback
[...] 原题是在 azalea says 的博客看到的，她是用Python的穷举法解答出来的，Python我是不懂的了，有兴趣的你就过去围观吧。一道小学数学题。 [...]