C ++中的Euler 001项目

#include <iostream>

#define UPPER_BOUND 1000

int main() {
    int sum = 0;

    for (int i = 1; i < UPPER_BOUND; ++i) {
        if (i % 3 == 0 || i % 5 == 0) {
            sum += i;
        }
    }

    std::cout << "The sum of the natural numbers below " << UPPER_BOUND << " that are multiples of 3 and 5 is " << sum;

    return 0;
}

#1 楼

constexpr一切

除了#define之外，您的代码还不错。但是您没有使用constexpr错过了一个真正简单的优化，constexpr variables在不同的上下文中具有不同的含义：

constexpr functions是编译时常量。如果常量的参数在编译时已知，则它们可以在编译时执行；如果它们的参数在编译时已知，则它们可以很好地替代常量定义的宏。然后编译器将常量替换为代码中的函数调用。

所以让我们从main()中提取一个函数并声明为constexpr：

#define UPPER_BOUND 1000 // bad, because preprocessing leads to a lot of bugs
constexpr int upper_bound = 1000; // good, safe

现在，每当在编译时使用已知的upper_bound调用它时，它将在编译时运行。

将代码通用化

在以下位置运行函数编译时意义重大，因为如果不能，并且需要代码在运行时快速运行，则必须实现更好的算法。正如@Dannnno指出的那样，您可以使用该算法来计算算术级数，对于您的代码，它是O(1)而不是O(n)：

constexpr int sum_of_multiples_of_3_and_5_under(int upper_bound) {
    int sum = 0;
    for (int i = 1; i < upper_bound; ++i) {
        if ( i % 3 == 0 || i % 5 == 0 ) {
            sum += i;
        }
    }
    return sum;
}

然后您可以计算3和5的倍数之和与：

constexpr int sum_multiples_under(int ratio, int upper_bound) {
    int nb_val = (upper_bound - 1) / ratio;
    int high = nb_val * ratio;
    int extremes = ratio + high;
    return nb_val * extremes / 2;
}

即使它比for -loop消耗了更多的脑力，它也很容易实现。但是，假设我们要泛化我们的代码，并使它适用于任意数量的除数，例如3、5和7的倍数之和。这将变得更加困难：您必须添加一个的所有成员集合，然后减去两个集合的所有成员，然后相加三个集合的所有成员...等等。这意味着计算组合，将函数应用于排列等。而我们的for -loop可以轻松缩放。

使用折叠表达式

通过折叠表达式（需要C ++ 17），您可以相当轻松地泛化代码：

auto sum = sum_multiples_under(3,  1000)
         + sum_multiples_under(5,  1000)
         - sum_multiples_under(15, 1000);

Multiples是可变参数模板参数。它可以代表任意数量的参数。然后，您可以在函数内部扩展参数的包。折叠表达式使您可以在运算符周围展开它。在这种情况下，运算符为||。 ( ... || (i % multiples == 0))将扩展为：

template <typename... Multiples>
constexpr int sum_of_multiples_under(int upper_bound, Multiples... multiples) {
    int sum = 0;
    for (int i = 1; i < upper_bound; ++i) {
        if ( ( ... || (i % multiples == 0)) ) {
            sum += i;
        }
    }
    return sum;
}

结论

constexpr是一个非常非常有用的关键字，并且是现代，优化的C ++的标志。码。无节制地使用它。如果您想了解所有相关信息，YouTube上有一个主题演讲，名为“ constexpr everyting”。

#2 楼

我不是在专注于算法，而是在C ++惯用语上。


非常好的陈述了您想要的东西。太好了！

我建议您熟悉Bjarne Stroustrup和Herb Sutter分类的核心准则。

#define UPPER_BOUND 1000

不要使用#define用于常量或“函数”（⧺ES.31）。

这是古代C ++首次出现在表中的内容之一！我们得到了const和inline而不是#define所遇到的所有问题。

即使使用前缀增量，循环本身也足够响亮。您将需要其他（非std）库来使用range-for编写整洁的代码。

但是，您根本不应该编写循环！ Stroustrup的视频会说：“不要“编写代码”，请使用算法。”您需要count_if，因为您要问“有多少项满足该谓词”。 （更新：仔细阅读后，我看到您不是在计数而是在求和。这正是从低级循环中提取高级含义的危险！）但是，您只是在对数字进行计数而不是要通过的集合，因此这不是正常情况。 std::generate_n将产生数字列表，但不能以可用于算法的形式显示！它会推动，而count_if会被拉。其他库：Boost.Range v2或即将发布的Range.v3，将非常简单。许多程序员使用Boost或有自己的计数范围（请参阅我自己的教程和附带的卡通插图☺）。

