我只是写书就学到了很多东西,希望我能从您的投入中学到更多!列出所有低于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
)
#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
评论
我刚刚意识到我的答案是错误的。直到现在无法验证。我通过将$ index <= $ endingIndex替换为$ index <$ endingIndex新手错误来修复了代码!感谢@mjolka指出这一点!