- 论坛徽章:
- 145
|
本帖最后由 jason680 于 2017-06-25 09:14 编辑
回复 6# sunzhiguolu
#穷举法 优化
$ time perl 3x3sum15.pl
2 7 6
9 5 1
4 3 8 count=1
2 9 4
7 5 3
6 1 8 count=2
4 3 8
9 5 1
2 7 6 count=3
4 9 2
3 5 7
8 1 6 count=4
6 1 8
7 5 3
2 9 4 count=5
6 7 2
1 5 9
8 3 4 count=6
8 1 6
3 5 7
4 9 2 count=7
8 3 4
1 5 9
6 7 2 count=8
real 0m0.044s
user 0m0.024s
sys 0m0.004s
#穷举法 无优化
注：这是训练思路过程...
编程则须再提高...
$ time perl 3x3sum15.pl
2 7 6
9 5 1
4 3 8 count=1
...
8 3 4
1 5 9
6 7 2 count=8
real 16m16.779s
user 16m0.012s
sys 0m0.744s
$ cat 3x3sum15.pl
#
use strict;
use warnings;
# array
# [0, 1, 2]
# [3, 4, 5]
# [6, 7, 8]
my $sCnt = 0;
for my $x0 (1..9){
for my $x1 (1..9){
#next if($x0 + $x1 < 6);
#next unless(unique($x0,$x1));
for my $x2 (1..9){
#...
for my $x3 (1..9){
#...
for my $x4 (1..9){
#...
for my $x5 (1..9){
#...
for my $x6 (1..9){
#...
for my $x7 (1..9){
#...
for my $x8 (1..9){
#...
if(check_3x3($x0, $x1, $x2, $x3, $x4, $x5, $x6, $x7, $x8)){
++$sCnt;
print "$x0 $x1 $x2\n$x3 $x4 $x5\n$x6 $x7 $x8 count=$sCnt\n";
}
}
}
}
}
}
}
}
}
}
sub unique{
my %hNum;
for(@_){ return 0 if(++$hNum{$_}>1)}
return 1;
}
sub sum{
my $sRet=0;
$sRet += $_ for @_;
return $sRet;
}
sub check_3x3{
return 0 unless(unique(@_));
# [0]+[1]+[2] = [3]+[4]+[5] = [6]+[7]+[8] = 15
return 0 if(sum(@_[0, 1, 2]) != 15);
return 0 if(sum(@_[3, 4, 5]) != 15);
return 0 if(sum(@_[6, 7, 8]) != 15);
# [0]+[3]+[6] = [1]+[4]+[7] = [2]+[5]+[8] = 15
return 0 if(sum(@_[0, 3, 6]) != 15);
return 0 if(sum(@_[1, 4, 7]) != 15);
return 0 if(sum(@_[2, 5, 8]) != 15);
# [0]+[4]+[8] = [2]+[4]+[6] = 15
return 0 if(sum(@_[0, 4, 8]) != 15);
return 0 if(sum(@_[2, 4, 6]) != 15);
return 1;
}
|
|
免费注册
发表于 2017-06-24 23:34