Задать вопрос
  • Как решить задачу комивояжера с магией?

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

    Вершина в новом графе характеризуется четверкой чисел: (m, x, y, k) - m - маска уже посещенных интересных точек, x, y - координаты клетки, k - сколько свитков осталось. Ребра в графе хранить не надо, а стоит их рассчитывать на лету. Всегда можно пойти в 4 соседние стороны. При этом x, y, пересчитываются, k не меняется. Маска m получает новый бит, если конечная точка - одна из интересных (через битовое or. Если бит уже был установлен, он не меняется). Если k>0 - то можно телепортироваться. Перебирайте все x', y' в пределах 8 клеток от изначальной. Маска m получает новый бит, если конечная точка интересная. k уменьшается на 1.

    Вот по этим четверкам с заданными ребрами запускайте обход в ширину из точки (0, x_start, y_start, N). Как только доходите до точки с маской включающей все интересные точки - вы нашли кратчайший путь.

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

    Это будет за O(W^2*H^2*N*2^M), если W,H - размеры поля, N - количество свиков, M - количество интересных точек.
    Ответ написан
  • Как вызвать появление меню в splitbutton?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если стоит visual studio, там есть утилита spy++. Она мониторит виндовые сообщения, приходящие выбранному окну.

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    pd.options.display.max_rows = 1000 перед выводом.
    Ответ написан
    3 комментария
  • Как сделать рекурсивную функцию, которая находит сумму нечетных элементов динамического массива на C?

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вам надо описать конструктор Ball без параметров. Например:
    Ball() x(0), y(0), r(0), vx(0), vy(0) {}

    Потому что new Ball[n] Создает n объектов, но конструктора по умолчанию (без параметров) у класса Ball нет. Обычно его генерирует компилятор сам, но только если вы не указали никаких своих конструкторов. А new не знает, какие числа передавать в качестве x, y, r и т.д.

    Смотрите правило трех.
    Ответ написан
    Комментировать
  • Как конвертировать steady_clock::time_point в system_clock::time_point и наоборот?

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

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Во встроенный printf вы это не добавите никак. Придется писать собственную обертку и там парсить строку формата.
    Так, чтобы это работало со всеми структурами, у которых есть член int a - нужны шаблоны, да. Гуглите variadic template, но это мрак и ужас. В любом случае это будет весьма громоздкий и непонятный код.

    Но раз уж у вас C++, то вы вместо printf используйте cout. Переопределите operator<< для ostream и вашей структуры и выводите через cout << *s1.

    Да, тут не получится в каждом конкретном месте вызова менять формат вывода, он будет одинаков везде - но так ли вам это нужно, чтобы городить костыли с printf?
    Ответ написан
    Комментировать
  • Как сделать перестановку с повторением в 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;


    Ну и вы там не проверяете, вдруг скорость нулевая, тогда время до пересечения - бесконечность.
    Ответ написан
    Комментировать