• Не понимаю в чём ошибка, можете помочь?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    У вас $rank равен 8, когда как допустимые значения 0..7. И вы обращаетесь по недопустимуому индексу в массиве, в котором 8 элементов.
    Ответ написан
    Комментировать
  • Как найти максимум среди всех локальных минимумов заданной матрицы?

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

    Фактически, тут 2 вложенные задачи: 1) Проверить, является ли значение локальным минимумом 2) Найти максимум в матрице (возможно игнорируя какие-то клетки).

    Советую решить задачи раздельно с помощью функций.

    Для первой задачи напишите функцию.

    bool IsLocalMinumum(int a[][m], int n, int m, int i, int j);


    Функция должна перебрать 4 варианта (прибавить/вычесть 1 из первого или второго индекса) и для каждого проверить: 1) сосед есть, т.е. не вышел за границу, 2) значение соседа меньше текущего. Если оба условия выполнились для какого-то направления - вы нашли "плохого" соседа. Текущая клетка не может быть минимумом. Сразу же возвращайте false. В конце функции всегда возвращайте true.

    Вторая задача - тривиальна совсем. Можете выбрать максимум из просто одномерного массива? Теперь вместо одного цикла по массиву делайте 2 вложенных по матрице. Потом допишите туда условие, вызывающее вашу IsLocalMinimum. Если вершине не минимум - просто делайте пропускайте клетку. Буквально if (!IsLocalMinimum(a, n, m, i, j)) continue;
    Ответ написан
    Комментировать
  • Как найти кратчайший путь с минимальным количеством поворотов(повороты в приоритете)?

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

    Во-первых, все расстояния в графе будут не одно число, а пара - собственно, длина пути и количество поворотов. При суммировании двух длин складывайте их покомпонентно, при сравнении сравнивайте сначала длины, а потом количество поворотов. Теоретически, можно схлопнуть все назад в одно число, если считать 100000*<длина> + <количество поворотов>. Но могут быть спецэффекты, если пути очень сложные и имеюют более 100000 поворотов. Еще, опасайтесь переполнения.

    Для каждой клетки сделайте 4 вершины, которые будут означать, что вы находитесь в этой клетке и "смотрите" в одну из 4-х сторон.

    Создайте 4 ребера между соседними направлениями с длиной {0, 1} (длина 0, но 1 поворот). От каждой вершины создайте также ребро длинной {1, 0} (длина - 1, 0 поворотов) в вершину в соседней клетке с тем же направлением (от "верхней" из 4-х вершин сделайте ребро в "верхнюю" же вершину в клетке сверху. Аналогично по трем остальным направлениям).

    Теперь кратчайший путь в этом графе будет то - что вам надо. Есть еще вопрос с начальными конечным направлением. Можно добавить в начальную и конечную клетки "центральную" вершину, в которая связанна ребрами длины {0, 1} (Важно сделать 1 поворот, иначе можно будет крутиться на месте через эту центральную вершину). Считайте, что эта вершина - "смотреть в пол". Вы начинаете в какой-то клетке, смотря в пол, и вам надо оказаться в другой клетке, опять же смотря в пол. Вы можете в клетке повернуться, или перейти в клетку впереди вас.

    Поскольку тут уже разные длины ребер, обход в ширину уже не будет искать кратчайшее расстояние. Но можно использовать дейкстру/A*.

    При реализации не надо даже хранить все вершины и ребра. Просто у вас теперь вершина вместо {x, y} будет описываться {x, y, d}. Вместо перебора 4-х направлений [-1,0],[0,-1],[0,1],[1,0] - вы делаете переход {x+dx[d],y+dy[d],d} или меняете d на (d+1)%d и (d+3)%4. И в очередях вы сохраняете не одно число, а пару {length, turns}. Для A* нужно еще прикидывать оставшуюся длину - ну вы по длине берите, что у вас уже есть, а по количеству поворотов берите 1, если у начала и конца разные направления.

    Играясь с длинами ребер и их сравнениями вы можете, например, разрешать чуть более длинные пути, если в них сильно меньше поворотов. (например, можно обойти лабиринт по периметру, чем чуть короче но зиг-загами ходить внутри). Для этого длина ребра может быть length*K+turns.

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Я правильно понимаю, что пользователь вводит от 1 до 3 чисел в строке и ожидает, что программа эти числа обработает и выведет результат? Иными, словами, программа реагирует на клавишу enter?

    Можно читать символы по одному через getch(), пока не прочитаете '\n'. По пути нужно парсить числа. Если символ цифра - то умножйте текущее число на 10 и прибавляйте цифру (помните, что (int)'0' != 0. Но символы цифры, слава богу, идут подряд в алфавите). Если прочитали пробел - переходите к следующему числу. Или, чтобы обрабатывать всякие много пробелов, лишние символы и другие проблемы ввода - лучше прочитать сразу же всю строку через fgets() и потом в ней уже парсить числа.
    Ответ написан
  • Как мне задать десятичкную дробь в моем коде?

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

    Выводить и читать его надо не через "%i", а через "%f" или "%lf".
    Ответ написан
  • Как создать программу перевода из 8-ричной СС в 10-ричную?

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

    Это один цикл, с последней цифры до первой: Прибавляйте к ответу текущую цифру, умноженную на текущую степень и потом домножайте текущую степень на 8.
    Ответ написан
    Комментировать
  • Как сохранить графическое изображение, нарисованное в Pascal ABC с помощью модуля GraphABC?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Похоже, можно воспользоваться методом Create(r: System.Drawing.Rectangle) - судя по описанию - это то, что вам нужно, но я не уверен. Picture же можно сохранять методом Save.

    Если не работает, то можно воспользоваться этим примером. Создайте Picture и рисуйте туда параллельно с рисованием на экран.
    Ответ написан
    Комментировать
  • Как исправить ошибку invalid controlling predicate?

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

    Вам надо сделать так:
    const int num_iterations=1000000;
    const double h = (b-a)/num_iterations/2.0
    x = a;
    #pragma  omp  parallel  for  reduction (+:S)
    for (int i = 0; i < maxi; i++)
    {
        S = S + 1*(x/(x+1));
        x = x + h;
        S = S + 4*(x/(x+1));
        x = x + h;
        S = S + 1*(x/(x+1));
    }


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

    Я добавил reduction (+:S) в инструкцию openMP, потому что вам надо подсчитать общую сумму же. Без этого каждый поток что-то насуммирует отдельно. Шарить S между потоками сложно - может быть data race.
    Ответ написан
    Комментировать
  • Где и для чего используют кучу (heap)?

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

    Детали:
    - Операция поиска минимума работает за константу, а не за логарифм. Но это мелочь, потому что чаще всего после поиска происходит удаление минимума, или добавление нового элемента, которые работают за логарифм.
    - Эта структура данных сильно проще сбалансированного дерева поиска и поэтому работает быстрее. Тупо на поддержку структуры надо тратить меньше сил. Проще поменять местами 2 элемента массива, чем крутить красно-черное дерево.
    - Куча требует меньше памяти. Тут нужны только сами элементы в массиве. Всякие деревья поиска требуют указателей на детей, какие-то дополнительные данные, вроде цвета вершины.
    - Куча всегда идеально сбалансирована. Деревья поиска же обычно могут быть раза в 2 выше, чем идеальный логарифм.
    - Кучу можно поддерживать в массиве. Это сильно дружественнее к кэшу процессора, чем разбросанные вершины дерева с указателями друг на друга. Поэтому куча, мало того, что выполняет меньше операций, эти операции сами происходят быстрее.
    Ответ написан
    4 комментария
  • Можно ли как-то оптимизировать/ускорить этот код?

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

    Как-то сильно ускорить мне не удалось, но можно брать каждую точку одного полигона, строить 2 касательные на другой полигон и оставлять только те, которые одновременно являются касательными к первому полигону.
    Это проверяется через векторные произведения веторов-сторон и вектора отрезка между полигонами. Отрезок между полигонами должен быть между двумя векторами сторон (если они ориентированны в одну сторону, скажем, против часовой стрелки). Это должно уже в почти в 4 раза уменьшить количество отрезков у вас.

    Еще, возможно, тут проблема не в касательных. Вот у вас 20 полигонов, в каждом по 8 точек - это 160 точек начал. Для нахождения касательных к полигону можно перебрать все вершины. Это еще раз по 20*8=160. Итого, получается 160^2=25600 операций. Операции сложные (найти 3 вектора, взять векторные произведения), да. Но жаже если умножить это на 50, получается 1,280,000 элементарных операций. Современные процессоры выполняют миллиарды таких операций в секунду. Т.е по этой грубой прикидке - построение всех касательных занимает считанные миллисекунды.

    У вас очень тормозит проверка на пересечения возможных кандидатов с полигонами.
    Во-первых, как только вы нашли пересечение - можно дальше не проверять. Разделите циклы по intersect_any_1 и intersect_any_2 и останавливайтесь, как только нашли пересечение. Во-вторых, вы для каждой касательной заново строите объекты turf.js. Это, возможно, очень медленно.

    Ну и, похоже turf.js слишком тормозной. Моя демка на C++ для 100 полигонов находит все хорошие касательные без пересечений за 30мс. А если отсекать полигоны по bounding box, то 16-20мс. Ну в 10 раз javascript медленнее. У вас явно что-то совсем не то делается где-то.
    Ответ написан
    1 комментарий
  • Как правильно создать массив строк?

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

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Если рекурсия валится, то делайте не обход в глубину, а обход в ширину (с очередью).
    Ответ написан
  • Есть ли способ решить в целых числах уравнение вида ax+by+cz = d?

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

    Решайте итеративно, добавляя новые переменные. Вот вы получили первые k переменных так что их сумма с коэффициентами равна GCD() коэффициентов. Пусть этот gcd(a1,a2,... ak) = d. Теперь решите тем же алгоритмом уравнение d*x + a(k+1)y = gcd(d,a(k+1)). y будет искомым значением последней переменной, а все предыдущие значения надо домножить на значение x.

    В конце вы нашли GCD всех коэффициентов и вы можете проверить, что правая часть на него делится. если нет - решения нет. Если делится, то надо на результат деления домножить все переменные.

    Да, тут еще спецэффект есть, что с отрицательными числами не работает GCD. Надо поменять знаки у коэффициентов, запомнить это и в конце поменять знаки у переменных назад.

    Решение за O(n log M), где n - количество переменных, M - максимальное значение коэффициентов.
    Ответ написан
    Комментировать
  • Как найти значение выражения?

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

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

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

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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Как вам уже сказали, вы не выделяете массив нужного размера. Можно вместо int a[1][1] делать int a[100][100], например, если вам известно, что массив не будет больше 100 строк и столбцов. Но, по хорошему, это надо обработать и, если пользователь ввел row == 101, то надо завершиться, сообщив пользователю о слишком большой размерности.
    Ответ написан
    Комментировать
  • Как перебрать из массива до тех пор, пока совпадают даты?

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

    Ваше условие не очень понятно, но вот, как сгрупировать массив по датам:
    st = 0; 
    end = 0;
    while (st < a.length) {
      end = st + 1;
      while(end < a.length && a[end].date == a[end-1].date) end++;
      console.log(a[st].date);
      for (st = st; st < end; st++) {
        console.log(a[st].id);
      }
    }


    Тут мы просто откусываем от массива кусок с одинаковыми датами, пока массив не кончится. Если вам нужна только последняя группа, то можно откусить только один раз с конца:
    end = a.length - 1;
    st = end - 1;
    while (st >= 0 && a[st].date == a[st+1].date) st--;
    console.log(a[end].date);
    for (st = st+1; st <= end; ++st) 
      console.log(a[st].id);


    Только учтите, этот код не работает на пустом массиве. Надо отдельно проверить этот случай.
    Ответ написан
    2 комментария
  • Как исправить странные ошибки Си-кода?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Куча не иницализированных локальных переменных. Эти переменные не обнуляются в языке Си. Там какой-то мусор. Может быть и 0, но это как повезет.
    number - вы там присваиваете rotor[number] что-то, а чему оно равно? i в цикле, как Rsa97 сказал.

    И вообще, вы с алгоритмом перемудрили. Вы случайно генерируете число, пока не найдете новое число в массиве.
    Есть более элегантное решение:
    Заполните массив числами от 0 до 74 подряд. Потом перемешайте его, как написанно в вики. Или можно совместить изначальное заполнение и перемешивание. Буквально, вся функция filling становится:
    void filling(int rotor[], int randvalue)
    {
      srand(randvalue);
      for(int i = 0; i < 75; ++i) {
        int j  = rand() % (i+1);
        rotor[i] = rotor[j];
        rotor[j] = i;
      }
    }
    Ответ написан
    Комментировать
  • Найти третью точку правильного треугольника?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Логика у вас правильная - взять середину отрезка AB и отложить от него перпендикуляр длинной sqrt(3)/2*d.

    Но не надо искать углы, вектор перпендикуляр находится тривиально - это {y2-y1, x1-x2} (Можно доказать перпендикулярность через скалярное произведение, например). Более того, длина этого вектора будет уже d (это ведь повернутый на 90 градусов вектор по стороне треугольника). Значит его остается тупо домножить на sqrt(3)/2.

    Таким образом формула x3 = (x1+x2)/2 +sqrt(3)/2*(y2-y1).
    Ответ написан
    Комментировать
  • Где точка M(x,y) принадлежит заштрихованной области?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    x лежит от -2 до 2. y лежит от -4 до кривой f(x). У вас там похоже парабола f(x)=-x^2.
    Ответ написан
    Комментировать
  • Как сделать поличество пропусков при замене равными длине слова или же сделать пересчёт чтоб не рушились замены?

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