Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.
Реалізуйте функцію знаходження квадратного кореня, не використовуючи функції піднесення, що надаються мовою, до степеня і витягань кореня.
Рішення
З курсу шкільної математики ми пам’ятаємо, що функція квадратного кореня є такою, що зростає на усій своїй області визначення (якщо ви цього не пам’ятаєте або вам це не очевидно, можете узяти похідну і переконатися, що вона більше нуля), тобто ми можемо скористатися алгоритмом бінарного пошуку.
Припустимо, що нам треба витягнути квадратний корінь з числа x. Встановимо ліву межу бинпоиска на 0, а праву – на max (1, x). Такою умовою ми врахуємо усі можливі випадки: на відрізку 0.1 корінь з числа більше самого числа, на відрізку 1.inf – менше).
Тепер знайдемо середнє арифметичне меж, назвемо його m, і перевіримо, чи більше m * m, чим x. Якщо так, то шукана відповідь лежить на числовій прямій лівіше m, тобто необхідно зробити m правою межею бинпоиска, інакше – лівою. Через пару сотень таких ітерацій ми знайдемо квадратний корінь з тією, що задовольняє усім потребам точністю.
Бонус з підвищеною складністю
Реалізуйте так само функцію для пошуку кореня n- ний мірі.
Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?
