下面的代码有效,据我所知结果是正确的。请问一下,让我知道我可以做得更好吗?

我只是写书就学到了很多东西,希望我能从您的投入中学到更多!列出所有低于10的自然数,这些自然数是3或5的倍数,我们得到3、5、6和9。这些倍数的总和是23。 。


<?php
/* 
** Project Euler Problem 1
** If we list all the natural numbers below 10 that are multiples of 3 or 5,
** we get 3, 5, 6 and 9. The sum of these multiples is 23. 
** Find the sum of all the multiples of 3 or 5 below 1000.
*/
$numberOne = 3;
$numberTwo = 5;
$endingIndex = 1000;
$multiplesOfNumbers = array();  

for ($index = 1; $index < $endingIndex; $index++) {
    if ($index % $numberOne == 0 || $index % $numberTwo == 0) {
        array_push($multiplesOfNumbers, $index);
    }
}
$sumOfMultiples = array_sum($multiplesOfNumbers);

print "The solution to Euler Project is <b>$sumOfMultiples</b> and the individual numbers are:<br><br>";
print "<pre>";
print_r($multiplesOfNumbers);
print "</pre>";
?>


输出:



用于健全性检查:

答案是正确的,单个数字是:


 Array
(
    [0] => 3
    [1] => 5
    [2] => 6
    [3] => 9
    [4] => 10
    [5] => 12
    [6] => 15
    [7] => 18
    [8] => 20
    [9] => 21
    [10] => 24
    [11] => 25
    [12] => 27
    [13] => 30
    [14] => 33
    [15] => 35
    [16] => 36
    [17] => 39
    [18] => 40
    [19] => 42
    [20] => 45
    [21] => 48
    [22] => 50
    [23] => 51
    [24] => 54
    [25] => 55
    [26] => 57
    [27] => 60
    [28] => 63
    [29] => 65
    [30] => 66
    [31] => 69
    [32] => 70
    [33] => 72
    [34] => 75
    [35] => 78
    [36] => 80
    [37] => 81
    [38] => 84
    [39] => 85
    [40] => 87
    [41] => 90
    [42] => 93
    [43] => 95
    [44] => 96
    [45] => 99
    [46] => 100
    [47] => 102
    [48] => 105
    [49] => 108
    [50] => 110
    [51] => 111
    [52] => 114
    [53] => 115
    [54] => 117
    [55] => 120
    [56] => 123
    [57] => 125
    [58] => 126
    [59] => 129
    [60] => 130
    [61] => 132
    [62] => 135
    [63] => 138
    [64] => 140
    [65] => 141
    [66] => 144
    [67] => 145
    [68] => 147
    [69] => 150
    [70] => 153
    [71] => 155
    [72] => 156
    [73] => 159
    [74] => 160
    [75] => 162
    [76] => 165
    [77] => 168
    [78] => 170
    [79] => 171
    [80] => 174
    [81] => 175
    [82] => 177
    [83] => 180
    [84] => 183
    [85] => 185
    [86] => 186
    [87] => 189
    [88] => 190
    [89] => 192
    [90] => 195
    [91] => 198
    [92] => 200
    [93] => 201
    [94] => 204
    [95] => 205
    [96] => 207
    [97] => 210
    [98] => 213
    [99] => 215
    [100] => 216
    [101] => 219
    [102] => 220
    [103] => 222
    [104] => 225
    [105] => 228
    [106] => 230
    [107] => 231
    [108] => 234
    [109] => 235
    [110] => 237
    [111] => 240
    [112] => 243
    [113] => 245
    [114] => 246
    [115] => 249
    [116] => 250
    [117] => 252
    [118] => 255
    [119] => 258
    [120] => 260
    [121] => 261
    [122] => 264
    [123] => 265
    [124] => 267
    [125] => 270
    [126] => 273
    [127] => 275
    [128] => 276
    [129] => 279
    [130] => 280
    [131] => 282
    [132] => 285
    [133] => 288
    [134] => 290
    [135] => 291
    [136] => 294
    [137] => 295
    [138] => 297
    [139] => 300
    [140] => 303
    [141] => 305
    [142] => 306
    [143] => 309
    [144] => 310
    [145] => 312
    [146] => 315
    [147] => 318
    [148] => 320
    [149] => 321
    [150] => 324
    [151] => 325
    [152] => 327
    [153] => 330
    [154] => 333
    [155] => 335
    [156] => 336
    [157] => 339
    [158] => 340
    [159] => 342
    [160] => 345
    [161] => 348
    [162] => 350
    [163] => 351
    [164] => 354
    [165] => 355
    [166] => 357
    [167] => 360
    [168] => 363
    [169] => 365
    [170] => 366
    [171] => 369
    [172] => 370
    [173] => 372
    [174] => 375
    [175] => 378
    [176] => 380
    [177] => 381
    [178] => 384
    [179] => 385
    [180] => 387
    [181] => 390
    [182] => 393
    [183] => 395
    [184] => 396
    [185] => 399
    [186] => 400
    [187] => 402
    [188] => 405
    [189] => 408
    [190] => 410
    [191] => 411
    [192] => 414
    [193] => 415
    [194] => 417
    [195] => 420
    [196] => 423
    [197] => 425
    [198] => 426
    [199] => 429
    [200] => 430
    [201] => 432
    [202] => 435
    [203] => 438
    [204] => 440
    [205] => 441
    [206] => 444
    [207] => 445
    [208] => 447
    [209] => 450
    [210] => 453
    [211] => 455
    [212] => 456
    [213] => 459
    [214] => 460
    [215] => 462
    [216] => 465
    [217] => 468
    [218] => 470
    [219] => 471
    [220] => 474
    [221] => 475
    [222] => 477
    [223] => 480
    [224] => 483
    [225] => 485
    [226] => 486
    [227] => 489
    [228] => 490
    [229] => 492
    [230] => 495
    [231] => 498
    [232] => 500
    [233] => 501
    [234] => 504
    [235] => 505
    [236] => 507
    [237] => 510
    [238] => 513
    [239] => 515
    [240] => 516
    [241] => 519
    [242] => 520
    [243] => 522
    [244] => 525
    [245] => 528
    [246] => 530
    [247] => 531
    [248] => 534
    [249] => 535
    [250] => 537
    [251] => 540
    [252] => 543
    [253] => 545
    [254] => 546
    [255] => 549
    [256] => 550
    [257] => 552
    [258] => 555
    [259] => 558
    [260] => 560
    [261] => 561
    [262] => 564
    [263] => 565
    [264] => 567
    [265] => 570
    [266] => 573
    [267] => 575
    [268] => 576
    [269] => 579
    [270] => 580
    [271] => 582
    [272] => 585
    [273] => 588
    [274] => 590
    [275] => 591
    [276] => 594
    [277] => 595
    [278] => 597
    [279] => 600
    [280] => 603
    [281] => 605
    [282] => 606
    [283] => 609
    [284] => 610
    [285] => 612
    [286] => 615
    [287] => 618
    [288] => 620
    [289] => 621
    [290] => 624
    [291] => 625
    [292] => 627
    [293] => 630
    [294] => 633
    [295] => 635
    [296] => 636
    [297] => 639
    [298] => 640
    [299] => 642
    [300] => 645
    [301] => 648
    [302] => 650
    [303] => 651
    [304] => 654
    [305] => 655
    [306] => 657
    [307] => 660
    [308] => 663
    [309] => 665
    [310] => 666
    [311] => 669
    [312] => 670
    [313] => 672
    [314] => 675
    [315] => 678
    [316] => 680
    [317] => 681
    [318] => 684
    [319] => 685
    [320] => 687
    [321] => 690
    [322] => 693
    [323] => 695
    [324] => 696
    [325] => 699
    [326] => 700
    [327] => 702
    [328] => 705
    [329] => 708
    [330] => 710
    [331] => 711
    [332] => 714
    [333] => 715
    [334] => 717
    [335] => 720
    [336] => 723
    [337] => 725
    [338] => 726
    [339] => 729
    [340] => 730
    [341] => 732
    [342] => 735
    [343] => 738
    [344] => 740
    [345] => 741
    [346] => 744
    [347] => 745
    [348] => 747
    [349] => 750
    [350] => 753
    [351] => 755
    [352] => 756
    [353] => 759
    [354] => 760
    [355] => 762
    [356] => 765
    [357] => 768
    [358] => 770
    [359] => 771
    [360] => 774
    [361] => 775
    [362] => 777
    [363] => 780
    [364] => 783
    [365] => 785
    [366] => 786
    [367] => 789
    [368] => 790
    [369] => 792
    [370] => 795
    [371] => 798
    [372] => 800
    [373] => 801
    [374] => 804
    [375] => 805
    [376] => 807
    [377] => 810
    [378] => 813
    [379] => 815
    [380] => 816
    [381] => 819
    [382] => 820
    [383] => 822
    [384] => 825
    [385] => 828
    [386] => 830
    [387] => 831
    [388] => 834
    [389] => 835
    [390] => 837
    [391] => 840
    [392] => 843
    [393] => 845
    [394] => 846
    [395] => 849
    [396] => 850
    [397] => 852
    [398] => 855
    [399] => 858
    [400] => 860
    [401] => 861
    [402] => 864
    [403] => 865
    [404] => 867
    [405] => 870
    [406] => 873
    [407] => 875
    [408] => 876
    [409] => 879
    [410] => 880
    [411] => 882
    [412] => 885
    [413] => 888
    [414] => 890
    [415] => 891
    [416] => 894
    [417] => 895
    [418] => 897
    [419] => 900
    [420] => 903
    [421] => 905
    [422] => 906
    [423] => 909
    [424] => 910
    [425] => 912
    [426] => 915
    [427] => 918
    [428] => 920
    [429] => 921
    [430] => 924
    [431] => 925
    [432] => 927
    [433] => 930
    [434] => 933
    [435] => 935
    [436] => 936
    [437] => 939
    [438] => 940
    [439] => 942
    [440] => 945
    [441] => 948
    [442] => 950
    [443] => 951
    [444] => 954
    [445] => 955
    [446] => 957
    [447] => 960
    [448] => 963
    [449] => 965
    [450] => 966
    [451] => 969
    [452] => 970
    [453] => 972
    [454] => 975
    [455] => 978
    [456] => 980
    [457] => 981
    [458] => 984
    [459] => 985
    [460] => 987
    [461] => 990
    [462] => 993
    [463] => 995
    [464] => 996
    [465] => 999
)
 