因此，有了手头的库，我可能会写类似以下内容：

auto r = int_range (1, upper_bound);
auto wanted = [](int i){return (i % 3 == 0 || i % 5 == 0); }
auto sum= accumulate (r|filtered(wanted));

由于这里是实际工作，因此for是如此琐碎，以至于对其进行任何详细说明都会使其变得更多代码。但是，想象一下业务逻辑中一个更现实的复杂情况。该算法（累加）以您正在执行的操作命名。选择标准在其自己的语句中被隔离，并被命名为Wanted，因此以后更容易编辑逻辑而又不会破坏任何内容。

这里的两个问题是所需的惯用语领先于适当的库/编译器支持；并使用一个琐碎的程序，似乎需要人工和繁琐的工作，以在其周围放置任何正式结构或“高级工程”。


可能有用的是验证您的总和没有溢出。这是我在审阅时注意到的内容，因此请评论一下您认为这是个好主意。

// sum will be a subset of the sum of all numbers in the range,
// so must be < (n+1)*(n/2) ≈ 500'000, which is well within the range
// of a 32-bit int.

#3 楼

您的编码样式可能更简洁；最好将其分解为一个函数，如下所示：

#include <iostream>

#define UPPER_BOUND 1000

int sum_of_sequence(int first_multiple, int second_multiple, int max_value)
{
    int sum = 0;
    for (int i = 1; i < max_value; ++i) {
        if (i % first_multiple == 0 || i % second_multiple == 0 ) {
            sum += i;
        }
    }
}

int main() {
    int sum = sum_of_sequence(3, 5, UPPER_BOUND);
    std::cout << "The sum of the natural numbers below " << UPPER_BOUND << " that are multiples of 3 and 5 is " << sum;
    return 0;
}

如果您决定要使用某个功能，则它具有更多的可配置性。不同的数字集。


我不喜欢你#define是一个常数，因为你真的可以做些const或constexpr-两者之间是有区别的，但这没关系。根据要编译的C ++标准的版本，如果适当地使用constexpr，可能可以在编译时完成工作。


您可以开始循环以最低的倍数，然后从那里开始递增；这样可以节省您的迭代次数。


您可以拥有更聪明的算法。对于算术序列，第一个\ $ n \ $项的总和为$$ S_n = \ frac {n（a_1 + a_n）} {2} $$

如果我们用它来计算3的前333倍和5的前199倍的总和将接近我们的答案（333，因为第334的倍数大于1000，并且对199的逻辑相同）。问题在于，我们将重复计算3和5的倍数，即15的倍数（3和5之间的最小公倍数）。因此，如果我们要计算这个值：

$$ \ frac {333（3 + 999）} {2} + \ frac {199（5 + 995）} {2}-\ frac {66 （15 + 990）} {2} $$

我们会得到正确的答案。您可以使用一些简单的函数（可能比它们所需的简单一些）来表达这一点。

int num_multiples_below_max(int value, int max)
{
    return (max - 1) / value;
}

int largest_value(int value, count)
{
    return value * count;
}

int sum_arithmetic_sequence_below_max(int value, int max_value)
{
    return sum_arithmetic_sequence(value, num_multiples_below_max(value, max_value));
}

int sum_arithmetic_sequence(int value, int count)
{
    return count * (value + largest_value(value, count)) / 2;
}

int least_common_multiple(int a, int b)
{
    return a * b;
}

int sum_of_multiples_below_max(int first_multiple, int second_multiple, int max_value)
{
    int sum_first_multiple = sum_arithmetic_sequence_below_max(first_multiple, max_value);
    int sum_second_multiple = sum_arithmetic_sequence_below_max(second_multiple, max_value);
    int lcm = least_common_multiple(first_multiple, second_multiple);
    int sum_least_common_multiple = sum_arithmetic_sequence_below_max(lcm, max_value);

    return sum_first_multiple + sum_second_multiple - sum_least_common_multiple;
}

您可以将其扩展到更多而不是2的倍数，但是我忘记了确切的算法，我的Google-fu目前似乎让我失望了。我将其留给用户练习。

#4 楼

这是一个错误。

该任务询问：


找到1000以下的3或5的所有倍数之和。


，但是您的程序报告：

“低于1000的自然数之和是3和5的倍数……”

您的代码计算得出正确的总和，但该总和与您所表示的含义不符！

这是一个小的优化：

鉴于两个倍数中的最小值为3，您可以从3开始而不是从1开始for循环。

显然，这里并没有节省太多，但是想象一个类似的任务可以处理117或209的倍数。

for (int i = 3; i < UPPER_BOUND; ++i) {
    if (i % 3 == 0 || i % 5 == 0) {
        sum += i;
    }