Задать вопрос
  • Как посчитать количество разных букв в массиве строк?

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

    Второй вариант - отсортировать символы. Там уже проще подсчитать все символы - это 1 + сколько разных соседей в отсортированном массиве. Это быстрее, если использовать быструю сортировку.

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Гуглите opencv find matching image part.

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

    Еще есть алгоритмы через перцептивные хеши.

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Если в метод передаются
    left = -1, right = phrases.Count
    , то их физический смысл: left - последний элемент точно левее искомой позиции (строка там или меньше pref, или начинается с него), а right - последний элемент точно правее искомой позиции (строка там больше pref и не начинается с него).

    Это не совсем стандартный инвариант. Обычно считают, что left, это такая позиция, что ответ не может быть левее ее, а right, что ответ не может быть правее.

    Но можно и с вашим инвариантом работать. Вам надо соответсвтующим образом менять left и right, чтобы инвариант поддерживался.

    Во-первых, если left == right -2, то вы уже знаете ответ - это может быть только left+1. Эти и должно быть условие в while. Правда стоит эту позицию после цикла все-таки проверить. Вдруг все строки в массиве меньше pref.

    Далее, подсчитали вы mid, если строка там оказалась меньше pref или c него начинается, то left = mid. Ведь уже следующая позиция может оказаться искомой, а физический смысл left, напоминаю - "точно левее искомой позиции". В противном случае надо делать right = mid+1. Ведь позиция mid вполне может и быть ответом.

    Вопрос, а не зациклится ли такой алгоритм? right-left >= 3. Значит mid оказывается строго больше left. Также, поскольку у вас округление вниз, то mid < right-1, а занчит в любом случае либо left либо right сдвинутся так, что длина отрезка уменьшится. Алгоритм не циклится.
    Ответ написан
    6 комментариев
  • Как посмотреть адрес в памяти у переменной с помощью отладчика (VS)?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    В отладчике же можно целые выражения вводить. &x введите в watches.
    Ответ написан
    1 комментарий
  • PHP: как в односвязном списке удалить из середины элемент по его номеру?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Подсказка: вам надо найти не levelToCut-ый элемент, а элемент с номером levelToCut-1, ведь это у него надо перезаписать next на next->next
    Ответ написан
  • Как записать в переменную типа char строку неизвестной длины из файла?

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

    Можно, например, выделить массив с запасом - если вы знаете, что строк будет не более 100 размером не более 100 символов, то можно завести массив 100x100:
    char names[100][100].
    Читать туда можно хоть посимвольно, хоть через getline_s, хоть scanf (не забудьте только прописать в спецификаторе формата размер буфера, чтобы оно не переполнило массив).

    Второй вариант - это руками реализовывать фактически vector. Вам надо выделить память под массив какой-то длины, допустим 10. Если же вы уже прочитали 10 символов и надо что-то еще читать, то вам надо память перевыделить через realloc размера, скажем, в 2 раза больше.

    Также надо выделять и память под массив со строками char*. Если у вас 10 указателей, а файл еще не кончился и вы будете читать 11-ую строку, то перевыделите память на больше указателей.

    Ну лучше всего, конечно, использовать std::string и std::vector.
    Ответ написан
    Комментировать
  • Почему C++ код работает неправильно?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Много ошибок:
    1) number[i - 3] == 8; number[i - 2] == 8;, вопреки вашим ожиданиям, не присвоит значения в массиве значению 8. Тут выполняются 2 сравнения с 8, результат которых игнорируется.

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Можно выводить в stderr через fprintf. Тогда перенаправление в файл запишет туда только то, что выведено в stdout через printf.

    А так /a.out > file.log просто перенаправляет stdout в файл и все, что будет туда выведено, будет записано в файл самой системой. Ваша программа не знает, куда там система будет содержимое потока выводить - в консоль или в файл. Никак на это повлиять вы не сможете. Остается только писать в другой поток, например stderr.
    Ответ написан
  • Какими функциями заменить array_diff() в Си?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Руками. Если лень писать свою хеш таблицу, то можно и совсем в тупую. Итерируйтесь по списку a. Внутри итерируйтесь по списку b и, если нашли там элемент, то удаляйте из a. Иначе переходите к следующему элементу.

    Более продвинутый вариант - отсортировать список b и искать там каждый элемент из a бинарным поиском.

    Удобный трюк для удаления элементов из массива - хранить индекс первого не занятого элемента. Тогда получается что-то вроде этого:
    int empty_pos = 0;
    for (int i = 0; i < n; ++i) {
      if (!ShouldDelete(a[i], b)) {
        a[empty_pos++] = a[i];
      }
    }
    n = empty_pos;
    Ответ написан
    3 комментария
  • Как принимать ввод с потока до символа новой строки?

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

    Почему после четвертой тройки она должна остановиться?

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

    while (std::cin >> value) попытается прочесть число и вернет ссылку на cin, котрая приводится к bool и будет равна false, если произошла ошибка, т.е. прочитать еще одно число не удалось.

    Консоль ждет от пользователя ввод и единственный случай, когда cin не сможет прочесть число, это если закончится входной файл (если запустить программу и перенаправить ввод из файла) или если пользователь введет какой-то символ, который не получится перобразовать в число. Кроме ctrl-z (символ eof) можно, например, ввести символ 'a', поставить точку или еще что-то.
    Ответ написан
    2 комментария
  • Возможно ли полностью покрыть поле паркетом без пересечений?

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

    Покрасьте поле как шахматную доску. Черные и белые клетки. Каждая доминошка будет лежать на двух соседних белой и черной клетках. Постройте граф. Назначьте каждой клетке вершину, а ребра проведите между соседними клетками, если там нет перегородки. Граф - двудольный, ведь черные клетки окружены белыми, а белые - черными. Любое заполнение поля доминошками будет идентично паросочетанию в этом графе и наоборт. Найдите максимальное паросочетание: если оно не полное, то поле покрыть нельзя. Иначе ребра в паросочетании будут местами, куда надо класть доминошки.

    Вот статья с описанием алгоритма и реализацией.

    Это будет решение за O(n^2m^2).

    Другое решение, которое будет быстрее, если одно из измерений очень маленькое, а второе очень большое - динамическое программирование по профилю. Гуглите эти слова. Это сложнее реализовать, но зато будет работать за O(4^n m)

    Edit:
    Alexandroppolus в коментариях предложил использовать Алгоритм Хопкрофта — Карпа для поиска паросочетания, что для данного графа будет быстрее предложенного мной алгоритма Куна и будет работать за O(nm sqrt(nm)) вместо O(n^2 m^2)
    Ответ написан
    7 комментариев
  • Что надо изменить в коде чтобы найти количество максимальных элементов массива?

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

    Каждый пункт - это один цикл for. Все еще не понятно?
    Ответ написан
    2 комментария
  • Как программировать и не работать?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Деньги, к сожалению, платят только за работу.
    Не работать по 8 часов в день, однако, есть варианты:
    1) Работать на пол ставки. Но и зарплата будет в 2 раза ниже.
    2) Фриланс. Но тут, опять же, заработок будет пропорционален потраченному времени.
    3) Работать очень много некоторое время, запустить супер успешный гениальный проект, потом не работать, получая прибыль с бизнеса. В среднем может даже быть меньше 8 часов работы в день. Но тут должно очень повезти.
    Ответ написан
    Комментировать
  • Почему при создании динамической строки игнорируется нулевой индекс?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Там же число, которое читается через scanf("%d", &N); в первой строке.
    Ответ написан
  • Как конструктор std::ofstream преобразует std::string в char const * filename?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Никак. Смотрите на (2).
    Ответ написан
    2 комментария
  • Как расширить вычисление до 2^120?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Код в вопросе найдет такое i, что result станет равен 1, если цикл сделать до N. Для любых дельта и гамма. (но там цикл не нужен вообще).

    И наоборот. Какие бы вы дельта и гамма не взяли, может прийти такой Input, что result станет 1, только для очень большого i.

    Во-первых, вам цикл не нужен. Вычисления ваши можно упростить.
    result = (input / delta) / (i / gamma) = input * (gamma / delta) / i

    Если result = 1, то получается i = input * (gamma / delta) (естественно, умножение и деление по модулю N).
    Цикла не надо. Можно сразу вычислить искомое i.
    Решение единственно (если N простое. А если оно не простое, то делить по модулю нельзя).

    И это самое i может оказаться очень большим. Не всегда N-1, потому что у вас ограничение на Input есть дополнительное, Но даже в самом лучшем случае подбора гамма и дельта (обе по 1), вам может прийти input такой, что i будет равно 2^120.

    Ну и, во-вторых, вам не нужны две константы дельта и гамма. Тут есть ровно одна степень свободы - значение gamma / delta. Это должна быть единственная константа в вашем коде. В итоге оно все упрощается до:
    beta = 0x42
    i = beta * input % N
    result = 1


    И вообще тут, очевидно, проблема XY. У вас есть какая-то задача X, вы придумали какую-то фигню, как-то сформулировали вот эту вот задачу в вопросе (У), но вы ошиблись. Решение вот этой фигни в вопросе вам никак не поможет решить вашу изначальную задачу, пототму что вам не хватает знаний (теории групп, например, да и математики в целом). Вы задаете практически бессмысленные вопросы (уже не первый раз). Если хотите, чтобы вам тут действительно помогли - давайте вашу изначальную задачу. Я подозреваю, что это взлом криптографии и вам тут популярно объяснят, что вы зря тратите время.
    Ответ написан
  • Почему мы имеем право решать уравнения методом замены переменной?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Ну, это просто подстановка. Если, как в моем примере, предположить, что z=x^2, то из-за равенства получается и x^2=z. А дальше можно каждый x^2 переписать как z, ведь они равны.

    Или это можно еще понимать как абстрактное мышление. Вот есть у вас уравнение на x. Вы можете заметить какое-то повторяющееся выражение. Оно имеет какое-то значение. Вот это значение можно обозначить новой буквой. Вот вы же можете буквой x обозначить "сколько у вас яблок". Вы точно также можете обозначить буквой z "сколько у вас яблок в квадрате".

    Это можно делать всегда, но в результате этого могут получиться лишние корни. Как например тут, если есть решения с отрицательными z, то никакой x ему не соответствует. Надо аккуратно проверять все значения z и искать соответсвующие им x.

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

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

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

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

    Вам надо, чтобы temp был размером не меньше text.
    Ответ написан
    Комментировать
  • Как вычислить правильно в скрипте python?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Я так понял, надо подобрать константы a,b,c,d?
    Вообще, можно a, b1, c считать равными 1 и менять только d.

    Но у вас там умножение и деление по модулю. Так что все очень сложно.

    Вообще, ваша задача не имеет решения.

    Модуль у вас в вопросе порядка 10^78. А X может быть 10^119-10^120. Если x взять по модулю N, то там может получится вообще любой остаток (потому что 10^120-10^119 = 9*10^119 > N)

    А дальше, умножая эти числа на константу, если N простое (а оно должно быть простым, иначе деление по модулю не определено), то можно получить любой остаток до N. Не только до 2^60 - 2^70.
    Ответ написан