Реалізуйте свою функцію знаходження квадратного кореня


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

Реалізуйте функцію знаходження квадратного кореня, не використовуючи функції піднесення, що надаються мовою, до степеня і витягань кореня.

Рішення

З курсу шкільної математики ми пам’ятаємо, що функція квадратного кореня є такою, що зростає на усій своїй області визначення (якщо ви цього не пам’ятаєте або вам це не очевидно, можете узяти похідну і переконатися, що вона більше нуля), тобто ми можемо скористатися алгоритмом бінарного пошуку.

Припустимо, що нам треба витягнути квадратний корінь з числа x. Встановимо ліву межу бинпоиска на 0, а праву – на max (1, x). Такою умовою ми врахуємо усі можливі випадки: на відрізку 0.1 корінь з числа більше самого числа, на відрізку 1.inf – менше).

Тепер знайдемо середнє арифметичне меж, назвемо його m, і перевіримо, чи більше m * m, чим x. Якщо так, то шукана відповідь лежить на числовій прямій лівіше m, тобто необхідно зробити m правою межею бинпоиска, інакше – лівою. Через пару сотень таких ітерацій ми знайдемо квадратний корінь з тією, що задовольняє усім потребам точністю.

Бонус з підвищеною складністю

Реалізуйте так само функцію для пошуку кореня n- ний мірі.

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *