Ответы пользователя по тегу Математика
  • Как найти значение выражения?

    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 для плоскости, положительные числа для одного полупространства и отрицательные для другого. Положительные в той части, куда торчит вектор нормали (ведь если отложить от точки на плоскости эту нормаль, и подсчитать знаковое расстояние, то получите тупо длину вектора нормали).
    Ответ написан
    1 комментарий
  • Как посчитать и проверить равенство?

    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)
    Ответ написан
    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 и вектором.
    Ответ написан
    1 комментарий
  • Простая производная?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Это производная комбинации: (f(g(x)))' = f'(g(x))*g(x).

    В вашем случае f(z) = z^2, g(w)=y-w*x.

    f(g(w)) = f(y-w*x) = (y - w*x)^2

    f'(z) = 2z, g'(w) = -x

    Подставляем в первую формулу:
    2(y - w*x)*(-x) - ровно то, что написано в книге.
    Ответ написан
    Комментировать
  • Как составить алгоритм слияния и разложения двух чисел?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Невозможно решить вашу задачу. У вас 65535*255 вариантов входных данных и по условию они должны выдавать разные значения. Итоговое количество чуть не дотягивает до 2^24 - а значит в 16 бит его никак не засунуть.
    Ответ написан
    Комментировать
  • Где мне может понадобится линейная алгебра?

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

    В игрострое в 3D куча линейной алгебры, но и в 2D куча аналитической геометрии где часто встречается линейная алгебра.
    Ответ написан
    Комментировать
  • Как доказать равенство множеств?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Формально по законам логики и определениям.
    Что значит какой-то элемент принадлежит правому множеству?
    x in A\(A\B), тогда и только тогда, когда x in A И x not in (A\B),
    Чтобы вторая половина после И выполнялось, надо наложить отрицание не x in (A\B) что тоже самое, что (x in A И x not in B). По законам логики это будет (x not in A ИЛИ x in B). добавляем к этому первую часть и раскрываем скобки:

    x in A И (x not in A ИЛИ x in B) = (x in A И x not in A) ИЛИ (x in A И x in B).

    Первая часть - всегда ложна и сокращается, остается только (x in A И x in B), что по определению x in A и B. Мы везде использовали только эквивалентность и из определения, что элемент принадлежит правому множеству, получили определение, что элемент принадлежит левому множеству. Значит эти 2 множества равны.
    Ответ написан
    Комментировать
  • Как найти n+1 ое простое число за минимальное время?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Есть - перебирайте следующее число, начиная с p_(n-1)+1, потом проверяйте делимость на все простые числа, пока они меньше корня и текущего числа.

    Можно применить следующие оптимизации - начинать с p_(n+1)+2 и идти с шагом 2 (только нечетные числа). Перебирать числа только вида 6k-1 и 6k+1 (k изначально floor(p_(n-1)+3) / 6). Вместо высчитывания корня, в коде должно быть возведение в квадрат - что-то вроде while (i < n && p[i]*p[i] <= x) ... i++;.

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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    В криптографии просто куча применений. Всякие RSA, DH, эллиптические кривые - это все основано на свойствах некоторых особых конечных полей.

    Но мне нравится такой пазл: есть таблица из лампочек-кнопок n x m. Какие-то горят, какие-то - нет. Можно нажать на какую-то лампочку и она переключится. Но вместе с ней переключатся и 4 соседние лампы (если нажали на угловую кнопку - то только 2). Нужно погасить все лампы за минимальное количество нажатий. Как ее вообще решать без полного или частичного перебора? Важно заметить, что 2 раза нажимать на лампу бессмысленно, потому что эти 2 нажатия просто отменят друг друга. Еще не важно, в каком порядке нажимать на лампы. Конечный результат будет одинаковый.

    А дальше, подключается математика! Введем переменные x_ij - сколько раз мы нажимаем на лампочку в позиции i, j. Эти переменные - это элементы поля по модулю 2. Потому что 2 раза нажать на кнопку - то же самое, что и 0 раз нажать. Составляем линейные уравнения, что сумма нажатий на все кнопки, влияющие на данную лампу - дает 0 или 1 по модулю 2 (в зависимости от того, горит ли эта лампа изначально).

    А дальше эту систему уравнений можно просто решать методом гаусса. Почему? Ведь он работает с вещественными числами? Но нет! Гауссу по-фигу над каким полем работать. Делаем все вычисления по модулю 2 - и получим решение в виде 0 и 1 для всех переменных.

    Поля по модулю простых чисел еще можно, например, использовать для реализации быстрого преобразования фурье для быстрого умножения длинных чисел без использования операций с float, что требуется в стандартной реализации (она вообще с комплексными числами работает). И такая реализация быстрее и точнее.
    Ответ написан
    1 комментарий
  • Какой будет ответ?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Если считается, что зависимость выхода от входа линейная, то ее можно составить так:
    y = k*x+b

    И вам даны 2 значения для x и y:
    0 = k*2.3+b
    400 = k*40.6+b


    Вам надо найти k*11.6+b.

    Система из двух линейных уравнений просто решается аналитически, без конкретных значений:
    y1 = k*x1+b
    y2 = k*x2+b
    
    y1-y2 = k*(x1-x2) +(b-b)
    k = (y1-y2)/(x1-x2)
    b = y1 - k*x1 = y1 - (y1-y2)/(x1-x2)*x1
    
    y = (y1-y2)/(x1-x2)*(x-x1) + y1


    Подставляем туда ваши значения при x = :
    y = (0-400)/(2.3-40.6)(11.6-2.3) + 0 = 400/38.3*9.3 = 43.81
    Ответ написан
    Комментировать
  • Количество комбинаций чисел JavaScript?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    В тупую можно подсчитать 2-мя вложенными циклами.

    ans = 0;
    for (i = 1; i <= 3; ++i) {
      for (j = 1; j <= 3; ++j) {
        mn = max(n - i - j - 3, 1);
        mx = n - i - j - 1;
        if (mn <= mx)
          ans += mx - mn + 1;
      }
    }


    Работает так - перебираем сколько символов в первом и втором блоке. После этого считаем, сколько минимально и максимально может быть символов в третьем блоке (оставляя на последний от 1 до 3 символов). Прибавляем к ответу количество возможных вариантов для длины третьего блока.

    Но это если у вас параметры фиксированные (4 блока 1-3 символа). Если параметры могут меняться, то решение - динамическое программирование f(i,k) - сколько способов разбить первые i символов на k блоков.

    База: f(0,0) = 1, f(0, k>0) = 0, f (i>0, 0) = 0;
    Пересчет: f(i,k) = sum_{l=min_length...min(max_length, i)}(f(i-l,k-1)).
    Ответ: f(n, num_blocks).
    Ответ написан
    Комментировать
  • Как быстро найти зависимость элементов в последовательном ряду?

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

    Если же возможна только зависимость вида +a_0, +a_1, +a_2,..., +a_k, +a_0, +a_1... т.е. повторяющийся фиксированный паттерн приращений, то есть быстрое и простое решение.

    Во первых, если вам дано 10 чисел, то всегда можно сказать, что есть паттерн длиной в 9 приращений.
    Но можно найти кратчайший паттерн с помощью алгоритма поиска периода в строке. Буквально, по определению, нужный вам кратчайший паттерн (типа {+3, -2} для второго примера) будет периодом строки. Правда, тут не строка, а массив чисел, но это вообще никак не меняет алгоритмы. Просто у вас алфавит нестандартный.

    Сначала от массива чисел перейдите к массиву приращений.

    Потом можно применить жадное наивное решение - просто перебираете все возможные значения периода от 1 до n/2 и проверяете, что a[i] == a[i+str] для всех i. Как только все совпало - вы нашли период. Это решение за квадрат. Если чисел вам задано много, то можно применить префикс функцию: найдите значение префикс функции (p) для всей строки и, если ее значение больше половины длины строки, то у строки есть период n-p. Это будет линейное решение.

    Еще можно применить алгоритм Дюваля. Тоже линейное решение, но более сложное в реализации и понимании.
    Ответ написан
    4 комментария
  • Как построить уравнение эллипса с заданным центром, который касается двух заданных отрезков в заданных точках?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Во-первых, перенесите центр системы координат в центр элипса - вычтите его из всех координат точек касания. В самом конце надо будет сделать обратный переход и подставить x=x-x0, y=y-y0 в уравнение.

    При выборе правильной системы координат, эллипс становится окружностью, ведь его уравнение x^2/a^2+y^2/b^2=1. Все остальное - это от переноса центра координат и поворота эллипса.

    Давайте переобразуем нашу систему координат, повернув на какой-то угол и сжав вдоль оси X, чтобы получить круг.

    с- cos(угол), s=sin(угол) k- коэффициент сжатия.

    Тогда новая система координат - {kc,ks}, {s,-c}. Преобразуем в эту систему координат тички касания и вектора касательных. Они так и останутся касающимися нашего эллипса, ведь преобразования поворота и сжатия оставит прямые прямыми, а эллипс - эллипсом (или кругом).

    Если x1,y1 - точка касания, а {xv, yv} - вектор касательной, то:

    x1' = x1*kc+y1*ks

    y1' = x1*s-y1*c

    xv' = xv*kc+yv*ks

    yv' = xv*s-yv*c

    Это просто формулы перобразования между системами координат. Аналогично можно сделать для x2', y2', xw,' yw'.

    Теперь составим уравнения. Мы же хотим найти преобразование, в котором наш эллипс будет окружностью. Во-первых, расстояния до точек касания должны быть одинаковыми. Во-вторых, касательные вектора должны быть перпендикулярны векторам из начала координат к точкам касания.

    Если аккуратно расписать x1'*x1'+y1'*y1'-x2'*x2'-y2'*y2' = 0, и заменить c^2=1-s^2, то будет:

    (y1*y1-y2*y2-x1*x1+x2*x2)*kkss + (2*x1*y1-2*x2*y2)kkcs + (x1*x1-x2*x2-y1*y1+y2*y2)ss +(2*x2*y2-2*x1*y1)*cs +(x1*x1-x2*x2)*kk+(y1*y1-y2*y2)=0

    Советую не верить мне тут с коэффициентами, а пепроверить их самостоятельно.

    Аналогичные уравнения для касательных x1'*xv'+y1'*yv' = 0:
    (y1*yv-x1*xv)*kkss + (x1*yv+y1*xv)kkcs + (x1*xv-y1*yv)ss +(-x1*yv-y1*xv)*cs +(x1*xv)*kk-y1*yv=0

    Важно заметить, что у нас тут 3 уравнения вида:

    A*kkss+B*kkcs-Ass-Bcs+Ckk+D=0, где константые коэффициенты A,B,C,D (разные в трех уравнениях) и 3 переменные k,s,c. Еще есть дополнительное условие s*s+c*c=1, это же синусы/косинусы угла, и k!=0. k может быть и отрицательным, это означало бы отражение и сжатие системы координат. Под наши цели подходит.

    Обратите внимание, 3-е и 4-ое слагаемые идут с теми же коээфициентами, что и 1-е и 2-е, но с обратными знаками. Можно подобрать такие коээфициенты для первых двух уравнений, что если их прибавить к тертьему уравнению, то коэффициенты перед kkss,kkcs,ss,cs - все станут равны нулю. Это надо решить систему из двух линейных уравнений.
    Пусть коээфициенты в уравнениях A1,A2,A3,B1,B2,B3,C1 и т.д. (напоминаю, это константы, вычеслимые через заданные координаты точек и векторов касания). Введем 2 переменные x, y - коээфециенты, с какими прибавлять первые 2 уравнения к тертьему. Условия: A1*x+A2*y+A3=0, B1*x+B2*y+B3=0. Решив эту систему уравнений, найдя коээфициенты и прибавив первые 2 уравнения к тертьему, вы получите уравнение вида

    C4*k*k+D4=0

    Элементарно решив его, вы найдете k. Подставив его в 2 предыдущих уравнения вы получите 2 уравнения вида:

    A4*ss+B4*cs + D4 = 0

    Это тригонометрическое уравнение можно решить, дописав множитель cc+ss к D4, получив уравнение вида:

    (A4+D4)*ss+B5*cs+D4*cc = 0.

    Теперь осталось поделить обе части на с^2 и решить квадратное уровнение для tan(). Еще, правда, надо рассмотреть подходит ли c=0,s=1 (s=-1 рассматривать не надо, Ведь без разницы, в какую сторону вращать на 90 градусов - все равно ось сжатия будет одна и та же).

    Теперь зная тангенс найдите косинус и синус (школьные тригонометрические формулы, вроде c=sqrt(1/(1+t^2)).

    Все, мы знаем k,c,s. Подставив их в формулы для x1',y1' мы узнаем радиус окрудности (расстояние до нуля). Пусть радиус будет r.

    Теперь уравнение эллипса x'^2+y'^2 = r^2.

    Подставляем преобразование:

    x'=x*k*s+y*k*c, y' = x*s-y*c. Потом не забываем сделать замену x<-x-x0, y<-y-y0, чтобы верунть центр эллипса в заданное место.

    Все эти замены надо аккуратно подставить и раскрыть скобки в уравнении x'^2+y'^2 = r^2 и получить ваши коээфициенты в уравнении Ax2+ Bxy + Cy2 + Dx + Ey = F. Потом поделите обе части на F.

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

    Edit:

    Тут есть потенциальная проблема - надо решить систему линейных уравнений и 2 квадратных уравнения в процессе решения. Я не могу доказать, но верю всей душой, что, если эллипс существует, то все эти уравнения будут решатся в вещественных числах, без делений на 0 и квадратных корней из отрицательных чисел.
    Ответ написан
    7 комментариев
  • Почему группа Шоттки выглядит неправильно?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Из обсуждения под вопросом стало понятно, что нужно, чтобы окружности в узоре касались, т.е. образовывали связную структуру. Для этого надо, во первых, чтобы исходные окружности касались и, во вторых, чтобы преобразование оставляло точки касания на месте. Можно подобрать множество таких преобразований, но подойдет например преобразование инверсии, которое оставляет на месте сами окружности целиком.
    Ответ написан
    Комментировать
  • Есть ли библиотека на javascript, которая может находить сложные интегралы и брать обратную функцию?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Даже тренированный студент и профессор, не всегда возьмет какой-нибудь хитрый интегралл, даже если он берется в элементарных функциях. У вас задача уровня "нужна библиотека, которая по описанию задачи, возвращает алгоритм ее решения". Короче говоря, такого нет. wolframalpha имеет большой набор табличных интеграллов и пробует кучу всяких методов, но работает далеко не на всех интеграллах.
    Ответ написан
    Комментировать