Задать вопрос
  • Как сделать перестановку с повторением в C++?

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

    Вот есть статья на хабре, даже с кодом, правда на go.

    Но сам алгоритм там простой, без труда переведете на си++.
    Ответ написан
    9 комментариев
  • Ошибка вывода списка C++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    cout умеет сам по себе выводить только базовые типы: int, char, string, и т.д.

    Ошибка об этом и говорит, что никто не реализовал оператор << для списка.

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

    еще можно перегрузить оператор << для списка, тогда код в main останется без изменения, но тот же самый цикл придется все равно написать в операторе.
    Ответ написан
    Комментировать
  • Как сделать масштабирование правильно?

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

    Т.е. у вас будут приотображентии не только константы растяжения, но и сдвига.
    Ответ написан
  • Какая временная сложность у простого алгоритма вычисления факториала (О большое)?

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

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

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Figure** figure_colletion = new Figure * [this->collection_size];


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

    Поэтому любой уважающий себя стиль форматирования кода подразумевает, что члены класса должны быть приватными и как-то по особому именоваться (например, заканчиваться на "_", или начинаться с "p") тогда бы вы этой ошибки не совершили. Еще можно включить предупреждения при компиляции.

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Я так понял, вы там перебираете 8 соседей клетки на замкнутом поле (после последней строки идет первая, перед певрой идет последняя и так же для столбцов). Вам поможет опреация взятия остатка от деления (она же деление по модулю).

    Можно так:
    for (int dx = -1; dx <= 1; ++dx) {
      for (int dy = -1; dy <= 1; ++dy) {
        if (dx == 0 && dy == 0) continue;
        int nx = (i + dx + height) % height;
        int ny = (j + dy + SIZE) % SIZE;
        neighbours += proc_states[iter][nx * SIZE + ny];
      }  
    }


    Или можно завести
    const int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
    const int dy[8] = { 1, 1, 0, -1, -1, -1, 0, 1};
    ...
    for (int k = 0; k < 8; ++k) {
      int nx = i + dx[k];
      int ny = j + dy[k];
      ...
    }


    Можно не заводить временные переменные и ужать код до двух строк.

    В конструкции (i + dx + SIZE) % SIZE есть лишний +SIZE, ибо -1 % SIZE == -1 и чтобы для 0 предыдущее значение было SIZE-1 надо прибавить лишний SIZE под модулем.
    Ответ написан
    Комментировать
  • Как получить адрес памяти переменной в массиве, а не адрес индекса массива?

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

    Edit: и вы через массив к исходному line никак не обратитесь, только если не смените тип массива на Figure*
    Ответ написан
    Комментировать
  • Как сделать динамическую подгрузку кода?

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

    defineCode(std::cout << 13 << std::endl); // work
    Работает, потому что тут макрос просто подставляет код в скобках вместо себя и он компилируется и выполняется.

    defineCode(stringLine); заменяется просто на stringLine, что есть бессмысленное выражение, вырезаемое еще на этапе компиляции.
    Ответ написан
    Комментировать
  • Как реализовать с помошью оператора ,побитовую операцию NAND?

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

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

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

    Ваш код так ужасен, что я не могу понять, что вам там надо подсчитать в итоге, но уже брасается в глаза, что у вас там считается число сочетаний. Во-первых, можно считать (n-k+1*k+2*..*n)/k!, что уже дает более мелкие числа.

    Потом, можно считать треугольником паскаля. Можно даже считать только одну строку, домножая и деля на одно число - тоже не получая в процессе чисел больше ответа.

    Если bills не больше 64, то все влезет в стандартный unsigned long long.

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

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

    Еще более продвинутый метод: считать по модулю больших простых чисел и в конце, через китайскую теорему об остатках вычислять ответ.
    Ответ написан
    Комментировать
  • ++i быстрее чем i++?

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Тут нужна школьная геометрия. Класс на 9, наврено даже раньше. Координаты центров шаров через время t будут (x1(t),y1(t))=(x1+vx1*t, y1+vy1*t)

    Во-первых, проверьте, что шары сейчас не пересекаются. Иначе выталкивайте их вдоль прямой через центры.
    Потом вам надо решить уравнение квадратное уравнение (x1(t)-x2(t))^2+(y1(t)-y2(t))^2 = 4*r^2.

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

    Если 2 шара столкнулись, то их скорости поменяются вдоль вектора на их ценры. Надо решить уравнения сохрнения импульса и энергии. Решение смотрите тут (Формулы в комментарии в моем ответе там).

    P.s. у вас там в коде вижу ошибку. Вы где считате пересечение со стенами знаки напутали. Должно быть:
    float t1 = (0.5 * Lxmax - (cords[i].x + r)) / cords[i].vx;
    float t2 = (-0.5 * Lxmax - (cords[i].x - r)) / cords[i].vx;


    Ну и вы там не проверяете, вдруг скорость нулевая, тогда время до пересечения - бесконечность.
    Ответ написан
    Комментировать
  • Вылетает программа на C++ с кодом -1073741571 (0xC00000FD)?

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

    А так вижу несколько ошибок. Обычно дерево отрезков реализуют только на массиве длинной в степень двойки. Добейте a нулями, до степени двойки. И тогда массив t может быть только в 2 раза больше a, а не в 4.

    Далее, при реализации get надо, если отрезок вершины лежит внутри отрезка запроса, возвращать t[v]. в противном случае надо запускаться слева и справа, но тольо если запрос торчит в нужную сторону. Вы не запускаетесь от левого сына, если l > m, например. Можно считать значение 0, если рекурсивного вызова нет. В конце берете gcd двух половинок.
    Ответ написан
  • Как правильно передать двойной массив из класса наследника C++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Проблема в том, что Box::box - член класса и он инициализируется в конструкторе и в тот самый момент, где вы пытаетесь его использовать в конструкторе предка, оно оказывается еще не инициализировано.

    Варианты решения:
    - вынести эту костанту куда-то, например сделать ее глобальной.
    - сделать Box::box static const (или constexpr - инче сами числа надо будет вынести вне объявления класса)
    - использовать Box::box в теле конструктора. Но тогда надо сделать конструктор по умолчанию для Figure и вызывать fill_figure в конструкторе Box.
    - создавать значение массива прямо в вызове конструктора Figure из Box:
    Box() : Figure( (const bool[4][4]){
          {0, 0, 0, 0},
          {0, 1, 1, 0},
          {0, 1, 1, 0},
          {0, 0, 0, 0}
      }, "Box") {};


    Лучше, конечно, завести static const.
    Ответ написан
  • Как посмотреть содержание data base файла?

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

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

    В движках чаще всего проверяются коллизии - если 2 коллайдера (фигуры, описывающие тело, часто упрощенные) пересекаются, то находится нормаль соприкосновения, и применяются веторные формулы для изменения скорости.
    Ответ написан
    5 комментариев
  • Как ускорить чтение строк из файла?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Может, ручной разбор будет быстрее. Читайте весь файл в большой буфер. Трехсимвольные строки - это пусть будут тупо char* на начало строк в этом буфере. Там пробелы замените на '\0' только. Вот вы уже сэкономили на разборе строк и выделении под них памяти. Числа руками разобрать придется правда (умножение на 10 + следующий символ - '0').

    Еще, вместо чтения файла какой-нибудь mmap может быть быстрее.

    Потом это можно еще и распараллелить каким-нибудь OpenMP, например. Разбейте буфер на примерно равные части, чуть подвигайте границы, чтоб они на переводы строк приходились и каждый кусок разбирайте отдельно.
    Ответ написан
  • Что происходит с string при передаче ссылки строки в структуру, почему может крашится?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    brick = (OBJECT*)realloc(brick, sizeof(*brick) * brickLength);


    Вот этот код вызывает ошибку. Вы выделяете стурктуру OBJECT через realloc. Но она не POD (plain old data) - там поле url - объект std::string. А объекты нельзя вот так выделять. Надо чтобы обязательно конструктор отработал. Вообще, конечно, есть способ извратиться и вызвать конструктор руками, но это костыль.

    Вы тут намешали вещи из C++ (объекты) и вещи из C (malloc) - и это все вместе не работает.

    Правильное решение будет создавть объект через new:
    brick = new Object[brickLength];

    Не забудьте только в конце отчистить это все через delete[].

    А еще лучше, используйте std::vector<Object>.
    Ответ написан
    1 комментарий
  • Почему возникает malloc(): corrupted top size?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вот тут: (long long int*) calloc(len_s1, sizeof(int)); вы выделяете массив int на len_s1 элементов, а потом работаете с ним, как с массивом long long той же длины. Но long long занимает больше байт! Поэтому вы выделяете меньше памяти, чем используете, а это UB.

    В этом случае программа может даже отработать, если повезет. И любое изиенение в ней может непредсказуемо изменить, как ошибка проявится: упадет ли программа, повиснет или просто не так отработает.
    Ответ написан
    1 комментарий