Необходимо создать 2 функции,каждая из которых принимают один аргумент number(число) обе функции будут находить и возвращать корень натурального числа с точностью до целого. Загвоздка в том, что одна функция использует метод последовательного подбора( с ней проблем нету), а вторая - БИНАРНЫЙ. Помогите плиз, уже битый час ломаю голову((( Изюминкой на торте является то, что по условии задания, Math.sqrt использовать нельзя(((СПАСИБО ВСЕМ!!!
Решение в лоб - это взять готовый алгоритм, если есть на JS, или взять на другом языке (если нет готового на JS) и переделать на JS:
function findSqrt(x)
{
// базовый вариант
if (x < 2) {
return x;
}
// для хранения пола `sqrt(x)`
let result;
// квадратный корень из `x` не может быть больше, чем `x/2` для `x > 1`
let start = 1;
let end = Math.floor(x / 2);
while (start <= end) {
// найти средний элемент
const mid = Math.floor((start + end) / 2);
const sqr = mid * mid;
// вернуть `mid`, если `x` - правильный квадрат
if (sqr == x) {
return mid;
}
// если `mid×mid` меньше, чем `x`
else if (sqr < x)
{
// отбрасываем левое пространство поиска
start = mid + 1;
// обновляем результат, так как нам нужен пол
result = mid;
}
// если `mid×mid` больше, чем `x`
else {
// отбрасываем правильное пространство поиска
end = mid - 1;
}
}
// возвращаем результат
return result;
}
for (let i = 0; i <= 16; i++) {
console.log(`sqrt${i} = ${findSqrt(i)}`);
}
Результат:
sqrt(0) = 0
sqrt(1) = 1
sqrt(2) = 1
sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(6) = 2
sqrt(7) = 2
sqrt(8) = 2
sqrt(9) = 3
sqrt(10) = 3
sqrt(11) = 3
sqrt(12) = 3
sqrt(13) = 3
sqrt(14) = 3
sqrt(15) = 3
sqrt(16) = 4
Источник: Найдите квадратный корень числа с помощью двоичного поиска
1 лайк
Спасибо огромное. С поиском числа в выбранном диапазоне бинарным методом, проблем нет, а вот корень числа никак не мог сопоставить с ним, ломал голову долго… Я только начинаю, и учу JS, поэтому приходится обращатся за помощью.