Вступ
Ми запускаємо ракету для дослідження далекого космосу, і нам потрібен спосіб переконатися, що навігаційна система залишається на правильному курсі.
Як перший крок у наших обчисленнях, ми беремо цільове число і знаходимо його квадратний корінь (тобто число, яке при множенні саме на себе дорівнює цільовому числу).
Подорож буде дуже довгою.
Щоб батареї протрималися якнайдовше, нам довелося зробити бортовий компʼютер нашої ракети дуже енергоощадним.
На жаль, це означає, що ми не можемо покладатися на вигадливі математичні бібліотеки та функції, бо вони споживають більше енергії.
Натомість ми хочемо реалізувати власне обчислення квадратного кореня.
Вказівки
Наше завдання - обчислити квадратний корінь заданого числа.
- Намагаймося не використовувати наявні математичні бібліотеки нашої мови програмування.
- На вхід ми отримаємо додатне ціле число, тобто 1, 2, 3, 4…
- Потрібно обробити лише випадки, коли результатом є додатне ціле число.
Кілька можливих підходів:
- Лінійний або двійковий пошук числа, яке в квадраті дає вхідне число.
- Послідовне наближення за методом Ньютона або Герона.
- Обчислення по одній цифрі чи по одному біту за раз.
Можемо зазирнути до статей у Вікіпедії про цілочисельний квадратний корінь та методи обчислення квадратного кореня, щоб легше вибрати метод обчислення.
Як побудовано цю вправу в Python
Python пропонує безліч математичних функцій у вигляді модуля math і вбудованих засобів, як-от оператор піднесення до степеня **, pow() та sum().
Однак радимо спробувати розвʼязати цю вправу без цих вбудованих засобів і модулів.
Хоча існує математична формула, яка знаходить квадратний корінь з будь-якого числа, ми пішли шляхом, де розвʼязками є лише натуральні числа (додатні цілі числа).
Квадратний корінь з будь-якого натурального числа можна обчислити, використовуючи в обчисленні лише натуральні числа.