评论

我刚刚意识到我的答案是错误的。直到现在无法验证。

我通过将$ index <= $ endingIndex替换为$ index <$ endingIndex新手错误来修复了代码!感谢@mjolka指出这一点!

#1 楼

其他答案集中在算法选择上。我将仅采用给定的算法,并专注于代码。这是我的写法:

<?php
/* 
** Project Euler Problem 1
** If we list all the natural numbers below 10 that are multiples of 3 or 5,
** we get 3, 5, 6 and 9. The sum of these multiples is 23. 
** Find the sum of all the multiples of 3 or 5 below 1000.
*/

$divisors = array( 3, 5 );
$multiples_of_divisors = array();

// since we want only the multiples strictly below the upper bound, we use < rather than <=
for ( $i = 1, $n = 1000; $i < $n; $i++ ) {
    foreach ( $divisors as $divisor ) {
        if ( 0 == $i % $divisor ) {
            $multiples_of_divisors[] = $i;
            // break out of the foreach so that we only add a given number once for a list of divisors
            break;
        }
    }
}

$sum_of_multiples = array_sum($multiples_of_divisors);

print "The solution to Euler Project is <strong>$sum_of_multiples</strong> and the individual numbers are:<br /><br />";
print "<pre>";
print_r($multiples_of_divisors);
print "</pre>";
?>


