proglib
Сообщение

Почему специалистом по кибербезопасности быть интереснее, чем разработчиком или сисадмином? Приглашаем на вебинар от HackerU

Почему специалистом по кибербезопасности быть интереснее, чем разработчиком или сисадмином? Приглашаем на вебинар от HackerU

Программная реализация 10 математических задач

0
11977

В этой подборке собрано 10 реализаций математических задач, которые с легкостью решаются программно. Сможете ли решить все самостоятельно?

Программная реализация 10 математических задач

Часть математических задач, которые мы разобрали, могут быть достаточно простыми. Но в каждой из них найдутся элегантные математические приемы, реализованные в виде программного кода.

Кратчайшее расстояние между точкой и кругом

Дан радиус круга, координаты его центра и точка. Нужно найти кратчайшее расстояние между точкой и кругом.

Дано: x1 = 4, y1 = 6, x2 = 35, y2 = 42, r = 5 
Результат: 42.5079

Дано: x1 = 0, y1 = 0, x2 = 5, y2 = 12, r = 3
Результат: 10

Кратчайшее расстояние между точкой и кругом

Обозначим радиус r. Координаты центра (x1, y1), точки (x2, y2). Пусть расстояние между точкой и кругом d. Тогда отрезок AC пересекает круг в точке B, кратчайшее расстояние отсюда будет равно отрезку BC, то есть (d-r). А d выражается как sqrt((x2 - x1)^2 - (y2 - y1)^2).

def dist(x1, y1, x2, y2, r):
    result = ((x2-x1)**2 + (y2-y1)**2)**0.5 - r
    return result


if __name__ == '__main__':
    example = 4, 6, 35, 42, 5

    print(dist(*example))

Кратчайшее расстояние от центра круга до хорды

Дан радиус круга и длина его хорды. Нужно найти расстояние от центра круга до дуги.

Вход: r = 4, d = 3 
Результат: 3.7081

Вход: r = 9.8, d = 7.3
Результат: 9.09492

Кратчайшее расстояние от центра круга до хорды

def dist(radius, chord):
    result = (radius**2 - chord**2/4)**0.5
    return result


if __name__ == '__main__':
    example = 4, 3

    print(dist(*example))

Радиус круга через длину и ширину его дуги

Дана дуга с высотой и шириной. Нужно найти радиус этого круга.

Вход: d = 4, h = 1 
Результат: радиус круга = 2.5

Вход: d = 14, h = 8
Результат: радиус круга = 7.0625

Обозначим радиус как r, а длину и ширину дуги – h и w соответственно. Тогда диаметр DC рассекает хорду AB на две половины, то есть на d/2. А хорда, в свою очередь, делит диаметр на отрезки h и 2r-h. Воспользовавшись теоремой о пересекающихся хордах, можно рассчитать радиус через равенство h*(2r-h) = (d/2)^2.

Радиус круга через длину и ширину его дуги

def radius(width, height):
    result = width**2 / 8*height + height/2
    return result


if __name__ == '__main__':
    example = 4, 1

    print(radius(*example))

Определить количество квадратов, которые пересекает линия

Задана линия через две точки: (x1, y1) и (x2, y2). Нужно определить, через сколько квадратов (размером 1 на 1) пройдет эта линия.

Вход: (x1 = 1, y1 = 1), (x2 = 4, y2 = 3)
Результат: 4 (на рисунке ниже линия пересекает 4 квадрата)

Вход: (x1 = 0, y1 = 0), (x2 = 2, y2 = 2)
Результат: 2

Программная реализация 10 математических задач
Линия образует прямоугольник, ширина и высота которого в квадратах – M и N соответственно (она является диагональю). Предположим, что M и N не имеют общего делителя, отличного от 1. Тогда линия пересечет M - 1 квадрат по горизонтали и N - 1 квадрат по вертикали (случай 1 и 2 на рисунке ниже). В сумме, учитывая начальный квадрат: 1+ (N-1) + (M-1) = N + M - 1.

