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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Для решения такой задачи нужен предварительный анализ.
    Поскольку две части соединены логическим ИЛИ, то пока первое неравенство выполняется, истинность второго не имеет значения.
    Значит нам надо рассмотреть только ситуацию, когда первое неравенство ложно. Второе, при этом, должно быть истинно.
    Инвертируем первое условие, получим 2x + 3y ≤ 30.
    Чтобы найти минимальное значение A, при котором выполняется x + y ≤ A, мы должны найти максимум x + y, при котором 2x + 3y ≤ 30.
    Задача формализуется в
    max(x + y), 2x + 3y ≤ 30, x ∈ N, y ∈ N.
    Дальше, опять таки, можно рассуждать аналитически. Поскольку при увеличении x величина 2x + 3y растёт медленнее, чем при увеличении y, то максимальное значение x + y будет достигаться при максимальном значении x и минимальном значении y, удовлетворяющих неравенству. Поскольку минимальное значение y = 0, то получаем неравенство 2x ≤ 30, отсюда x = 15, x + y = 15, A = 15.
    А можно написать программу для перебора:
    a = 0;
    for (x = 0; 2 * x <= 30; x += 1) {
      for (y = 0; 2 * x + 3 * y <= 30; y += 1) {
        if (a < x + y) { 
          a = x + y;
        }
      }
    }
    Ответ написан
    Комментировать
  • Многомерная задача о рюкзаке?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Для 16 товаров проще всего сделать прямой перебор. Всего то 216 вариантов.
    Ответ написан
  • Каким образом отобразить реализацию кольцевой очереди на основе массива?

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Задача сводится к поиску циклов в графе.
    https://neerc.ifmo.ru/wiki/index.php?title=%D0%98%...
    Ответ написан
    Комментировать
  • Как вернуть первые N максимальных элементов из массива без сортировки массива?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    const littleN = (arr, N) => arr.reduce(
      (acc, cur) => {
        const idx = acc.findIndex((el) => el.distance > cur.distance);
        if (idx !== -1) {
          acc.pop();
          acc.splice(idx, 0, cur);
        }
        return acc;
      },
      Array(N).fill(arr[0])
    );

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Лень вспоминать C, держите вариант конечного автомата проверки римских цифр на JS.
    // Матрица переходов конечного автомата
    // -1 - допустимое конечное состояние
    // null - недопустимое состояние
    const dka = [
      [-1, 1, 5, 4, 10, 9, 15, 14], // 0
      [-1, 2, 5, 4, 10, 9, 15, 14], // 1
      [-1, 3, 5, 4, 10, 9, 15, 14], // 2
      [-1, null, 5, 4, 10, 9, 15, 14], // 3
      [-1, 8, 8, 7, null, null, null, null], // 4
      [-1, null, null, 6, 10, 9, 15, 14], // 5
      [-1, null, null, 7, 10, 9, 15, 14], // 6
      [-1, null, null, 8, 10, 9, 15, 14], // 7
      [-1, null, null, null, 10, 9, 15, 14], // 8
      [-1, null, null, 13, 13, 12, null, null], // 9
      [-1, null, null, null, null, 11, 15, 14], // 10
      [-1, null, null, null, null, 12, 15, 14], // 11
      [-1, null, null, null, null, 13, 15, 14], // 12
      [-1, null, null, null, null, null, 15, 14], // 13
      [-1, null, null, null, null, 18, 18, 17], // 14
      [-1, null, null, null, null, null, null, 16], // 15
      [-1, null, null, null, null, null, null, 17], // 16
      [-1, null, null, null, null, null, null, 18], // 17
      [-1, null, null, null, null, null, null, null], // 18
    ];
    
    // Алфавит
    const alphabet = 'MDCLXVI';
    
    // Разбивает строку на лексемы
    // (номера символов в алфавите, начиная с 1)
    // для отсутствующих символов возвращает 0
    const lexer = (str) => str.split('').map((l) => alphabet.indexOf(l) + 1);
    
    // Проверяет корректность числа в римской записи
    const check = (str) => {
      const lexems = lexer(str);
      let state = 0;
      let idx = 0;
      while (true) {
        const lex = lexems[idx] ?? 0;
        state = dka[state][lex];
        if (state === null) {
          return false;
        }
        if (state === -1) {
          return  idx === str.length;
        }
        idx += 1;
      }
    }
    Ответ написан
    2 комментария
  • Почему вставка элементов занимает такое время?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Классический массив - это непрерывная область памяти, заполненная данными в порядке возрастания индексов. Чтобы вставить элемент в массив необходимо перенести часть уже имеющихся элементов, освободив место под вставляемый. При вставке в случайное место матожидание количества переносимых элементов будет n/2, соответственно сложность алгоритма оценивается в O(n). Добавление элемента в конец массива имеет сложность O(1), если нам известен текущий размер и мы не выходим за пределы памяти, выделенной для хранения массива. Если памяти недостаточно, то придётся выделить новый блок, перенести туда весь массив и освободить старый блок памяти. Эта процедура тоже занимает O(n).

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Берём матрицу, размером с изображение, заполняем нулями. Отмечаем единицами точки, принадлежащие линиям контура.
    Добавляем в очередь точку, заведомо лежащую внутри контура и ставим в неё единицу.
    Забираем точку из очереди, добавляем в очередь соседей этой точки (слева, справа, сверху и снизу), в которых ещё не стоит единица, и ставим в них единицы. Повторяем, пока очередь не опустеет.
    Ответ написан
    1 комментарий
  • Как лучше обработать пробег автомобиля?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Интерполировать. Как именно - зависит от того, как используются автомобили.
    Если предположить, что пробег каждый день одинаковый, то берём общий пробег за интервал и делим на кличество дней в интервале. Затем либо сохраняем полученный средний пробег для каждого дня интервала, либо вычисляем пробег на конец месяца и сохраняем помесячно.
    Если, например, весь пробег только в будни, то, соответственно, вычисляем количество рабочих дней в интервале и делим на него. При раскидывании по дням, опять же, записываем нулевой пробег в выходные и средний в будни.
    Ответ написан
    4 комментария
  • Сортировка слиянием с выводом границ. Как реализовать?

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    У вас неэффективно написана сортировка.
    При правильной сортировке пузырьком в худшем случае будет (N2-N)/2 итераций, у вас - N2.
    Ответ написан
  • Как сделать перебор всех значений строки определенной длины состоящей из цифр и букв?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Просто переводите числа от 0 до 366 в систему счисления с основанием 36.
    010 = 036
    ...
    910 = 936
    1010 = a36
    ...
    3510 = z36
    3610 = 1036
    ...
    217678233510 = zzzzzz36
    Ответ написан
    Комментировать
  • Как написать алгоритм сортировки?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Комментировать
  • Найдите перестановку по её номеру в лексикографическом порядке. Total - кол-во элементов, К - номер перестановки. Как сократить время программы?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Рассмотрим список всех перестановок в лексикографическом порядке. Этот список содержит N! перестановок. При этом его можно разбить по первому элементу на N непрерывных групп по (N-1)! перестановок.
    Таким образом, определить первый элемент перестановки с номером M (начиная с 0) можно как К1=⌊M/(N-1)!⌋ (также, начиная с 0). Внутри группы перестановка будет иметь номер M'=M mod (N-1)!.
    Вычеркнем найденный элемент из списка и повторим вычисления, пока не найдём все элементы.

    Пример:
    Элементы: (a, b, c, d).
    Перестановка M=11 (начиная с 0).
    Список (a, b, c, d). K1 = ⌊11/3!⌋ = 1. Элемент 'b'. M' = 10 mod 3! = 5.
    Список (a, c, d). K2 = ⌊5/2!⌋ = 2. Элемент 'd'. M' = 5 mod 2! = 1
    Список (a, c). K3 = ⌊1/1!⌋ = 1. Элемент 'c'. M' = 1 mod 1! = 0
    Список (a). K4 = ⌊0/0!⌋ = 1. Элемент 'a'.
    Получили перестановку (b, d, c, a).
    Сгенерируем все перестановки и проверим правильность:
    0: a, b, c, d
    1: a, b, d, c
    2: a, c, b, d
    3: a, c, d, b
    4: a, d, b, c
    5: a, d, c, b
    6: b, a, c, d
    7: b, a, d, c
    8: b, c, a, d
    9: b, c, d, a
    10: b, d, a, c
    11: b, d, c, a
    12: c, a, b, d
    13: c, a, d, b
    14: c, b, a, d
    15: c, b, d, a
    16: c, d, a, b
    17: c, d, b, a
    18: d, a, b, c
    19: d, a, c, b
    20: d, b, a, c
    21: d, b, c, a
    22: d, c, a, b
    21: d, c, b, a
    Ответ написан
    1 комментарий
  • Как найти расстояние между двумя отрезками?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Назовём концы отрезка как A1-A2 и B1-B2
    Для начала проверьте вариант, когда отрезки пересекаются. В этом случае расстояние между ними равно нулю.
    Берём первый конец первого отрезка (A1). Опускаем перпендикуляр на прямую, построенную на втором отрезке. Получаем точку пересечения O. Если точка O лежит внутри второго отрезка, то берём расстояние A1O. Если нет, то берём минимальное из A1B1 и A1B2.
    Повторяем для точек A2, B1 и B2.
    Из четырёх полученных расстояний выбираем минимальное. Это и будет расстоянием между непересекающимися отрезками.
    Ответ написан
    Комментировать
  • Как сделать генератор всевозможных сочетаний символов заданной длины?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    $result = array_map(
        function ($x) {
            return str_pad(dechex($x), 4, '0', STR_PAD_LEFT);
        },
        range(0, 0xffffff, 1)
    );
    Ответ написан
    9 комментариев
  • Сумма арифметической прогрессии?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Внутренняя сумма раскладывается как 1 + 2 + 3 + ... + n - i = (1 + n - i) * (n - i) / 2
    Ответ написан
    Комментировать
  • Какой алгоритм используется при возможности 2 неудачных попыток?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Какой угодно. Раз у задачи нет цели на минимизацию чего-либо, значит можно просто кидать один предмет с метра, двух, трёх и т.д., пока не разобъётся.
    Ответ написан
    2 комментария
  • Алгоритм перевода RGB-компонент в длину волны?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Длина волны в RGB.
    Взято из https://www.johndcook.com/wavelength_to_RGB.html
    const w = 640 // Длина волны
    let red, green, blue;
    
    if (w < 380 || w > 781) {
      [red, gren, blue] = [0, 0, 0];
    } else if (w < 440) {
      [red, green, blue] = [(440 - w) / 60, 0, 1];
    } else if (w < 490) {
      [red, green, blue] = [0, (w - 440) / 50, 1];
    } else if (w < 510) {
      [red, green. blue] = [0, 1, (510 - w) / 20];
    } else if (w < 580) {
      [red, green, blue] = [(w - 510) / 70, 1, 0];
    } else if (w < 645) {
      [red, green, blue] = [1, (645 - w) / 65, 0];
    } else {
      [red, green, blue] = [1, 0, 0];
    }
    
    let factor;
    if (w < 380 || w > 781) {
      factor = 0;
    } else if (w < 420) {
      factor = 0.3 + 0.7 * (w - 380) / 40;
    } else if (w < 701) {
      factor = 1.0;
    } else {
      factor = 0.3 + 0.7 * (780 - w) / 80;
    }
    
    const gamma = 0.8;
    
    const R = (red > 0 ? 255 * Math.pow(red * factor, gamma) : 0);
    const G = (green > 0 ? 255 * Math.pow(green * factor, gamma) : 0);
    const B = (blue > 0 ? 255 * Math.pow(blue * factor, gamma) : 0);
    
    const color = `rgb(${R}, ${G}, ${B})`;
    console.log(color); // rgb(255, 32.763138565028974, 0)
    Ответ написан
    4 комментария
  • Как определить число на основе результата?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Однозначного решения тут нет, одно и то же количество игр может быть при различном количестве команд.
    Например, 3 и 4 команды дадут по 3 игры, 18 и 40 команд - по 45 игр.
    Количество команд можно представить как k = 2xy, где x - целое неотрицательное число, y - нечётное положительное число.
    Тогда количество игр будет n = (2x - 1)y + (y - 1)y/2 = 2xy - 3y/2 + y2/2
    Отсюда можно получить
    2x+1 = 3 - y + 2n/y
    Поскольку решение нужно в целых числах, то y - один из делителей числа 2n.
    Значит, перебирая делители мы должны найти такой нечётный делитель, при котором правая часть уравнения даст в результате степень двойки.
    Например, n = 171
    2n = 342
    Нечётные делители: 1, 3, 9, 19, 57, 171
    Значения правой части: 344, 114, 32, 2, -48, -166
    Степени двойки: 32, 2
    Соответствующие значения x: 4, 0
    Количество команд: 144, 19
    Ответ написан
    Комментировать