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

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

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    0. Установить начальное состояние, установить указатель на первый символ.
    1. Получить следующий символ.
    2. По таблице переходов найти переход для пары (состояние, символ).
    3. Если такой переход есть, то установить новое состояние, сдвинуть указатель на следующий символ, перейти на пункт 1.
    4. По таблице допустимости проверить допустимость завершения в текущем состоянии.
    5. Если завершение недопустимо, то выдать ошибку, завершить работу.
    6. Выдать корректное завершение, завершить работу.
    Ответ написан
    Комментировать
  • Придумал алгоритм, оцените его верность?

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

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

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    var arr = [1, 2, 3, 'a', 4, 5, 'b', 9, 'n', 'm'];
    arr = arr.reduceRight(function(prev, el, i) {
      if (prev.length == 0 || 
         (typeof(el) != typeof(prev[0][0]))) {
        prev.unshift([el]);
      } else {
        prev[0].unshift(el);
      }
      return prev;
    }, []);
    console.log(JSON.stringify(arr));

    [[1,2,3],["a"],[4,5],["b"],[9],["n","m"]]
    Ответ написан
    3 комментария
  • Почему в С 0 != 0, а 0 == 0?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Из-за особенностей машинного представления вещественных чисел сравнивать их напрямую крайне не рекомендуется. Попробуйте вместо %f использовать %e и, скорее всего, обнаружите, что в массиве вовсе не нули.
    Ответ написан
    6 комментариев
  • ГОСТ 2015 и Диффи-Хеллман, как подружить?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    отправляет ключ для расшифровки зашифрованного текста по протоколу (или алгоритму) Диффи-Хеллмана

    Что-то в этой фразе не так. Алгоритм Диффи-Хеллмана позволяет двум сторонам согласовать ключ шифрования не передавая данных, по которым третья сторона могла бы этот ключ получить (кроме атаки MiTM).
    Как правило, этим методом стороны в начале общения вырабатывают общий сессионный ключ, а затем используют его при обмене сообщениями.
    Ответ написан
    9 комментариев
  • Поиск частоты сигнала?

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

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    1. Математически формализовать понятие "наиболее точный", составить формулу метрики.
    2. Выбрать все интервалы, где :value BETWEEN `start` AND `end` и посчитать для них метрику.
    3. Отсортировать по метрике.
    4. Выбрать первую строку из сортированного списка.
    Ответ написан
    5 комментариев
  • Какие алгоритмы для парсинга текстовых строк являются самыми быстрыми?

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Создать массив X[1..N]
    Заполнить его X[i] = i
    Сделать много (например, N) перестановок случайных элементов X[rand(1..N)] <=> X[rand(1..N)]
    Взять M первых элементов
    Ответ написан
    Комментировать
  • Что в ядре сортировки?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Стандартом не оговорено, а значит каждый движок может использовать свой алгоритм. Главное соблюдать стандарт на вызов и результат.
    Ответ написан
    Комментировать
  • Алгоритм Диффи — Хеллмана, какова должна быть длина ключа?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    343 - это уже не три бита. Три бита - это числа от 0 до 7.
    Из вики:
    В практических реализациях для a и b используются числа порядка 10100 и p порядка 10300.

    Соответственно, ключ будет порядка 10300 или 21000.
    Ответ написан
    Комментировать
  • Как правильно генерировать псевдослучайные числа?

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Тут основная проблема в том, что для компьютера, при использовании чисел одинарной точности, 4.63710 = 100.1010001100010010011012 = 4.636999607110, то есть точно посчитать количество десятичных знаков после запятой невозможно. Приблизительно можно считать беря дробную часть числа. Если эта часть близка к нулю (r < epsilon) или к единице (1-r < epsilon), то, с какой-то вероятностью можно сказать, что мы посчитали длину дробной части. Если нет - то умножаем дробную часть на 10, увеличиваем счётчик и проверяем сначала.
    Ответ написан
    8 комментариев
  • Как найти дубликаты в массиве 64-битных чисел по (битовому) расстоянию Хэмминга?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Расстояние Хэмминга на MySQL посчитать несложно.
    BIT_COUNT(HEX(:value1) ^ HEX(:value2))
    Но надо определиться с понятием "группы таких чисел". Возьмём три двоичных числа (001, 011, 111) и определим расстояния между ними.
    d(001, 011) = 1
    d(001, 111) = 2
    d(011, 111) = 1
    Таким образом, первое и третье числа находятся на расстоянии 1 до второго, но между собой они находятся на расстоянии 2. Если границей расстояния выбрать 1, то как должны сформироваться группы?
    Ответ написан
    8 комментариев
  • Как оптимизировать алгоритм для нахождения числа с 500 делителями?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Для разложения числа на множители проверяют не все варианты подряд, а только простые числа. Таблицу можно подготовить заранее или генерировать в программе. Для разложения числа N0 надо проверять простые числа до N01/2 включительно. После каждого найденного множителя текущее значение Ni делится на него и перебор простых чисел начинается сначала.
    Получается разложение вида
    N0 = p1n1·p2n2·...·pknk, где pi - все простые числа от 2 до N01/2.
    Количество различных делителей K получается как количество комбинаций степеней
    K = (n1+1)·(n2+1)·...·(nk+1)
    На примере:
    N0 = 72
    Простые числа до 721/2: pi = [2, 3, 5, 7]
    Инициализируем счётчики степеней: ni = [0, 0, 0, 0]
    72 на 2 делится, n1 = 1, проверяем 72/2 = 36
    36 на 2 делится, n1 = 2, проверяем 36/2 = 18
    18 на 2 делится, n1 = 3, проверяем 18/2 = 9
    9 на 2 не делится
    9 на 3 делится, n2 = 1, проверяем 9/3 = 3
    3 на 2 не делится
    3 на 3 делится, n2 = 2, 2/3 = 1, закончили поиск.
    Получили массив степеней: ni = [3, 2, 0, 0]
    Количество делителей: K = (3+1)·(2+1)·(0+1)·(0+1) = 12
    Ответ написан
    4 комментария
  • Есть алгоритм, где шифрованный текст разный, а дешифрованный одинаковый?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Обычная асимметричная схема.
    Баш-скрипт в URL передаёт случайную строку запроса, сервер шифрует её своим ключом, передаёт обратно скрипту. Если после расшифровки парным ключом строки совпали - бинго.
    Ответ написан
    3 комментария