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

    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 имеет большой набор табличных интеграллов и пробует кучу всяких методов, но работает далеко не на всех интеграллах.
    Ответ написан
    Комментировать
  • Как объединить массивы с дубликатами в уникальные списки?

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

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

    Суть в том, чтобы построить граф, где все различные элементы всех массивов будут вершинами. Ребра есть между двумя вершинами, если соответствующие им элементы присутствуют в одном и том же входном массиве.

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

    Чуть проще и быстрее будет работать решение через систему непересекающихся множеств (DSU). Сначала пройдитесь по всем массивам и, как и в первом решении, перенумеруйте все уникальные элементы. Заведите DSU, где каждый элемент - сам себе множество.

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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Очень похоже на переполнение. Попробуйте тест, где одно устройство и миллион задач по 100 каждая.
    Ответ написан
    Комментировать
  • Фибоначчи: Возможно ли найти порядковый номер последовательности Фибоначчи ( x ), исходя из числа ( y )?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Не школьник, но вроде все просто.
    У вас есть y = B^x/A
    Дано y, отсюда x= log_B(A*y) = ln(A*y) / ln(B).

    Надо будет округлить. Формула может давать сбои на мелких числах.
    Ответ написан
    1 комментарий
  • Как посчитать кол-во возможных исходов?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Ответ - количество сочетаний по n-1 из (n+m-2), или сколько способов выбрать n-1 объект из n+m-2.

    Это потому что нужно обязательно сделать n-1 шагов вниз и m-1 шагов вправо. Вопрос только, в каком порядке их делать. Всего будет сделано n-1+m-1 шагов и из них надо выбрать какие-то n-1 вниз, остальные будут шаги вправо. Вот и получаются сочетания.

    Можно считать треугольником Паскаля, получится в точности то же, что описал poznavaka,
    можно считать по формуле факториалов: (n+m-2)! / (n-1)! / (m-1)!

    Для вашего примера, где N=3 и M=4 ответ будет 5!/2!/3! = 120/2/6 = 10.
    Ответ написан
    Комментировать
  • Какие существуют алгоритмы поиска равноудаленных прямоуголиников?

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

    1) найти ближайший сверху (слева/снизу/справа) из тех, которые имеют перекрытие.
    2) повторить операцию, найдя следующий сверху. Расстояние между ними взять за d.
    3) продолжить идти вверх. Если следующий ближайший тоже на расстоянии d - нарисовать промежуток. Если нет, то остановится.
    4) Зная ближайший прямоугольник из пункта 1) и расстояние d - можно его отступить вниз и у вас есть точка примагничивания.

    Можно ускорить алгоритм немного. Сначала за один проход выделите все прямоугольники, которые выше данного, но пересекаются с ним по оси X. Отсортируйте их снизу вверх по нижней границе. Теперь в пунктах 1,2,3 надо рассматривать только один следующий прямоугольник из списка.

    Если есть пересечения то можно или выбрасывать прямоугольники, пересекающиеся с текущим, или остановится, как будто следующего прямоугольника нет.

    Что бы ускорить еще больше, когда у вас очень много прямоугольников на экране, можно хранить их в quad tree и из него вытаскивать прямоугольники, которые перекрываются с заданным и выше его уже в правильном порядке. Но скорее всего просто пройтись по списку всех прямоугольников будет достаточно.
    Ответ написан
    Комментировать
  • Очень быстрый алгоритм умножения длинных чисел, куда копать?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    При умножении на маленькое число всякие хитрые алгоритмы типа преобразования Фурье или Карацубы лаже медленнее тупого умножения в лоб: Просто проходитесь по большому числу от младших разрядов к старшим, умножете на маленький множитель, прибавляете перенос. Потом берете остаток от деления на базу (если множитель маленький, то быстрее будет просто вычесть несколько раз в цикле вместо модуля), а результат целочисленного деления записываете в перенос.
    Ответ написан
    Комментировать
  • Делимость двоичного числа на N?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Динамическое программирование:
    F(a,b,r) = может ли число составленное из a едениц и b нулей давать остаток r при делении на N.
    База: F(0,0,0) = true, F(0,0,r) = false.

    Пересчет: Итеративный пересчет такой - F(a,b,r) => то F(a+1,b,(2*r+1) % N) и F(a,b+1,(2*r+1) % N) Тут мы знаем, что есть число, дающее остаток r из a едениц и b нулей. Если мы к нему припишем в конец 1, то остаток будет (2*r+1)%N, а единиц будет на одну больше. Также почти можно приписать 0.

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

    Теперь можно найти x такое, что 2x = 1 (mod N) - обратное к 2 по модулю N. Смотрите расширенный алгоритм Эвклида для этого.

    Дальше можно вычислять так (N - нечетное):
    F(a,b,r) = F(a-1,b, (r-1)*x % N) || F(a, b-1, r*x % N).

    Объяснение тут тоже простое - число или оканчивается на 0 или на 1. Попробуем оба варианта и сотрем последнюю цифру. Оставшееся число должно давать остаток (r-1)*x % N или r*x % N соответственно.

    Ответ: Если F(A,B,0) - true, то число делящееся на N есть. Для нахождения числа надо дополнительно запоминать, какие цифры приписывались к чисам при рассчетах выше.
    Ответ написан
    1 комментарий
  • Пересечение двух линии в 3D?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Во первых, определите, что линии лежат на одной плоскости и не паралельны.
    Обозначим точки первой прямой как A1 и B1, а второй - A2 и B2.

    Введем вектора D1 = B1-A1 и D2 = B2-A2. Введем векторное уравнение.

    D1*t + D2*r + (A1-A2) = 0.

    Тут 2 неизвестные t и r, 3 уравнения (расписать по x, y и z).

    Если система уравнений решается, то точка пересечения A1+D1*t или A2 - D2*r.

    Тут правда предется повозиться со случаями. Надо попробовать решить систуму только для x, y, потом проверить в z. Если не получилось, то еще надо попробовать решить в x, z, потом поробовать подставить полученные r и t в у.
    Ответ написан
    Комментировать