Ответы пользователя по тегу Математика
  • Что это такое в решении предела (lim)?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Это они просто вынесли за скобки максимальную степень x отдельно в числителе и знаменателе.
    Ответ написан
  • Как выразить динамику набора данных одним числом?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Возьмите для каждого товара набор точек {день, показатель} за сколько-то последних дней. Постройте линейную регрессию. Наклон прямой (т.е. коэффициент перед номером дня) и будет этим показателем динамики.
    Ответ написан
  • Как посчитать вероятность того, что конкретная подстрока встретится во всей строке только 1 раз?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Тут надо построить конечный автомат, который принимает строки, которые кончаются на заданную строку. Посмотрите эту статью, там в начале расписан этот автомат (секции перфикс функция - атомат КМП).

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

    Вот построили вы автомат. Теперь задача состоит в том, чтобы найти вероятность, что случайный путь в этом автомате длины n пройдет через конечное состояние ровно один раз. Для этого подсчитайте 2 вероятности: что путь из начала длины k дойдет до конечного состояния один раз, и что путь из конечного состояния длины n-k не вернется в него.

    Обе эти вероятности можно подсчитать динамическим программированием:
    P1(i, k) - вероятность того, что путь начиная с состояния i (i < n) за k шагов дойдет до состояния n первый раз. Это просто сумма по всем возможным переходам:

    P1(i, k) = sum_{c - все символы} P1(next(i, c), k-1) * p(c)

    База:
    P1(m, 0) = 1
    P1(m, k>0) = 0
    P1(i < m, 0) = 0


    Вторая вероятность: сделать k шаговиз состояния i и ни разу не войти в конечное состояние:
    P2(i, k) = sum_{c - все символы, next(i,c) < m} P2(next(i, c), k-1) * p(c)


    База:
    P1(i, 0) = 1

    Ответ к задаче - сумма по всем возможным длинам первой части пути:
    sum_{k=m..n} P1(0, k) * P2(m, n-k)

    Это решение через динамическое программирование будет O(n*m) по вермени и по памяти.

    Замкнутой формулы, как в задаче в моей статье я тут не вижу. Может, если бы вероятности всех символов были бы одинаковы, то что-то можно было бы сократить.
    Ответ написан
  • Как получить координаты точки, если известны координаты трёх других точек и расстояние от этих точек до искомой точки?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вам просто надо пересечь 3 окружности на плоскости. По "формула пересечения окружностей" гуглится, например, это или это.

    Пересекайте 2 любые окружности и из двух получившихся точек пересечения выбирайте ту, которая лежит на третьей окружности.
    Ответ написан
  • Какие два числа до 60 наименее кратны друг другу в прогрессии?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Не очень понятно, но вам, похоже, нужны такие числа, чтобы у них был максимальное наименьшее общее кратное (это то самое 42 для 6 и 7).

    Из чисел до 60, очевидно, вам подходят числа 60 и 59 - у них нет общего делителя и НОК равен просто их произведению (3540). Если нужно строго меньше 60, то берите 58 и 59. Вообще, 2 максимальных числа в промежутке будут вашим ответом. У соседних чисел НОК всегда равен их произведению и произведение двух максимальных в отрезке будет самым большим возможным значением.
    Ответ написан
  • Как проверить, попадает ли географическая точка в правильный шестиугольник?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вычтите координаты центра из координат точки. Теперь шестиугольник лежит центром в (0, 0).

    Составьте 6 уравнений сторон шестиугольника в виде Ax+By+C=0, так что C положительно (если нет - домножте на -1). Подставьте в эти 6 уравнений координаты точки, все они должны дать положительные значения (или нули, если точка на границе считается лежащей внутри в вашей задаче).

    Почему это работает? Мы просто проверяем, что точка лежит с той же стороны от всех 6 прямых, что и центр (0, 0).

    Как составить уравнения? Найдите координаты 6-ти углов. Если сторона = a, то координаты точек (a, 0), (a/2, sqrt(3)*a/2), (-a/2, sqrt(3)*a/2), (-a, 0) ...

    Для уравнения одной из сторон возьмите в виде A разность по у у соседних точек, а в виде B разность по x (но с другим знаком). Потом подставьте туда координаты одной из точек и возьмите C так, чтобы был 0.

    Можно все 6 уравнений составить на бумажке и закодировать в программе.

    Пример для первой стороны:
    A = sqrt(3)*a/2-0 = sqrt(3)*a/2
    B = a - a/2 = a/2
    C = -A*a - B*0 = -sqrt(3)*a*a/2.

    Поскольку C отрицательно, меняем знаки:
    A = -sqrt(3)*a/2
    B = -a/2
    C = sqrt(3)*a*a/2

    Для второй прямой будет 0*x-a*y+sqrt(3)*a*a/2 = 0

    И да, это работает, если предположить, что шестиугольник маленький или на плоскости. если у вас кривизна земли играет роль, то все сильно усложняется.
    Ответ написан
  • Правильно ли я понимаю запись через сигму?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Y у вас из множества R^W*H*2. Т.е. Y состоит из W*H*2 чисел проиндексированных тремя индексами - первый до w, второй до h, третий до 2. Соответственно в формуле считается сумма по всем значениям первых двух индексов. Y_wh - это пара чисел. У вас множества в примере неправильно составлены - там вместо a и b должны быть пары чисел.

    Далее, нижний индекс 2 после || - это обозначение нормы L2 в двумерном пространстве - это корень второй степени из суммы квадратов (обычное декартово расстояние). Верхний индекс после || - это просто возведение в квадрат, который отменяет извлечение корня для ||...||_2.

    Т.е. Вся эта формула говорит взять W*H*2 покомпонентные разности, возвести их в квадрат и сложить.
    Ответ написан
  • Как посчитать этот пример (суммы ряда)*(произведение ряда)+почему выводит такой результат?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    У вас ошибка в том, что вы считаете произведение один раз после цикла по k. На тот момент k после цикла равно n. Т.е. как будто у вас вместо k в формуле стоит n как граница для произведения.

    Вам надо считать proizr внутри цикла по k и домножать на него каждое слагаемое. (не забудьте инициализировать proizr единицей).
    Ответ написан
  • Как визуализировать эллиптическую кривую?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вы пробовали подставлять в вашу формулу a=-1, b=1?

    При x=-1, ваша формула выдаст y= 1.

    Почему она не рисует ничего, я не могу сказать, не видя весь ваш код. Возможно у вас там что-то ломается из-за корней из отрицательных чисел. Надо сначала проверить. что x^3+ax+b >= 0, и только в этом случае вычислять y и рисовать точки. И, да, вам надо цикл по x гнать с отрицательных чисел тоже.

    Можно сначала решить уравнение x^3+ax+b = 0, чтобы понять область определения функции.
    Ответ написан
  • Сколько существует путей и почему?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Количество сочетаний из 125 по 50. Или 125!/50!/75!
    Потому что он обязательно сделает 50 шагов вправо и 75 шагов вверх. В любом порядке. Т.е. всего 125 шагов из которых любые 50 - по горизонтали.
    Ответ написан
  • Какой алгоритм решения данной задачи?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Тут нет никакого алгоритма. Надо тупо записать формулу с математического языка, на вашем ЯП.

    Вещественные числа в Си, например - это тип float. Корень - sqrt(). Пи - M_PI. В формуле есть e в степени чего-то там. Почти в любом языке уже есть функция exp().

    Все решение - читаете 2 числа, потом присваивайте вещественной переменной один, деленное на второе число, помноженное на sqrt() от двух, умноженного на Пи. Это все умноженное на exp() от первой переменной, домноженной на себя, поделенной на 2 и на вторую переменную в квадрате.
    Ответ написан
  • Есть ли способ решить в целых числах уравнение вида ax+by+cz = d?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Для двух переменных задача решается через расширенный алгоритм Евклида.

    Решайте итеративно, добавляя новые переменные. Вот вы получили первые k переменных так что их сумма с коэффициентами равна GCD() коэффициентов. Пусть этот gcd(a1,a2,... ak) = d. Теперь решите тем же алгоритмом уравнение d*x + a(k+1)y = gcd(d,a(k+1)). y будет искомым значением последней переменной, а все предыдущие значения надо домножить на значение x.

    В конце вы нашли GCD всех коэффициентов и вы можете проверить, что правая часть на него делится. если нет - решения нет. Если делится, то надо на результат деления домножить все переменные.

    Да, тут еще спецэффект есть, что с отрицательными числами не работает GCD. Надо поменять знаки у коэффициентов, запомнить это и в конце поменять знаки у переменных назад.

    Решение за O(n log M), где n - количество переменных, M - максимальное значение коэффициентов.
    Ответ написан
  • Как найти значение выражения?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    У вас порядок проверок нарушен.

    Сначала надо проверить, что знаменатель не ноль, а только потом, что вся дробь неотрицательна.
    Для проверки, что логарифм не берется из отрицательного числа надо проверить именно это (что выражение под логарифмом >=0). Вы же почему-то проверяете, что оно равно нулю.

    И еще у вас выражение неправильно считается. Надо скобки расставить. (sqrt(X - 5 / X * X - 9) подсчитает корень из x минус 5, деленное на x^x, минус 9 - 3 слагаемых, из которых только второе дробь.

    Итого вам надо:
    - переставить местами условия, чтобы деление на 0 было первым.
    - исправить условие на логарифм из отрицательного числа
    - расставить скобки в выражении.
    Ответ написан
  • Как определить, что вектор не направлен в сторону центра координат?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Во-первых, берите две соседние стороны многоугольника. Если они коллинеарны, то берите другие 2 соседние. Но по хорошему, у вас коллинеарных соседних строн быть не должно и их можно объеденить при вводе полигона.

    Но все-равно остается вопрос, а вдруг нормаль смотрит в сторону отчки (0,0,0).
    Постройте уравнение плоскости ax+by+cz+d=0. (a,b,c) - это ваш найденный вектор нормали. d высчитывается, если подставить одну любую точку полигона.

    Теперь, если d положительно, то точка (0,0,0) лежит в том полупространстве, куда смотрит вектор и вам надо развернуть нормаль.

    Тут используется свойство знакового расстояния. Можно в уравнение плоскости подставить любую точку. Вы получите 0 для плоскости, положительные числа для одного полупространства и отрицательные для другого. Положительные в той части, куда торчит вектор нормали (ведь если отложить от точки на плоскости эту нормаль, и подсчитать знаковое расстояние, то получите тупо длину вектора нормали).
    Ответ написан
  • Как посчитать и проверить равенство?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Возьмите функцию f(x)=(1+1/x)^(1+x)-x.

    Через матан (взять производную, убедиться, что она всегда отрицательна. Подсчитать значение f(x) при x=1) можно убедится, что у функции нет корней, кроме одного на отрезке (1, +inf), ведь она всегда убывает и для единицы она положительна.

    Теперь мы знаем, что только одно число удовлетворяет этому уравнению.

    Судя по всему, корень не пи: https://www.wolframalpha.com/input/?i=%281+%2B+1%2...

    То, что он где-то там можно понять, если подсчитать функцию в точках 3.1, 3.2, 3.3 - между двумя, где функция меняет знак, и лежит корень.
    Ответ написан
  • Как правильно написать условие проверки для функции?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Эта функция не определена при x < 0 или 1-cos(x) = 0. Т.е. Если x < 0 или x= pi/2+2pi*k.

    Ф программе вычисляйте функцию по шагам. Сначала знаменатель, если он оказался 0 - not defined. Иначе смотрите, что числитель можно вычислить (x>=0).
    Ответ написан
  • Как найти точку, между двумя точками?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    векторная формула: A + (B-A)/sqrt(|A-B|)*3

    В числах
    x = Ax+(Bx-Ax)*3/sqrt((Ax-Bx)^2+(Ay-By)^2)
    y = Ay+(By-Ay)*3/sqrt((Ax-Bx)^2+(Ay-By)^2)
    Ответ написан
  • Есть ли метод генерации большого простого числа с факторизацией p - 1?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Можно такой подход: Сгенерируйте два случайных простых числа длиной n/2 бит (Генерируйте случайное число, пока не получили простое). Потом перемножте их, прибавьте 1 и проверьте, что тоже результат простой.

    Для этого надо уметь относительно быстро проверять что число простое. Можно использовать метод Миллера-Рабина. Он вероятностный, но увеличивая число итераций можно достичь произвольно маленькой вероятности ошибки.
    Ответ написан
  • Существует ли алгоритм выведения неизвестного из формулы?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    В общем случае решения может и не быть вообще. Если формула - нетривиальный полином 20-ой степени, то решения символьного вообще не существует.

    Системы символьной алгебры грубо говоря умеют кучу частных случаев. Типа туда забита формула решения линейных и квадратных уравнений.

    Судя по всему, ваша задача - весьма частная. Если формула может быть только произведением величин в каких-то степенях, то алгоритм вы уже описали - перенести все лишнее в другую сторону и взять корень нужной степени.
    Ответ написан
  • Как найти угол между средней линией и катетом в треугольнике?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Как найти угол на компьютере? Как его вообще можно вычислить? Очень редко в задаче можно выразить угол через какие-то другие известные углы в градусах. Чаще всего у вас есть какие-то координаты каких-то точек.

    Из координат можно найти все тригонометрические функции - косинус, синус, тангенс... Из них потом уже можно получить значение угла в градусах/радианах через обратные тригонометрические функции, например арктангенс (atan в решении). Она по определению возвращает угол если ей передать значения арктангенса.

    Чаще всего используют именно арктангенс, потому что, в отличии от косинусов/синусов, он хорошо работает для любого угла (у арксинуса, например, невозможно различить 45 и 135 градусов - значение синуса одно и то же). У арксинуса и арккосинуса нужно добавлять какие-то проверки сверху для решения неоднозначностей.

    Почему в задаче такой ответ? atan() передаются косинус и синус угла, возможно растянутые на один и тот же коэффициент. Координаты точки М - (1/2 AB, 1/2 BC), ведь это середина AC. Представьте перпендикуляр из точки М на ость OX(BC). В получившемся треугольнике будет прямой угол, гипотенуза BM и катеты с длинами 1/2 AB, 1/2 BC. Соответственно, косинус/синус искомого угла будут 1/2/AM*AB, 1/2/AM*BC. Теперь вспоминаем, что atan() можно передавать значения, умноженные на константу. Вот пусть константа будет 2/AM. Тогда остаются AB и BC.

    Еще, можно смотреть на atan() так - передайте ему координаты конца вектора и он вернет угол между OX и вектором.
    Ответ написан