Задать вопрос
  • Входит в бесконечный цыкл,как исправить?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    После while (collision && try_counter <= 100); вставьте:
    if (try_counter > 100) break;

    Добавьте отладочный вывод в каждый цикл - посмотрите, а в каком же цикле оно висьнет-то.
    Вам еще понадобиться try_counter в цикл по монстрам (while (map[py][px] != ' ')).

    А вообще, очень странный цикл вот:
    do
            {
                center_y = ry + (r_size_y / 2);
                center_x = rx + (r_size_x / 2);
            } while (map[center_y][center_x] != ' ');


    Тут явно какая-то ошибка, потому что center_x и center_y на каждой итерации получатся одинаковые и цикл или сразу закончится, или повиснет.
    Ответ написан
  • Как декодировать матрицу?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    В комментариях мы выяснили, что была матрица 3x4 из цифр от 1 до 9. над ней произвели одно из трех действий и выдали результат. Надо по нему восстановить исходную матрицу. Надо решить на одной конкретной матрице.

    Надо попробовать применить все 3 метода и посмотреть, какой из них даст матрицу из цифр 1-9.

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

    Вот так проделайте для 9^3 вариантов, если по пути получили числа не из диапазона 1-9, то можно дальше не считать, надо пробовать другой вариант для первого столбца.

    Чуть хуже для случая "стороны и диагонали не включая элемент". Все так же переберите 3 числа в первом столбце. Во втором столбце вы получаете 3 уравнения: сумма первых двух чисел известна из числа в первой строке. Сумма всех трех известна из числа для второй строки. Сумма двух последних - из последнего числа. Т.е. вам дано x+y=A, x+y+z=B, y+z=C. Отсюда элементарно z=B-A, x=B-C, y=A+C-B.

    Этот перебор отработает где-то за 1мс - довольно быстро.

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

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

    Изначально в стек поместите корень дерева и 0. Потом в цикле, пока стек не пуст, смотрите на вершину стека. Если там счетчик 0, то выводите вершину в ответ. Увеличивайте там счетчик на 1. Если он стал равен количеству детей у вершины, удаляйте ее из стека. Иначе добавляйте в стек вершину-ребенка с номером из счетчика с 0. Можно чуть по другому: выводите вершину при помещении ее в стек с 0. Но тогда надо отдельно вывести корень дерева.
    Ответ написан
    Комментировать
  • Как найти линейную комбинацию векторов которая будет ближе всего к заданной?

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

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

    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 комментария
  • Хештаблицы, можно ли мешать open addressing и chaining(решено)?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Мешать можно. Особо память это не сократит, а реализацию сильно усложнит.
    Ответ написан
    Комментировать
  • Как ускорить решение задачи "Детский праздник"?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Бинпоиск - правильная идея. Но вот вы плохо считаете, сколько шариков один работник надует за заданное время. Вы линейно по одному шарику надуваете, а можно за 2 действия: поделите время на ti*zi+ci - узнаете, сколько полных групп шариков надуется. Остаток отдельно подсчитайте, поделив на ti. Учтите только, что оставшееся время может быть прервано на отдыхе - не насчитайте там больше zi шаров по ощибке.

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

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


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

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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Если брать более большой промежуток, отображение будет не биективным.
    Например, для x=2 отображение дает -2. Это же -2 можно получить для x=-2/3.
    Потом, в точках x=+-1 это отображение вообще не определено.
    Ответ написан
    2 комментария
  • Как решить задачу "Шестерки" с меньшими затратами памяти?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Выведите 6^2, 66^2 и так далее. N до 20 хотя бы. Посмотрите на числа. Можете ли вы угадать цифру на заданной позиции без подсчета всего числа?

    Подсказка, вы получите вот такие вот числа:
    36
    4356
    443556
    44435556
    4444355556
    444443555556
    44444435555556
    4444444355555556
    444444443555555556
    44444444435555555556
    4444444444355555555556
    444444444443555555555556
    44444444444435555555555556
    4444444444444355555555555556
    444444444444443555555555555556
    44444444444444435555555555555556
    4444444444444444355555555555555556
    444444444444444443555555555555555556
    44444444444444444435555555555555555556
    4444444444444444444355555555555555555556


    Этот паттерн можно и доказать. Надо лишь представить возводимое в квадрат число как (10**n-1)2/3 и применить чуть-чуть элементарной алгебры, вроде формулы квадрата разности.
    Ответ написан
    Комментировать
  • Что быстрее индексы или указатели?

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

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

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

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

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Обход в ширину, он же алгоритм заливки: закрасьте на невидимом канвазе или в массиве все блоки, пройдитесь по всей границе канваза/массива, если там непокрашенная точка, то красьте ее и добавляйте ее в очередь. Потом берите из очереди точки и добавляйте в нее 4 соседа, если они еще не покрашены. В конце все непокрашенные пиксели - ваши полости.

    Можно ускорить алгоритм сжатием координат: вввпишите все x и y координаты всех углов блоков, отсортируйте и унифицируйте (отдельно по каждой оси). Потом замените все координаты в блоках на порядковый номер в массиве уникальных координат. Примените алгоритм выше, но в конце надо помнить, что каждая ячейка теперь не 1x1, а сколько-то больше по вертикали и горизонтали.
    Ответ написан
  • Как обеспечивается совместимость динамических библиотек при ликовке в рантайме?

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

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

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вы не правы. Двумерный массив считает, можно ли набрать вес i используя первые j предметов. А не j-ый предмет.
    Далее, обычно можно сэкономить память храня и пересчитывая только одну строку этого массива, но ДП все еще остается двумерным. Также числа Фибоначчи можно считать храня лишь 2 последних числа, но на самом деле там массив на n элементов в дп.

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

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

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


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

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

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Формула: W/sin(a). Ну, или косинус, в зависимости от того, что вы за угол задаете. W - ширина прямоугольника.

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

    Формула осмысленна: если нет отражений, она очевидна. Чем вертикальнее луч, тем больше ответ.

    Формула меняется для любой отправной точки: надо лишь опять нарисовать решетку из прямоугольников. Видимо, там будет не W, а оставшаяся ширина от начала до правой стенки.
    Ответ написан
    6 комментариев
  • Как ускорить аудио под необходимый длину?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    727/x. Для 720 получается 1.0097222222...
    Но вообще, если это аудио, то можно паузы попробовать повырезать в какомнибудь audacity руками.
    Ответ написан
    Комментировать