Ответы пользователя по тегу C++
  • Почему одни, незначащие скобочки, меняют ответ?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    У вас i - целое, а x - вещественное. При делении целого на целое идет деление нацело (с округлением вниз до целого). При делении целого на вещественное или вещественного на целое - результат вещественное.

    Если лишние скобки поставить, то у вас сначала происходит деление нацело (2*i+1)/(2*i), а потом домножение на вещественное.
    Без скобочек операции выполняются слева направо - a *(-1*x)*(2*i+1) даст вещественный результат, который точно поделится.

    Если вы в скобочках приведете к вещественному, то у вас тоже все заработает: a = a *(-1*x)*((2*i+1.0)/(2*i));
    Ответ написан
  • Можете пожалуйста написать на С++ произведение сумм?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вам надо перед циклами инициализировать переменные-аккамуляторы: Перед циклом по i нужно присвоить y = 1. Перед циклом по j нужно присвоить sum = 0.

    Иначе у вас в sum накапливается сумма для всех разных i. А y вообще непонятно какое значение имеет до домножения.
    Ответ написан
  • Сколько элементов массива больше своих соседей (предыдущего и следующего элементов)?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Чтобы пропустить первый и последние элементы просто измените границы цикла:
    for (int i = 1; i < 24; i++)

    Если вы хотите эти элементы считать, если они больше единственного их соседа, то воспользуйтесь ленивым вычислением логических формул (при вычислении A || B, если A == true, то B вообще вычисляться не будет):
    for (int i = 0; i < 25; i++)
      {
        if ((i +1 == n || ARR[i] > ARR[i + 1]) && 
             (i == 0 || ARR[i] > ARR[i - 1]))
          count++;
      }
    Ответ написан
  • Как складывать элементы двумерного массива с++?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вам нужен цикл по строкам. Внутри считайте сумму каждой строки и выводите.
    Чтобы найти сумму одной строки вам нужен еще один цикл: Заводите переменную, равную 0, перед цикорм. В цикле прибавляете элементы строки к ней. Потом выводите.

    Таким образом, у вас будет 2 вложенных цикла.
    Ответ написан
  • Как посчитать этот пример (суммы ряда)*(произведение ряда)+почему выводит такой результат?

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

    Вам надо считать proizr внутри цикла по k и домножать на него каждое слагаемое. (не забудьте инициализировать proizr единицей).
    Ответ написан
  • Как удалять элементы массива?

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

    std::vector<int> a = {1, 2 ,3 ,4 ,5};
    // Удалит элементы с l по r (l включительно, не удалит r).
    // Если надо удалить r-ый элемент, то добавьте +1 во второй аргумент.
    a.erase(a.begin()+l, a.begin()+r);


    Если же вы хотите делать руками, то надо просто посмотреть, куда двигаются элементы. Те, что до l - не двигаются. Те, что от l до r - исчезают. Те, что после r сдвигаются влево на r-l+1 позиций.

    for (i = l; i < n - 1 + l - r; ++i) {
      a[i] = a[i + r - l + 1];
    }
    // New length: n -1 + l - r;
    Ответ написан
  • У меня калькулятор выводит целое число почему?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    y = c / d;

    Вы делите целое число на целое. В языке С в этом случае происходит деление нацело. Чтобы в результате был float, вам надо один из операндов перобразовать во float/double. Можно или явно это написать, или просто прибавить 0.0:

    y = (c + 0.0) / d;
    Ответ написан
  • Как мне задать десятичкную дробь в моем коде?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вы используете тип int. Для дробей нужно вещественное число float или double.

    Выводить и читать его надо не через "%i", а через "%f" или "%lf".
    Ответ написан
  • Как найти значение выражения?

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

    Сначала надо проверить, что знаменатель не ноль, а только потом, что вся дробь неотрицательна.
    Для проверки, что логарифм не берется из отрицательного числа надо проверить именно это (что выражение под логарифмом >=0). Вы же почему-то проверяете, что оно равно нулю.

    И еще у вас выражение неправильно считается. Надо скобки расставить. (sqrt(X - 5 / X * X - 9) подсчитает корень из x минус 5, деленное на x^x, минус 9 - 3 слагаемых, из которых только второе дробь.

    Итого вам надо:
    - переставить местами условия, чтобы деление на 0 было первым.
    - исправить условие на логарифм из отрицательного числа
    - расставить скобки в выражении.
    Ответ написан
  • Как переделать функцию сортировки вставками по убыванию?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Поменяйте < на > там, где у вас сравниваются элементы. Подсказка: у вас массив передан двумя int указателями. Т.е. сами элементы - это там где вы разименовываете какие-то указатели (это операция *что-то).
    Ответ написан
  • Как задать приоритетную очередь с пользовательским cmp?

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

    У шаблона std::priority_queue 3 параметра - тип элемента, контейнер и компаратор.
    priority_queue хранит элементы в заданном контейнере, поддерживает там какую-то свою структуру (кучи) используя переданный компаратор для быстрой реализации операций приоритетной очереди.

    Дефолтный контейнер - vector и компаратор стандартный std::less, поэтому работает просто priority_queue, например.

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

    Однако, если вам надо поменять только компаратор (третий параметр), то передать второй параметр тоже придется. Ну, вот перепутали порядок параметров разработчики стандарта. Нельзя задать компаратор, не задав и контейнер. Поэтому, надо писать там vector<> во втором параметре.

    Edit. Там же в документации написано, что компаратор должен возвращать true, если первый элемент строго меньше второго. Ваш пример компаратора - похоже правильный. Однако, учтите, что очередь выдает сначала максимальный элемент. Т.е, если вам нужна очередь на минимум, то вам надо поменять знак в компараторе.
    Ответ написан
  • Как решить эту задачу, используя массив char'ов?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Ну... читайте по одному символу. Можно считать, допустим, начала слов. Что такое начало слова? Это символ-буква, перед которым стоит не буква. Все, что вам надо хранить - это был ли буквой предыдущий символ. Если предыдущий не был, а текущий - является, то прибавляете 1 к ответу. Еще надо аккуратно рассмотреть случай слова в самом начале (т.е. фактически прибавляете 1 если текущий - буква и позиция == 0 или предыдущий символ - не буква).
    Ответ написан
  • Как определить все способы выплаты суммы n с помощью монет достоинством в 1, 5, 10, 15, 20, 50 копеек?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Это задача о рюкзаке.

    Решение через динамическое программирование:
    int Count(vector<int> coins, int n) {
      vector<int> cnt(n+1, 0);
      cnt[0] = 1;
      for (int i = 0; i < n; ++i) {
        for (int coin : coins) {
          if (i+coin <= n) cnt[i+coin] += cnt[i];
        }
      }
      return cnt[n];
    }
    Ответ написан
  • Как найти цикл в ориентированном графе?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Один момент меня смущает: зачем вы внутри DFS не вызываете cycle когда у вас есть ребро в p? Это цикл длины 2 - вполне нормальный цикл. Или по условию задачи такие надо исключить?

    А главная ошибка - надо при выходе из dfs помечать вершину другим цветом - как обработанную (например, 2). Чтобы color == 1 только у вершин, которые в стеке. При этом в самом Dfs нужно рекурсивно вызываться только отвершин с color == 0.

    Допустим, у вас в графе есть ребро 2->1 и все. Вы вызоветесь от вершины 1 в цикле в main, ничего не найдете. Потом вызоветесь от вершины 2, найдете ребро в уже обработанную вершину и среагируете на это, как на цикл. Хотя это не цикл.
    Ответ написан
  • Нужны ли алгоритмы с графами в региональном этапе по программированию?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Да, могут быть нужны. Про то, что ограничения порядка 10^5 - это не факт. Может быть и задача, где ограничения меньше, а решение сложнее.

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

    Далее, что за дерево отрезков на графе?! А еще дейкстра может быть написан за (n+m)logn. И форд-беллман работает за nm, а не n^2.
    Ответ написан
  • Запрет на ввод букв в консоли на C++ для вещественных?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Читайте строку std::string. Проверяйте,что в ней максимум 1 '-' в самом начале, далее первая цифра не '0' (если второй не ',', есть максимум один символ ',' и он не первый. Потом используйте stringstream чтобы прочитать double.
    Ответ написан
  • Почему здесь нельзя решать через жадный алгоритм?

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

    Могу еше привести пример. В {1, 2, 3, 2, 1} - ответ 3. Тут надо удалить отрезок 1..5, потом 2..4, потом 1 вхождение элемента 3, Если же форма будет немного другая, например {1, 100, 1000, 100, 1} - то ответ 4. После первого удаления отрезка надо удалять числа по одному.

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

    Это можно доказать так:
    Рассмотрим какое-то решение (последовательность действий). Перенесем все удаления одиночных элементов в самый конец, возможно изменив количество удаляемых за раз элементов. Кроме того, объеденим несколько операций удаления одного и того же элемента в одну, просуммировав количества удаленных элементов. Все шаги-отрезки все так же можно выполнить, потому что мы только перетащили какие-то операции за них, поэтому перед шагом количество элементов могло только увеличится, а значит весь отрезок все так же не содержит нулей. Это решение имеет такое же количество шагов или меньше. Значит можно искать оптимальное решение именно такого вида.


    Многие жадности доказывается похожими рассуждениями, без применения теории матроидов: Рассмотрите ответ, как-то его поменяйте, чтобы он обладал свойствами, которые получаются вашей жадностью. если он при этом становится не хуже - вы доказали что так делать можно.

    Пока вы так не докажите свой алгоритм, можно смелло считать, что есть еще какой-то тест, где он выдаст не оптимальный ответ.

    Подсказка1: посмотрите на ограничения. n всего лишь 5000. Значит, подразумеватся решение за квадрат. Посмотрите на теги.

    Подсказка2: Можно смотреть на эту задачу так - есть башенки из кубиков высоты a[i]. Можно за раз или покрасить вертикальный отрезок башни у самого верха, или покрасить какой-то горизонтальный отрезок кубиков. Надо покрасить все кубики за наименьшее количетсво шагов. Тут только неочевидно, почему нужно красить горизонтальные отрезки, ведь несколько операций удаления отрезка могут пересекатся. Но тут поможет рассуждение как выше, через изменение любого ответа. Эти операции можно сложить как доски, в виде пирамид, т.ч. верхние операции целиком лежат в нижних операциях. От этого ответ станет не хуже.

    Еще подсказка, подумайте, как можно убрать самый высоко стоящий кубик, какие варианты?
    Ответ написан
  • Как найти в графе все циклы определённой длины?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    В общем случае, чтобы найти все циклы длины n надо подсчитать Tr(A^n)/n. A - матрица смежности. Tr() - это след (сумма элементов на диаганали). Т.е. возводите матрицу смежности из 0 и 1 в степень n и суммируете элементы по диагонали. Делить на n надо, потому что тут циклы считаются ориентированными и упорядочеными. Т.е. A->B->C посдчитается отдельно от B->C->A. Если граф неориентированный, то надо будет дополнительно поделить на 2 в конце.

    Важно, тут будут считаться циклы, ходящие по одним и тем же вершинам и ребрам. Но для n=3 это не важно, если только у вас петель в графе нет.

    Для n=3 можно чуть быстрее - возвести матрицу в квадрат и получить матрицу количеств путей длины 2. Потом можно пройтись по всем ребрам и просуммировать все циклы с этим ребром (известное уже количество путей длины 2 между двумя концами ребра). Тут как бы последнее, третье умножение пропускается и вместо него считаются только элементы на диагонали. Потом надо будет поделить на 3, потому что тут вы считаете каждый цикл 3 раза.

    Можно воспользоваться быстрым умножением матриц Штрессена или присобачить какое-нибудь битовое сжатие, как я уже советовал вам в этом вопросе.

    В зависимости от размерности матрицы (количества вершин) битовое сжатие может быть быстрее Штрассена или какого-либо другого быстрого алгоиртма умножения матриц.
    Ответ написан
  • Почему неправильно работает такая реализация алгоритма быстрой сортировки?

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

    1) не надо в конце part менять местами 0-ой и i-ый элементы. Это бессмысленно. Вы поддерживаете вариант, что элементы с 0 по i-ый <=x, c j-ого и дальше >=x

    2) У вас у part() параметр m передается по значению. Изменение его в конце функции не видно из места вызова. Вы каждый раз, независимо от того, как разбиение произошло, рекурсивно запускаетесь половин массива разделенных ровно по середине.

    3) Что у вас с рекурсивными вызовами твориться? Вы хвостовую рекурсию руками схлопнули что ли? А зачем выбирать, с какой стороны рекурсивно вызваться, а с какую дальше в цикле обрабатывать? Там у вас что-то с вычислениями напутанно, всякие +-1 неверно распиханы. Вы там делаете k -= left+1 и k -= right+1. По логике в одной половине left элементов, в другой - right. Тогда почему вы -1 еще делаете и там и там?
    Ответ написан
  • Где у меня может быть ошибка в нахождении площади сложной фигуры?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Не совсем понятен ваш код слияния двух массивов отрезков. Я бы все промежуточные точки тупо загнал в один вектор и отсортировал. Ну или сделал стандартное слияние двух отсортированных массивов. Дальше в цикле считал бы на отрезке между двумя соседними точками (если длина отрезка хотя бы 1e-6), Параметры кривых ищутся легко - держите 2 счетчика, как у вас уже есть, и двигайте их, пока текущий отрезок для той или иной функции не станет закрываться позже начала текущего отрезка. Может ваш код и эквивалентен этому, но я в этом не уверен.

    Попробуйте взять какой-то тест и разбить имеющиеся куски на несколько так, чтобы у двух функций точки были совсем разные, и чтобы они чередовались нерегулярно (не первая, вторая, первая, вторая...). Побробуйте, чтобы точки у второй кривой были последними и наоборот.

    Еще, очевидная проблема вот: comp_a != 0. Флоаты нельзя никогда сравнивать точно. Только с епсилон:
    x < y  ====> x < y - eps
    x <= y ====> x < y + eps 
    x == y ====> fabs(x-y) < eps
    x != y ====> fabs(x-y) > eps
    Ответ написан