Программная реализация 10 математических задач

Допустим, N и M имеют наибольший общий делитель, отличный от 1. Обозначим его как q. Отсюда следует, что N/q и M/q не имеют общего делителя. Это значит, что мы можем разделить сетку на q меньших прямоугольников и считать их так же, как в первом случае: N/q + M/q - 1 для каждого. В общем случае: N + M - q. Это и есть конечная формула.

from math import gcd


def number_of_crossed_squares(x1, y1, x2, y2):
    dx = abs(x2 - x1)
    dy = abs(y2 - y1)

    result = dx + dy - gcd(dx, dy)  # gcd - встроенная функция поиска наибольшего общего делителя

    return result


if __name__ == '__main__':
    example = 1, 1, 4, 3

    print(number_of_crossed_squares(*example))

Посчитать количество шагов из точки (0, 0) в точку (x, y) зигзагом

Даны координаты (x, y). Нужно посчитать количество шагов, которые нужно проделать из точки (0, 0) в точку с координатами.

Вход: x = 4, y = 4
Результат: 8
На рисунке ниже этот вариант разобран визуально

Вход: x = 4, y = 3
Результат: 9

Вход: x = 2, y = 1
Результат: 5

Программная реализация 10 математических задачЗдесь два варианта:

    1. Если x меньше y, то ответ будет равен x + y + 2*((y-x)/2).
    2. Если x больше или равен y – x + y + 2*(((x-y)+1)/2).
