Задать вопрос
Ответы пользователя по тегу C++
  • Как сократить код с подпрограмой?

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

    Ну какая разница, как у вас там переменная называется sA или sB - результат будет один и тот же.

    Да, может вы путаетесь, но аргумент в функции можно тоже переменовать. Хоть там и написано int masivA(int* a), этот a - это аргумент. Он никак не привязан к массиву a в main(). Туда можно передать и a и b и любой другой массив.
    Ответ написан
    4 комментария
  • Аварийное прекращение создания объекта из класса, который является родителем?

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

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

    Но этот метод не так легко обобщается на цепочки наследников. Надо чтобы все они одинаково интерпретировали этот флаг и меняли его при неудачной инициализации.
    Ответ написан
    3 комментария
  • Почему substr работает странно?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Потому что читайте документацию. substr принимает начало и длину подстроки, а не конец.

    Соответственно, надо делать вот так:
    std::string variable_value = var.substr(variable_value_start + 1, variable_value_end - variable_value_start - 1);
    Ответ написан
    Комментировать
  • Как перевести число в двоичную систему счисления?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Нужно или выводить нужное количество ведущих нулей, или изменить условие в цикле перевода. У вас там сейчас while (Notspace[i] > 0), что как раз считает цифры до последней значащей цифры. Поменяйте на цикл в 8 итераций и будет у вас всегда 8 цифр.
    Ответ написан
    Комментировать
  • Где ошибка? Почему массив выводится в линию?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    }cout << "\n"; - вот ошибка.

    Вас не смущает, что эта строчка не похожа на все остальные? Что, по-вашему, означает закрывающая скобка в начале?

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

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

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

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

    Суть переопределения в том, что это ПЕРЕопределение. Замена одной функциональности на другую. Без virtual этого не происходит.

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Кроме параметров функции, можно возвращать структуру с именованными значениями или std::vector или std::touple.
    Ответ написан
    6 комментариев
  • Как не обрезать стркоу после \0?

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

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

    Скорее всего, это происходит на строчке:
    result = num.at(0);
    Ответ написан
    Комментировать
  • Почему в С++ появляется Segmentation fault?

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    q.push(make_pair(x,y));
    // или эффективнее.
    q.emplace(x,y);
    Ответ написан
    3 комментария
  • Проблема с преобразование с char в int?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Проблема с win api: https://learn.microsoft.com/en-us/windows/win32/in...

    Оно ожидает вот такие коды. И, если для заглавных английских букв оно еще совпадает с кодами ascii, то для строчных букв - нет.
    Ответ написан
  • Ошибка unresolved external symbol с конструктором/деструктором в классе?

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

    Или пользуйтесь системой сборки (cmake, visual studio, ninja, и т.д...) или вручную запускайте 3 команды: сделать объектник из main.cpp, сдлеать объектник из EcsSystems.cpp, собрать из объектников исполняемый файл.
    Ответ написан
    Комментировать
  • Как понять запись кода?

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

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

    Умное и быстрое решение, к сожалению, будет сложно написать без std::unordered_map. Такое решение будет работать за O(n). Самостоятельно хеш таблицу писать будет сложно. Но если без хеш таблицы, то решение будет работать также медленно, как и тупое рекурсивное прикладывание, поэтому приведу тут все решение.

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

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

    Пустые вершины всегда имеют какой-то номер, допустим, 0.

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

    void Match(Tree *stack, Tree *needle) {
      std::unordered_map<std::pair<int, int>, int> shapes;
      int needle_shape = ClassifyShape(needle, shapes, -1);
      ClassifyShape(stack, shapes, needle_shape);
    }
    
    int ClassifyShape(Tree *tree, std::unordered_map<std::pair<int, int>, int> &shape, int find_shape) {
      if(!tree) return 0;
      int l = ClassifyShape(tree->left);
      int r = ClassifyShape(tree->right);
      auto pat = make_pair(l, r);
      auto it =  shapes.find(pat);
      int this_shape = -1;
      if (it == shapes.end()) {
        this_shape = shapes.size();
        shapes[pat] = this_shape;
      } else {
        this_shape =  it->second;
      }
      if (this_shape == find_shape) {
        std::cout << "Found match at node " << tree->value << std::endl;
      }
      return this_shape;
    }


    В нивном решении надо заменить unordered_map shapes на массив пар чисел (или массив структур или два массива чисел). Циклом в нем проищите текущую пару l, r, если не нашли, то допишите в конец.

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

    Но, возможно вашему преподу такое будет слишком заумно. Тогда вам нужна аккуратная рекурсивная функция сравнения:
    bool Compare(Tree* a, Tree *b) {
      if (a->left && !b->left) return false;
      if (a->right && !b->right) return false;
      return (!a->left || Compare(a->left, b->left)) && (!a->right || Compare(a->right, b->right));
    }


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

    А дальше вам надо рекурсивно пройтись по первому дереву и вызвать вот эту Compare для текущей вершины и корня второго дерева. Если совпало - то выводите текущую вершину.
    Ответ написан
  • Существует ли быстрый алгоритм поиска общих подстрок во множестве больших строк?

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

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

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

    Второй вариант, возможно более подходящий для таких объемов данных - это полиномиальные хеши. Можно для каждой строки вычислить L-N+1 хешей для всех подстрок длины N. Первый хеш считается тупо по формуле, а дальше дописывание одного символа справа и удаление одного символа слева можно за 2 операции пересчитать. Вот так вы быстро, за линейное время, можете построить все хеши для одной строки. Запишите их в файл, отсортируйте его (гуглите - известная задача сортировки очень большого файла). А потом операцией слияния можно найти повторяющиеся числа во всех файлах.

    Более того, можно не сравнивать каждый файл с каждым, а выполнять слияние сразу на всех файлах. Для этого надо завести приоритетную очередь, она же куча, она же heap, в которую складывать текущие числа из всех файлов (по одному из файла) вместе с указателем на сам файл. Вам надо из этой очереди вынуть минимальное число, и потом вынимать дальше, пока минимум в очереди не изменился. Т.е. вынуть все одинаковые минимальные числа. Файлы, на которые они указывают - это строки с совпадениями. Пометьте это где-то, и для каждого файла прочитайте следующее число и положите его в очередь.

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

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

    Если все-таки надо искать совпадения по всем строкам глобально, то придется помучиться. Разбейте ваши данные на K частей примерно одинакового размера так, что каждый компьютер может обработать по 2 части, а хранить хотя бы по 3 части.

    В идеале у вас должно быть еще и K/2 компьютеров, иначе схема усложняется.

    Надо будет провести K-1 раундов. На первом раунде части 1 и 2 лежат на компьютере 1, части 3 и 4 на втором, и т.д. На втором раунде вы храните части 2 и 3 на компе 1, 4 и 5 на компе 2 ... K и 1 на последнем. При переходе между раундами каждый комп отдает одну часть куда-то, и одну откуда-то получает. На третьем и четвертом раунде вы обрабатываете все пары, в которых вторая часть имеет номер на 2 больше первой части (если брать по модулю K). И так далее. На последнем раунде будут обрабатываться пары, где одно число больше другого на (K-1)/2.

    Например, для K=4 вы получаете такие пары на компах:
    1. (1,2) (3,4)
    2. (2,3) (4,1)
    3. (1 3) (2 4)


    Тут надо порисовать и составить схему так, чтобы поменьше данных перекладывалось. Для некоторых K так красиво не получится, и какие-то компы будут простаивать на каких-то раундах.

    По поводу оптимизаций - узкое место будет загрузка данных с диска и передача их по сети. Ассемблером баловаться тут смысла нет особо. Запускайте кучу потоков, чтобы диск не простаивал. Еще репликацию данных можно запускать параллельно с обработкой предыдущего куска, если места хватает.
    Ответ написан
    Комментировать
  • Можно ли вызвать деструктор void*?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Нет. Компилятору же надо знать, что там за деструктор вызывать. Что вы в void* на самом деле положили - он знать не может. Более того, там не только деструкторы, там и delete у указателей вызван не будет. Руками придется сначала привести к правильному типу и потом отчистить память (что вызовет деструктор).
    Ответ написан
  • Как создать цикл для того чтоб заменять 0 на 1 и 1 на 0?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Подсказка: в c++ в цикле for не обязательно использовать i++. Можно, например, i+=10.
    Ответ написан
    Комментировать
  • Не работает код C++?

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

    Ну и вывод в цикле будет весьма спамный.
    Ответ написан
    Комментировать