到知乎上回答了…… 感觉在班门弄斧
递归低效率版,Perl
my @init = (0, 0, 0, 0, 0, 0); #初始值
our @e = (1999, 1299, 1499, 2799, 2499, 3299); #系数
our @limit = (607, 534, 60, 660, 100, 209); #范围
our $check = 2328450; #校验
func( \@init, 0 );
sub func
{
our @e;
our @limit;
our $check;
my ($ref, $lv) = (shift, shift);
if ($lv <= $#$ref)
{
for my $n ( 0 .. $limit[$lv] )
{
$ref->[$lv] = $n;
func( $ref, $lv+1 );
}
}
else
{
my $sum = 0;
for my $idx ( 0 .. $#$ref )
{
$sum += $ref->[$idx] * $e[$idx];
}
if ($sum == $check)
{
print join(", ", @$ref), "\n";
}
}
}
暴力6层循环,C语言版
#include <stdio.h>
int main(int argc, char *argv[])
{
long a,b,c,d,e,f;
long limit[6] = {607, 534, 60, 660, 100, 209};
long coe[] = {1999, 1299, 1499, 2799, 2499, 3299};
long sum;
for (a = 0; a <= limit[0]; a++ ) {
for (b = 0; b <= limit[1]; b++ ) {
for (c = 0; c <= limit[2]; c++ ) {
for (d = 0; d <= limit[3]; d++ ) {
for (e = 0; e <= limit[4]; e++ ) {
for (f = 0; f <= limit[5]; f++ ) {
sum = a*coe[0] + b*coe[1] + c*coe[2] +
d*coe[3] + e*coe[4] + f*coe[5];
if (sum == 2328450)
{
printf("%d %d %d %d %d %d\n", a,b,c,d,e,f);
}
}}}}}}
return 0;
}
6层循环,批处理版
代码: 全选
@echo off &setlocal enabledelayedexpansion
set var=a b c d e f
set /a a=607, b=534, c=60, d=660, e=100, f=209
set /a exp=0, check=2328450
for %%x in ( %var% ) do (
set fo="for /l %%%%x in (0, 1, !%%x!) do (!fo!"
set end="!end!)"
set exp= !exp! + %%%%x
set echo=!echo! %%%%x
)
%fo:"=%
set /a sum = %exp%
if "!sum!" == "%check%" (
echo %echo%
)
%end:"=%
pause
分而治之,Perl版
our $check = 2328450; #校验
our @limit = (607, 534, 60, 660, 100, 209); #范围
our @e = (1999, 1299, 1499, 2799, 2499, 3299); #系数
my $sum;
my %hash;
print "step1\n";
for my $a ( 0 .. $limit[0] )
{
for my $b ( 0 .. $limit[1] )
{
for my $c ( 0 .. $limit[2] )
{
$sum = $a * $e[0] + $b * $e[1] + $c * $e[2];
$hash{$sum} = [$a, $b, $c];
}
}
}
print "step2\n";
my $part1;
my $part2;
open $WRT, ">:raw", "D:/Result.txt";
for my $d ( 0 .. $limit[3] )
{
for my $e ( 0 .. $limit[4] )
{
for my $f ( 0 .. $limit[5] )
{
$part2 = $d * $e[3] + $e * $e[4] + $f * $e[5];
$part1 = $check - $part2;
if ( exists $hash{$part1} )
{
print $WRT join( ", ", @{ $hash{$part1} }, $d, $e, $f );
print $WRT "\n";
}
}
}
}
close $WRT;
<STDIN>;
i7,用时约40秒,输出282,819 KB大小的文件。
这里有一个疏忽,
$sum = $a * $e[0] + $b * $e[1] + $c * $e[2];
$hash{$sum} = [$a, $b, $c];
$sum 可能是相同的值,从而忽略了一些不同情况下的 a b c ,保存所有情况下的a b c,提示 out of memory。虽然可以保存到文件,然后建立索引。。。