Задать вопрос
  • Как в js равномерно распределить комбинации пунктов в массиве, который был создан с помощью рекурсивного размещения?

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

    Допустим количество работ (N) и количество людей (M) взаимно просты.

    Тогда сгенерируйте M строчек беря людей подряд:
    1, 2, 3
    4, 5, 1
    2, 3, 4
    5, 1, 2
    3, 4, 5

    Тут каждый человек одинаковое количество раз (по одному разу) будет на каждой работе. И дни, когда он будет работать будут максимально равномерно распределены (минимальное расстояние и максимальное между соседними работами будут различаться максимум на 1 и равны floor(N/M) и ceil(N/M)). Это идеальное с точки зрения равенства расписание. Но у него минус - частоты пар работников будут не одинаковыми. 1 гораздо чаще будет работать с 2 и 5, чем с 3 и 4.

    Теперь, если N и M не взяимно просты. Пусть D = GCD(N,M) - наибольший общий делитель.

    Разбейте всех людей на D групп по N'=N/D человек. N' и M взяимно просты, поэтому можно применить алгоритм выше к каждой группе.

    Дальше эти D расписаний надо перемешать. Для максимальной равномерности - сначала взять все первые строки всех расписаний, потом все вторые, и т.д.

    На i-ом месте будет день i / N' из расписания i % N' (если индексация с 0).

    Так, например, решение для 2 работ и 6 людей:

    N' = 3. 2 группы.
    В первой:
    1 2
    3 1
    2 3

    Во второй:
    4 5
    6 4
    5 6

    В итоге:
    1 2
    4 5
    3 1
    6 4
    2 3
    5 6
    Ответ написан
    Комментировать
  • Как получить вывод с pidof в работующую программу?

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

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

    Можно запоминать предыдущие поля. Хотя бы в виде хешей для экономия памяти. Чтобы из-за коллизии не заврешаться раньше времени, можно считать несколько принципиально разных хешей (допустим, sha256 и какой-то полиномиальный хеш), и плюс брать "слепок" от поля (какие-то 256 разбросанных по полю клеток).

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это называется "задача упаковки" (packing problem). В простейшем случае - прямоугольников в прямоугольник. Нашласть статья на хабре и какая-то научная статья. Дальше вам придется гуглить самостоятельно.

    Вообще, это NP-полная задача, поэтому для решения скорее всего придется использоваать метод ветвей и границ или какие-то переборы с отсечениями. Если коробки занимают почти все место в машине и решение есть, но оно редкое, то найти его за разумное время вы сможете, скорее всего, лишь для относительно небольшого количества коробок (штук 40-50).

    А разрешение класть на бок вообще усложняет задачу кардинально. Это вам придется еще для каждой коробки перебирать, а каким боком ее класть на пол.

    А если их еще друг на друга класть можно, то перебор еще сложнее становится и вы решить задачу сможете уже лишь для 10-20 коробок. Иначе вам понадобится супер компьютер и нелеля вычислений.

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Зачем вам самый длинный путь? Вообще, эта задача очень сложная. Кратчайший путь можно найти обходом в щирину или глубину, быстро и просто. Самый длинный - только полным перебором. Возможно, его можно как-то соптимизировать используя особенности вашей конкретной задачи (вроде заполнения прямоугольника змейкой и конструтирование маршрута из таких шаблонов), но это тоже очень сложно.
    Ответ написан
    4 комментария
  • Вывод в файл c++?

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    У вас каждый раз выполняется MoveToEx() в начало координат. Надо вам куда-то сохранить координаты последней точки и делать MoveToEx туда, потом LineTo в новые координаты и запомнить их.
    Ответ написан
    4 комментария
  • Какой длины массив чисел можно "упаковать" по 3 элемента 25 комбинациями?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Пусть делящихся на 2 - x, а делящехся на 3 - y.

    Тогда количество способов "выбрать три числа так, чтобы
    среди них было как минимум одно четное число и хотя бы одно число, делящееся на 3" - x(x-1)y/2+x*y*(y-1)/2. Или мы берем 2 четных числа и одно, делящееся на 3. или наоборот.

    Теперь надо подобрать такие x и у, чтобы вот эта формула сверху дала 25. Ответом будет x+y.

    Можно или перебрать мелкие значения x и y и посмотреть, что 2 и 5 подойдут, или вывести это логически. Формулу можно факторизовать до x*y*(x+y-2)/2. Приравняем к 25 и домножим на 2: x*y*(x+y-2) = 5*5*2. Справа произведение трех простых чисел. Слева три неизвестных целых множителя. Значит надо лишь перебрать способы распихать эти три простых числа по трем множителям. x и у не могут быть 1 вместе, ибо 1*1*0 != 50. Если x=1, а y!=1, То надо там тоже видно, что решения для y нет. x+y-2 тоже не может быть 1, ведь кто-то из x и y будет точно хотя бы 5. Ну и остается тольковариант x=5, y=2, (x+y-2) = 5.

    Итого, ответ - 7.
    Ответ написан
    Комментировать
  • Как работает этот рекурсивный алгоритм разложения на слагаемые?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Функция генерирует все разбиения числа n на слагаемые не больше maxx. Ддя этого ыункуия перебирает, а какое же максимальное число будет в разбиении (цикл по i), берет это число и рекурсивно разбивает оставшуюся часть. Обратите внимание, в качестве maxx в рекурсии передается i. Ведь именно это было максимальное число в перебираемом разбиении. Значит следующее не может его превышать.

    Вся эта сложность с максимальным числом сделана, что бы не перебирать перестановки слагаемых. Ведь 4=1+2+1 можно по идее получить тремя способами, меняя порядок. Генерируя слагаемые в не возрастающем прядке, мы избавляемся от таких дубликатов.
    Ответ написан
    Комментировать
  • Как оптимально организовать структуру памяти, Кучу? Как она реализована в виртуальных машинах?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Там не происходиит копирование данных. Просто среда выаолнения запоминает, что переменная a лежит вон там внутри "массива" кучи. При чтении оттуда данных все происходит за одну асскмблерную операцию, как если бы вы читали из int.

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Внимательно читайте свой код:
    std::ofstream out("/home/artem/Рабочий стол/EntryFile/NewFile");
    std::ifstream  in("/home/artem/Рабочий стол/EntryFilee/NewFile");


    Я пробелы расставил, чтобы строки выравнились. Найдите одно отличие.
    Ответ написан
    Комментировать
  • Почему не могу парсить именно этот сайт?

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

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Сначала перемешайте слова. Возьмите массив длины NUM_WORDS чисел и заполните его изначально индексами от 0 до NUM_WORDS-1. Перемешайте. Потом сделайте цикл по словам, который будет загадывать слово с индексом вот из этого массива. Внутри while(true) будет спрашивать пользователя, пока он не угадает. Т.е. вот этот ваш код весь выносится в отдельную функцию и вместо случайной генерации choice, получает его в качестве параметра. Можно через возвращаемое значение сообщать о том, что пользователь попросил выйти.

    И еще, чтобы перемешать случайно слово/массив индексов надо делать вот так (а не так, как у вас):
    for(int i = 0; i < length; ++i) //меняет буквы местами
        {
            int prev = (rand() % (i+1));
            char temp = jumble[prev];
            jumble[prev] = jumble[i];
            jumble[i] = temp;
        }


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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Различия обусловнены тем, что строки - особый вид массивов. Весьма частый и использующийся повсеместно. Плюс, в отличии от обычных массивов, в строках есть нулевой завершающий байт. Поэтому некоторые вещи стандартом Си были добавлены в язык отдельно для строк. Как, например, инициализацию const char* строковым литералом, или инициализацию массива с рассчетом его размера (учитывая нулевой символ в конце). Оно же потом перекочевало в Си++.
    Ответ написан
    Комментировать
  • Как передать двумерный массив функции?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если ваш двумерный массив сделан как указатель-на-массив-указателей-на-строки - то да. Если же вы завели массив вроде int a[100][200]; - то нет.
    Ответ написан
    Комментировать
  • Какой можно применить алгоритм для хранение индекса для 50 миллиардов записей в golang?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    vgray, Удаляются ли записи?

    Так-то, поиск на полное совпадение по строке не самое сложное. Какое-нибудь B-Tree или Trie - отлично подойдут тут. Проблема только в том, что оно в память не влезает, поэтому придется повозиться с хранением этого всего кусками в файлах. B-Tree как раз для этого и сделано, но оно будет медленнее работать со строками. Аккуратно порезанный на куски Trie будет быстрее.
    Ответ написан
    Комментировать
  • Как реализовать опциональные колбэки?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Тут похоже ошибка в архитектуре. Логичнее было бы сделать чтобы Lane::Place(Unit *) вызывало какие-то методы у Unit, если это надо для конкретной реализации Lane (Эта логика будет в виртуальном методе, переопределенном в конкретных реализациях интерфейса).

    Или Unit::OnPlaced(Lane*) всегда вызвает какие-то методы у Lane и вот они могут сказать, что Unit-у не надо ничего делать.

    Ну, или раз вам вот так хочется сделать, то пишите шаблонный метод Unit::OnPlaced(T*), И ручками прописывайне инстанциировки с кокретными SkyLane, GroundLane и т.д. Ну и "дефолтную" реализацию пропишите пустую - вообще ничего не делающую для типа T*
    Ответ написан
    Комментировать
  • Возможно ли изменять windows 10 с помощью c++?

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

    C++, наверно, не самый удобный для этого язык, хотя бы из-за его скудности работы со строчками и возможностей выстрелить себе в ногу.

    Вам тут в первую очередь надо изучать не C++, а настройки windows и документацию о нем же.
    Ответ написан
    Комментировать
  • Чем отличаются структуры данных от колекции?

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

    Но не любая структура данных - коллекция. Например, граф, хранимый в виде списков смежности - не является коллецией. Еще примеры: cуффиксное дерево, дерево отрезков - тоже не являются коллекциями.
    Ответ написан