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

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

    Один вариант решения - прибавлять к текущему числу 65536, пока оно меньше предыдущего. Можно обойтись арифметикой:

    a[i] += ceil((a[i-1]-a[i])/65536)*65536

    Только проверьте, что в вашем языке ceil(-0.5) даёт 0, иначе надо отдельно проверять случай, когда последовательность возрастает в начале и прибавлять ничего не надо. И ещё, тут считается, что числа в неурезанной последовательности могут повторяться. Если нет, то надо отдельно рассмотреть случай равных чисел в итоге и ещё раз прибавить 65536.
    Ответ написан
    Комментировать
  • Как можно найти центроид четырёх точек ( Quadrilateral ), зная координаты этих вершин?

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

    Сначала надо триангулировать четырехугольник. Потом, центр масс каждого треугольника - среднее арифметическое координат. Далее, остается найти центр масс двух точек - центров масс треугольников, где в каждой точке лежит масса равная площади треугольника.

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

    Итоговая фромула (в векторах):
    C = ((p1+p2+p3)/3*(p1p2*p1p3)+(p3+p4+p1)/3*(p1p3*p1p4))/((p1p2*p1p3)+(p1p3*p1p4))


    Тут pi - i-ая вершина четырехугольника, pipj - вектор между точками i и j. pipj*pkpl - векторное произведение двух векторов.
    Ответ написан
    Комментировать
  • Есть ли сервис для создания формулы для числа?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Зачем сервис? Вот вам формула для любого числа X = (X-1) + 1. Например, 172 = 171+1.

    Или вам какое-то особое свойство у формулы нужно?
    Ответ написан
  • C# Math правильно ли я делаю?

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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Запишите уравнение повернутого конуса.
    Конус будет иметь то же уравнение в повернутой системе координат x', y', z. Можно выразить x', y' через x, y и косинусы/синусы угла поворота alpha. Подставьте это в уравнение конуса и получите уранение в нормальных координатах.

    Пересеките конус с плоскостью. Решите систему из уравнений. Из уравнения плоскости выразите z^2 и подставьте в конус. Получите уравнение второго порядка на x и y.

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

    Введите декартову систему координат на плоскости (взяв один любой вектор на плоскости как одну ось и векторное произведение его с нормалью как вторую ось). Параметризируйте плоскость через эту систему координат в виде x=x(u,v), y=y(u,v), z=z(u,v). Подставьте это в ваше предыдущее уравнение второго порядка.

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

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

    Дальше завивит от того, как графики заданны. Если это наборы точек, то надо найти 2 одинаковые точки в отсортированных массивах. Или попересекать кучу отрезков, если график кусочно-задан.

    Если графики заданны функциями, то надо решить уравнение. Тут вам помогут численные методы, если это не полиномы степени 4 и меньше. Например, метод Ньютона.

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

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

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

    В отдельных случаях (сумма не очень большая и множеств всего 2; числа очень маленькие) возможны быстрые алгоритмы на основе динамического программирования
    Ответ написан
  • Определить победителя КНБ?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    (-1) % 3 = 2

    Это математическое определение вычетов по модулю. Все числа, которые отличаются на n, имеют одинаковый остаток по модулю n. Конфуз происходит из-за того, что операция взятия по модулю во многих языках программирования работает не так. Для отрицательных чисел она выдаст отрицательное значение, правда к которому можно прибавить n, что бы получить правильный модуль - число от 0 до n-1.

    Поэтому при реализации можно делать (a-b+3)%3 Или преобразовать, чтобы не было вычитания: b == (a+1)%3
    Ответ написан
    Комментировать
  • Формула повышения уровня игры?

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

    Попробуйте что-то вроде 1.2**lvl *50 и 1.3**lvl *100.
    Ответ написан
  • Сумма арифметической прогрессии?

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

    Первый член - 1 (при j=i+1), последний - n-i (при j=n). Всего их n-i. Ну а дальше - стандартная формула: среднее крайних членов, помноженное на их количество.

    Как из этого получается O(n^3). По уму, надо раскрыть скобки и разложить на сумму трёх рядов, в зависимости от степени i в слагаемом. Дальше сумма i даст также O(n^2). Сумма по i^2 даст O(n^3). Тут уже нельзя арифметическую прогрессию применять, но это известная формула - сумма n квадратов даст n(n+1)(2n+1)/6. Ее можно вывести, если взять ряд f(x)=1+x+x^2+...+x^n = (1-x^{n+1})/(1-x) и найти (x*f'(x))'. Потом туда можно подставить x=1. Или есть визуальные доказательства. Каждый квадрат - это квадрат из кубиков. Их все можно сложить в пирамиду. 6 таких пирамид можно сложить в параллелепипед.
    Ответ написан
    1 комментарий
  • Как посчитать число 2 в 1 000 000 000 000 000 степени?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    2^10 ~ 10^3. 2^1 000 000 000 000 000 ~ 10^300 000 000 000 000.

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

    Вряд ли у вас цель - получить эти 300 миллиардов цифр. Наверно, вам нужно что-то с этим числом делать. Возможно, это можно сделать без вычисления всех цифр числа. Например, если вам нужны последние 100 цифр - то можно на том же питоне производить вычисления по модулю 10^100. Правда, придется писать экспоненциальное возведение в степень самостоятельно.
    Ответ написан
    Комментировать
  • Какой алгоритм использовать для определения нахождения точки за границей треугольника пространства?

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

    Если же оно на плоскости, то введите там систему координат (например, орто-нормируйте вектора p2-p1 и p3-p1). Получите координаты всех точек (p1 можно назначить началом координат).

    Потом придется применять формулу для плоскости. Можно воспользоваться векторными произведениями. Произведение пар векторов {p-p1, p2-p1}, {p-p2, p3-p2}, {p-p3, p1-p3} должны все давать одинаковый знак (или все <=0 или все >=0. Равенство 0 чего-то будет означать, что точка на границе).

    Или можно посчитать площади, опять же через векторное произведение. |(p2-p1)(p3-p1)| = |(p1-p)(p2-p)+(p2-p)(p3-p)+(p3-p)(p1-p)|
    Ответ написан
  • Какой алгоритм использовать для нахождение уравнения поверхности по 3 точками?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Пусть точка p=(x,y,z) принадлежит плоскости. Пусть 3 точки - p1, p2, p3.

    Тогда вектор (p-p1) должен раскладываться на вектора p2-p1 и p3-p1.

    Т.е. определитель матрицы 3x3 из этих трех векторов должен быть нулевым.

    det {{x-p1x, p2x-p1x, p3x-p1x},
     {y-p1y, p2y-p1y, p3y-p1y},
     {z-p1z, p2z-p1z, p3z-p1z}} = 0


    Раскрываете определитель по первому столбцу и получаете
    A = det({{p2y-p1y, p3y-p1y}, {p2z-p1z, p3z-p1z}})
    И т.д.
    D = -p1x*A-p1y*B-p1z*C
    Ответ написан
  • Что думаете об этом решении задачи?

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

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

    Что касается кода: ваш разбор случаев, что там больше - весьма странен. Код тяжело читать и он в несколько раз медленее, чем мог бы быть из-за постоянных вызовов максимума и минимума. Может даже медленнее простого вычисления чисел фиббоначи без пропусков нечетных.

    Заведите вы третью временную переменную и считайте через нее, чтобы в цикле всегда n было большим числом (m = 4*n+b; b=n; n=m). Или вообще воспользуйтесь фишками питона и делайте множественное присвоение:
    b, n = n, 4*n+b;
    Ответ написан
    8 комментариев
  • Как практически использовать теорему Колмогорова-Арнольда?

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

    Например, x*y*z вы в сумму никогда не разложите. Зато, если взять f(a,b) = a*b, то можно сделать f(x,f(y,z)).

    Это хорошо для оптимизации

    Эта суперпозиция не будет лучше для оптимизации ни с какой точки зрения.

    Практически это можно сделать так - расставьте все скобки рядом со всеми операциями в выражении. Каждая операция - это своя функция. Вот у вас и суперпозиция.
    Ответ написан
    Комментировать
  • Как найти принадлежность точки к закрашенной области на плоскости?

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

    Далее, фигура повторяется блоками 2x2, т.е. вам не важны сами координаты, а только их положение в блоке.

    Для высчитывания координаты в блоке можно или вычитать 2, пока координата больше 2, или вычесть из x (floor(x) - floor(x)%2). floor(x) даст целые числа. Потом надо это число сделать четным, возможно вычесть 1. floor(x)%2 - как раз и даст нам, что надо вычесть.

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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Разбейте область на простые фигуры (квадраты, окружности, полуплоскости) и опишите логически. Вроде точка в области, если она в фигуре А, но не фигуре Б; или в фигурах В и Г, или в фигурах Д и Е.

    Далее перевести это в код - это один if с кучей условий объедененных логическими или (||) или логическими И (&&).
    Ответ написан
    Комментировать
  • Как разбить числа по группам так, чтобы в группах находились близкие по значению числа?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Надо ввести какую-то метрику - какая-то числовая оценка, которая говорила бы вам, почему [[1,2],[3,4],[5,6]] лучше чем [[1,2,3,4],[5],[6]]. Например, можно взять максимальную разность двух чисел в любой группе. Или сумму квадратов расстояний от всех чисел до среднего в их группе. Или минимальное расстояние между числами в разных группах (это надо максимизировать).

    Потом можно применять какой-то из известных методов кластеризации, в зависимости от выбранной метрики. В случае одного измерения, как у вас (просто числа) можно еще применить и динамическое программирование. Этот метод работает для практически любой вменяемой метрики. Считайте функцию F(n,k) - лучшая возможная метрика если первые n чисел разбить на k групп. Для пересчета надо перебрать, сколько чисел идет в последнюю группу (i), и пересчитать метрику на основе F(n-i, k-1). из всех вариантов выбрать лучший.
    Ответ написан
    Комментировать
  • Что есть максимальная сумма делителей?

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

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

    Далее, используя эти данные, можно подсчитать сумму всех простых делителей используя формулу S=(p1^(k1+1)-1)/(1-p1)*...*(pm^(km+1)-1)/(1-pm) (тут p1^k1...pm^km - разложение числа на простые множители).

    Надо считать эту сумму делителей от меньших чисел к большим (обозначим ее S(n)). Тогда S(n) = S(n/p^k)*(p^k*p-1)/(p-1).

    Но это так, для любопытных. Я думаю в вашей задаче достаточно для кадого числа проверять все делители до корня (а оставшиеся делители получаются как n/i, если i - делитель до корня). Надо только аккуратно разобрать случай, когда i = sqrt(n) - тогда второй делитель не надо рассматривать, ибо это вторая копия того же самого.
    Ответ написан
    3 комментария
  • Как повернуть прямую на систему координат?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Вам надо арктангенс брать от отношения, а не тангенс (y2-y1) / (x2-x1).
    Ответ написан