Алгоритм Эвклида - НОК на php
Для повышение разряда в говнокодинге периодически решаю разные задачки и вот наткнулся на очередную:
подумал пару минут и написал так
проверил на малых числах, вроде работает. Загнал одним из чисел 146 млн. и ждал почти 100 сек. ответ.
Потом пишу сыну (он у меня на питоне кодит) - типа реши задачку. Он посмотрел и говорит - алгоритм Эвклида для этого есть, лучше не придумаешь.
Полез искать что за зверь, нашел решение на пхп
Восхитился математиками и математикой, но есть 2 вопроса:
1. почему какие бы числа я не загонял во второй код, он решает все почти мгновенно, вообще нет разницы сотни или миллиарды с триллионами?
2. почему microtime во втором коде сбоит и почти всегда показыает просто 0. (я перед каждым выполнением перезагружаю опенсервер) 1 раз покажет время, 10 раз - просто ноль, хотя цифры ввожу разные, результат показывает. Думал кеширует, но я то код меняю и серв перезапускаю, как так?
Цитата:
|
//Сделайте функцию, которое будет принимать 2 числа, а возвращать их НОК - наименьшее общее кратное. // НОК двух чисел - это самое маленькое число, которое делится и на одно, и на второе число. Пример: числа 12 и 15 имеют НОК 60. // Число 60 делится и на 12, и на 15 и это самое минимальное такое число. |
Цитата:
|
function Nok ($i, $n){ $start = microtime(true); for ($a=1;$a<=1000000000000000;$a++){ $pervoe = $i*$a; if ($pervoe % $n == 0){ echo "НОК=".$pervoe."<br>"; $finish = microtime(true); $delta = $finish - $start; echo $delta . ' сек.'; break; } } } Nok(1467,146000000); //НОК=214182000000 //94.320394992828 сек. |
Потом пишу сыну (он у меня на питоне кодит) - типа реши задачку. Он посмотрел и говорит - алгоритм Эвклида для этого есть, лучше не придумаешь.
Полез искать что за зверь, нашел решение на пхп
Цитата:
|
function gcd($a, $b) { $num = $a; $div = $b; /* Euclid Algorithm */ while (true) { $rem = $num % $div; $num = $div; $div = $rem; if ($rem == 0) break; // no remainder? } return $num; } /* Least Common Multiple */ function lcm($a, $b) { return $a * $b / gcd($a, $b); } $stat = microtime(true); echo lcm(1467,146000000)."<br>"; $finish = microtime(true); $delta = $finish - $stat; echo $delta . ' сек.'; //НОК=214182000000 //0.00099992752075195 сек. |
1. почему какие бы числа я не загонял во второй код, он решает все почти мгновенно, вообще нет разницы сотни или миллиарды с триллионами?
2. почему microtime во втором коде сбоит и почти всегда показыает просто 0. (я перед каждым выполнением перезагружаю опенсервер) 1 раз покажет время, 10 раз - просто ноль, хотя цифры ввожу разные, результат показывает. Думал кеширует, но я то код меняю и серв перезапускаю, как так?