Задать вопрос
  • Как цикл for может считать ввод?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    У вас цикл на 10 итераций (for (int count=0; count < 10; ++count)). С возможным ранним выходом (break).
    Ответ написан
    Комментировать
  • Известен ли эффективный алгоритм поиска всех элементарных циклов в неориентированном графе?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Что вы подразумеваете под словом "эффективный"?

    Проблема в том, что циклов в графе из n вершин может быть O(n!) (n-факториал): представьте клику - граф, где есть ребра между всеми парами вершин. Любое подмножество вершин, да еще и в любом порядке, задает элементарный цикл.

    Обычно под словом "эффективный" подразумевают полиномиальный алгоритм. Такой алгоритм тут, очевидно, не существует (потому что надо перебрать экспоненциальное количество объектов).

    Используйте обход в глубину без запоминания обойденных вершин. Такой полный перебор гарантированно найдет все циклы. Можно его ускорить, если предварительно разбить граф на двусвязные компоненты мостами и искать циклы внутри каждой компоненты отдельно.
    Ответ написан
    9 комментариев
  • Для чего объявляется вложенная структура (или класс) перед тем, как она объявляется дружественной?

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

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

    Но откуда тут вообще может быть непонимание? В C++ никогда нельзя менять, на что ссылаются ссылки. const/не const может быть только то, на что оно ссылается.

    Edit: изначально я тут некорректно назвал это константной ссылкой, но по хорошему, оно называется ссылка на константу.
    Ответ написан
    4 комментария
  • Можно ли выразить алгоритм в виде математической формулы?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Используйте функцию max.

    Значение в каждой ячейке будет
    max(0, (тукущее значение) - max(0, (платеж) - (сумма всех следующих ячеек)))


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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вы сами ответили на свой вопрос - "Обычные однобайтовые символы". Какая разница, в каком порядке этот один байт записывать?
    Ответ написан
    Комментировать
  • Как сравнить два списка ArrayList?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Есть. Складывайте элементы array в HashMap (храните там количетсво каждого элемента).

    Потом пройдитесь по list и, если в HashMap текущий элемент есть с ненулевым счетчиком, выводите другим цветом и уменьшайте счетчик.

    Как выводить в цвете - зависит от языка и платформы. Можно хоть символами "*" ***выделять*** при выводе.
    Ответ написан
    Комментировать
  • Сколько существует инъективных отображений Z7-Z4?

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

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

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

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

    Никакого переполнения быть не может, bigInteger вам не нужен. Даже long не нужен: максимальная длина пути - 10000.
    Ответ написан
    7 комментариев
  • Есть ли ошибки в реализации fft?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Зачем buffer[i] *= 1;?

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

    Если же делать с нечетными n, то эти стандартные формулы не работают.

    Еще возможно по коду разбросаны всякие off by one error и перепутанные знаки (почему в w() аргумент у синуса/косинуса берется со знаком минус?)

    Еще недочет - вы 2 раза вызываете w(), когда как можно было бы и запомнить результат первого вызова.

    И еще, обычно рекурсию разворачивают в циклы. В английской вики приведен псевдокод.
    Ответ написан
    Комментировать
  • Почему в C++ не удаётся чтение при помощи fstream объекта, записанного в файл при помощи того же fstream?

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

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

    Или файл не открывается, потому что его нет, или у вас компилируется через C++98.
    В документации написанно (примечание после параметров):
    If the mode has both trunc and app set, the opening operation fails. It also fails if either is set but out is not, or if both app and in are set.


    Вы же, судя по комментариям, открываете с app и in вместе.

    Вам точно надо читать и писать из этого файла да еще и увеличивать его размер?
    Ответ написан
  • Почему возникает ошибка "cannot be implicitly captured because no default capture mode has been specified" при передачи в функцию?

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

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

    F(i,k) - максимальная сумма, которую можно получить из первых i троек, такая что ее остаток от деления на 4 равен k.

    База: F(0,0) = 0, F(0,k) = -infinity.
    Ответ: F(n, 0).

    Пересчет
    F(i,k) = max(F(i-1, ((k-a[i][0]-a[i][1])%4+4)%4)+a[i][0]+a[i][1], 
                 F(i-1, ((k-a[i][1]-a[i][2])%4+4)%4)+a[i][1]+a[i][2], 
                 F(i-1, ((k-a[i][0]-a[i][2])%4+4)%4)+a[i][0]+a[i][2])


    Только лучше вместо -infinity как-то отмечать, что позиция (i,k) недопустима (нельзя первыми i тройками набрать сумму с остатком k. И недопустимые варианты при выборе максимума выбирать ненадо.

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

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Сравнивайте дальше третии символы в строках, если первые совпадают.
    Или сравнивайте строки через strcmp.
    Ответ написан
  • Как удалить объект объявленный в функции?

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

    На самом деле, вам тут не нужна динамическая память. Сам класс Vector не жрет много памяти. Поэтому mulVec может возвращать просто Vector, а не указатель на него. Cам Matrix4x4 тоже не жрет память, поэтому не надо заводить и на него указатели. Вся память у него внутри в указателе data (кстати, вы же в деструкторе ~Matrix4x4 эту data удаляете же?).

    Если же там еще что-то и Vector большой, то возвращайте unique_ptr или shared_ptr на него. Тогда все само удалится, когда надо.

    И еще, в вашем текущем коде вы в main выделяете test, а потом перезаписываете. Тут у вас происходит утечка памяти. Его надо было delete-нуть перед перезаписью, это же указатель. Это хороший пример, почему вот так использовать сырые указатели где не надо - это плохо. Легко ошибиться: надо всегда помнить, кто ответственен за удалиение указателя.
    Ответ написан
    Комментировать
  • Как реализовать реакцию на комбинации клавиш?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    if (S && D) {
      functino3();
    } else if (S) {
      function1();
    } else if (D) {
      function2();
    }
    Ответ написан
    Комментировать
  • Как нормально сделать перемещение по диагонали (sfml)?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Считайте вектор скорости и потом делите на его длину. В зависимости от зажатых кнопок прибавляйте или вычитайте speed из vx или vy (которые изначально 0). Потом, после проверок, делите оба числа на sqrt(vx*vx+vy*vy) (если оно не 0) и сдвигайте спрайт на vx, vy.

    Можно соптимизировать - прибавляйте 1/-1 вместо speed. Тогда значение vx*vx+vy*vy может быть только 0,1 или 2. Заведите константный массив kScaleCoef[3] = {1, 1, sqrt(2)} и потом делайте
    Sprite.Move(speed/kScaleCoef[vx*vx+vy*vy]*vx, speed/kScaleCoef[vx*vx+vy*vy]*vy);
    Ответ написан
    Комментировать
  • Как передать одномерный массив из одной функции в другую?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Если это, таки, С++, то используйте std::vector. Одна функция его создает и возвращает, другая печатает.
    Чтобы не было лишнего копирования передавайте как константную ссылку:
    std::vector<int> MakeArray();
    void Print(const std::vector<int> array);


    Если надо работать с сишными массивами, то тогда придется длину возвращать отдельно через выходной параметр. Передавайте как указатель + длина.
    int* MakeArray(int *len);
    void Print(int *array, int len);
    Ответ написан