Задать вопрос
  • Зачем нужен амперсанд перед именем функции/метода?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    На самом деле понятнее писать вот так:
    int& Foo();

    Функция возвращает ссылку на int. Ссылка - это как указатель, только она не может указывать вникуда. Соответственно, вы не можете завести переменную ссылку сразу не инициализировав ее - а на что она будет указывать. И также ссылки, в отличии от указателей, не надо ее разыменовывать.

    Использовать можно, например, вот так:
    int& ref = Foo();
    std::cout << ref+10;


    Тут под переменную ref не выделяется память, ведь это ссылка, которая инициализируется тем, что вернула Foo. Так же сам объект не копируется. Максимум, под капотом скопируется адрес.
    Поэтому ссылки имеет смысл заводить на тяжелые объекты, чтобы не копировать их зря и не выделять память.

    Так же можно через эту возвращенную ссылку изменять основной объект:
    int x;
    int& Foo() {
        return x;
    }
    ...
    
    x = 0;
    int& ref = Foo();
    ref = 10;
    std::cout << x:

    Этот код выведет 10.

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

    Ну и еще, можно с этой возвращенной ссылкой работать и как с обычным int:
    int x = 2 + Foo();
    Но если вы не собираетесь менять значение внутри или не пытаетесь сэкономить на копировании объекта, то вам нет смысла вообще ссылки использовать.

    Ну и, конечно, аккуратно со ссылками надо быть. Вполне можно извернуться и получить ссылку указывающую на удаленную память. Напрямую ссылки на локальные переменные компилятор возвращать не дает, но если сначала взять адрес в указатель, а потом его разименовать и вернуть как ссылку, то вы получите undefined behavior.
    Ответ написан
    1 комментарий
  • В чем отличия между кодами?

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

    Вам надо использовать s.substr.
    Ответ написан
    Комментировать
  • Как оформить список C++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Используйте snprintf. Так можно с тем же форматом вывести все данные не в консоль, а в строку.
    Ответ написан
  • Зачем Zobrist хешированию случайные числа?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Наверное, можно и константами ограничиться. Вот только выписывать 768 констант никому не охота. Что-то простое брать, вроде подряд идущих чисел - плохой хеш будет. Надо реально 700 разных псевдослучайных чисел.
    Ответ написан
    Комментировать
  • Что означает -'0' на C?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Это вычитание значения '0' из значения str[j]. И то и другое - символы, они же char. В языке Cи, это целочисленный тип. Просто каждому символу дается его ascii код.

    Тут это используется для получения численнного значения цифры из ее символьного значения, ведь символы '0'-'9' в ascii идут подряд в натуральном порядке.
    Ответ написан
    Комментировать
  • Доказательство простого факта. Математический анализ, равномерная непрерывность. Как?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Я так понял в условии на самом деле говрится, что для любого достаточно маленького z (0 < z < Z0) функциональный ряд равномерно сходится на (a+z, b-z)

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

    Пусть есть a<x0<b. Возьмем z = min(Z0, (x0-a)/2, (b-x0)/2). Используем данное, что ряд равномерно сходится на отрезке (a+z,b-z), а значит F на этом отрезке непрерывна. Значит F непрерывна в точке x0 (ведь мы так z подобрали, чтобы x0 в этом интервале лежала). Мы взяли любую точку x0 из (a,b), а значит F непрерывна на всем интервале.

    Edit: Если же в условии тупо дана равномерная сохдимость на каком-то интервале (c,d) (a < c < d < b), а не для сколь угодно близкого к (a,b) вложенного интервала, то, очевидно, что непрерывности там никакой и нет.
    Ответ написан
    Комментировать
  • Как правильно пропарсить лабиринт в граф?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Самое простое - это сделать вершиной каждую клетку и гнать в этом графе поиск в ширину. Можно даже не строить граф явно - а просто при обходе смотреть на четырех соседей и проверять, а не стена ли там, а были ли мы в клетке (x+dx[k], y+dy[k]), и класть координаты в очередь, если надо.

    Вы же хотите считать только перекрестки и повороты врешинами. В худшем случае, если поворотов в лабиринте много - это будет даже медленнее обхода в ширину. Потому что он работает за линию, а дейкстра - за O(n log n) в лучшем случае. Плюс там константа больше у этого n log n. Правда, это можно решить если вместо дейкстры использовать обобщенный 0-1-BFS (BFS с ограниченными ребрами - там где много очередей используется). Но реализация будет сильно посложнее простого BFS.

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

    Что-то типа такого:
    int last_node = 0;
    for (i = x_start, j = y_start; i <n && j < m; i+= dx, j+=dy) {
       if (is_wall[i][j]) {
        last_node = -1;
      }  
      if (node_number[i][j] <- 0) continue;
      if (last_node > 0) {
        // добавить ребро между вершинами.
        AddEdge(last_node, node_number[i][j]);
      }
      last_node = node_number[i][j];
    }


    Тут я просто добавляю ребра в строке или столбце между двумя соседними вершинами.
    Ответ написан
    Комментировать
  • Как определить тип функции для шаблона?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Можно использовать typedef int value_type; в классе с Setter/Getter.

    Тогда в вашем шаблоне вы можете использовать C::value_type. Так в STL, например, сделано.

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

    Минусы: Надо обязательно заводить этот самый value_type и обновлять его вместе с методами Getter/Setter.
    Ответ написан
  • Сдвиг двумерного массива, появление ошибки Stack around the variable 'arr' was corrupted. Как исправить без переписывания кода?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Код исправляется элементарно. Надо внутренний цикл по j гнать не до 0, а до 1. Что бы не вылезать за границу массива, вы же там к j-1 -ому элементу обращаетесь. А поскольку вы делаете swap, то вы меняете элементы массива с памятью перед ним. Массив - локальная переменая, а значит он лежит на стеке и вот это вот затирание памяти рядом с массивом и есть это самое "Stack around the variable 'arr' was corrupted".

    Ну и по стилю - вместо i > -1 обычно пишут i >= 0.
    Ответ написан
    Комментировать
  • Как решить задачу с символами? Почему не работает одна функция?

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

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

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Открывайте файл в бинарном режиме "wb" и пишите туда через fwrite (лучше побайтово, чтобы не мучиться с переносимостью из-за порядком байтов в int).

    Читайте, соответственно, через fread.

    Для шифрования лучше всего, во-первых, байты в разном порядке писать, (не 0,1,2,3, а, скажем, 2,0,3,1) и, во-вторых, xor-ить их с какими-то константами. А еще лучше не с константами, а со случайными данными, которые тоже записываются в файл рядом. Или не рядом, так будет закономерность меньше видна.

    Но все это может спасти только от людей незнакомых с reverse engineering'ом и отладкой. Более менее осведомленный ползователь посмотрит в ассемблерный код и поймет, что и как там читается и где и что надо поменять. Но да, это посложнее просто редактирования txt файла.

    Ну и, artmoney с cheat engine никто не отменял.
    Ответ написан
    Комментировать
  • Алгоритм максимально равномерного распределения предметов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    std::vector<int> DistributeExtraObjectsFairly(std::vector<int> objects, int extra_objects) {
        std::vector<int> permutation;
        permutation.reserve(objects.size()+1);
        permutation.resize(objects.size());
        std::iota(permutation.begin(), permutation.end(), 0);
        std::sort(permutation.begin(), permutation.end(),
            [&objects](const int &a, const int &b) {return objects[a] < objects[b];});
        int num_increased = 1;
        permutation.push_back(0);
        int step = (objects[permutation[num_increased]] - objects[permutation[num_increased-1]]) * num_increased;
        while (extra_objects >= step && num_increased < objects.size()) {
            extra_objects -= step;
            ++num_increased;
            step = (objects[permutation[num_increased]] - objects[permutation[num_increased-1]]) * num_increased; 
        }
        int final_value = objects[permutation[num_increased-1]] + extra_objects / num_increased;
        int num_bigger_values = extra_objects % num_increased;
        for (int i = 0; i < num_bigger_values; ++i) {
            objects[permutation[i]] = final_value + 1;
        }
        for (int i = num_bigger_values; i < num_increased; ++i) {
            objects[permutation[i]] = final_value;
        }
        return objects;
    }


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

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

    Edit: работает за O(n log n), где n - количество элементов в списке. Быстрее, я подозреваю, никак. Есть еще решение за O(n log M) - где М - максимально возможное число во входных данных. Это через бинпоиск по минимальному числу в конце.
    Ответ написан
    Комментировать
  • Почему при вызове деструктора не меняется переменная?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Я так понимаю, у вас проблема со строчкой
    aobj1[0] = a(2);

    Тут вызывается конструктор для временного значения a. Потом оператор копирования из временной переменной в *aobj. Потом вызывается деструктор временного значения.

    А потом где-то в конце произойдет и деструктор aobj.

    У aobj delete_counter после этой строчки равен 1 (ведь он скопирован у временного значения, которое сделало delete_counter единицей в констукторе). В конце при вызове деструктора aobj там delete_counter будет 1 в начале.

    Вы смотрите на адрес this в дебагере в деструкторе. Два вызваных деструктора будут для двух разных объектов (для временного значения и для aobj).

    Если вы хотите какой-то счетчик ссылок делать, то вам надо переопределять операторы копирования и перемещения (а так же все возможные конструкторы). И там аккуратно изменять счетчик ссылок. И счетчик ссылок должен быть частью общего объекта - частью класса b, а не класса a.
    Ответ написан
    4 комментария
  • Почему простой цикл на c++ выполняется медленнее, чем на golang?

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

    Чтобы этого не было, можно ксорить не с константой, а с индексом i, например.
    Ответ написан
    Комментировать
  • Как объявить функцию в другой функции?

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

    Перед F напишите
    int G(int n);

    Это скажет компилятору, что есть вот такая функция. Ее определение же остается также дальше по тексту после F.
    Ответ написан
    Комментировать
  • Как избежать дублирования последней строки из файла?

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

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

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

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

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