Задать вопрос
  • Перебрать все комбинации массивов строк?

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

    Еще, естественно, надо передавать в функцию массив массивов строк - ваши исходные данные.
    Ответ написан
    Комментировать
  • Нужно ли строго проверять if?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    А почему не рассматривается третий вариант? Что-нибудь вроде
    if (ToString(exampleVar)[0].length() == 4) alert(1)


    Умышленно писать === true, конечно может быть иногда оправданно в языках без строгой типизации, но в целом это довольно редко оправданная вещь.
    Ответ написан
    Комментировать
  • В чём ошибка реализации алгоритма Прима?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    if ((matrix[i][j] < minValue[j]) && (isPartOfOutputTree[j] == false))


    Вот тут ошибка. Ведь i - это номер итерации,а совсем не только что включенная в дерево вершина, относительно которой надо сделать релаксацию.
    Ответ написан
  • Почему при копировании файлов получаются битые файлы?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Аккуратно выведите куда-нибудь параметры, которые вы передаете в функцию создания symlink.

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вот алгоритм выделения граней планарного графа: https://e-maxx.ru/algo/facets

    Сначала вам придется попересекать отрезки друг с другом и получить граф: вершины - точки пересечения и концы отрезков, ребра - куски отрезков. Потом выделяете алгоритмом выше внешнюю и внутренние грани.

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

    Upd: Дополнение - выбрасывать можно только точки, "вогнутые" внутрь полигона, такие, что их удаление только сделает внешнюю часть больше, а внутреннюю меньше.

    В итоге, если удачно подобрать границы в алгоритме выше, то получится примерно как у вас на картинке.
    Ответ написан
    Комментировать
  • Как удалить первый элемент однонаправленного списка в с++?

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

    Еще отдельная проблема с удалением первого элемента, потому что там менятся должна не ссылка next у предыдущего элемента, а ссылка на начало списка. Эту проблему можно решить по разному. Например, можно вместо указателя head держать один элемент списка без значения. Тогда указатель на начало списка будет менятся также как и любой другой. Фактически, в любом списке всегда будет один фиктивный элемент. Этот способ также предподчителен для работы с двусвязными списками. Тогда список как бы замыкается в кольцо и не надо разбирать отдельно ни случай первого, ни случай последнего элемента. Мне больше нравится другой метод - можно помнить не предыдущий элемент, а указатель-на-указатель, который надо будет поменять.

    node** prev_link = &head;
    node* cur = head;
    for  (node* cur = head; cur != nullptr; cur = cur->next) {
      if (cur->val == to_del) {
        *prev_link = cur->next;
        delete cur;
        break;
      }
      prev_link = &cur->next;
    }
    Ответ написан
    1 комментарий
  • Возможен ли треугольник по стороне, углу и пропорциональным сторонам?

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

    Итак, дано только A и k, так?

    Чтобы как-то угол связать со сторонами надо воспользоваться теоремой косинусов:

    c^2 = a^2+b^2-2*a*b*cosA.
    подставив суда b=ck, получим
    с^2 = a^2+k^2c^2-2*k*a*c*cosA

    Это квадратное уравнение, связывающее C и A. Можно решить его относительно a (c - параметр) и вы получите а, выраженное через с.

    Ну и в конце надо проверить, что a+b > c, a+c > b, b+c > a, подставив туда найденные формулы для b и a через c. В этих неравенствах будут известные cosA, sinA, k и неизвестная с. Поскольку тругольник по углу и соотношению сторон можно масшабировать, то неравнество должно выполнятся для всех c. Но на самом деле в этих неравенствах все c можно будет тупо сократить. Какие-то из них можно сразу же выкинуть, если рассмотреть 2 случая k>1 и k<=1. Ну а как их дальше решать - думайте сами.
    Ответ написан
    3 комментария
  • Как исправить ошибку "Нарушение прав доступа при записи по адресу"?

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

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

    Можно во время отладки нажать на "продолжить" и тогда дебаггер остановится именно на той инструкции, которая вызвала ошибку. Дальше уже можно смотреть, в какую переменную вы там пишите и откуда она взялась.

    Падает оно потому, что нельзя string читать и писать в файл вот так, просто интенрпретируя память объекта как char*. Потому что string содержит в себе указатели на динамически выделенную память.

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

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Шансы 1:3:3:1. Генерируйте случайное число от 0 до 7. При 0 - выдавайте случайное число < 50. При 1-3 - случайное число от 50 до 74, при 4-6 - выдывайте ответ от 75 до 89, при 7 выдавайте число от 90 до 100.

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    analiz(func(n));

    Вот тут вы вызываете функцию func и передаете результат ее работы в analiz. Хотя analiz хочет получать функцию. Надо делать так: analiz(&func);
    Ответ написан
    4 комментария
  • Как найти общую часть у вещественных чисел?

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

    Я думаю, вам остается только вывести оба числа в строки в каком-нибудь фиксированном формате и дальше сравнивать посимвольно.
    Ответ написан
  • Как занести в char int?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Используйте sprintf. Только сначала выделите достаточно памяти под строку.

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Во-первых, может быть проблема со вводом. cin и cout работают медленно с большими объемами данных. Или читайте через scanf, или можно отключить синхронизацию с stdio.

    Во-вторых, описанная вами структура данных быстродействие не убъет, но мне не понятно, чем она поможет в задаче.

    Вам точно понадобятся map-ы из строки во что-то еще. В питоне вы наверняка использовали словари (использовали строки в виде ключа в массиве), вот это оно и будет в с++. Можно поэксперементировать std::unordered_map может быть побыстрее std::map. А вообще, особенно быстрое решение вы можете получить используя cтруктуру данных бор (оно же trie). Правда, ее придется самостоятельно писать.
    Ответ написан
    3 комментария
  • Как называются алгоритмы, который показывает пошаговые изменения в слове?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это про теорию графов и кратчайшие пути. Вам надо найти путь в графе из слов, где ребра есть между словами с одним изменением.
    Ответ написан
    5 комментариев
  • Что определяется в переменной stack в Python3 в случае такой записи stack = [(src, [src])]?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вам поможет встроенная функция type(). Она описывает тип передаваемого объекта.

    Посмотрите, что выводит type(stack). Потом можно удалять уже понятные части, чтобы смотреть что там внутри.
    Ответ написан
    Комментировать
  • Можно ли реализовать графику на стандратных и системных библиотеках?

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

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

    Если возможны перекосы, то есть простой алгоритм.
    Сначала за один проход подсчитайте частичные суммы s1=y1, s2=y1+y2, s3=y1+y2+y3...

    Потом идем с конца. В последнюю стопку можно положить от max(0, z-s(n-1)) до yn блоков. Все оставшиеся блоки гарантированно влезают в предыдущие стопки. Уменьшайте z на сгенерированное случайное число блоков и повторяйте дальше.

    Если надо все равновернятно, то все сложно. Надо динамическим программированем уметь считать, сколько вариантов разместить k блоков на первых i стопках. Потом сгенерировать случайный номер среди всевозможного количества размещений и считать, а сколько бывает вариантов при последней стопке с 0, 1, ... yn блоках и так можно понять, сколько блоков надо поставить в последнюю стопку, чтобы накрыть нужный вариант в лексикографическом порядке. Для этого используйте подсчитанные динмическим программированием значения.
    Ответ написан
    Комментировать
  • Почему транслятор ожидает указатель в моем коде?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Параметр функции int arr[],

    Но далее у вас arr[i][j]. Компилятор пытается взять индекс j, но перед ним же уже число. Вот он вам и говорит "начальника, индекс я у массива (указателя) взять могу, а тут число, непонятно".

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Есть алгоритм за O(n log n), где n - количество точек в кривой.

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

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

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

    Удобно это реализовывать, если взять углы наклона всех сторон оболочки, их же сдвинутые на 90, 180 и 270 градусов и отсортировать. Далее надо перебирать рамки с такими углами наклона певрой стороны (можно в пределах [0,90) градусов). Первую рамку найдите перебором, а дальше какие-то точки надо будет сдвигать.

    Итак, весь алгоритм:
    1) построить выпуклую оболочку
    2) добавить в массив углы всех сторон и их копии повернутые на 90, 180 и 270 градусов и отсортировать, но не добавлять углы не в [0,90).
    3) для первого угла в массиве найдите 4 точки касания рамки.
    4) Для каждого отрезка углов в отсортированном массиве проверить, а надо ли сдвинуть точки касания вперед (каждую из четырех точек со своим углом), потом найти площадь рамки в известных точках с известным наклоном.

    Вместо работы с углами, для чего нужны тригонометрические функции, можно работать с векторами на единичной окружности. На отрезке углов можно легко взять середину, просто сложив два вектора-границы и нормировав. Для тернарного поиска не обязательно брать 1/3 и 2/3 на отрезке, поэтому можно так же просто просуммировать вектора с коэффициентами 1 и 2 и опять нормировать (v1+2*v2). Сортировать по углу тоже можно сравнивая вектора через векторное произведение векторов (иногда его называют псевдоскалярным).

    Чтобы найти рамку с заданным углом на точках не надо ничего пересекать (кроме ответа в конце, если вам надо координаты рамки вывести, а не только площадь найти). Надо представить прямые в виде cosa*x + sina*y + c = 0. Отсюда, зная точку (x, y) и угол прямой (a), можно найти c. cosa и sina считать не надо - это координаты вектора, перпендикулярного к известному вектору наклона прямой. Когда вы нашли два значения c для двух параллельных сторон, эти коэффициенты можно сложить - это и будет расстояние между сторонами (надо складывать, потому что cosa и sina в этих двух прямых будут с разными знаками, ведь у одной прямой угол на пол оборота больше). Остается подсчитать это два раза для перпендикулярных прямых и перемножить.

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Ошибка состоит в том, что при сборке линкеру не передается библиотека с определениями TiXmlDocument::LoadFile и других символов. Надо в CMake, например, дописать link_libraries или target_link_libraries c указанием TinyXML2, подобно тому, как вы сделали с SFML.
    Ответ написан