如果列出10以下的所有自然数，它们是3或5的倍数，则得到3、5、6和9。这些倍数的总和为23。

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


我的解决方案：与：gcc（GCC）4.8.3 20140624（Red Hat 4.8.3-1）

评论

这会产生正确的结果吗？我的假设是您可能比285或570差。
得到正确的答案。否则我不会在这里发布。
哦，我看到最后一个减去了。
没有人怎么会注意到void main（void）?!需要返回int类型，或者不指定参数，或者（int argc，char * argv []）
@OllieFord：如果可以，请发布答案，如果您认为它对社区具有潜在价值。恕我直言，确实如此，您应该发布答案

#1 楼

通常，您的算法/解决方案很聪明。我最喜欢的是\ $ O（1）\ $解决方案，而其他大多数解决方案都是\ $ O（n）\ $并对3和5取模。其中应该有明确的注释，包括原因。
find_last_multiple也是一个很好的解决方案。没问题，它很简单，不需要评论。

不幸的是，sum_of_series存在一些问题...。应该首先对其进行评论...逻辑远非如此。显然...。我还没有弄清楚...。。

此外，这时它变成基于float的计算，这使我花了一秒钟。我立即开始考虑基于int的数学，因为代码具有int常量，并且它在find_last_multiple中执行int值，但随后进行了隐式强制转换以进行浮动。非常令人困惑。

最后，我们假设该系列从3、5或15开始，但问题描述从其他地方开始...。我建议您放弃starts_from参数，

因此，使用基于浮点数的逻辑并返回基于浮点数的解决方案是意外的....我希望对为什么总和有一些评论。系列中的整数是浮点数。

最后，您的sum_of_series应该代表系列之和的标准公式（请参阅维基百科的替代形式）：

$$
\ frac {n} {2}（2a +（n-1）d）
$$

其中n是序列中的项数， a是起始值，d是差异。

可以通过将a设置为0（消除2a项）来简化，对于int数学，可以这样做： （n-1）} {2} d
$$

数学上，偶数的任何倍数总是会是偶数。现在，\ $ n \ $或\ $ n-1 \ $是偶数....因此，\ $ n（n-1）\ $将是偶数，并且可以安全地除以2。

我也将从0开始。使用整数数学，问题更简单：

int sum_of_series(int limit, int difference)
{
    // from: http://en.wikipedia.org/wiki/Arithmetic_progression
    // formula for calculating the sum of a progression from 0 to a 'limit'
    // in steps of 'difference'. e.g. limit 10, difference 2 adds 0, 2, 4, 6, 8, 10 = 30
    int n = 1 + limit / difference; // integer math gives number of terms including term 0
    return ((n * (n - 1)) / 2) * difference;
}


因此，您可以安全地将以上内容用作：

int sum = sum_of_series(999, 15);


，将得出结果15 * (67 * 66) / 2或33165

请注意，问题陈述要求的值之和小于1000，并且sum_of_series公式计算包含限值的值，因此，我们使用999的限制，而不是1000的限制。另外，使用基于整数的逻辑，根本不需要使用find-limit方法。这将您的主要方法减少为：

评论

\ $ \ begingroup \ $
如果在问题中省略第0个项，则在计算\ $ n \ $时也可以消除\ $ + 1 \ $，并使用更标准的公式对第一个\ $ n \ $正整数求和：\ $ n（n + 1）\超过2 \ $。
\ $ \ endgroup \ $
– David Harkness
2014年8月10日19:46


\ $ \ begingroup \ $
如果不对公式进行更好的解释或对公式进行解释的URL，您的sum_of_series函数可能仍不完整。我知道这时数学家会更熟悉它的形式，而您所包含的公式从Calculus看来对我来说很熟悉。普通程序员不是数学家，但是可能不熟悉此公式。同时，对于非数学家来说，问题陈述非常容易理解。当代码难以理解然后出现问题陈述时，您需要非常非常好的注释。
\ $ \ endgroup \ $
– nhgrif
2014年8月10日在20:47
\ $ \ begingroup \ $
应该提到void main（void）是C（和C ++）的非标准签名，因为这是代码审查。
\ $ \ endgroup \ $
–拉普兹
2014年8月11日，0：17
\ $ \ begingroup \ $
@Cthulhu普通程序员不可能在所有方面都高于平均水平。我既是程序员又是数学家，但我不是设计师，统计学家或系统工程师，这也许让我很遗憾。也许不是。不管我们如何对此产生情感上的反应，有很多才华横溢的工程师并没有将数学作为他们的强项，我很喜欢与其中一些打交道。
\ $ \ endgroup \ $
–埃里克·威尔逊（Eric Wilson）
2014年8月11日在18:31
\ $ \ begingroup \ $
@EricWilson不，程序员不必是专业的数学家，但是没有数学思考的编程就太可怕了。
\ $ \ endgroup \ $
–克苏鲁
2014年8月12日4:45


#2 楼

您做得好的

使用公式来计算总和是有效的。使用包含-排除原理很聪明。您为函数和变量选择了描述性名称。仅通过阅读以下单行代码即可清楚了解其意图：

float answer = sum_of_series_3 + sum_of_series_5 - sum_of_series_15;


关注点

