Ответы пользователя по тегу Алгоритмы
  • Как решить задачу по методу Монте-Карло?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Если я правильно понимаю,
    весь диапазон:
    0 - 28, 28 - (28+72), (28+72) - (28+72+100) = 0 .. 200

    Как я понимаю, вопрос, какой интервал на этом отрезке займут соотв. "7" значения:
    от 28 / 200 до (28+72) / 200
    Ответ написан
  • Как избавиться от бликов на фото матовой бумаги по опорным точкам?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    В программах обработки фото есть функция корректировки «баланса белого» – это для коррекции на цвет освещения (пасмурный день / лампы накаливания). Тыкаешь пипеткой на участок изображения, заведомо нейтрального цвета, например, специальную серую картонку, и вычисляется коррекция оттенков для всего изображения, цвета становятся правдоподобнее.

    Контраст регулируется примерно так же. Пипеткой для «чёрного» тык на участке заведомо чёрном – и уровни корректируются, делая этот цвет настоящим чёрным. Это влияет на всё изображение и более тёмные участки сделаются тоже плоским-черным, потеряв детали.

    То же с самой светлой областью. Тоже своя пипетка.

    Так тремя сэмплами — нецветной областью, самой тёмной и самой светлой — можно по-быстрому скорректировать изображение.

    Какая за этим стоит математика не подскажу, надо изучать вопрос.
    Вот на SO обсуждали.
    Ответ написан
    Комментировать
  • Как создать матрицу смежности на основе 2D карты?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Поскольку «порталов» не предусмотрено, в любую ячейку можно попасть максимум из 4-х соседних.

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

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    f(1, 1) = 100
    f(1, 95) = 1.05
    f = ?

    Это две точки. Через них можно провести прямую и бесконечное число кривых.

    Уравнение прямой через две точки
    Для прямой через две заданные точки формула
    x - x1      y - y1
    -------  =  -------
    x2 - x1     y2 - y1

    Две точки шанс-выигрыш: (1, 100) и (95, 1.05) дают такое уравнение прямой:98.95 * x + 94 * y = 9498.95
    График
    5db0876180897208100664.png
    Ответ написан
  • Как вычислить, принадлежат ли координаты этому графику?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Представьте, как бы условно выпиливали эту деталь из листа металла на станке с ЧПУ.

    1. Наверное, сначала прямоугольник, включающий деталь. Проверьте по этим условиям точку.
    2. Потом вырезали круглую дыру – проверьте расстояние от точки до центра (1, 2) — должно быть >=2
    3. Затем, что она не лежит выше прямой через [(-4, -1), (-2, 2)]
    4. Затем, что она не лежит выше прямой через [(3, 2), (4, 0)]
    Ответ написан
  • Как перевести число в 16-ричное представление?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Псевдокод:
    if (0 <= A  &&  A < 10) return (string) A;
    else // тут уже сами допишите


    А вообще вот.
    Ответ написан
    Комментировать
  • Как сделать рандомайзер с возможностью проверки цепочки?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Перемешивать биты в порядке, определяемом «секретом». Так при фиксированном числе бит один диапазон однозначно отображается в такой же, в псевдослучайном порядке, т.е. 1, 2, 3 на входе даст «случайно» разбросанные на выходе.

    Такое отображение множества называет биекция (bijection).

    Например, зеркалить порядок битов, а там, где у секрета "1", попарно ещё раз менять местами.
    Для байта:
    10101101  // вход: 173
    10110101  // отзеркалили = 181
    01010000  // секрет = 80
              // поменяли местами где "1" в секрете
    11100101  // получилось 229


    Но надо что-то придумать с диапазонами.
    0 .. 0x3FFF это 14 бит. На входе, видимо, надо тоже 14, хотя можно домножить.
    Ответ написан
    Комментировать
  • Как найти арифметическую прогрессию в списке?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Для первого числа построить массив разниц с каждым из остальных, что правее.

    Для второго массив разниц с теми, что правее.
    И так для всех.

    Затем в массивах этих разниц найти хотя бы два одинаковых.
    Ответ написан
  • Как быстро сгруппировать набор точек (2500х2500) по ячейкам Вороного?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    По контрольным точкам диаграммы: которая из них ближайшая к очередной точке - в тот массив заносим.

    Можно оптимизировать: все ячейки д.в. выпуклые, поэтому если две несоседние точки обе принадлежат одной ячейкке, то и все точки между этими двумя – тоже.
    Ответ написан
    Комментировать
  • Как вычислить 9**(9**9) не потратив на это огромное количество времени?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Алгоритм:
    1. ручкой пишем на бумаге первые несколько степеней 9
    2. в голове появляется догадка
    Ответ написан
    3 комментария
  • Как считать RPS, если соединение устанавливается от 0 до 5 секунд?

    sergiks
    @sergiks Куратор тега JavaScript
    ♬♬
    Запросы имеют протяжённость во времени.
    Начало запроса — отправка запроса клиентом.
    Окончание – завершение получения данных клиентом и закрытие соединения.

    Неизвестно тут, что сервер считает за отметку времени запроса: его начало, конец, или что-то ещё.

    Допустим, разрешены 3 запроса в 1 секунду.
    Отправил 3 одновременно. Но 2 из них призадумались и тянутся по 5 секунд каждый, а один отыграл за 500 миллисекунд. Когда можно отправить ближайший следующий запрос?
    |--------------------|
    |--------------------|
    |--|
    0-----1-----2-----3--

    Гарантированно можно через 1 секунду после завершения 3-го быстрого, т.е. через 1500мс со «старта».

    И можно эвристически порисковать и чуть уменьшить эту паузу с окончания очередного запроса.

    Можно держать N «дорожек» – по числу одновременных запросов в единицу времени. И ставить очередной запрос на первую освободившуюся «дорожку».
    Ответ написан
    Комментировать
  • Как можно выбрать главные числа?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Находить среднее и брать навыки, которые выше среднего = (сумма указанных процентов) / количество?
    Поскольку порядок тоже имеет значение, при равных процентах считать весомее более ранний навык.
    С количеством в выборке уже решать вручную: сколько взять навыков из 10 по 100% каждый.

    физика 50%, химия 49%, биология 48%, английский 10% -----> главные будут физика, химия, биология.
    (50+49+48+10)/4 = 39.25 – выше желаемые три: физика, химия, биология. ОК

    физика 50%, химия 9%, биология 8%, английский 7% -----> главным будет только физика.

    (50+9+8+7)/4 = 18.5, выше только физика, ОК

    физика 50%, химия 49%, биология 49%, английский 48% -----> главными будут физика и химия.
    (50+49+49+48)/4 = 49FAIL
    Тут не понятно, почему разорвать именно химию и биологию. Но если перед вычислением добавлять коэффициент за позицию [+3, +2, +1, +0], всё получается:
    (53+51+50+48)/4 = 50.5 рвёт точно как хотелось: физика и химия выше. OK

    физика 50%, химия 30%, биология 1%, английский 1% -----> главными будут физика и химия.

    (50+30+1+1)/4 = 20.6физика и химия FTW. OK

    физика 50%, химия 30%, биология 30%, английский 30% -----> главным буде только физика.
    (50+30+30+30)/4 = 35; выше 35 только физика. ОК
    Ответ написан
    Комментировать
  • Задачи с собеседований по максимальным числам: как решить?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Отсортировать по убыванию и двумя циклами – некошерно?
    на JS
    const maxprod = arr => {
      const a = arr.slice().sort((a, b) => b - a);
      const max = a[0];
      const len = a.length;
      let iter = 0;
        
      for (let i = 1; i < len - 2; i++) {
        iter++;
        const A2 = a[i];
        const x2 = max / A2;
        if (!Number.isInteger(x2)) continue;
          
        for (let j = i + 1; j < len - 1; j++) {
          iter++;
          const A3 = a[j];
          const x3 = x2 / A3;
          if (!Number.isInteger(x3)) continue;
          
          if (!!~a.indexOf(x3)) {
            return [max, A2, A3, x3, iter]);
          }
        }
      }
      
      return false;
    }

    По сути циклов три, т.к. indexOf() всё равно перебирает массив.

    Из оптимизаций только отсечение мелких хвостов, когда произведение становится меньше искомого.
    И проверка каждого кандидата на делимость.
    В хвост результата пихается ещё число итераций.

    Тесты
    [
      [20,5,3,2,2], // [ 20, 5, 2, 2, 3 ]
      [7,9,4,60,5,3,2,2], // [ 60, 5, 4, 3, 4 ]
      [1,2,3,199], // false
      [2430,2431,2431,2431,1,1,1,2,3,5,7,9,11,13,15,17,19,23], // [ 2431, 17, 13, 11, 8 ]
    ].forEach(test => console.log(test, maxprod(test)));
    Ответ написан
    5 комментариев
  • Как найти исходное число?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    только нейронными сетями надо решать!

    X = 0.7 * Y Что здесь сложного? Найдо найти все пары (X, Y), где оба целые ?

    То ли лыжи не едут..
    function search_start_value($price, $sale) {
      return $price * 100 / (100 - $sale);
    }
    echo search_statr_value(1499, 30); // 2141,4285714286
    Ответ написан
    3 комментария
  • Как решить задачу расстановки арифметических знаков между числами для получения другого числа?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Полным перебором можно считать каждый знак битом: 0 это плюс, 1 минус. Получается, надо перебрать все числа от 0 до 2^(n-1) и их двоичная запись кодирует знаки.

    Для оптимизации можно сначала проверить некоотрые крайние условия:
    • например, «все плюсы» должны быть >= S. Чтобы сразу отсечь проверку вариантов получения 1E9 из всего 1E6 единиц. Эта же проверка имеет смысл в процессе перебора, для оценки, дотянутся ли оставшиеся цифры до оставшейся до S суммы
    • Проверить четность - из четного числа нечетных не получить нечетное.
    • Подумать, что делать с одинаковыми числами, как-то отсечь их зеркальные комбинации.
    • Ещё подумать
    Ответ написан
    3 комментария
  • Какой может быть алгоритм заполнения матрицы?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    У вас же простой тетрис! ) Только вверх-ногами.

    Берёте случайную фигуру и пытаетесь её поставить так, чтобы она заняла клетки в самом верхнем ряду-с-дырками. Если это невозможно, случайно выбираете ещё раз из фигур шириной 1 (1x1, 1x2).

    Всё.
    Ответ написан
  • Какой алгоритм решения этой задачи можете посоветовать?

    sergiks
    @sergiks Куратор тега JavaScript
    ♬♬
    1. найти все подстроки,
    2. для каждой посчитать вес: сколько букв в ней совпадают регистром с деф.строкой
    3. взять с наибольшим.
    Плохая реализация
    // но тесты проходит
      function repairCase(src, input) {
        const len = input.length;
        if (len === 0) return '';
        
        const _src = src.toLowerCase();
        const _input = input.toLowerCase();
        let i, from = 0, maxWeight = -1, maxIndex = -1;
        while (i = _src.indexOf(_input, from), -1 !== i) {
          from = i + 1; 
          const match = src.substr(i, len);
          let weight = 0;
          for (let k = 0; k < len; k++) if (match[k] === input[k]) weight++;
          if (maxWeight < weight) {
            maxWeight = weight;
            maxIndex = i;
          }
        }
        
        if (-1 === maxIndex) return '';
        
        return src.substr(maxIndex, len);
      }
    Ответ написан
    Комментировать
  • Алгоритм на php или js - как из любого хэша получить числовое значение из интервала X-Y?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    да хоть разбить хэш на байты, сложить, взять остаток от деления на 10 и прибавить 5.
    Ответ написан
    3 комментария
  • Как определить хороший и добросовестный отзыв от плохого?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    От "Nnnnn" поможет проверка по словарю и длине отдельных слов выше критического порога.
    Но от случайного набора слов из словаря это никак не защитит.

    На самом сайте попробуйте измерять время, потраченное на заполнение отзыва. Слишком короткое может означать копипасту, либо легитимный заранее написанный в другой программе отзыв. Но несколько отзывов подряд с коротким промежутком времени - паттерн спама.

    С большим объёмом текстов можно попробовать развернуть анализ используемых слов и расстояний между ними - обучить на проверенных вручную точно-отзывах и массивах валидных текстовых комментов, может, с другого форума, где нет смысла в спаме и накрутке и все комменты можно считать валидными. Тогда получится проставлять новому комменту вероятность его спамовости/реальности и просить модераторов проверять только наиболее подозрительные из них, а также несколько случайно отобранных, отмеченных как валидные.

    Ещё одна странная идея: просить самих авторов к их рассказу придумывать ещё и по несколько вопросов для быстрой проверки, прочёл ли вообще критик это произведение? Не в лоб "Главного героя зовут: Вася / Толя / Оля" и не что-то, что ищется в тексте поиском. А абстрактно: «Этот рассказ: сочитает иронию и описания / описывает любовный треугольник / является философским эссе»
    Ответ написан
    4 комментария
  • Выбрать числа из множеств, чтобы они не пересекались?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    1. Выбираете 1-е число из полного диапазона.
    2. Выкидываете множество выпавшего числа.
    3. Выбираете 2-е число из оставшегося диапазона.


    Например:
    1. случайное из [0, 2346] оказалось 105 из диапазона "B"
    2. выкидываем диапазон B, остаётся [0, 1902], т.к. длина "B" 544-101+1 = 444, 2346 - 444 = 1902
    3. случайное из [0,1902] оказалось, например, 404. Для чисел выше 100 добавляем 444 и получаем 848 из диапазона "C" по старому стилю )
    Ответ написан
    Комментировать