Задать вопрос
Ответы пользователя по тегу Алгоритмы
  • Как определить язык по автомату с магазинной памятью (ДМПА)?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Анализировать переходы.
    delta(q0,c,Z) = {(q0,cZ)} - состояние q0, на входе символ 'c', в стеке пусто. Остаёмся в q0, в стек кладём 'c'.
    delta(q0,c,c) = {(q0,cc)} - состояние q0, на входе 'c', с вершины стека снят 'c'. Остаёмся в q0, в стек кладём 'c', 'c'.
    И так далее.
    lambda - это пустой символ λ.
    Ну а язык, вроде, cna2n+1b*
    Ответ написан
    1 комментарий
  • Что нужно сделать чтобы код заработал как надо?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Ох уж эти программисты, не помнящие школьный курс математики. Всего то надо решить две системы линейных уравнений:
    m₃     m₄   | -1630.2
    m₃z₃   m₄z₄ | 88464
    
    m₃     m₄   | -4636.8
    m₃z₃   m₄z₄ | -9772.88

    import math
    
    def main():
        m_values = [40, 50, 60, 71, 76]
        z_values = [160, 240, 320]
        for m3 in m_values:
            for m4 in m_values:
                for z3 in z_values:
                    for z4 in z_values:
                        d = m3 * m4 * (z4 - z3)
                        if d == 0:
                            continue;
                        x3 = (-1630.2 * z4 - 88464) * m4 / d
                        x4 = (88464 + 1630.2 * z3) * m3 / d
                        y3 = (-4636.8 * z4 + 9772.88) * m4 / d
                        y4 = (-9772.88 + 4636.8 * z3) * m3 / d
                        r1 = math.sqrt(x3 * x3 + y3 * y3)
                        r2 = math.sqrt(x4 * x4 + y4 * y4)
                        if 42 <= r1 <= 88 and 42 <= r2 <= 88:
                            print("Найдено решение, удовлетворяющее условию 42 <= r <= 88:")
                            print(f"  x3 = {x3_val:.2f}, x4 = {x4_val:.2f}")
                            print(f"  y3 = {y3_val:.2f}, y4 = {y4_val:.2f}")
                            print(f"  r1 = {r1:.2f}, r2 = {r2:.2f}")
                            print(f"  Параметры: m3 = {m3}, m4 = {m4}, z3 = {z3}, z4 = {z4}")
                            return
        print("Не найдено решений, удовлетворяющих условию 42 <= r <= 88.")
    
    if __name__ == "__main__":
        main()

    Не найдено решений, удовлетворяющих условию 42 <= r <= 88.
    Ответ написан
    6 комментариев
  • Правильно ли выражение парсится в ПОЛИЗ форму?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    IMHO, вы неправильно поняли польскую обратную запись.
    Каждая строка должна включать одно действие, выполняемое над стеком.
    00: 10          10: :=          20: i
    01: &a          11: i           21: output
    02: :=          12: 0           22: 
    03: a           13: >
    04: 10          14: 12
    05: +           15: 4
    06: &b          16: <=
    07: :=          17: and
    08: 12          18: 22
    09: &i          19: jz

    А после оптимизации код должен вообще стать пустым.
    12 <= 4 всегда false, заменяем.
    На момент вычисления условия i всегда 10, заменяем.
    10 > 0 всегда true, заменяем.
    true and false всегда false, заменяем.
    Условие всегда false, поэтому выбрасываем if вместе с содержимым.
    Переменная i получает значение, но не используется, выбрасываем.
    Переменная b получает значение, но не используется, выбрасываем.
    Переменная a получает значение, но не используется, выбрасываем.
    Ответ написан
    Комментировать
  • Почему неправильно работает сортировка вставками из "Алгоритмов..." Кормена и др.?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    - while j > 0 and a[j] > key:
    + while j >= 0 and a[j] > key:
    Ответ написан
    Комментировать
  • Какая сложность у этого алгоритма?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Цикл while же выполняется пропорционально количеству цифр в числе..
    Да. А количество цифр в числе C это ⌊log10C⌋ + 1.
    Элемент суммы с меньшей степенью (1) отбрасываем, округление вниз убираем, основание логарифма неважно, получаем logC
    Ответ написан
    6 комментариев
  • Как набрать нужную сумму из определенного количества монет?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    В лоб - составить все возможные варианты набора определённой суммы, затем определить непересекающиеся группы наборов и для каждой группы рекурсивно перебирать все комбинации.

    Скажем, номиналы 5, 4, 3, 2, необходимая сумма 8
    Получаем наборы (5, 3), (4, 4), (4, 2, 2), (3, 3, 2), (2, 2, 2, 2).
    Одна группа, в которую входят все наборы.
    Номиналы 5, 4, 3, необходимая сумма 8
    Получаем наборы (5, 3), (4, 4).
    Две группы [(5, 3)] и [(4, 4)]

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Ответ написан
    Комментировать
  • Как уменьшать числовую последовательность, чтобы каждое последующее число было меньше предыдущего?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Для арифметической прогрессии с шагом X рублей и N рабочих:
    Первый получает Y, второй Y - X, ..., N-й получает Y - X * (N - 1)
    Сумма прогрессии: S = (Y + Y - X * (N - 1)) * N / 2
    Отсюда, Y = (2S/N + X(N - 1))/2
    При 100 рублях, 100 рабочих и шаге 1 копейку получим
    Y = (2 * 100р / 100 + 0.01р * 99)/2 = 1.495 рубля
    Первый получает 1.495, второй 1.485, ..., сотый 0.505 рубля
    Ответ написан
    1 комментарий
  • Как разбить треугольник в прямоугольной области на N треугольников?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Обычная задача клипинга в 2d-графике.
    https://en.wikipedia.org/wiki/Sutherland%E2%80%93H...
    Ответ написан
    Комментировать
  • Как найти решение для задачи?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Геометрически здесь задача проверки, что заданный в координатах X(distance) - Y(light) прямоугольник полностью покрывается набором других прямоугольников.
    Как вариант, формируем общий список левых и правых границ всех покрывающих прямоугольников по X, сортируем его, слева и справа ограничиваем целевым прямоугольником, затем для каждого интервала проверяем, что он полностью покрывается по Y.
    Например:
    Целевой прямоугольник (1, 1)-(6, 6)
    Покрывающие прямоугольники: (0, 0)-(3, 4), (2, 1)-(7, 5), (0, 3)-(6, 7)
    Составляем список границ по X: 0, 3, 2, 7, 0, 6
    Удаляем дубли, сортируем и ограничиваем по [1, 6]: 1, 2, 3, 6
    Для каждого интервала составляем список интервалов по Y и объединяем интервалы:
    [1, 2]: [0, 4] + [3, 7] = [0, 7], что перекрывает целевой [1, 6]
    [2, 3]: [0, 4] + [1, 5] + [3, 7] = [0, 7], что перекрывает целевой [1, 6]
    [3, 6]: [1, 5] + [3, 7] = [1, 7], что перекрывает целевой [1, 6]
    На всех интервалах полное покрытие, значит целевой прямоугольник покрывается полностью.
    Сложность, правда, высокая - n2.
    Ответ написан
    Комментировать
  • Почему код не работает?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Вам надо не получить последовательность, а только определить значение элемента этой последовательности.
    Запишем последовательность и пронумеруем её элементы с нуля. После этого переведём номера в двоичную систему и запишем их над элементами
    Номера в десятичной системе:
    00000000001111111111222222222233
    01234567890123456789012345678901
    Номера в двоичной системе:
    00000000000000001111111111111111
    00000000111111110000000011111111
    00001111000011110000111100001111
    00110011001100110011001100110011
    01010101010101010101010101010101
    Последовательность:
    10010110011010010110100110010110

    Можно заметить, что там, где двоичное представление содержит чётное количество битов, элемент последовательности равен 1, нечётное - 0.
    Остаётся преобразовать номер в двоичную систему и посчитать количество битов. Надо учесть, какая нумерация используется в задании и, при необходимости, переводить её в нумерацию с нуля.
    Ответ написан
    1 комментарий
  • Как узнать, входит ли игрок1 (x,y,z) в поле игрок2 (x,y,z)?

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    В общем случае - теория графов, Эйлеров путь.
    Для случая, когда путь заведомо есть, он только один и проходит через каждую вершину только один раз, ищем вершину, для которой есть исходящий маршрут, но нет входящих.
    В вашем примере это "USA". Есть маршрут, который с неё начинается, но нет маршрута, который в ней заканчивается.
    Ответ написан
    1 комментарий
  • Как объединить списки, полученные от 2 REST API с параметрами `limit` и `offset`, и вернуть его, согласно параметрам `limit` и `offset`?

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

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    prev < cur || prev == 4 && cur == 0 - по часовой.
    иначе против часовой.
    Ваш К.О.
    Ответ написан
  • Как сделать распределение по процентам, чем дороже цена тем меньше шансов?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Если у вас заранее определённый список призов и их количество известно (100 ручек, 10 блокнотов, 1 телефон), то можно создать общий массив, сделать shuffle и выдавать призы из полученного случайного массива по порядку.
    Ответ написан
  • Как решить задачку "ЛИРИК = 0,5*ФИЗИКА" на ЯП?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Самое простое - в лоб
    exit:
    for (let l = 1; l < 10; l += 1) {
      for (let f = 1; f < 10; f += 1) {
        if (f === l) {
          continue;
        }
        for (let i = 0; i < 10; i += 1) {
          if (i === l || i === f) {
            continue;
          }
          for (let r = 0; r < 10; r += 1) {
            if (r === l || r === f || r === i) {
              continue;
            }
            for (let k = 0; k < 10; k += 1) {
              if (k === l || k === f || k === i || k === r) {
                continue;
              }
              for (let z = 0; z < 10; z += 1) {
                if (z === l || z === f || z === i || z === r || z === k) {
                  continue;
                }
                for (let a = 0; a < 10; a += 2) {
                  if (a === l || a === f || a === i || a === r || a === k || a === z) {
                    continue;
                  }
                    const lirik = l * 10000 + i * 1010 + r * 100 + k;
                    const fizika = f * 100000 + i * 10100 + z * 1000 + k * 10 + a;
                    if (lirik * 2 === fizika) {
                      console.log(`lirik = ${lirik}`);
                      console.log(`fizika = ${fizika}`);
                      break exit;
                    }
                }
              }
            }
          }
        }
      }
    }
    Вариант на JS.
    Ответ написан
    Комментировать
  • Как из первых N натуральных чисел составить максимальное количество пар, суммы которых являются простыми?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Ключевые слова - максимально возможное количество пар. Значит простой перебор тут не работает, поскольку можно упереться в локальный оптимум и не найти глобального. Нужно перебрать все возможные комбинации пар и найти ту, где простых чисел больше всего.
    Пример: при поиске наивным способом для N = 8 получим три пары с простой суммой (1, 2), (3, 4), (5, 6). Оставшаяся пара (7, 8) даст 15, что не является простым числом. Однако, при разбиении (1, 2), (3, 4), (5, 8), (6, 7) получим уже четыре пары с простой суммой.
    Ответ написан
  • Динамическое программирование Разбиение на слагаемые. Как получить вывод результатов?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Написать новую функцию, которая будет перебирать все разбиения. Текущая функция вычисляет P(n, n) по рекурентной формуле.
    Ответ написан