2

警告：Project Euler 问题 1 剧透

我最近发现了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，所以解决方案越多越好。

提前致谢。

4

2 回答 2

6

直截了当的方法

为了回答您的问题，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
于 2013-06-03T01:36:53.093 回答
5

不太简洁，但速度更快：

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因此需要减去 。

于 2013-06-03T01:37:04.013 回答