Задать вопрос
wataru

Wataru

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

  • Как посчитать кол-во возможных исходов?

    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 комментарий
    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 в у.
    Ответ написан
    Комментировать
    Комментировать