Ответы пользователя по тегу C++
  • Возможно ли избежать ошибку чтения в массиве если алгоритм задействует ячейку которой нет?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Для игры "жизнь" есть несколько вариантов:
    1) Увеличить поле на 2 клетки по каждому измерению, поле будет храниться с 1, а индексы 0 и n+1 - всегда будут пустыми. Потребление памяти это почти не увеличит, а код упростит.
    2) Если соседние клетки считаются циклами, то можно границы области 3x3 пересечь с полем:
    for (int nx = max(0, x-1); nx < min(x+2, n); ++nx) {
      for (int ny = max(0, y-1); ny < min(y+2, n); ++ny) {
        if (nx == x && ny == y) continue;
        // {nx, ny} - сосед в поле, обрабатываем его.
      }
    }

    Можно код чуть ускорить, предподсчитав границы.
    3) Более читаемый, но чуть более медленный метод - явно проверять, а не за границей ли соседняя клетка:
    for (int nx = x-1; nx <= x+1; ++nx) {
      for (int ny = y-1; ny <= y+1; ++ny) {
        if ((nx == x && ny == y) || nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
        // {nx, ny} - соседняя клетка.
      }
    }


    Я бы просто раздул поле - так код сильно проще.

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вы случайным образом генерируете координаты комнаты в цикле, пока вам не повезет выбрать полностью пустое место (while (collision == true);).

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

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

    Еще можно сделать немного по другому - вместо случайного выбора места и потом проверки на пересечение, найдите все места, куда комнату можно впихнуть и из их списка выбирайте случайное одним rand(). Тут уже не будет цикла, завершающегося только когда вам повезло. Но тут тоже может быть проблема, что мест для размещения новой комнаты вообще нет. Или перезапускайте с нуля расстановку комнат, или требуйте, чтобы они были маленькие. Еще можно их ставить в порядке от больших к маленьким.
    Ответ написан
    2 комментария
  • Не могу, понять как компьютер перемещает свой знак?

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


    Вот этот код ставит фигуру в текущую клетку: board[move] = computer;
    Двумя строчками ниже этот ход откатывается: board[move] = EMPTY;

    found = winner(board) == computer; - этот код присваивает булевой переменной found значение выражения winner(board) == computer.
    Ответ написан
    9 комментариев
  • Что быстрее индексы или указатели?

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

    Практический совет - лучше писать через индексы, ибо так понятнее и больше шансов что компилятор там все наоптимизирует (например, он сможет векторизовать работу через какие-нибудь SSE инструкции процессора).

    Совет по бенчмарку - если памяти не хватает, стоит по одному достаточно большому массиву пройтись 10000 раз. А лучше использовать готовые фреймворки для измерения скорости, вроде того де gbenchmark.

    Еще, иногда полезно посмотреть на ассемблерный выхлоп. Вот, например, что происходит при -O3 опции компилятора. Он генерирует вообще идентичный код для обеих функций (развернув циклы)! И даже при -O2 оно одинаковый код выдает.

    Без оптимизаций код разный, но там все не так как вы думаете. Вместо инструкции mov eax, dword ptr [rax + 4*rcx] в варианте с индексами используется инструкция mov eax, dword ptr [rax] для указателей. Это самое "складывание с указателем массива" вообще не отдельная операция - а вариант адрессации в инструкции mov. Они могут вообще одинаковое количество тактов занимать, это надо мануал по конкретной архитектуре процессоров читать.
    Ответ написан
    Комментировать
  • Как обеспечивается совместимость динамических библиотек при ликовке в рантайме?

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вообще, работу с указателем на base тоже надо переписать через memcpy. Потому что это UB. Вдруг выравнивание у массива не такое, как у структуры Base. Без memcpy тут никак. Другого способа разместить 2 структуры в памяти подряд компактно - нет.

    Edit: конечно, можно объявить вашу стоуктуру где поля base и S1 идут рядом, но там будет какой-то padding. Работать с этим как с сериализированным массивом байт - нельзя.
    Ответ написан
    1 комментарий
  • Как использовать класс, определенный в двух подключаемых файлах?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Есть костыль:
    #define Class3 Class3_Unused
    #include "module1.h"
    #undef Class3


    Таким побразом при включении module1.h вместо Class3 будет объявлятся какая-то хрень, которую нигде вы использовать не будете.

    Правда, все ломается, если у вас этот module1.h включен по цепочке других инклудов. Надо аккуратно в каждом месте, где вы его включаете так же обарачивать в define.

    Но по уму, это большой косяк авторов module1 и module2, что они не используют namespace. Их надо бы переписать.
    Ответ написан
    1 комментарий
  • Как решить подобную задачу?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Ошибка, если интересно, в том, что в коде написан & вместо %. Соответственно, пропускаются не числа, которые не делят n, а числа, дающие не 0 в побитовом И с n.

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

    Если надо побыстрее, то можно, например, запустить программу на нескольких прервых числах, посмотреть результат и попробовать вывести закономерность, смотря на битовую запись n и корня из n. Правда там не похоже, что что-то простое.

    Совсем быстрое решение - это динамическое программирование по бинарным цифрам корня. Это весьма сложный алгоритм. Сработает, в общем-то, для n до 2^64. Считайте F(l,f) - количество способов как-то расставить первые l бит числа, т.ч. все биты, единичные в n, взяты по 0, и число не превосходит корня из n, а f - флаг, означающий, что число уже строго меньше корня.

    Легче считать это циклом снизу вврех. Смотрите, какую цифру можно дописать к (l,f): если в n стоит 1 в этом бите - то только 0. Иначе, можно дописать 1, только если f=1 или в sqrt(n) стоит 1 в этом бите. Новый флаг f' будет 1, только если f=1, или вы поставили 0, а в sqrt(n) стоит 1.

    Потом ответ надо домножить на 2 и вычесть 1, если (int)sqrt(n) & n == 0.
    Ответ написан
    1 комментарий
  • Как найти наикратчайшие пути взвешенного орграфа, представленного матрицей инцидентности, используя алгоритм Дейкстры?

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

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

    Кстати, у вас матрица инцидентности неправильная: должно быть по 2 числа в каждой строке. Обычно ставят -цену у начальной вершины и +цену у конечной.
    Ответ написан
    4 комментария
  • Как преобразовать char* содержащий символы unicode?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вам надо \uXXXX преобразовать в char16_t? Можно это руками делать. Берете по 6 байт из строки. Последние 4 руками преобразуете из 16ричной системы. Если символ от a до f, то прибавляете к нему 10-'a'. Если от 0 до 9 - 0-'0'.

    Удобно это циклом делать, сдвигая ответ на 4 бита влево и прибавляя новый символ:
    std::wstring Parse(const std::string encoded) {
      std::wstring result;
      for (int start = 0; start < encoded.length(); start += 6) {
        if (encoded[start] != '\\' || encoded[start+1] != 'u') return result // строка неправильного формата.
        char16_t nxt = 0;
        for (int i = start +2; i < start+6; ++i) {
          int cur = 0;
          char &chr = encoded[i];
          if ('0' <= chr && chr <= '9') cur = chr - '0';
          if ('a' <= chr && chr <= 'f') cur = chr - 'a' + 10;
          if ('A' <= chr && chr <= 'F') cur = chr - 'A' + 10;
          nxt = (nxt << 4) + cur;
        }
        result += nxt;
      }
      return result;
    }
    Ответ написан
  • Как можно улучшить код?

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


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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Очень многие числа нельзя записать в виде числа с плавающей запятой, потому что они не представимы в виде доичной дроби с заданным количеством знаков. Например вы 1/3 как десятичную дробь не запишите. Ибо там 0.3333... - бесконечная последовательность троек. Для хранения double выделенно сколько-то бит под мантиссу, но их сильно меньше бесконечности.
    Поэтому ни 1/10, ни 3/100, ни 1467/1000 и почти любая дробь будет непредставима в виде float. Поэтому, если вам нужна точность, то вы округляете до целого и храните количество, скажем, тысячных долей в целых числах. Как сумму денег вы храните не долларах, округленных до 2 знаков, а как целое число центов.
    Ответ написан
    Комментировать
  • В чем проблема в коде работы с графом?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Ошибка в том, что у вас граф криво задан. У вас там ровно 6 списков. А размер графа - 7. Поэтому в MakeStep вы обращаетесь к graph[6], а это undefined behavior. А там непонятно, что происходит. Может вы таблицу портите каким-то значениями и никогда положительного значения не получаете. Скорее всего корраптите память через обращение к мусорным adj в std::array (который на стеке лежит) и получаете мусор в каких-то локальных переменных.
    Ответ написан
  • Компиляция C++ кода на Ubuntu и Windows даёт мне разный результат, почему?

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

    Советую переписать код. Возвращайте std::array<std::bitset<16>,4> например. Вместо push_back сразу обращайтесь к i-ому элементу ответа.

    Далее, у вас там 2 функции делают одно и то же - разбивают большой bitset на несколько маленьких. Напишите template функцию, которая выделяет из битсета длиной N битсет длиной M со сдвигом offset. Внутри просто циклом присваивайте res[i] = input[i+offset].

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

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

    Т.е. действительно, в вашем случае надо в AIJH добавить точки ABKJH.

    Образуются ребра длины 0 - значит повторяющиеся вершины надо просто выкинуть.
    Ответ написан
    Комментировать
  • Как решить данную задачу на двумерные массивы c++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    int sum = 0;
    int cnt = 0;
    for (int dx = -1; dx <= 1; ++dx) {
      for (int dy = -1; dy <= 1; ++dy) {
        if (dx == 0 && dy == 0) continue;
        int nx = i + dx;
        int ny = j + dy;
        if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
        sum += A[nx][ny];
        ++cnt;
      }
    }
    B[i][j] = cnt == 0 ? 0 : sum / cnt;
    Ответ написан
    Комментировать
  • Что не так с кодом, проверяющим логическую схему?

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

    Во-вторых, у вас ошибка с тем, что вы из bitmask берете биты, которые есть числа 0 и 1 и проводите над ними битовые операции, а не логические. И это у вас там 32-битные числа же! Для | и & оно еще совпадает с вашими ожиданиями, а вот ~ обращает ВСЕ 32 бита числа.

    Поэтому ~(bitset[E] | bOrD) всегда выдаст или -1 или -2. Вы потом это пропустите через or, получите опять же -1 или -2 и в конце преобразуете это в bool. И вот тут-то оно всегда и станет true.

    Чтобы это исправить, или используйте логические операции (||, &&, !), или вместо ~x используйте x^1, или в самом конце возвращайте результат с &1, чтобы значения остальных бит ни на что не влияли.
    Ответ написан
    5 комментариев
  • Правильно ли понимаю работу ссылок в С++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Это называется передача по ссылке/передача по значению. С амперсантом, передается ссылка на переменную. Иначе - копия значения переменной. Если вы будете менять копию значения, ничего вне функции не изменится, ведь вы копию меняете. А если будете менять значение ссылки, вы будете менять значение той же самой переменной.
    Ответ написан
    Комментировать
  • Почему нельзя использовать std::function как аргумет шаблонной функции?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Потому что лямбда не ялвяется std::function. Компилятор, вообще говоря, может лямбду привести к типу std::function, но не в вашем случае. Вам надо, например, самим преобразовать лямбду в std::function:
    std::function<bool(int, int)> comp = [](int left, int right)
      {
        return left < right;
      };
      Sort(vec, comp);


    Сам компилятор тут это сделать не может, потому что ему тип к которму приводить-то неизвестен - он зависит от параметра шаблона T.

    Можно, еще, например, указать компилятору параметры шаблона, тогда все скомпилируется:
    Sort<int>(vec, [](int left, int right)
      {
        return left < right;
      });


    Но лучший вариант - не использовать std::function в шаблоне. Просто используйте какой-то typename U, у которого вы продполагаете существует operator(int, int). Если туда передать не function и не лябмду, оно не скомпилится:

    template <typename T, typename U>
    void Sort(std::vector<T>& vector, U comparison) {
        // Используете comparison, как-будто это std::function:
        if (comparison(1, 1)) return;
    };
    
    
    int main()
    {
      std::vector<int> vec = { 1, 2, 3, 4, 5, 7, 6, 9 ,8 };
    
      Sort(vec, [](int left, int right) -> bool
      {
        return left < right;
      });
        return 0;
    }
    Ответ написан
    Комментировать
  • Почему умножение матрицы 8x8 медленнее чем 10x10?

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

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

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