魔方分割数
Posted feedbacks - Perl
#4835ほぼそのまま移植(違いは進捗をprintするぐらい)ですが、こんなになりましたorz。
2316.28 real 2312.21 user 1.48 sys
もう少し工夫しないとだめですね、こりゃ。
Dan the Perl Monger
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #!/usr/local/bin/perl
use strict;
use warnings;
my @bits;
my $n = shift || 3;
my $n2 = $n * $n;
my $cnt = 0;
sub comb {
my ($a, $k, $s, $b) = @_;
if ($k < $n-1){
comb($_+1, $k+1, $s-$_, $b|1<<($_+1)) for ($a .. $n2-1);
}else{
push @bits, $b|1<<($s+1) if $a <= $s && $s <= $n2;
}
}
sub calc{
my ($s, $k, $b) = @_;
if ($k == $n){
printf "%d\r", $cnt++;
return;
}
for my $i ($s..@bits-1){
next if $b & $bits[$i];
calc($i, $k+1, ($b | $bits[$i]));
}
}
comb(1, 0, ($n * ($n2+1) / 2), 0);
@bits = sort {$a <=> $b} @bits;
calc(0, 0, 0);
print "$cnt\n";
|
xsd
#4702()
Rating8/8=1.00
たとえば、N=3のときは、
(1) { 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }
(2) { 1, 6, 8 }, { 2, 4, 9 }, { 3, 5, 7 }
の2通りの方法があります。
ここで指定されたNに対して、何通りのグループ分けの方法があるかを数えるプログラムを作ってください。
(何通りかという値だけが出力されればよいのですが、予め計算してある結果を返すのはダメですよ。)
また、N=5を指定したときの実行時間もあわせて教えてください。
なお、数え上げるときの注意として、
・{ 1, 5, 9 } と { 1, 9, 5 }は同じもの
・{ 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }と
{ 1, 5, 9 }, { 3, 4, 8 }, { 2, 6, 7 }は同じもの
とすることに注意してください。
[ reply ]