Ответы пользователя по тегу Алгоритмы
  • Как построить машину Тьюринга для умножения десятичного числа на 11?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Примем, что в исходном положении каретка стоит на последней цифре числа.
    У нас будут состояния от q0 до q10, соответствующие сумме младшего разряда исходного числа и переноса из него . Начальное состояние - q0.
    qiaj → q((i + j) div 10) + ja(i + j % 10)L,
    qi ≠ 0ε → q(i div 10)a(i % 10)L,
    q0ε → qstop,
    где div - целочисленное деление.
    Теперь каретка стоит в пустой клетке перед результатом.
    Ответ написан
  • Ошибка переполнения стека в быстрой сортировке на JS. Как решить?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Смотрите, подаём на вход массив [1, 2, 3]
    fundam = Math.round(3 / 2) = 2.
    arr[2] = 3
    less = [1, 2, 3], так как в него попадают все элементы, меньшие или равные 3
    greater = []
    И снова вызываем сортировку массива [1, 2, 3]. Всё повторяется заново. При этом само число 3 будет добавлено в результат ещё раз.

    Во-первых, брать надо не round, а floor.
    Во-вторых, должно быть три массива - меньше опорного числа, равные ему и больше него.
    const qSort = (arr) => {
      if (arr.length < 2) {
        return arr;
      }
      const fund = arr[Math.floor(arr.length / 2)]
      let less = []
      let equal = []
      let greater = []
      for (let i = 0; i < 0; i += 1) {
        if (arr[i] < fund) {
          less.push(arr[i])
        }
        if (arr[i] === fund) {
          equal.push(arr[i])
        }
        if (arr[i] > fund) {
          greater.push(arr[i])
        }
      }
      return qSort(less) + equal + qSort(greater)
    }
    Ответ написан
    1 комментарий
  • Как предать данные от детей к родителю в древовидном объекте?

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Создаём M списков (0..M-1). Каждое получаемое число Xi записываем в список Xi % M. Затем выводим пары из списков (0, 0), (1, M-1), (2, M-2), ... (M/2, M/2).
    Ответ написан
    2 комментария
  • Случайные числа с заданной сумой, какой алгоритм?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    x = rand(1, 97);
    y = rand(1, 98-x);
    z = rand(1, 99-x-y);
    result = sort([x, y, z, 100-x-y-z]);
    Ответ написан
    2 комментария
  • Как решить такую задачу на логику?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Один поезд начинает движение влево, второй вправо, какой именно куда - неважно. Если не встретились, то через время t меняют направление движения. Потом через время 2t, 3t, 4t и т.д. Как вариант t, 2t, 4t, 8t.
    Ответ написан
    2 комментария
  • Как сгенерировать направленный граф с N количеством путей?

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

    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 за плюс.
    Ответ написан
    Комментировать