def count_steps(x, y):
    if x < y:
        return x + y + 2 * ((y - x) // 2)
    else:
        return x + y + 2 * (((x - y) + 1) // 2)


if __name__ == '__main__':
    x, y = 4, 3
    print(count_steps(x, y))

Найти простое число палиндром, которое следует за данным

Дано положительное целое число N, такое, что 1 <= N <= 10^9. Найти самое маленькое простое число-палиндром, которое больше N. Из всех математических задач данной статьи, эта затрагивает самые красивые элементы математики: палиндромы и простые числа.

Вход: 8
Результат: 11

Вход: 7000000000
Результат: 10000500001

Простым и интуитивным решением будет идти по всем N+1 и делать проверки на простое число и палиндром. Но при решении подобных математических задач просто – не значит эффективно.

Предположим, что наше число R – искомое. Так как это палиндром, то первая половина его числа может представить его в 2 вариациях. Возьмем K как первую половину. Если K = 123, то R может быть и 123321, и 12321. Так что можно взять K до 10^5, составлять из этого числа палиндром R и проверять его, простое оно или нет.

import math


# Функция, которая проверяет, является ли число простым
def is_prime(number):
    return number > 1 and all(number % divider for divider in range(2, int(math.sqrt(number)) + 1))


def next_prime_palindrome(n):
    for k in range(1, 10**5+1):

        # проверка на палиндром нечетной длины
        s = str(k)
        x = int(s + s[-2::-1])  # пример: s = '1234', x = int('1234321')

        if x >= n and is_prime(x):
            return x

        # проверка на палиндром четной длины
        s = str(k)
        x = int(s + s[-1::-1])  # пример: s = '1234' to x = int('12344321')

        if x >= n and is_prime(x):
            return x


if __name__ == '__main__':
    test = 7000000

    print(next_prime_palindrome(test))

Количество пар чисел из N натуральных, чья сумма делится на K

Простым решением, наверное, будет цикл по всем парам и вычисление делимости их суммы на K. Так? Или же нет?

На самом деле можно использовать хеширование, которое заметно упростит задачу.

Вход: N = 10, K = 5
Результат: 9
Все пары, чья сумма делится на 5: (1, 4), (1, 9), (6, 4), (6, 9), (2, 3), (2, 8), (3, 7), (7, 8) и (5, 10)

Вход: N = 7, K = 3
Результат: 7
Все пары, чья сумма делится на 3:  (1, 2), (1, 5), (2, 4), (2, 7), (3, 6), (4, 5) и (5, 7).
def find_pair_count(n, k):
    count = 0

    # Создаём массив размером k
    reminders = [0 for _ in range(k)]

    # Первым элементом массива является количество натуральных чисел, которые при делении
    # на K в остатке дают 0. Сам 0 при этом мы не считаем, так как это не натуральное число.
    reminders[0] = n // k

    # Заполняем массив количеством целых чисел, остаток от деления на K, который равен индексу
    for i in range(1, k):
        reminders[i] = (n - i) // k + 1

    # Проверяем, является ли k четным
    if k % 2 == 0:
        # Считаем пары, где оба числа делятся на K
        count += (reminders[0] * (reminders[0] - 1)) // 2

        # Считаем пары, где первое число - остаток от деления, а второе - это разность K и этого остатка
        for i in range(1, k // 2):
            count += reminders[i] * reminders[k - i]

        # Считаем пары, где оба остатка равны K / 2
        count += (reminders[k // 2] * (reminders[k // 2] - 1)) // 2

    else:
        # Считаем пары, где оба числа делятся на K
        count += (reminders[0] * (reminders[0] - 1)) // 2

        # Считаем пары, где первое число - остаток от деления, а второе - это разность K и этого остатка
        for i in range(1, k // 2 + 1):
            count += reminders[i] * reminders[k - i]

    return count


if __name__ == '__main__':
    # Print the count of pairs
    print(find_pair_count(10, 4))

Проверить, можно ли выразить число как сумму двух избыточных чисел

Число является избыточным, если сумма его положительных делителей, отличных от него самого, превышает это число.

Вход: N = 24 
Результат: 12, 12

Вход: N = 5
Результат: -1 (невозможно)
from math import sqrt


def abundant(limit):
    abundant_numbers_set = set()

    for i in range(1, limit):

        sum_of_divisors = 1
        for j in range(2, int(sqrt(i)) + 1):

            if i % j == 0:
                sum_of_divisors += j

            if i / j != j:
                sum_of_divisors += i // j

        if sum_of_divisors > i:
            abundant_numbers_set.add(i)

    return abundant_numbers_set


def is_sum_of_abundant(n):
    v = abundant(n)

    for i in range(1, n + 1):
        if list(v).count(i) and list(v).count(n - i):
            return True, i, n-i

    return False


if __name__ == '__main__':
    example = 24
    print(is_sum_of_abundant(example))

Найти максимальный куб, который можно составить, убрав минимальное количество чисел из числа

Дано число N. Задача найти такой куб, который составляется из числа N путем удаления цифр.

Вход: 4125
Результат: 125
Объяснение:
125 = 5^3. Можно составить 125, убрав 4 из числа 4125

Вход: 876
Результат: 8
Объяснение:
8 = 2^3. Можно сформировать 8, убрав 7 и 6 из числа 876
import math


def perfect_cubes(limit):
    cubes = list()
    for i in range(1, math.ceil(limit ** (1. / 3.))):
        cube = i ** 3
        cubes.append(str(cube))

    return cubes


def find_largest_cube(num):
    cubes = perfect_cubes(num)
    num = str(num)
    cubes = cubes[::-1]

    cubes_number = len(cubes)

    # Цикл по всем кубам
    for i in range(cubes_number):
        current = cubes[i]

        digits_count_in_cube = len(current)
        index = 0
        digits_count_in_number = len(str(num))
        for j in range(digits_count_in_number):

            # проверяем, что цифра в кубе совпадает с цифрой в числе
            if num[j] == current[index]:
                index += 1

            if digits_count_in_cube == index:
                return current

    # Если цикл завершается, такого числа нет
    return "Not Possible"


if __name__ == '__main__':
    example = 4125
    print(find_largest_cube(example))

Источник

А вы делали программную реализацию математических задач? Каких? :)

РУБРИКИ В СТАТЬЕ

МЕРОПРИЯТИЯ

Комментарии 0

ВАКАНСИИ

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ

BUG