В этой подборке собрано 10 реализаций математических задач, которые с легкостью решаются программно. Сможете ли решить все самостоятельно?
Часть математических задач, которые мы разобрали, могут быть достаточно простыми. Но в каждой из них найдутся элегантные математические приемы, реализованные в виде программного кода.
Кратчайшее расстояние между точкой и кругом
Дан радиус круга, координаты его центра и точка. Нужно найти кратчайшее расстояние между точкой и кругом.
Обозначим радиус r. Координаты центра (x1, y1), точки (x2, y2). Пусть расстояние между точкой и кругом d. Тогда отрезок AC пересекает круг в точке B, кратчайшее расстояние отсюда будет равно отрезку BC, то есть (d-r). А d выражается как sqrt((x2 – x1)^2 – (y2 – y1)^2).
Кратчайшее расстояние от центра круга до хорды
Дан радиус круга и длина его хорды. Нужно найти расстояние от центра круга до дуги.
Радиус круга через длину и ширину его дуги
Дана дуга с высотой и шириной. Нужно найти радиус этого круга.
Обозначим радиус как r, а длину и ширину дуги – h и w соответственно. Тогда диаметр DC рассекает хорду AB на две половины, то есть на d/2. А хорда, в свою очередь, делит диаметр на отрезки h и 2r-h. Воспользовавшись теоремой о пересекающихся хордах, можно рассчитать радиус через равенство h*(2r-h)=(d/2)^2.
Определить количество квадратов, которые пересекает линия
Задана линия через две точки: (x1, y1) и (x2, y2). Нужно определить, через сколько квадратов (размером 1 на 1) пройдет эта линия.
Линия образует прямоугольник, ширина и высота которого в квадратах – M и N соответственно (она является диагональю). Предположим, что M и N не имеют общего делителя, отличного от 1. Тогда линия пересечет M – 1 квадрат по горизонтали и N – 1 квадрат по вертикали (случай 1 и 2 на рисунке ниже). В сумме, учитывая начальный квадрат: 1+ (N-1) + (M-1)=N + M – 1.
Допустим, N и M имеют наибольший общий делитель, отличный от 1. Обозначим его как q. Отсюда следует, что N/q и M/q не имеют общего делителя. Это значит, что мы можем разделить сетку на q меньших прямоугольников и считать их так же, как в первом случае: N/q + M/q – 1 для каждого. В общем случае: N + M – q. Это и есть конечная формула.
Посчитать количество шагов из точки (0, 0) в точку (x, y) зигзагом
Даны координаты (x, y). Нужно посчитать количество шагов, которые нужно проделать из точки (0, 0) в точку с координатами.
Здесь два варианта:
-
- Если x меньше y, то ответ будет равен x + y + 2*((y-x)/2).
- Если x больше или равен y – x + y + 2*(((x-y)+1)/2).
Найти простое число палиндром, которое следует за данным
Дано положительное целое число N, такое, что 1 <=N <=10^9. Найти самое маленькое простое число-палиндром, которое больше N. Из всех математических задач данной статьи, эта затрагивает самые красивые элементы математики: палиндромы и простые числа.
Простым и интуитивным решением будет идти по всем N+1 и делать проверки на простое число и палиндром. Но при решении подобных математических задач просто – не значит эффективно.
Предположим, что наше число R – искомое. Так как это палиндром, то первая половина его числа может представить его в 2 вариациях. Возьмем K как первую половину. Если K=123, то R может быть и 123321, и 12321. Так что можно взять K до 10^5, составлять из этого числа палиндром R и проверять его, простое оно или нет.
Количество пар чисел из N натуральных, чья сумма делится на K
Простым решением, наверное, будет цикл по всем парам и вычисление делимости их суммы на K. Так? Или же нет?
На самом деле можно использовать хеширование, которое заметно упростит задачу.
Проверить, можно ли выразить число как сумму двух избыточных чисел
Число является избыточным, если сумма его положительных делителей, отличных от него самого, превышает это число.
Найти максимальный куб, который можно составить, убрав минимальное количество чисел из числа
Дано число N. Задача найти такой куб, который составляется из числа N путем удаления цифр.