Проект Euler Puzzler (особенно на PHP)
Вопрос
Есть еще один недавний вопрос Project Euler, но я думаю, что он немного более конкретен (меня действительно интересуют только решения на основе PHP), поэтому я все равно спрашиваю.
Вопрос № 5 ставит перед вами следующие задачи: " Что является наименьшим число, которое равномерно делится на все числа от 1 до 20? "
Теперь я решил это дважды. Когда-то очень неэффективно, а иногда гораздо эффективнее, но я все еще далек от особенно изощренного ответа (и я не особенно хорош в математике, поэтому мое решение грубой силы). Я вижу несколько областей, в которых я мог бы улучшить это, но мне интересно, сможет ли кто-нибудь из вас продемонстрировать более эффективное решение этой проблемы. Р>
* спойлер: вот мое менее чем оптимальное (7 секунд для запуска), но все еще терпимое решение (не уверен, что делать с двойным $ ... просто притворитесь, что вы видите только 1 ...
function euler5(){
$x = 20;
for ($y = 1; $y < 20; $y++) {
if (!($x%$y)) {
} else {
$x+=20;
$y = 1;
}
}echo $x;
};
Решение
в php это будет выглядеть так:
<?php
function gcd($a,$b) {
while($a>0 && $b>0) {
if($a>$b) $a=$a-$b; else $b=$b-$a;
}
if($a==0) return $b;
return $a;
}
function euler5($i=20) {
$euler=$x=1;
while($x++<$i) {
$euler*=$x/gcd($euler,$x);
}
return $euler;
}
?>
Это как минимум в два раза быстрее, чем вы опубликовали.
Другие советы
Соберите простые множители для всех чисел от 1 до 20. Подсчитав максимальные показатели каждого простого множителя, мы имеем 16 = 2 ** 4
, 9 = 3 ** 2
, а также 5, 7, 11, 13, 17, 19 (каждый появляется только один раз). Умножьте лот, и вы получите ответ.
Крис Шут-Янг прав.
Как правило, если вам нужно наименьшее число, которое делится на равные числа всех чисел от 1 до N, вам нужно найти все простые числа от 2 до N, и для каждого из них найти наибольшее число раз. он делит любое число в диапазоне. Это можно рассчитать, найдя наибольшую мощность простого числа, не превышающую N.
В случае 20, как указал Крис, 2 ^ 4 - это наибольшая сила 2, не превышающая 20, а 3 ^ 2 - наибольшая сила 3, не превышающая 20, и только для всех других простых чисел первая сила не больше 20.
Вы можете удалить некоторые числа, которые разделены, например, 1 не является необходимым, все натуральные числа делятся на 1. Вам тоже не нужно 2, и, следовательно, все числа делятся на кратные 2 (4, 8 , 16 и т. Д.) Также делятся на 2. Таким образом, соответствующие цифры будут 11, 12, 13, 14, 15, 16, 17, 18 и 19.
Итак:
<?
function eulerPuzzle()
{
$integers = array( 11,12,13,14,15,16,17,18,19 );
for ($n = 20; 1; $n += 20 ) {
foreach ($integers as $int) {
if ( $n % $int ) {
break;
}
if ( $int == 19 ) {
die ("Result:" . $n);
}
}
}
}
eulerPuzzle();
?>
<?php
$i=20;
while ($i+=20) {
for ($j=19;$j!==10;--$j){
if ($i%$j) continue 2;
}
die ("result: $i\n");
}
Пока самое быстрое и самое короткое решение php. Примерно в 1,4 раза быстрее, чем Czimi на моем компе. Но посмотрите на решение Python, это хороший алгоритм.
Некоторые люди действительно обдумывают это ...
В Ruby:
puts 5*7*9*11*13*16*17*19
@ Люди занимаются простой математикой; Я не уверен, является ли это целью упражнения. Вы должны изучать новые языки и новые способы выполнять вещи. Просто делать это с помощью калькулятора - неправильный путь.
И я знаю, что это сообщение в старой ветке, но оно все равно появляется в результатах Google:)
Делая это в коде (то есть PHP), я нашел, что это самое быстрое решение:
function eulerPuzzle() {
$integers = array (11, 12, 13, 14, 15, 16, 17, 18, 19 );
for($n = 2520; 1; $n += 2520) {
foreach ( $integers as $int ) {
if ($n % $int) {
break;
}
if ($int == 19) {
die ( "Result:" . $n );
}
}
}
}
eulerPuzzle ();
Да, это модифицированная часть от CMS. Основная причина того, что он быстрее, заключается в том, что когда вы читаете вопрос, они уже заявляют, что наименьшее возможное число для первых 10 целых чисел равно 2520. Поэтому вы можете просто увеличить его на 2520 вместо 20. В результате в 126 раз меньше циклов р>
Я знаю, что вы сказали PHP, но вот мой набросок на Python.
#!/usr/bin/env python
from operator import mul
def factor(n):
factors = {}
i = 2
while i < n and n != 1:
while n % i == 0:
try:
factors[i] += 1
except KeyError:
factors[i] = 1
n = n / i
i += 1
if n != 1:
factors[n] = 1
return factors
base = {}
for i in range(2, 2000):
for f, n in factor(i).items():
try:
base[f] = max(base[f], n)
except KeyError:
base[f] = n
print reduce(mul, [f**n for f, n in base.items()], 1)
Это не так элегантно, как я мог бы это сделать, но он вычисляет наименьшее общее число от 2 до 2000 в .15 с. Если ваше итеративное решение может обрабатывать миллиард кандидатов в секунду, это займет 10 ^ 849 лет.
Другими словами, не пытайтесь оптимизировать неправильный алгоритм.