试图找出是否有更短/更好的方法来实现类似条件和的函数

Question

警告:Project Euler Problem 1 Spoiler

我最近发现了Project Euler,并决定尝试一些问题.第一个问题是将0-999之间的数字相加,即3或5的倍数.

我的第一个"类似java"的解决方案是:

print threeAndFive(1000)."\n";

# Returns the sum of the numbers less than $max that are multiples of 3 or 5
sub threeAndFive
{
    my $max = shift;
    my $sum = 0;

    for (my $i=; $i < $max; $i++)
    {
        $sum+=$i if (validate($i)); 
    }   

    return $sum;
}

sub validate
{
    my $num = shift;

    if ($num % 3 == 0 || $num % 5 == 0)
    {
        return 1;
    }

    return undef;
}

然后我以更流行的方式重写它:

print eval(join ('+', map {($_ % 3 == 0 || $_ % 5 == 0) ? $_ : ()} (1 .. 999)));

虽然这显然比原始代码更简洁,但我觉得它可能更短或以更好的方式完成.例如,在Python中,可以做到:

print sum([i for i in range(1,1000) if i%3==0 or i%5==0])

是否有更简洁/更好/更清晰的方法来做到这一点？或者使用不同功能的其他等效方式？我有兴趣学习尽可能多的perl,所以解决方案越多越好.

提前致谢.

Answer 1

直截了当的方法

要回答您的问题,List :: Util提供sum.

use List::Util qw( sum );

或者你可以写自己的

sub sum { my $acc; $acc += $_ for @_; $acc }

然后你得到:

say sum grep { $_ % 3 == 0 || $_ % 5 == 0 } 0..999;

当然,这是一种未被优化的方法.

优化方法

您可以使用计数循环轻松地将上述内容从Ω(N)减少到Ω(1)内存.

my $acc;
for (1..999) { $acc += $_ if $_ % 3 == 0 || $_ % 5 == 0; }
say $acc;

但这远远不是最好的,因为结果可以在Ω(1)时间和内存中获得!

这是通过将3的倍数之和加到5的倍数之和,然后减去15的倍数之和来实现的,因为可以使用$ x的倍数之和来计算

( sum 1..floor($n/$x) ) * $x    # e.g. 3+6+9+... = (1+2+3+...)*3

这可以利用这个公式

sum 1..$n = $n * ($n+1) * 0.5

Answer 2

简洁但更快:

sub sum1toN { my $N = int(shift); ($N * ($N+1)) / 2; }
my $N = 999;
print sum1toN($N/3)*3 + sum1toN($N/5)*5 - sum1toN($N/15)*15, "\n";

该sum1toN函数计算从1到N的整数之和.

以来:

3 + 6 + 9 + 12 ... + 999

等于:

(1 + 2 + 3 + ... 333 ) * 3

我们可以使用计算3的倍数之和sum1toN(N/3) * 3.这同样适用于5.注意,由于我们在两种情况下都计算了15的倍数,sum1toN(N/15)*15因此需要减法.