Форум Сайтостроение Веб-строительство

Алгоритм Эвклида - НОК на php

D
На сайте с 28.06.2008
Offline
1101
Dram
595

Для повышение разряда в говнокодинге периодически решаю разные задачки и вот наткнулся на очередную:

//Сделайте функцию, которое будет принимать 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 сек.

проверил на малых числах, вроде работает. Загнал одним из чисел 146 млн. и ждал почти 100 сек. ответ.

Потом пишу сыну (он у меня на питоне кодит) - типа реши задачку. Он посмотрел и говорит - алгоритм Эвклида для этого есть, лучше не придумаешь.

Полез искать что за зверь, нашел решение на пхп

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 сек.

Восхитился математиками и математикой, но есть 2 вопроса:

1. почему какие бы числа я не загонял во второй код, он решает все почти мгновенно, вообще нет разницы сотни или миллиарды с триллионами?

2. почему microtime во втором коде сбоит и почти всегда показыает просто 0. (я перед каждым выполнением перезагружаю опенсервер) 1 раз покажет время, 10 раз - просто ноль, хотя цифры ввожу разные, результат показывает. Думал кеширует, но я то код меняю и серв перезапускаю, как так?

S
На сайте с 30.09.2016
Offline
469
Sitealert
#1

1. А что ты хотел увидеть на нескольких итерациях? На примере из стартпоста - 7 итераций, если воткнуть lcm(1467111111111111,14622222222222222222) - 22 итерации. Это мизер.

2. Смотри п.1.

Отпилю лишнее, прикручу нужное, выправлю кривое. Вытравлю вредителей.
Gerga
На сайте с 02.08.2015
Offline
94
Gerga
#2
Dram:
1. почему какие бы числа я не загонял во второй код, он решает все почти мгновенно, вообще нет разницы сотни или миллиарды с триллионами?

Во втором варианте каждая последующая интерация цикла уменьшает числовой диапазон.

Представьте пирамиду. Первая итерация - это дно пирамиды, последняя - вершина.

В первом же варианте линейное решение.

Представьте квадрат, вы движитесь со дна к вершине не уменьшая числовой диапазон.

L
На сайте с 10.02.2015
Offline
222
livetv
#3

Dram, откройте для себя форматирование кода, разряд в говнокодинге повысится.

Оптимизайка
На сайте с 11.03.2012
Offline
396
Оптимизайка
#4
Dram:
1. почему какие бы числа я не загонял во второй код, он решает все почти мгновенно, вообще нет разницы сотни или миллиарды с триллионами?

https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4%D0%B0#%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0

https://ru.wikipedia.org/wiki/%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C

⭐ BotGuard (https://botguard.net) ⭐ — защита вашего сайта от вредоносных ботов, воровства контента, клонирования, спама и хакерских атак!

Авторизуйтесь или зарегистрируйтесь, чтобы оставить комментарий