Ответы пользователя по тегу Математика
  • Как узнать какое будет следующее число?

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

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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Да, нижние индексы - это обозначение системы счисления. Так, 110 в двочиной - это 6 в десятичной, или вот то разложение по степеням двойки.
    Ответ написан
  • Какая будет единая формула для ячейки?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Разница по горизонтали всегда +2. Значит число из строки 2 будет входить с коэффициентом 2.
    По вертикали разница на -1. Значит число из столбца B будет с коэффициентом -1.

    Итак, формула -1*$B3+2*C$2 - 1 . -1 в конце подбираем так, чтобы в самой первой ячейке оказался 0.
    Ответ написан
    Комментировать
  • Как решать задачи на разбиение фигуры на сектора по цветам?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Лемма бернсайда. Гуглите. Но суть в том, что надо подсчитать количество раскрасок, которые не меняются при повороте на какой-то угол. Для всех углов сложить и поделить на количество поворотов.

    Поворот на 1<=i<=42 секторов создает gcd(i,42) циклов, каждый из которых должен быть окрашен целиком в один из 6 цветов. Т.е. получается 6^gcd(i,42) раскрасок, инвариантных для поаорота на i секторов.

    Отсюда ответ к задаче: sum i=1..42 6^gcd(i,42)/42.
    Ответ написан
    2 комментария
  • Как соединить рандомные точки на координатной плоскости в многоугольник?

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

    Надо точки как-то отсортировать. Например, берете самую нижнюю, из всех таких самую левую. Сортируете все оставшиеся точки по углу, относительно этой (по значению atan2(yi-y0, xi-x0)), при равенсве угла по расстоянию (не важно по возрастанию или убыванию). Потом в таком порядке их соединяйте, пересечений не будет.

    В примере из вопроса оно как раз отсортирует их как на картинке.

    Edit, а еще, можно вместо atan сравнивать углы через векторное произведение. Если входные данные - целые точки, то вообще все вычисления будут в целых переменных.
    Ответ написан
    3 комментария
  • Как доказать, что группы неизоморфны?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Надо найти какое-то противоречие в структурах групп.
    Например, в C есть элементы {1, i, -1, -i}. Это 4 различных элемента которые при умножении сами на себя дают 1. Если группы изоморфны, то должны быть 4 соответствующих им элемента в R, все - квадратные корни из 1. Но в R таких только 2: {1, -1}.

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

    Опять же, 0 в {Q, *} не имеет аналога в {R, +}
    Ответ написан
    Комментировать
  • Поможете сделать код лучше, чем у меня сейчас, a³+b³=c³?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    2. Этот код не для Windows;


    Там нет ничего платформо-зависимого. Если установите какой-нибудь mingw на windows, то оно makefile съест.

    В крайнем случае, установите любой C компилятор и введите команду вручную (последняя строчка тут)

    3. Если я в формуле a³+b³+c³=3 поменяю 3, на 0 будет ли программа правильно считать?

    Там в описании написано "cubefree k = +/- 3 mod 9 at most 1000", т.е. для k=0 не сработает.

    Поможете сделать код лучше?


    Выкиньте цикл по c. Вам не надо его перебирать, а вам надо решить уравнение c³=3-a³+b³.
    Для чего просто вычислите значение справа, потом возьмите кубический корень: int((3-a**3-b**3)**(1/3.0)). Не забудьте только проверить, что это значение c подходит, ибо тут корень округляется до целого. И не факт, что уравнение выполняется.
    Ответ написан
  • Как решить эту задачу?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    У вас 7 неизвестных и 3 уравнения. Так что однозначно вы найти значения переменных никак не сможете. Но и найти вам надо какую-то сумму. Есть шанс, что как-то комбинируя, складывая, вычитая и домножая левые части этих уравнений можно получить искомую сумму. Иными словами, вам надо вектор (16, 25..100) представить в виде линейной комбинации векторов (1, 2..49), (4, 9..64) и (9, 16..81). Обратите внимание, что там везде получаются суммы трех квадратов равны следующему.

    Вам надо подобрать такие 3 коэффициента, что x*n^2 + y(n+1)^2+z(n+2)^2 = (n+3)^2. Для n=1..7. У вас тут квадратные многочлены от n получаются, равны они в 7 точках, так что они должны быть равны вообще при любых n. Значит, вам надо раскрыть скобки, сгрупировать степени n и приравнять к 0 все коэффициенты.

    Так вы получите 3 уравнения на 3 переменные x, y, z.
    x+y+z=1
    2y+4z=6
    y+4z=9

    Отсюда получается x=1 y=-3 z=3

    В итоге получаете 1*1-3*12+3*123 - это ваш ответ.
    Ответ написан
    2 комментария
  • Не работает math.pow, что я делаю не так?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Скобки в делителе в переменной numerator пропустили.
    Еще, у вас имена переменных кривые. Зачем-то назвали два множителя "числитель" и "делитель". Причем дробь целиком считается в первой.
    Ответ написан
  • Чем отличается оператор от матрицы в линейной алгебре?

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

    Линейное преобразование - это конкретный тип операторов, который действует на элементы R^n и характирезуются тем, что они обладают свойством линейности (F(x+y) = F(x)+F(y), F(kx) = kF(x)).

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

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

    Вообще, не для любых функций распределения можно получить любую корреляцию. Например, вы никак не сможете добиться полной (corr=1) корреляции равномерно распределенной величины и нормально распределенной величины.

    Но, если функция для обеих величин одинаковая, то есть, например, такой способ:
    1) Сгенерируйте случайную величину a согласно функции распределения.
    2) C вероятностью k выдайте это же значение как и вторую переменную (b=a).
    3) C вероятностью 1-k сгенерируйте случайную величину b согласно той же функции распределения.

    Этот способ выдаст коэффициент корреляции k. Если нужна отрицательная корреляция, то можно выдать b=2Ea-a во втором шаге (отражение относительно матожидания). Но тогда в третьем шаге плотность распределения будет уже не такая же как у a. Если заданная функия распределения f(x), то там надо использовать g(x)=(f(x) -kf(2Ea-x))/(1-k). Суть в том, чтобы g(x)*(1-k)+k*f(2Ea-x) = f(x) - и итоговая плотность распределения будет одинаковая.

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

    Другой вариант, сгенерировать случайную величину a ~ f(x), потом взять b = k*a+c, где c - это какая-то независимая случайная величина, распределенная как-то хитро (об этом ниже). Регулируя k можно получать разный уровень корреляции. Удобно работать уже с центрированными случайными величинами. Пусть Ea = Eb = Ec= 0.

    Тогда коэффициент корреляции будет E((ka+c)a)/D(a) = (kEa^2+Eac)/D(a) = kE(a^2)/D(a) = k. Потому что a и c независимые случайные величины и Eac = Ea*Ec = 0*0. А D(a) = E(a^2)-Ea*Ea = E(a^2)-0*0.

    Пусть функция распределения a и b - F(x) (плотность f(x)). Искомая функция для c - G(x) (плотность g(x)).

    Надо будет решить интегральное уравнение:
    Int -int..inf g(t)f((x-t)/k)/k dt = f(t)

    Лучше всего это через преобразование лапласа это решать. Теоремму о свертке и свойство умножения на число примените.
    Ответ написан
    Комментировать
  • Как сгенерировать случайную величину с заданной многомерной функцией распределения?

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

    Известно, как сгенерировать одномерную величину с заданной функцией распределения: обращаем функцию распределения (интеграл плотности) и подставляем туда равномерно распределенную на отрезке 0..1 величину.

    Пусть у вас 3 компонены x,y,z. Интегриркем по y,z, получаем функцию плотности для x. Гегерируем. Потом подставляем это значение в функцию плотности и получаем новую, уже двухкомпонентную функцию (ее еще надо будет поделить на плотность для данного x l, чтобы нормировать). Повторяем операцию для y.

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

    В противном случае можно натягивать сетку и считать интеграллы и обратные функции численно.
    Ответ написан
    4 комментария
  • Почему не существует не итерационных/точных методов для вычисления корня из числа?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Есть же методы: https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D...

    Они обычно медленнее и более трудоемкие, поэтому из и не используют особо.
    Ответ написан
  • Как доказать, что a³+b³+c³=3?

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

    Это диафантово уравнение. При чем очень сложное: от трех переменных да еще и кубическое. Только для каких-то самых тривиальных случаев, вроде линейного уравнения, еще есть какие-то алгоритмы прямо получения решения (вроде расширенного алгоритма Эвклида). Для некоторых классов существуют методы порождения всех решений, если вам известно одно, но это одно часто надо еще найти - перебором. Но вот такие уравнения человечество еще решать не научилось.
    Ответ написан
  • Как оптимизировать алгоритм самонаведения ракеты?

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

    Обозначьте |MSL_VEL - TGT_VEL| за t.

    Получите уравнение TGT_DIR = (MSL_VEL-TGT_VEL)/t

    Преобразуйте: TGT_DIR*t = (MSL_VEL-TGT_VEL)

    Но тут неизвестные вектор MSL_VEL и t. Но они связаны, ведь t - это длина вектора. Обозначим неизвестный вектор MSL_VEL как (x, y, z) Значит:
    t^2=(x - TGT_VEL_x)^2 + (y - TGT_VEL_y)^2 + (z - TGT_VEL_z)^2

    Ну и еще вы знаете, что скорость ракеты фиксированная же:
    x^2+y^2+z^2 = MSL_SPEED^2

    У вас тут 4 неизвестных и аж 5 уравнений (ведь первое - это векторное уравнение):
    TGT_DIR_x*t = x - TGT_VEL_x
    TGT_DIR_y*t = y - TGT_VEL_y
    TGT_DIR_z*t = z - TGT_VEL_z
    t^2=(x - TGT_VEL_x)^2 + (y - TGT_VEL_y)^2 + (z - TGT_VEL_z)^2
    x^2+y^2+z^2 = MSL_SPEED^2


    Раскройте скобки в 4-ом, подставьте туда пятое и из первых трех выразите x, y, z:

    t^2 = MSL_SPEED^2+TGT_SPEED^2-2*TGT_VEL_x*(TGT_DIR_x -t*TGT_VEL_x)-... = MSL_SPEED^2+(1-2t)TGT_SPEED^2-2(TGT_DIR*TGT_VEL)


    Там в конце векторное произведение векторов. Дальше сами раскройте и получите квадратное уравнение на t. Решите его по школьной формуле. Если дискриминант отрицательный, то решения тупо нет. Слишком быстро цель улепетывает. Потом не забудьте проверить, чтобы t получилось положительное. Потом подставьте t в первые 3 уравнения и найдите искомые x, y, z.

    Еще можно так себе это все представить. Свяжем систему координат с целью. Тогда множество точек, куда может смотреть скорость ракеты - это сфера с центром в TGT_VEL и радиусом MSL_SPEED. Вам надо выбрать на этой сфере точку так, чтобы она была коллинеарна с вектором TGT_DIR. Т.е. у вас есть луч из центра координат вдоль векторо TGT_DIR. Вам надо найти где он пересечет сферу. Введите параметр t вдоль луча и дальше получите то же самое квадратное уравнение.
    Ответ написан
    2 комментария
  • Таблица истинности С++. Почему здесь разные результаты?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    ( x == z) || (!x || (y && z)) == 0 означает ( x == z) || ( (!x || (y && z)) == 0 ).
    Приоритет у сравнения выше, чем у ||, которое, по идее, есть лишь часть считаемого выражения. Поэтому у вас полечается не "выражение == 0" а "выражение1" или "выражение2 == 0".
    Возьмите все ваше выражение в скобки и все заработает.

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

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

    Вектора можно перемножать. Скалярное или вектороное произведения. Чаще скалярное ставят на operator*, а векторное на какое-нибудь operator^

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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Решите систему линейных уравнений. Обозначьте коэффициенты с1,с2,с3, сложите полиномы, приравняйте коээфициенты пред всеми степенями x к 0. Будет 3 уравнения, 3 неизвестных, но одно из них лишнее (раз они линейно зависимы). Подставьте что угодно ненулевое вместо C, решите первые 2 уравнения относительно A и B.
    Ответ написан
    Комментировать
  • Двойная сумма, непонятно как поменялись предели сумирования?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Что означает вот эта первая надпись с одним знаком суммы? Там же 2 переменные в условии - j и k! Эта надпись означает сумму по всем значениям j и k, т.ч. 1 <= j < k+j <= n. Это множество допустимых значений можно представить как какую-то фигуру на плоскости.
    Ее можно описать вот этими неравенствами, а можно перебрать все допустимые значения j, для каждого из них посмотреть, какие значения k попадают в искомое множество. Вот так и получаются 2 суммы, одна по j, другая по k.
    k не может быть меньше 1 (Видимо, по условию раньше) и больше n, потому что иначе k+j превзойдет n. Зафиксировав k, остаются 2 условия 1 <= j и k+j <= n. ведь j < k+j всегда. Из этих двух условий получаем границы суммирования на j.
    Ответ написан
    Комментировать