浮点数的引入对准确性有点令人不安，和性能原因。我说“温和”，是因为我怀疑它在此特定解决方案中不会带来任何实际的后果，但我仍然认为使用浮点数进行整数计算是不明智的做法。数学表达式

您将TOP_LIMIT定义为1000，但在格式字符串中硬编码为1000。如果您需要更改TOP_LIMIT，则输出将看起来是错误的。 >可能的简化是定义更原始的，通用的有用函数。

$$ \ begin {align *}
\ underbrace {3 + 6 + 9 + 12 + \ ldots + 999} _ {n \ \ textrm {terms}} \＆= 3 \（1 + 2 + 3 + 4 + \ ldots + n）\\
＆= 3 \ frac {n \（n + 1）} { 2}
\ end {align *} $$ 

int sum_of_1_to_n(int n) {
    return n * (n + 1) / 2;
}

int count_multiples_under(int limit, int step) {
    /* Integer division automatically rounds down as necessary */
    return (limit - 1) / step;
}

int main(void) {
    int limit = 1000;
    int sum_of_series_3  =  3 * sum_of_1_to_n(count_multiples_under(limit, 3));
    int sum_of_series_5  =  5 * sum_of_1_to_n(count_multiples_under(limit, 5));
    int sum_of_series_15 = 15 * sum_of_1_to_n(count_multiples_under(limit, 15));

    int answer = sum_of_series_3 + sum_of_series_5 - sum_of_series_15;
    printf("sum of all the multiples of 3 or 5 below %d = %d\n", limit, answer);
}


评论

\ $ \ begingroup \ $
count_multiples_under是一个更好的名称。总而言之，这更具可读性。
\ $ \ endgroup \ $
– njzk2
2014年8月11日19:38

#3 楼

正如@rolfl指出的那样，在重写sum_of_series以使用整数并返回int之后，可以在整个程序中将所有float变量替换为int。 （当然，将最后一个printf更改为使用%d而不是%f。） />
尽可能避免使用void main。最好在int方法中使用全局常量，甚至使用局部常量。但是，如果将其作为命令行参数，则该程序会变得很有趣，例如：

#include <stdlib.h>

int main(int argc, char ** argv) {
    int top_limit = atoi(argv[1]);
    // ...
    printf("answer = %d\n", answer);
}


，然后在运行时： 
$ gcc t.cpp  && ./a.out 10
sum of all the multiples of 3 or 5 below 10
answer = 23
$ gcc t.cpp  && ./a.out 100
sum of all the multiples of 3 or 5 below 100
answer = 2318
$ gcc t.cpp  && ./a.out 1000
sum of all the multiples of 3 or 5 below 1000
answer = 233168
$ gcc t.cpp  && ./a.out 10000
sum of all the multiples of 3 or 5 below 10000
answer = 23331668
$ gcc t.cpp  && ./a.out 100000
sum of all the multiples of 3 or 5 below 100000
answer = 2333316668
$ gcc t.cpp  && ./a.out 1000000
sum of all the multiples of 3 or 5 below 1000000
answer = 233333166668
$ gcc t.cpp  && ./a.out 10000000
sum of all the multiples of 3 or 5 below 10000000
answer = 23333331666668


哎呀，10s（大于100）的幂的答案似乎总是与正则表达式#define匹配，其中main！

（对于更大的数字，我不得不将某些23{n}16{m}8类型更改为m = n - 1。）

评论

\ $ \ begingroup \ $
关于公式23 {n} 16 {m} 8有点冗长，但不难证明存在这样的模式。最终您可以在math.stackexchange.com上提问
\ $ \ endgroup \ $
– Emanuele Paolini
14年8月10日在21:09

#4 楼

为什么要使用一个如此复杂的算法，使其尽可能简单，如： />

评论

\ $ \ begingroup \ $
现在看起来好多了……但是这个解决方案实际上是\ $ O（n）\ $。这与现已删除的答案受到了同样的批评非常相似。
\ $ \ endgroup \ $
– Jamal♦
2014年8月10日在20:11
\ $ \ begingroup \ $
这意味着线性复杂度。此代码循环通过一定数量。恒定的复杂性将涉及单个操作。 OP的代码为\ $ O（1）\ $。
\ $ \ endgroup \ $
– Jamal♦
2014年8月10日在20:16
\ $ \ begingroup \ $
@EmanuelePaolini-没错，由于输入为常数，因此所有解决方案均为O（1），并且根本没有缩放的概念。谈论缩放的时间复杂性将需要假设。不过，您的解决方案要比OP的解决方案慢约1000倍
\ $ \ endgroup \ $
–rolfl
2014年8月10日20:31


\ $ \ begingroup \ $
慢1000倍意味着我的PC上需要10毫秒。如果考虑到编写程序所花费的时间呢？ Euler项目只需要获得正确的解决方案，因此我认为拥有一个可以轻松信任的简单程序比复杂且难以检查的算法要好得多。还要考虑这不是问题1 ...会有时间去研究复杂的算法！
\ $ \ endgroup \ $
– Emanuele Paolini
14年8月10日在21:20
\ $ \ begingroup \ $
欧拉计划不仅仅是解决方案。同样，这样做，int n = whatNumber; for（int i = 1; i \ $ \ endgroup \ $
–西尔维·布鲁斯（Silviu Burcea）
2014年8月11日在7:16