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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Оценка сложности алгоритма O() - это то, как меняется время вполнения алгоритма от изменения объёма обрабатываемых этим алгоритмом данных.
    O(1) - время не зависит от объёма данных.
    O(n) - время растёт пропорционально объёму данных.
    O(n2) - время растёт пропорционально квадрату объёма данных.
    и т.д.

    Получение длины строки может иметь разную сложность в зависимости от языка программирования. Если используется хранение строк с префиксом длины, как в Паскале, то сложность будет O(1), так как достаточно только прочитать хранящееся значение. Если же строка хранится как в C/C++, с нулевым байтом в конце, то сложность будет O(n), так как надо в цикле перебрать все байты строки, пока не найдём ноль.
    Ответ написан
    Комментировать
  • Правильный ли алгоритм?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Судя по примеру, задачи должны выполняться последовательно, но каждая следующая может быть запущена на произвольном устройстве.
    Значит сортируем задачи по времени в убывающем порядке и запускаем на устройствах по кругу.
    function allTestsTime(numDevices, testTimes) {
      testTimes.sort((a, b) => b - a);
      let totalTime = 0;
      for (let i = 0; i < testTimes.length; i++) {
        totalTime += testTimes[i] * (2 * Math.floor(i / numDevices) + 1);
      }
      return totalTime;
    }
    
    console.log(allTestsTime(3, [6, 2, 5]));
    
    // 13
    Ответ написан
  • Как правильно реализовать приложение с использованием алгоритмов Брезенхема и Люка для решения задачи отрисовки букв?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Но вот вопрос - что имеется ввиду в задаче, что координаты концов отрезков, образующих буквы должны отображаться в символьных матрицах 50*80 точек?
    Значит, что каждая буква рисуется в прямоугольнике 50x80 точек. Соответственно, координаты концов отрезков будут в диапазоне 0-49 по горизонтали и 0-79 по вертикали.
    И что означает то,что буквы отобразить горизонтально, рядом в центре экрана, через "пробел" (пустую символьную матрицу), это как?
    А вот прямо так: буква пробел буква. Центр пробела должен совпадать с центром экрана.
    А вообще, такие вопросы лучше задавать своему преподавателю.
    Ответ написан
    7 комментариев
  • Почему скорость алгоритма измеряется в количестве операций, а не в секундах?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    А что вам дадут секунды?
    Вот у вас есть две программы, обрабатывающие одни и те же данные и получающие одни и те же результаты по разным алгоритмам. Первая программа делает это за 10 секунд, вторая за 20. Как оценить, насколько вырастет время обработки при увеличении объёма данных в 10 раз?
    Никак, пока мы не знаем сложности алгоритма. Если первый имеет сложность O(n2), а второй - O(n), то время работы первого вырастет в 100 раз и составит 1000 секунд, а второго - всего в 10 раз (200 секунд). То есть, программа, которая была быстрее на малом наборе данных, внезапно становится гораздо медленнее на большом наборе. И определяющим параметром здесь становится именно вычислительная сложность алгоритма.
    Ответ написан
    1 комментарий
  • Интересный вопрос от Я! Как решить проблему неправильных монет?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Предположим, что мы бросили n-1 монет и получили какое-то количество единиц (орлов). Бросаем следующую монету (n). Если выпадет ноль (решка), то количество единиц не изменится, и чётность останется той же. Если выпадет единица, то чётность изменится.
    Poddn = Poddn-1*P0n + Pevenn-1*P1n
    Pevenn = Pevenn-1*P0n + Poddn-1*P1n
    Но, поскольку события Pevenn и Poddn образуют полный набор вариантов (либо чёт, либо нечет), то Pevenn + Poddn = 1.
    Аналогично, P0n + P1n = 1.
    Отсюда, Poddn = Poddn-1*(1-P1n) + (1-Poddn-1)*P1n
    var Podd = 0;
    var Peven = 1;
    for (var i = 1; i <= 100; i++) {
      P1 = 1 / (2 * i + 1);
    //  P0 = 1 - P1;
    //  Po = Podd * P0 + Peven * P1;
    //  Peven = Podd * P1 + Peven * P0;
    //  Podd = Po;
    // Всё, что выше, ужимается в
      Podd = Podd * (1 - P1) + (1 - Podd) * P1;
    }
    console.log(Podd);
    // 0.49751243781094556
    Ответ написан
    3 комментария
  • Какой алгоритм даст лучший результат?

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Просмотрев все значения. Ваш К.О.
    Ответ написан
  • Как вывести первые N элементов последовательности 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    let number = 1;
    let count = 1;
    for (let i = 1; i <= n; i++) {
      console.log(number);
      if (0 == --count) {
        count = ++number;
      }
    }
    Ответ написан
    1 комментарий
  • Как составлять формулы в мат.логике?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Для начала научитесь выражать всё словами.
    Что такое "эквивалентность"? Это значит, что оба операнда (A и B) равны, то есть либо оба они равны единице, либо оба равны нулю.
    Оба операнда равны единице: A∧B
    Оба операнда равны нулю: ¬A∧¬B
    Общее выражение: A∧B ∨ ¬A∧¬B
    Избавляемся от дизъюнкции: ¬(¬(A∧B) ∧ ¬(¬A∧¬B))
    Остаётся составить таблицу истинности и проверить
    A | B | ¬(¬(A∧B) ∧ ¬(¬A∧¬B))
    0 | 0 |           1
    0 | 1 |           0
    1 | 0 |           0
    1 | 1 |           1

    Во втором случае утверждение будет "из A следует B и из B следует A".
    (A→B) ∧ (B→A)
    Остаётся избавиться от конъюнкции
    ¬((A→B) → ¬(B→A))
    Ответ написан
    Комментировать
  • Как разработать алгоритм для нахождения двух элементов, сумма которых дает x?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Фантастический способ:
    Изучить O-нотацию.
    Изучить различные алгоритмы с их оценкой сложности в O-нотации.
    Подобрать необходимые алгоритмы и провести их композицию в свой алгоритм, решающий задачу.

    Реальный способ:
    Бегать по всем форумам с просьбой помочь, авось кто и откликнется.

    P.S. Задача, кстати, примитивная, в два действия, первое O(n log n), второе O(n).
    Ответ написан
    3 комментария
  • Как сгенерировать множество с покрытием максимального числа результатов?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    А в чём проблема то?
    $nullPercents = [10, 20, 50];
    $totalRows = 11;
    $result = [];
    for ($i = 1; $i <= $totalRows; $i++) {
      $row = [];
      foreach ($nullPercents as $percent) {
        if ($i <= $totalRows*$percent/100) {
          $row[] = null;
        } else {
          $row[] = $i;
        }
      }
      $result[] = $row;
    }
    Ответ написан
  • Какой алгоритм разбиения сети на подсети указанного размера?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Несколько обобщив задачу получаем следующее:
    - на входе есть список имеющихся подсетей (возможно из одного элемента) и список размеров подсетей, которые надо выделить;
    - на выходе надо получить выделенные подсети и список оставшихся нераспределёнными подсетей.
    1. Находим маску необходимой подсети mask := 32 - ⌈log2(size + 2)⌉. 2. Ищем в списке свободных подсеть subNet с максимальной маской меньшей либо равной mask.
    3. Если не нашли, то выделить подсеть невозможно, возвращаем ошибку.
    4. Пока маска subNet меньше mask, удаляем subNet из списка свободных, разбиваем её на две подсети, добавляем полученные подсети в список свободных, в качестве subNet берём одну из них.
    5. Если маска subNet равна mask, то выделяем подсеть, удаляем её из списка свободных, возвращаем результат.

    Пример:
    Вход: список подсетей = [192.168.0.0/24], размер = 30
    mask = 32-ceil(log2(32)) = 27
    после поиска subNet = 192.168.0.0/24
    24 < 27 => список подсетей = [192.168.0.0/25, 192.168.0.128/25], subNet = 192.168.0.0/25
    25 < 27 => список подсетей = [192.168.0.0/26, 192.168.0.64/26, 192.168.0.128/25], subNet = 192.168.0.0/26
    26 < 27 => список подсетей = [192.168.0.0/27, 192.168.0.32/27, 192.168.0.64/26, 192.168.0.128/25], subNet = 192.168.0.0/27
    27 == 27 => список подсетей = [192.168.0.32/27, 192.168.0.64/26, 192.168.0.128/25], выделенная подсеть = 192.168.0.0/27
    Ответ написан
    Комментировать
  • Как решить задачу расстановки арифметических знаков между числами для получения другого числа?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Если у вас только два знака и ставиться они могут только между числами, то просто генерируете все числа от 0 до 2N-1 и принимаете, например, бит 0 за минус, а бит 1 за плюс.
    Ответ написан
    Комментировать
  • Как правильно разработать возможность разнообразия характеристик у персонажей?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    {
      "parameters": {
        "speed": ...,
        "visionArea": ...,
        ...
      },
      "events": {
        "getSight": [
          {
            "objects": ["fox", "wolf"],
            "actions": [
              {
                "probability": 0.5,
                "action": "run"
              }, {
                "probability": 0.5,
                "action": "wait"
              }
            ]
          }, {
            "objects": ["carrot"],
            "actions": [
              {
                "probability": 1,
                "action": "eat"
              }
            ]
          }
        },
        "hungry": [ ... ],
        "thirsty": [ ... ].
        ...
      }
    }
    Ответ написан
    5 комментариев
  • Как последовательно сгенерировать максимально разные цвета?

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Вообще, в таком виде задача может не иметь однозначного решения.
    Первый же пример X=8, Y=1 даёт два решения - (3,4) и (4,3).
    Ответ написан
    3 комментария
  • Какой алгоритм для решения задачи на динамическое программирование про лестницу и монеты?

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Берёте три массива по пять элементов, в первом будет сами числа, во втором и третьем - индексы. Инициализируете массивы индексов значениями -1.
    Обходите всю матрицу и для каждого элемента матрицы проверяете все элементы массива. Если в массиве есть элемент с индексами -1 или значение в массиве меньше, чем элемент матрицы, то записываете в массив значение из матрицы с его индексами.
    Ответ написан
    Комментировать
  • Как связать M из N?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Возьмём вариант "2 из 3".
    F(X, T, Z) = F(X, Y, Z) = F(X, Y, Q)
    Но
    F(X, T, Z) ≠ F(X, Y, Q)
    Следовательно такой функции существовать не может.
    Единственное, что можно сделать - считать функцию расстояния
    F((X, Y, Z), (X, T, Z)) = 1
    F((X, Y, Z), (X, Y, Q)) = 1
    F((X, T, Z), (X, Y, Q)) = 2
    Ответ написан
    Комментировать
  • Как реализовать поиск по Linked List?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Что я делаю не так?
    Не занимаетесь отладкой своей программы. Если не умеете пользоваться отладчиком, то возьмите лист бумаги, карандаш, и пошагово пройдите всю свою программу.
    Если таки ничего не поможет
    node->value на первом же элементе равняется нулю, соответственно отрабатывает последняя ветка условия и возвращает false.
    Ответ написан
    Комментировать