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

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

    По первой цели надо выбрать такую шкалу, чтобы как можно больше разных цветов было на графике. Можно, например, максимизировать энтропию. Пусть pi - доля стран цвета i. Надо максимизировать sumi=1..n -log(pi) pi

    По второй цели - надо выбрать красивые круглые границы. Ну не воспримет человек, если у вас граница цевета будет 111 234 564 человек. Ему проще будет 100 000 000. Плюс, произвольные числа на шкале делать не принято. Обычно делают только 2 типа шкал: линейная и логарифмическая. В линейной каждая граница на одно и тоже число больше, в логарифмической в одно и то же число раз. У вас на примере логарифмическая шкала, чуть округленная до круглых чисел. Если тут взять линейную, то почти все страны попадут в белый цвет из-за парочки очень больших стран.
    Ответ написан
    2 комментария
  • Как найти площадь большого сегмента?

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


    Это прямая y=C. Горизонтальная прямая - она всегда на одно и то же расстояние выше оси OX. Вот это расстояние - C - вам и дано. Ясно, что "соответствующая" ось координат - это OX. потому что с OY горизонтальная прямая пересекается. И вообще, расстояние между двумя прямыми имеет смысл, если они параллельны.

    Легче сначала решить другую задачу: Найдите нужную площадь, если расстояние от прямой до центра окружности - D. Уже потом подставьте в это abs(C-Y0).
    Ответ написан
  • Как правильно заниматься перебором: a³ + b³ + c³ = d³?

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

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

    У вас самый наивный перебор в лоб, его можно ускорить. Сначала сгенерируйте все кубы и схраните их в массив. Их будет примерно кубический корень из |MAX_VAL-MIN_VAL| - это достаточно маленькая величина.

    Теперь задача: найти 3 числа в массиве, дающих в сумме число из массива. Это все еще O(n^3), если исползовать 4 индекса. Но можно ускорить решение методом "встреча по середине".
    Вместо A+B+C=D из массива будем искать A+B=C-D. Для этого переберем все пары чисел, подсчитаем их сумму и сохраним в dict() вместе со списком индексами этих чисел (список всех пар, дающих эту сумму). Потом опять переберем все пары, подсчитаем их разность и посмотрим в словаре, а была ли пара с такой же суммой. Если была - вот мы нашли 4 числа, таких что A+B=C-D. извлекаем корни и выдаем это в ответ.
    Это будет уже O(n^2) - заметно быстрее.
    Ответ написан
    8 комментариев
  • Как симулировать комбинаторные сочетания (C(k, n)) за O(1) памяти?

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

    Edit: Если, все-таки, хочется именно случайно сочетание сгенерировать, то вот алгоритм, основанный на reservoir sampling:

    int taken = 0;
    for (int i = 0; i < n; ++i) {
      if (rand()*(n-i) < k-taken) {
        ++taken;
        // Взять элемент i.
      }
    }
    Ответ написан
  • Можно ли как-то короче доказать этот факт?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    После пункта 4 вам надо лишь доказать, что найденные xi yi будут всеми решениями системы. Допустим есть какое-то еще решение {x' y'} не среди xi, yi. Но, раз оно удовлетворяет f(x',y')=0, то x'=f'(y'). Еще оно удовлетворяет g(x',y')=0, а значит и g(f(y'),y') = 0, т.е. вы бы это y' нашли среди ваших yi, но мы предположили обратное.
    Ответ написан
  • Более формальный вывод из доказательства по принципу наименьшего числа?

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

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

    Есть еще тонкий момент: рассуждения получающие меньший элемент заданного иногда нельзя применить ко всем числам. Например, если вы работаете с целыми положительными, а предположенный минимальный у вас 1, то из 1 вы меньшее число никак не получите. Поэтому надо сначала проверить, принадлежит ли 1 к множеству и потом предполагать существование минимального элемента > 1.
    Ответ написан
    1 комментарий
  • Как найти или показать существование цикла в ориентированном графе быстрее, чем за O(IVI+IEI)?

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

    Это можно доказать. Вам так или иначе придется посмотреть на все ребра. Допустим, есть алгоритм, который всегда может проверить цикл, смотря не все ребра. Рассморим какой-то граф без циклов. Алгоритм там какие-то ребра посмотрел и сказал, что циклов нет. А мы возьмем и скормим этому алгоритму почти такой же граф, только одно из ребер, которые он вообще не трогал, сделаем обратным какому-то другому ребру в графе, сделав таким образом цикл. Но алгоритм посмотрит на те же самые ребра, увидет все то же самое и сделает точно такой же вывод, что циклов нет, и ошибется. Все потому что мы допустили алгоритм, который всегда смотрит не все ребра. Значит таких алгоритмов нет и там всегда будет хотя бы O(|E|).
    Ответ написан
    2 комментария
  • Возможно ли обнаружить сортировкой Кана изолированные узлы, сортировать сразу рёбра и не использовать степень?

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


    Без нее работает медленно. Смотрите алгоритм. В алгоритме надо брать вершину в которую не входит ни одно ребро, а также удалять вершины. Кончено, можно наивно брать все вершины, потом брать все ребра, смотреть, не удалено ли ребро и не ведет ли оно в эту вершину. Но это будет O(VE) для поиска одной вершины, а суммарно алгоритм будет O(V^2E). Когда как реализация с подсчетом степеней и очередью будет O(V+E).

    Есть ли возможность сортировать не узлы, а рёбра сразу?

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

    Можно ли таким образом обнаружить, что этот граф содержит изолированные узлы, которые могут быть соединены между собой?


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

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

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

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

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

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

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

    Вы доказали, что частичные разницы не возрастают. Тут могут быть 3 варианта:
    1) они все неотрицательные. Функция унимодальна (монтонность с максимумом в конце - частный случай унимодальности).
    2) они все неположительные. Монотонно убывающая функция.
    3) есть и положительные и отрицательные. Но раз разности не могут возрастать, после первого 0 могут идти только нули а после отрицательного только отрицательные. А заначит разности выглядят ровно так, как у унимодальной функции.
    Ответ написан
    Комментировать
  • Как доказать коэффициенты Фурье?

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

    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, +}
    Ответ написан
    Комментировать