原因:

如果代码紧随注释之后,则假定注释说明该段代码。如果注释是更笼统的标题(例如,对整个代码应该完成的功能的描述),那么如果您将注释与代码之间留有空格,则将很有帮助。

CamelCase不能很好地推广到其他语言。考虑改用underscore_delimited变量名。这些非母语人士更容易识别。如果您是在跨国环境中工作,例如跨国公司或开源项目,这将有所帮助。

如其他人所述,数组比$ numberOne和$ numberTwo更通用。 $ divisors比$ numbers更具描述性。

如果您一开始做错了什么然后将其修复,请考虑添加注释以突出显示该修复(可能是错误)。因此,您想解释为什么使用<而不是<=这里。

如果变量用于索引数组,则用$ index替换$ i是有意义的。不过,这不是它在做什么。使用更标准的$ i或使用一个真正的描述性名称。我认为$ i在这里已经绰绰有余。

在代码的同一点定义开始和结束边界。我是在这里的for语句中这样做的。您也可能同时退出了循环,并遇到了类似

$lower_bound = 1;
$upper_bound = 1000;
for ( $i = $lower_bound; $i < $upper_bound; $i++ ) {


在PHP之类的C风格语言中,当您打算进行相等性检查(==)时,很容易进行赋值(=)。为了防止这种情况,有人将值侧(0 == $ i)放在了第一位,而不是变量侧($ i == 0)。这将导致编译器抛出错误,而不是默默地执行赋值操作,然后检查赋值的值是否为false。

在PHP中,如果要处理单个值,则[] =比array_push更快。如果要添加值列表,请坚持使用array_push。

如果您的代码做得很聪明(或解决了先前的错误),请对其进行注释。这样一来,不必再花更多的时间去弄清正在发生的事情,下一个人就可以编辑代码。

请注意,要修改问题的参数,必须修改代码。通常最好让代码接受输入。这允许不是程序员的人使用您的代码。因此,处理用户输入的程序会更好。对于PHP,您通常会使用GET参数来执行此操作,并且可以提供HTML表单来输入它们。

该程序产生无效的HTML。通常这不是问题,因为浏览器将添加缺少的标签。但是,依靠它是一个不好的做法。

我的某些更改纯粹是风格上的。不使用它们的代码是完全有效的。我鼓励您考虑一下代码的外观。

评论


\ $ \ begingroup \ $
感谢您的回答,那是一个更加优雅的程序。您能建议我做些什么来帮助我的程序生成有效的HTML吗?我不介意如果它帮助我的代码变得更好,就变得更加冗长。
\ $ \ endgroup \ $
– ran
2014-09-26 15:49

\ $ \ begingroup \ $
主要是将输出包装在HTML标签中的问题,例如html,head,body等。此外,所有文档都应以正确的DOCTYPE开头。我倾向于使用XHTML,但是事情似乎正在回溯到HTML5和HTML5。
\ $ \ endgroup \ $
– Brythan
2014年9月26日在18:01

#2 楼

您使用的是蛮力法,时间复杂度在范围内,线性因素数呈线性,即\ $ \ mathcal {O}(nk)\ $,其中\ $ n \ $是数字范围(1000)和\ $ k \ $是要检查的因子数(此问题中为2)。 n \ $,然后让\ $ c_i = \ lfloor \ frac {n-1} {k_i} \ rfloor \ $然后:

\ $ S_i = \ sum_ {m = 1} ^ {c_i} {m \ cdot k_i} = k_i \ cdot c_i \ frac {c_i + 1} {2} \ $

现在解决该问题的第一步是:

\ $ \ sum _ {\ forall i} S_i = \ sum _ {\ forall i} {k_i \ cdot c_i \ frac {c_i + 1} {2}} \ $

但这可算为整数\ $ k_i \ $和\ $ k_j \ $两次,因此我们需要减去重复计算的数字。令\ $ K_ \ ell \ $为\ $ i \ ne j \的\ $ k_i \ $和\ $ k_j \ $的所有成对乘积(换句话说,\ $ K_ \ ell = k_j \ cdot k_i \ $)。 $,那么解决方案是:

\ $ S = \ sum _ {\ forall i} {k_i \ cdot c_i \ frac {c_i + 1} {2}}-\ sum _ {\ forall \ ell } {K_ \ ell \ cdot C_ \ ell \ frac {C_ \ ell + 1} {2}} \ $其中\ $ C_ \ ell = \ lfloor \ frac {n-1} {K_ \ ell} \ rfloor \ $ 。

时间复杂度为\ $ \ mathcal {O}(k ^ 2)\ $,而随着\ $ k \ ll n \ $的出现,速度明显加快。

对于您的实现,我将对所有数字使用数组来求和,然后在内部循环中对其进行迭代,以免if语句中的表达式爆炸。除此之外,我认为它看起来不错。

(注意:欧拉问题1可以用纸和笔轻松解决)

#3 楼

让我们解决一个简单的问题:找到1000以下的3的所有倍数之和。

我们有

\ begin {align}
3 + 6 + 9 + 12 + \ cdots + 999&= 3(1 + 2 + 3 + 4 + \ cdots + 333)\\
&= 3 \ times \ frac {333 \ times(333 + 1)} {2},
\ end {align}

第二行来自身份

\ begin {align}
1 + 2 + 3 + \ cdots + n = \ sum_ {k = 1} ^ nk = \ frac {n(n + 1)} {2}。
\ end {align}

(另请参见Wikipedia。)

现在我们可以使用上述过程来找到1000以下5的所有倍数之和。这使我们非常接近解决方案。

问题是,我们正在计算3的倍数和5的倍数中的数字\ $ 15、30、45,\ ldots \ $,因此最后一步是从计数中减去15的倍数,为原始问题提供解决方案。

评论


\ $ \ begingroup \ $
这正是解决问题的预期方法。不幸的是,暴力很容易。后来的那些增加了上限,以尝试(通常成功地)避免这种情况。
\ $ \ endgroup \ $
–罗斯·米利坎(Ross Millikan)
2014-09-26 3:24



\ $ \ begingroup \ $
这正是我的答案,它是在您的答案发布前1小时发布的...
\ $ \ endgroup \ $
–艾米莉·L。
2014-09-26 6:02

\ $ \ begingroup \ $
@EmilyL。这是针对不同受众的相同解决方案。我认为这对某些人来说将更容易上手。 Phrancis在聊天中特别提到他在为您的答案做数学运算时遇到困难。
\ $ \ endgroup \ $
–mjolka
2014-09-26 6:22



\ $ \ begingroup \ $
@EmilyL可能是我缺乏数学技能使您的答案很难被我理解。不过,我对两个答案都投了赞成票,非常感谢您花费宝贵的时间来帮助算法。
\ $ \ endgroup \ $
– ran
2014年9月26日在6:26