• Как найти треугольники с максимальной площадью?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    До 15 точек можно полным перебором сделать. Вам надо перебрать все разбиения 3n точек на тройки. Таких разбиений (3n)!/(3!)^n/n! для n=5 - это чуть больше миллиона.

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

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

    Какое-то геометрическое решение в голову что-то не приходит.
    Ответ написан
    Комментировать
  • Какой оптимальный алгоритм для однозначного определения слагаемых в сумме?

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

    Сначала полным перебором найдите суммы всех подмножеств. Если есть совпадения, возьмите минимальную сумму, которую можно набрать больше 1 раза. Вычтите из случайного заказа 1 копейку. Повторяйте процесс. Если цены правдоподобны, сильно больше 100 копеек и цены различаются, то даже для 20 заказов вам придется лишь несколько копеек вычесть.

    Правда, если куча заказов с одинаковой ценой, то тут придется также младшие биты менять.
    Ответ написан
    Комментировать
  • Теряются/бьются UDP пакеты на localhost, так и должно быть?

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

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

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

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

    Для поиска простых чисел лучше восспользоваться каким-то тестом на простоту, например тест Миллера-Рабина
    Ответ написан
    Комментировать
  • Не компилируется код. Как исправить ошибку?

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

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

    Форомула будет (x0 - xr)(y1-yr) - (x1-xr)(y0-yr), где xr, yr - центр окружности.
    Ответ написан
    Комментировать
  • Проблема с оптимизацией сортировки методом Bubble sort. Как ускорить сортировку для списка из 100 тысяч элементов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Никак не ускорить. Сортировка пузырьком - медленная. Имеет квадратичное время выполнения. для 100000 элементов там будет 5 миллиардов сравнений в худшем случае. Для случайных массивов в пару раз меньше в среднем. С учетом, что это питон - вам этих 2х миллиардов операций придется ждать минуту. А с учетом 10 повторений - все 10 минут.
    Ответ написан
    3 комментария
  • Перемножить численные значения unsigned char?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Unsigned char - это целочисленная переменная, которая хранит код символа.

    Если вы хотите получить из кода символа цифры ее значение, то можно, например, вычесть код символа '0'.
    Ответ написан
    Комментировать
  • Как решать задачу используя динамическое программирование?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Какой-то идиот задачу составлял.
    Во-первых, для N<60 ответ помещается в 64-битный целочисленный тип, который есть сейчас практически во всех языках программирования. Тут не надо ничего придумывать для избегания переполнения.
    Во-вторых, чтобы избежать переполнения, в таких задачах обычно просят выдать ответ по какому-то большому модулю. И последнее, как ответ может получиться нецелым - это просто загадка. Пример решения явно неверен.

    А так, динамическое программирование тут простое: Пусть F(N,K) - сколько существует невзрывоопасных стопок длины N, таких что в конце есть ровно K опасных контейнеров (очевидно, 0 <= K < 4). Это не совсем прям то, что вам нужно в задаче, но количество опасных стопок - это количество всех стопок (2^N) минус количество невзрывоопасных, поэтому это ДП нам подходит.

    Пересчет очень прост:

    F(N,K>0) = F(N-K,0)
    F(N,0) = F(N-1,0)+F(N-1,1)+F(N-1,2)+F(N-1,3)


    Если на конце K плохих контейнеров, то до этого точно должен быть хороший контейнер. Если на конце стоит хороший контейнер - то до него может быть 0..3 плохих контейнера.

    База: F(0,0) = 1, F(0, K>0) = 0

    Ответ: 2^N - F(N,0)-F(N,1)-F(N,2)-F(N,3)
    Ответ написан
    2 комментария
  • Почему моё решение данной задачи неправильное?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    28 тут не подходит, потому что надо что бы у числа было хотя бы 4 делителя и все делители отличались хотя бы на d.

    У 28 шесть делителей (1, 2, 4, 7, 14, 28). Среди них есть делители 1 и 2, которые отличаются меньше чем на d=3.
    Ответ написан
    1 комментарий
  • Как избавиться от кучи if в методе?

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    PurifiedElement_Constants не имеет конструктора по умолчанию (очень неудобные названия у вас ElementPurified_Constant vs PurifiedElement_Constants - обратите внимание, ошибка не про ваш класс, а про тип _properties).

    Т.е. член _properties в вашем классе нельзя сконструировать без каких-то параметров.

    Вам надо в вашем конструктрое класса явно вызывать конструктор _properties с какими-то параметрами:
    Machinarium::Materials::ElementPurified_Constant::ElementPurified_Constant()
        : _properties(some, valid, parameters)
    {
    }
    Ответ написан
    4 комментария
  • Имитация ООП в C, где ошибка?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    int self_addr = here-2*int_size;
    point *self = self_addr;


    Это что вообще такое?! Объясните, что вы пытались тут сделать вообще.

    Для имитации ООП надо в структуре иметь указатель на функцию, который надо инициализировать, внезапно, указателем на функцию, например, вот так:
    ret.tochar = &ToCharFunc.

    Сама функция должна помимо обычных параметров еще и принимать указатель на объект, с которым вы хотите работать.
    Ответ написан
  • Какой получится результат псевдокода на языке Си?

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

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

    Если же у вас будет какая-то функция, которой нужен указатель, то ей можно аргуаментом указать Conteiner* conteiner или еще что там больше по смыслу подходит.
    Ответ написан
    Комментировать
  • Задача Иосифа с++ с помощью циклического связного списка проблема со связью во 2 очереди?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Надо же выводить удаляемый элемент, да? Вы же выводите предыдущий. Ну и, раз первый всегда удаляется в начале, надо перед вашим циклом его вручную удалить. Может быть проще, если вы сделаете двусвязный список и напишите функцию, которая удаляет элемент и возвращает следующий. Лучше будет использовать цикл do while в решении - удаляете элемент и сдвигаетесь. Потом проверка на сколько осталось элементов... Ну или for можно использовать - вы же знаете, сколько удалений будет из n войнов.
    Ответ написан
  • Почему sum(sum(xy)/sum(x))/n приближенно равен sum(sum(xy))/sum(sum(x))?

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

    X= {{1, 5}, { 1, 5}}, Y={{5, 1/5}, {5, 1/5}}

    слева даст: 1/2 (10/2 + 2/10) = 1/2 (5 + 0.2) = 2.7

    а справа: (5+5+1+1)/(1+5+1+5)= 1

    Вообще даже близко не равно. Меняя 5 в матрице выше на сколь угодно большое число, вы получите сколь угодно большую разницу.
    Ответ написан
    4 комментария
  • Как решить задачу про кузнечика путем динамического программирования?

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