Ответы пользователя по тегу Алгоритмы
  • Сгенерировать 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 комментария
  • Как определить входит ли координаты в круг?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    1. Записать маршрут в базу данных, например MySQL умеет работать с географическими данными.
    2. Определять отклонение от маршрута (ST_Distance), если больше заданного - оповещать.
    Ответ написан
  • Алгоритм, как вписать прямоугольник в трапецию?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    В общем случае задача решения не имеет. В частном, когда основание трапеции параллельно одной из осей, есть бесконечное множество решений.
    Ответ написан
    1 комментарий
  • Как проверить два *.txt на наличие совпадений по словам на C?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Для начала надо определиться, что значит "одинаковые слова". Если важен смысл слов, то это непросто (идти, иду, пойду, шёл - одно и то же слово).
    Если слово берёте просто как цепочку символов, то всё проще. Открываете файл через open(name, O_RDONLY | O_BINARY), пишете подпрограмму, которая читает файл посимвольно, пропускает всё до первой буквы, читает пока не встретится небуквенный символ, возвращает слово. В основном цикле получаете из подпрограммы слово, записываете его в словарь. Если пишете на чистом C, то словарь придётся реализовать самому, например как дерево.
    Затем также читаете второй файл и ищете слова в собранном словаре.
    Ответ написан
    3 комментария
  • Как нарисовать только часть окружности, заданной точками кривой Безье?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    1. Если отрезок P0P2 делит окружность пополам, значит центр окружности лежит на этом отрезке.
    2. Из условия непонятен радиус окружности. Если она должна проходить через точки P0 и P2, то центр окружности лежит на середине отрезка.
    3. Раз отрезок делит окружность пополам, то дуга будет начинаться от угла вектора P2P0, и заканчиваться на ±π от этого угла. Направление вращения определяется положением точки P1 относительно вектора P2P0.
    Ответ написан
    Комментировать
  • Java. N ферзей, на доске, нужен алгоритм для проверки, "а что, если ферзь может стоять на том же месте" или как найти все способы?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Самый очевидный алгоритм:
    Очевидно, что в одой вертикали или горизонтали не может быть двух ферзей. Таким образом, все варианты можно представить как перестановки N чисел от 1 до N, где позиция числа - это номер вертикали, а само число - номер горизонтали. Остаётся сгенерировать такие перестановки и проверить в них диагонали, если |Pi-Pj| = |i-j|, то ферзи стоят на одной диагонали и позиция недопустима.
    Ну а дальше можно оптимизировать алгоритм, проверяя диагонали ещё на стадии генерации перестановок.
    Ответ написан
    Комментировать
  • Как рассчитать среднеквадратичное отклонение, если среднее значение неизвестно?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Формула в таком виде смысла не имеет.
    Причина: (i-1) * avg = SUM(Value0...Valuei-1), что, по вашим же словам, в память не поместится.
    Можно считать среднее блока (например, 100 чисел), затем суммировать эти средние и делить на количество блоков. Продолжая алгоритм, средние для каждых 100 блоков можно считать отдельно, как суперблок, затем суммировать их и т.д.

    Точное значение среднего квадратического отклонения без знания среднего арифметического не посчитать. Соответственно, надо знать, что представляют из себя эти числа. Вполне может быть, что достаточно взять небольшую случайную выборку, чтобы получить оценочные значения нужных параметров.
    Ответ написан
    Комментировать
  • Хорош ли мой подход к созданию своего алгоритма движка разбора JSON, XML, HTML, CSS? А что насчет разбора кода на ЯП?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Для начала изучите то, что было придумано до вас. Начните, например, с книги красного дракона.
    Ответ написан
    1 комментарий
  • Как можно улучшить программу(алгоритм) для поиска чисел-вампиров? Возможно ли такое?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Вот вам слепленный на скорую руку вариант на Javascript
    a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    for (d1 = 1; d1 <= 9; d1++) {
      a[d1]++;
      for (d2 = 0; d2 <= 9; d2++) {
        a[d2]++;
        for (d3 = d1; d3 <=9; d3++) {
          a[d3]++;
          for (d4 = (0 == d2 ? 1 : (d1 == d3 ? d2 : 0)); d4 <= 9; d4++) {
            a[d4]++;
              val1 = d1*10+d2;
              val2 = d3*10+d4;
              val = val1*val2;
              b = [a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9]];
              b[val%10]--;
              b[Math.floor(val/10)%10]--;
              b[Math.floor(val/100)%10]--;
              b[Math.floor(val/1000)]--;
              diff = 0;
              for (i = 0; i < 9; i++)
                diff |= b[i];
              if (0 == diff)
                console.log(val1, val2, val);
            a[d4]--;
          }
          a[d3]--;
        }
        a[d2]--;
      }
      a[d1]--;
    }
    Ответ написан
    1 комментарий
  • Как реализовать рекурсивную функцию волнового алгоритма на языке c?

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

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Без явных условий, но с плавающей арифметикой, посему неточно:
    sqrt(pow(x1+x2-x3-x4))
    С одним условием при положительных числах:
    x = x1+x2-x3-x4;
    if (0 > x) x = -x;
    Ответ написан
    Комментировать
  • Какой алгоритм работы у консоли, когда в ней пишешь название приложения и команду?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Консоль ничего не знает. В простейшем случае (если набрана одна команда без пайпов и перенаправления потоков):
    Когда вы набираете строку и нажимаете Enter сначала из строки отделяется первая подстрока до пробела (или конца строки, если пробелов нет). Остаток строки будет передан выполняемой команде как аргументы.
    Затем проверяется, не является ли эта подстрока внутренней командой шелла. Если да, то выполняется эта команда.
    Если это не внутренняя команда и не указан полный путь к файлу, то идёт поиск файла с таким именем в каталогах, перечисленных в строке окружения PATH. Если файл найден и у пользователя есть права на его запуск, то он запускается.
    Если указан полный путь (например, /usr/bin/perl), то поиск не производится, идёт только проверка на права запуска.

    PS. Если речь о досовском/виндовом cmd, то он ищет файлы добавляя расширения .bat, .cmd, .exe, если расширение не указано явно. Кроме того, в нём поиск начинается с текущего каталога, а затем уже по переменной PATH.
    Ответ написан
    4 комментария
  • Как решить задачу на статическую балансировку?

    Rsa97
    @Rsa97
    Для правильного вопроса надо знать половину ответа
    Точное решение можно получить только полным перебором, MN вариантов. Приближённое - эмпирическими алгоритмами, например жадным.
    Ответ написан
    Комментировать