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

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

    Покрасьте поле как шахматную доску. Черные и белые клетки. Каждая доминошка будет лежать на двух соседних белой и черной клетках. Постройте граф. Назначьте каждой клетке вершину, а ребра проведите между соседними клетками, если там нет перегородки. Граф - двудольный, ведь черные клетки окружены белыми, а белые - черными. Любое заполнение поля доминошками будет идентично паросочетанию в этом графе и наоборт. Найдите максимальное паросочетание: если оно не полное, то поле покрыть нельзя. Иначе ребра в паросочетании будут местами, куда надо класть доминошки.

    Вот статья с описанием алгоритма и реализацией.

    Это будет решение за O(n^2m^2).

    Другое решение, которое будет быстрее, если одно из измерений очень маленькое, а второе очень большое - динамическое программирование по профилю. Гуглите эти слова. Это сложнее реализовать, но зато будет работать за O(4^n m)

    Edit:
    Alexandroppolus в коментариях предложил использовать Алгоритм Хопкрофта — Карпа для поиска паросочетания, что для данного графа будет быстрее предложенного мной алгоритма Куна и будет работать за O(nm sqrt(nm)) вместо O(n^2 m^2)
    Ответ написан
    7 комментариев
  • Как расширить вычисление до 2^120?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Код в вопросе найдет такое i, что result станет равен 1, если цикл сделать до N. Для любых дельта и гамма. (но там цикл не нужен вообще).

    И наоборот. Какие бы вы дельта и гамма не взяли, может прийти такой Input, что result станет 1, только для очень большого i.

    Во-первых, вам цикл не нужен. Вычисления ваши можно упростить.
    result = (input / delta) / (i / gamma) = input * (gamma / delta) / i

    Если result = 1, то получается i = input * (gamma / delta) (естественно, умножение и деление по модулю N).
    Цикла не надо. Можно сразу вычислить искомое i.
    Решение единственно (если N простое. А если оно не простое, то делить по модулю нельзя).

    И это самое i может оказаться очень большим. Не всегда N-1, потому что у вас ограничение на Input есть дополнительное, Но даже в самом лучшем случае подбора гамма и дельта (обе по 1), вам может прийти input такой, что i будет равно 2^120.

    Ну и, во-вторых, вам не нужны две константы дельта и гамма. Тут есть ровно одна степень свободы - значение gamma / delta. Это должна быть единственная константа в вашем коде. В итоге оно все упрощается до:
    beta = 0x42
    i = beta * input % N
    result = 1


    И вообще тут, очевидно, проблема XY. У вас есть какая-то задача X, вы придумали какую-то фигню, как-то сформулировали вот эту вот задачу в вопросе (У), но вы ошиблись. Решение вот этой фигни в вопросе вам никак не поможет решить вашу изначальную задачу, пототму что вам не хватает знаний (теории групп, например, да и математики в целом). Вы задаете практически бессмысленные вопросы (уже не первый раз). Если хотите, чтобы вам тут действительно помогли - давайте вашу изначальную задачу. Я подозреваю, что это взлом криптографии и вам тут популярно объяснят, что вы зря тратите время.
    Ответ написан
  • Почему мы имеем право решать уравнения методом замены переменной?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Ну, это просто подстановка. Если, как в моем примере, предположить, что z=x^2, то из-за равенства получается и x^2=z. А дальше можно каждый x^2 переписать как z, ведь они равны.

    Или это можно еще понимать как абстрактное мышление. Вот есть у вас уравнение на x. Вы можете заметить какое-то повторяющееся выражение. Оно имеет какое-то значение. Вот это значение можно обозначить новой буквой. Вот вы же можете буквой x обозначить "сколько у вас яблок". Вы точно также можете обозначить буквой z "сколько у вас яблок в квадрате".

    Это можно делать всегда, но в результате этого могут получиться лишние корни. Как например тут, если есть решения с отрицательными z, то никакой x ему не соответствует. Надо аккуратно проверять все значения z и искать соответсвующие им x.

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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Я так понял, надо подобрать константы a,b,c,d?
    Вообще, можно a, b1, c считать равными 1 и менять только d.

    Но у вас там умножение и деление по модулю. Так что все очень сложно.

    Вообще, ваша задача не имеет решения.

    Модуль у вас в вопросе порядка 10^78. А X может быть 10^119-10^120. Если x взять по модулю N, то там может получится вообще любой остаток (потому что 10^120-10^119 = 9*10^119 > N)

    А дальше, умножая эти числа на константу, если N простое (а оно должно быть простым, иначе деление по модулю не определено), то можно получить любой остаток до N. Не только до 2^60 - 2^70.
    Ответ написан
  • Что означают эти формулы?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    "E" (это вообще-то сигма из греческого алфавита) - знак суммы. выражение справа надо просуммировать, подставив вместо k все числа от 3 до n. П - это знак произведения. Выражение справа надо перемножить для всех указанных значений i.

    Поскольку тут в выражении П есть переменная k, связанная в сигме, то можно однозначно сказать, что перемножение идет внутри суммы.

    Ваше решение в вопросе почти правильное. Проблема только в том, что вам надо подсчитать что-то вроде c1*a1*a2*a3 + c2*b1*b2*b3. А вы используете одну и ту же переменную для подсчета каждого слагаемого и общей суммы. У вас получается что-то вроде (c1*a1*a2*a3+c2)*b1*b2*b3
    Ответ написан
    2 комментария
  • Если мы возьмём кубическую кривую Безье и вытянем усы в одну точку, будет ли это квадратичная кривая?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Нет. Потому что кривая называется "кубической" не потому, что там 4 разные точки, а потому что она задается уравнением третьей степени (кубы): a(1-t)^3+bt(1-t)^2+ct^2(1-t)+dt^3. Если вы приравняете b и c, то уравнение так и останется кубическим и в квадртаичное не превратится.
    Ответ написан
  • Как решить эту задачу на python?

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

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

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

    Но вообще, комплексные числа, группы и кольца очень часто используются в криптографии, намример. Сами алгоритмы шифрования и обмена ключами (всякие там RSA, Diffie-Hellman) - это вообще часто чистая математика с этими объектами. Плюс, комлпексные числа используются в быстром преобразовании Фурье, которое позволяет быстро перемножать огромные числа, а эта операция в криптографии тоже очень важна.
    Ответ написан
    Комментировать
  • Как правильно перевести GPS координаты из одной системы в другую?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Пока похоже, что первые 3 символа - градусы * 6.
    Потом 2 символа минуты, потом '0', потом 2 символа секунды. Последние 2 символа непонятно как переводятся в десятичные доли секунд. Есть подозрение, что вы ошиблись с координатами на гуглмапсах.

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

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

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

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

    Тогда надо разбить строку на отдельные "слова" - группы тире и точек, разделенные пробелами и каждую группу перевести в букву по таблице. Таблицу в идеале надо хранить в trie ("бор" по русски), но эта структура не реализована в стандартной библиотеке C++, поэтому можно воспользоваться просто std::map<std::string, char>

    Edit: Разумеется, таблица для обратного перевода должна быть отдельной переменной. Не получится смешать в одну кучу переводы и туда и обратно.
    Ответ написан
    Комментировать
  • Что значит описать встретившуюся геометрическую фигуру и определить положение точки в этой фигуре?

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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Можно. Из второго уравнения: x=u/(1-c).
    Ответ написан
    7 комментариев
  • Как вписать прямоугольник в многоугольник?

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

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

    Но тут слишком много случаев. Это очень сложная задача строк этак на 1000 мозгодробящей геометрии.
    Ответ написан
    Комментировать
  • Как узнать место пересечения луча со сферой?

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

    Луч:
    x = x0 + t*vx
    y = y0 + t*vy    (1)
    z = z0 + t*zy

    Где (x0,y0,z0) - начало луча (камера?), (vx, vy, vz) - направление луча.

    Уравнение сферы:
    (x-xs)**2 + (y-ys)**2 + (z-zs)**2 = R**2 (2)

    Где (xs, ys, zs) -центр сферы, R - радиус.

    Подставьте (1) в (2) - получите квадратное уравнение на t. Решите его по школьной формуле и возьмите минимальное положительное t. Подставьте в (1) и получите координаты точки пересечения (и заодно длину луча, если вектор направления нормализован).
    Ответ написан
    7 комментариев
  • Какой длины массив чисел можно "упаковать" по 3 элемента 25 комбинациями?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Пусть делящихся на 2 - x, а делящехся на 3 - y.

    Тогда количество способов "выбрать три числа так, чтобы
    среди них было как минимум одно четное число и хотя бы одно число, делящееся на 3" - x(x-1)y/2+x*y*(y-1)/2. Или мы берем 2 четных числа и одно, делящееся на 3. или наоборот.

    Теперь надо подобрать такие x и у, чтобы вот эта формула сверху дала 25. Ответом будет x+y.

    Можно или перебрать мелкие значения x и y и посмотреть, что 2 и 5 подойдут, или вывести это логически. Формулу можно факторизовать до x*y*(x+y-2)/2. Приравняем к 25 и домножим на 2: x*y*(x+y-2) = 5*5*2. Справа произведение трех простых чисел. Слева три неизвестных целых множителя. Значит надо лишь перебрать способы распихать эти три простых числа по трем множителям. x и у не могут быть 1 вместе, ибо 1*1*0 != 50. Если x=1, а y!=1, То надо там тоже видно, что решения для y нет. x+y-2 тоже не может быть 1, ведь кто-то из x и y будет точно хотя бы 5. Ну и остается тольковариант x=5, y=2, (x+y-2) = 5.

    Итого, ответ - 7.
    Ответ написан
    Комментировать
  • Как работает этот рекурсивный алгоритм разложения на слагаемые?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Функция генерирует все разбиения числа n на слагаемые не больше maxx. Ддя этого ыункуия перебирает, а какое же максимальное число будет в разбиении (цикл по i), берет это число и рекурсивно разбивает оставшуюся часть. Обратите внимание, в качестве maxx в рекурсии передается i. Ведь именно это было максимальное число в перебираемом разбиении. Значит следующее не может его превышать.

    Вся эта сложность с максимальным числом сделана, что бы не перебирать перестановки слагаемых. Ведь 4=1+2+1 можно по идее получить тремя способами, меняя порядок. Генерируя слагаемые в не возрастающем прядке, мы избавляемся от таких дубликатов.
    Ответ написан
    Комментировать
  • Как найти площадь квадрата, имея 2 отрезка?

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

    Не совсем пока еще понятно, квадрат может быть ориентирован как угодно, или тоже должен быть параллелен осям координат? Судя по тупости формулеровок я думаю, что составители задачи имели в виду более простой вариант, и стороны квадрата тоже должны быть параллельны.

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

    Если же это не сработает и квадрат можно вращать, то тут все сложно. Путем очень хитрых геометрических рассуждений можно доказать, что квадрат в оптимальном случае, все-таки, будет параллелен осям координат и просто написать решение выше. Ну, или, если не верите, то можно ввести угол поворота как переменную, написать функцию, котороя поворачивает все точки на данный угол, а потом ищет (по алгоритму в начале) площадь описанного параллельного осям квадрата, и потом запустить тернарный поиск минимума по этой функции.
    Ответ написан
    2 комментария
  • Почему последний множитель в формуле числа размещений = (n-k+1)?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Потому что оно есть n! / (n-k)! Вот n-k и в числителе и в знаменателе сокращается. А вот n-k+1 в числителе остается, потому что сокращатся ему не с чем.
    Ответ написан
    Комментировать
  • Формула вращающегося прямоугольника как?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Ну это же школьная геометрия. (L-W)/sqrt(2), если длинная сторона L, а короткая W.

    Там равносторонний прямоугольный треугольник с длиной (L-W)/2 (вычли пересечение из длины, осталось 2 одинаковых куска, поделили пополам - нашли искомый кусок. А дальше - теорема Пифагора.
    Ответ написан
  • Как в данной системе из линейных уравнений получился x и y?

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

    Можно из одного уравнения выразить y через x, подставить в другое, найти x, потом найти y.

    Или можно получить эти формулы в одно действие методом Крамера.
    Ответ написан
    5 комментариев