Задать вопрос
Ответы пользователя по тегу Алгоритмы
  • Определить, что точка внутри фигуры или нет?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Проведите из точки луч в любую сторону. Если он пересекает контур нечётное число раз, то точка в контуре, если чётное (или ноль), то вне контура.
    Если луч попадает в вершину, то надо определить, как расположены примыкающие к этой вершине отрезки контура относительно луча. Если отрезки находятся с разных сторон от луча, то засчитывается одно пересечение, если с одной - то ни одного.
    Если один из отрезков контура совпадает с лучом, то надо смотреть как располагаются относительно луча соседние отрезки.

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

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Вероятности так не складываются. Как влияет одно событие на другое - в данном случае определяется правилами игры. Представьте, что игра идёт до миллиона очков. Как одно очко, заработанное Мишей повлияет на общий счёт игры? А если игра заканчивается с первым набранным очком?
    Что касается общей формулы - то вероятность победы команды
    Pпобеды = 0.36×P(победы|Миша заработал очко) + (1 - 0.36) × P(победы|Миша не заработал очко)
    Ответ написан
    4 комментария
  • Подсчет количества автомобилей для перевозки n пассажиров?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Если нет других ограничений, то [(n-1)/30]+1 30-местных автомобилей.
    Ответ написан
    6 комментариев
  • Как слить два отсортированных массива в один?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Надо начинать процедуру слияния с конца заполненной части первого массива и, соответственно, с начала второго. Результат заносить в конец первого массива.
    Заводите индексы для движения по каждому из исходных массивов и для вставки результата. Затем сравниваете числа по индексам в исходных массивах, записываете в результат меньшее из них, сдвигаете индексы результата и записанного числа. Не забывайте проверять индексы на выход за пределы массива.
    Спойлер. Лучше решить самостоятельно.
    int n1 = 5, n2 = 5;
    int a1[10] = {1, 4, 9, 12, 54};
    int a2[] = {99, 17, 9, 8, 4};
    int i1 = 0, i2 = n2-1, i = n1+n2-1;
    while (i >= 0) {
      if (i1 > n1-1) {
        a1[i--] = a2[i2--];
      } else if (i2 < 0) {
        i = -1;
      } else if (a1[i1] < a2[i2]) {
        a1[i--] = a1[i1++];
      } else {
        a1[i--] = a2[i2--];
      }
    }
    Ответ написан
    Комментировать
  • Как сделать подобные слагаемые коэффициентов многочлена с одинаковыми степенями?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Самый простой способ - представить полином как массив [0..n], где значение элемента массива - это коэффициент при соответствующей степени.
    Ответ написан
  • Как подсчитать количество людей в помещении?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Ответ написан
    Комментировать
  • Как узнать какие товары входят в ценник, если известна итоговая сумма?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Простейшая рекурсия.
    function makeBasket($sum, $prices, $result) {
        if ($sum % $prices[0] == 0) {
            return array_merge($result, [$sum / $prices[0]]);
        }
        if (count($prices) == 1) {
            return false;
        }
        for ($i = 0; $i <= $sum / $prices[0]; $i++) {
            $res = makeBasket($sum - $prices[0] * $i, array_slice($prices, 1), array_merge($result, [$i]));
            if ($res != false) {
                return $res;
            }
        }
        return false;
    }
    
    $prices = array_values($accessories[$article]);
    $res = makeBasket($accessoriesSum, $prices, []);
    $result = [];
    $i = 0;
    foreach ($accessories[$article] as $key => $val) {
        if (($i < count($res)) && ($res[$i] != 0)) {
            $result[$key] = $res[$i];
        }
        $i++;
    }
    print_r($result);

    Возвращает первый найденный результат.
    sandbox.onlinephpfunctions.com/code/f9d233c85ed30b...
    Ответ написан
    4 комментария
  • Как найти ошибку в генерации поколения в "game of life"?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    У вас неверно описано основное условие игры. Оно звучит так:
    - в пустой (мёртвой) клетке, рядом с которой ровно три живые клетки, зарождается жизнь;
    - если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае, если соседей меньше двух или больше трёх, клетка умирает («от одиночества» или «от перенаселённости»)

    При формализации получаем:
    - Два соседа: новое состояние = старое состояние
    - Три соседа: новое состояние = живая
    - Иначе: новое состояние = мёртвая
    У вас же при двух соседях клетка всегда становится живой.

    Ну и можно слегка упростить алгоритм, если использовать не bool, а char и обозначать живую клетку как 1, мёртвую как 0. Тогда количество соседей можно посчитать просто суммируя значения, без тернарных операторов.
    Ответ написан
    2 комментария
  • Как оптимизировать сумму ряда?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Аналитически.
    59fe144ebe173368222815.gif
    Я нашёл этому поистине чудесное доказательство, но поле ввода слишком узко для него. (C) Ферма.
    Решение
    Рассмотрим дроби - слагаемые данной суммы. Очевидно, что знаменатели могут меняться от 2 до 2k.
    Попробуем определить, какие числители будут в дробях со знаменателем n. Для этого нам надо разложить n на пары x и y всеми возможными способами, учитывая ограничения 1 ≤ x ≤ k, 1 ≤ y ≤ k и взять допустимые значения x.
    Если 2 ≤ n ≤ k, то допустимыми значениями x будут 1 ... n-1. Для k+1 ≤ n ≤ 2k допустимыми значениями x будут n-k ... k. Таким образом, мы можем записать сумму числителей для каждого знаменателя:
    59fef5831ed62261528289.png
    Теперь, с учётом полученной системы запишем, как будет выглядеть полная сумма всех дробей:
    59fef5c331774953483286.png
    Заметим, что если в первой сумме начать суммирование не с 2, а с 1, то сумма не изменится, поскольку добавленное слагаемое равняется нулю. Во второй сумме перенесём k из пределов суммирования в слагаемое. Получим две суммы с одинаковыми пределами, а значит их можно объединить в одну:
    59fef699cef72869621752.png
    Ответ написан
    2 комментария
  • Каким образом реализовать быстрое сравнение таблиц?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    "Таблицы" - это массивы в памяти? Тогда сортировать все массивы по бренду и артикулу, затем двигаясь параллельно по всем трём массивам сформировать общий.
    Ответ написан
  • Как можно закодировать три числа в одно с последующей однозначной расшифровкой?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Никак.
    Три числа от 0 до 30 - это 313 = 29791 вариант. Так что уложить их в 100 не получится никак.
    Ответ написан
    6 комментариев
  • Как можно оптимизировать алгоритм сокращения дроби?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Бинарный алгоритм вычисления наибольшего общего делителя (НОД)

    function nod(m, n) {
      var mult = 0;
      while (true) {
        if (0 == m) {
          return n << mult;
        }
        if (0 == n) {
          return m << mult;
        }
        if (1 == m || 1 == n) {
          return 1 << mult;
        }
        if (m == n) {
          return m << mult;
        }
        if (0 == (m & 1) && 0 == (n & 1)) {
          mult++;
          m >>= 1;
          n >>= 1;
        } else if (0 == (m & 1)) {
          m >>= 1;
        } else if (0 == (n & 1)) {
          n >>= 1;
        } else if (m > n) {
          m = (m-n) >> 1;
        } else {
          n = (n-m) >> 1;
        }
      }
    }
    
    function reduceFrac(numerator, denomerator) {
      var divider = nod(numerator, denomerator);
      return {n: numerator/divider, d: denomerator/divider};
    }
    Ответ написан
    4 комментария
  • Каков алгоритм функции для перевода строки в уникальное число?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
  • Как оптимизировать алгоритм для выполнения 5 задачи с проекта Эйлера?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Задачу можно решить и без перебора.
    Для начала, берёте все числа от 2 до 20 и раскладываете на простые множители.
    Как-то так:
    2 = 21
    3 = 31
    4 = 22
    5 = 51
    6 = 21·31
    7 = 71
    8 = 23
    9 = 32
    10 = 21·51
    11 = 111
    12 = 22·31
    13 = 131
    14 = 21·71
    15 = 31·51
    16 = 24
    17 = 171
    18 = 21·32
    19 = 191
    20 = 22·51
    Затем берёте максимальные степени из всех разложений и перемножаете их:
    24·32·51·71·111·131·171·191 = 232792560
    Ответ написан
    Комментировать
  • Как правильно представить карту (метро) для поиска и каким алгоритмом реализовать?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Поиск пути в графе.
    Но, учитывая количество станций, проще прописать все маршруты заранее, их тут всего 15.
    Ответ написан
    1 комментарий
  • Как правильно генерировать уникальный код из алфавита?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Вариант 1. Генерируем код, проверяем на уникальность, если не уникален - начинаем сначала.
    Вариант 2. Описываем уникальное отображение (порядковый номер <=> код), генерируем код по номеру.
    Ответ написан
    Комментировать
  • Объединение пересекающихся периодов?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Для начала, я бы преобразовал даты в формат, удобный для сравнения:
    spoiler
    $intervals = 
      [['start' => '2017-01-01', 'end'   => '2017-01-06'],
       ['start' => '2017-01-21', 'end'   => '2017-01-30'],
       ['start' => '2017-01-10', 'end'   => '2017-01-20'],
       ['start' => '2017-01-05', 'end'   => '2017-01-16'],
       ['start' => '2017-01-15', 'end'   => '2017-01-20']];

    Затем нужна функция, определяющая пересечение интервалов и функция, объединяющая интервалы с добавлением подинтервалов:
    spoiler
    function is_intersect($int1, $int2) {
      return ($int2['end'] >= $int1['start'] && $int1['end'] >= $int2['start']);
    }
    function combine($int1, $int2) {
      if (!isset($int1['subintervals'])) {
          $int1['subintervals'] = [$int1];
      }
      if (!isset($int2['subintervals'])) {
          $int2['subintervals'] = [$int2];
      }
      return array('start' => min($int1['start'], $int2['start']), 'end' => max($int1['end'], $int2['end']),
                   'subintervals' => array_merge($int1['subintervals'], $int2['subintervals']));
    }

    Теперь пишем функцию, один раз проверяющую все интервалы на пересечения:
    spoiler
    function combine_intersected($intervals) {
      $result = [];
      $noIntersects = true;
      foreach ($intervals as $int1) {
        $combined = false;
        foreach ($result as &$int2) {
          if (is_intersect($int1, $int2)) {
            $int2 = combine($int1, $int2);
            $noIntersects = false;
            $combined = true;
            break;
          }
        }
        if (!$combined) {
          $result[] = $int1;
        }
      }
      if ($noIntersects) {
        return false;
      }
      return $result;
    }

    Ну и, напоследок, цикл, объединяющий интервалы:
    spoiler
    while ($ints = combine_intersected($intervals)) {
      $intervals = $ints;
    }

    Запускаем:
    spoiler
    Array (
        [0] => Array (
                [start] => 2017-01-01
                [end] => 2017-01-20
                [subintervals] => Array (
                        [0] => Array (
                                [start] => 2017-01-10
                                [end] => 2017-01-20
                            )
                        [1] => Array (
                                [start] => 2017-01-15
                                [end] => 2017-01-20
                            )
                        [2] => Array (
                                [start] => 2017-01-05
                                [end] => 2017-01-16
                            )
                        [3] => Array (
                                [start] => 2017-01-01
                                [end] => 2017-01-06
                            )
                    )
            )
        [1] => Array (
                [start] => 2017-01-21
                [end] => 2017-01-30
            )
    )
    Ответ написан
    2 комментария
  • Как найти схожие записи в БД по частичному вхождению?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Если нужно частичное совпадение по строкам при полном совпадении отдельных полей, то примерно так (8 и 2 - веса соответствующих полей):
    SELECT *
      FROM `table`
      ORDER BY (`phone` = :phone) * 8 + 
               (`lastName` = :lastName) * 2 + 
               (`firstName` = :firstName) * 2 + 
               (`middleName` = :middleName) * 2 + 
               (`city` = :city)
        DESC

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    В виде журнала транзакций (приход/расход) отдельной таблицей и дополнительного поля "баланс" в основной таблице. Дополнительное поле менять триггером AFTER INSERT из таблицы транзакций.
    Периодические списания выполнять отдельным скриптом, запускаемым из cron.
    Ответ написан
    Комментировать