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

    sergiks
    @sergiks Куратор тега PHP
    ♬♬
    PHP_INT_MAX это обычно 31 бит (не меньше), поэтому можно взять функцию crc32(), например, и обрезать старший бит:
    <?php
    for($i=0; $i<=10; $i++) {
    	echo "$i - " . f($i) . "\n";
    }
    
    function f($s) {
    	return crc32($s) & 0x7FFFFFFF;
    }
    /*
    0 - 1960566561
    1 - 64810935
    2 - 450215437
    3 - 1842515611
    4 - 1941314360
    5 - 78719918
    6 - 498629140
    7 - 1790921346
    8 - 2046842643
    9 - 218589061
    10 - 559752673
    */
    Ответ написан
    Комментировать
  • Какой алгоритм подойдет для описания полета насекомого?

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

    Очередную точку ставить на плоскости случайно, в любом месте внутри допустимой области. Эта точка – цель, к которой стремится следующая, невидимая точка: каждый следующий кадр её координаты изменяются на k * векторИзТекущегоПоложения-в-Цель:
    x = x + k * (xTarget - x);
    y = y + k * (yTarget - y);

    Так «преследователь» замедляется, по мере приближения к цели, никогда её не достигая.

    Эта невидимая точка – не одна. К ней, как к цели, стремится следующая. К той ещё одна. Наконец, сама муха по этому закону стремится к хвосту этой цепи - очередной точке.

    Чем больше звеньев в такой цепи, тем плавнее получается кривая. При приближении мухи к цели ближе, чем на D, генерится следующая случайная цель.

    Сделал рабочий пример.

    Можно поменять алгоритм и сделать, скажем, линейную скорость постоянной. Или случайно варьировать параметры k и D – от этого поменяется скорость и траектория от плавной ближе к ломаной.
    Ответ написан
    Комментировать
  • Случайное число с заданной вероятностью, какой алгоритм?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Делают длинный диапазон, составленный из отрезков, пропорциональных вероятностям.
    0..22 : "0"
    22..22+19=41: "1"
    41..41+16=57: "2"
    ...
    ..100: "8"

    Выбор из него с линейной вероятностью даст желаемое распределение.

    Например, выпало 56 – попадает в диапазон, относящийся к "2"
    Ответ написан
    1 комментарий
  • Как написать алгоритм поиска соседних элементов?

    sergiks
    @sergiks Куратор тега JavaScript
    ♬♬
    Идея с отдельной работой по X и по Y неплохо работает. На каждом кадре проверяем каждую из 200 точек (это совсем не много).

    Сортируем массив точек по их X-координате. Двигаемся слева направо, выбирая очередную точку.

    Смотрим от неё влево (чтобы не проверять одну связь дважды, выбираем полуплоскость от точки) и отбираем только те точки, чей X отличается не более, чем на radius.

    Из них смотрим только на те, у которых Y не более, чем на radius отличается (уже в любую сторону: и вверх и вниз).

    У них проверяем уже евклидово расстояние – корень из суммы квадратов расстояний по X и по Y – чтобы было не больше radius. У таких есть «связь» – рисуем им ребро.

    Работающий fiddle (неминифицированный исходник на github)
    538264abb31847baa28fe05e015ac13c.png

    На компе даёт около 60 fps, на мобильнике от 40 до 55, т.е. совершенно приемлемая скорость при 200 точках.

    Первая версия ответа

    Интересна ситуация, наихудшая для оптимизации: когда за 1 кадр может поменяться максимальное число связей. Предположу, что это сетка из равносторонних треугольников, где длина ребра равна «триггерной» дистанции:
    картинка треугольной сетки
    5297fe1c584f4551aca5b77a2a987549.jpg
    Тут большинство точек, кроме крайних, взаимосвязаны. У каждой по 6 ближайших соседей. Примерно 200 * 6 / 2 = 600 связей (чуть меньше из-за краёв).

    Если такую сетку пропорционально увеличить на любую малую величину, сразу все связи порвутся, их станет ноль. Пусть на месте останется, скажем, левый верхний угол сетки. Тогда наибольший путь проделает нижний правый угол. Тут вопросы к особенностям вашей задачи:
    1. округляются ли координаты до целых или до какой-то точности?
    2. какой наибольший путь может проделать за один кадр точка?

    В идеальном мире всем достаточно проделать бесконечно малый шаг, и, вуаля!, было 600 связей, стало 0. Такой же шажок назад – не было связей, и вот их 600. Т.е. надо бы в каждый кадр проверять 600 ребер. Считать это за теоретический предел оптимизации?

    Сущности
    Точки и рёбра. Ребро ссылается на две точки. Точка ссылается на рёбра. Ребро имеет длину и, в зависимости от длины, может быть «видимым».

    Важнее всего следить за рёбрами, длина которых близка к пороговой – и с меньшей и с большей стороны. Такие стоит проверять почти каждый кадр, т.к. статус ребра может поменяться за один кадр. Прочие рёбра и кандидаты в рёбра проверять можно изредка.

    Можно давать рёбрам веса, пропорциональные желаемой частоте их обновления. Скажем, от 0 до 1. Вес равный 1 значит, что нужно проверять каждый кадр. Например, вес W = Math.max(0, D - Math.abs( length - D))/D, где D – пороговая дистанция.

    Остаётся сделать механизм, отбирающий рёбра в работу на очередном кадре, исходя из их весов. Запоминать время, когда ребро было обновлено. Приоритет его попадания в обработку равен W * (time - timeUpdated)
    Ответ написан
    3 комментария
  • Как вычислить пересекаются ли много многоугольников?

    sergiks
    @sergiks Куратор тега JavaScript
    ♬♬
    Вкратце:
    1. набросать фигуры по сетке. Пусть они где-то накладываются, где-то выходят за границу полотна.
    2. дать им «расслабиться» – будто они льдины, свободно плавающие. И при этом взаимно-отталкиваются. Для упрощения можно посчитать, что каждая точка отталкивается от всех точек других фигур, сила пропорциональна квадрату расстояния. Просчитать несколько «шагов» такого плавания.

    Для определения, пересеклись ли полигоны, как уже написал Хасан Истамкулов, надо проверять пересечение отрезков. Если у двух фигур найдётся, что какие-то два отрезка пересеклись, значит есть коллизия:
    8186a53eefde4e0dbbba93ce279bf961.png
    Ответ написан
    Комментировать
  • Как правильно организовать продажу билетов?

    sergiks
    @sergiks Куратор тега PHP
    ♬♬
    «Бронировать» билеты на время в один клик:

    1. Показывать все доступные билеты, где ни "куплен" ни "забронирован".
    2. По клику на билет AJAX'ом помечать его как забронированный под данного юзера: записывать в поле id юзера. В другое поле - время установки брони. Статус брони снимать автоматом через час-два-три.
    3. Так пользователь увидит выбранные билеты, которые гарантированно не куплены ещё.
    4. Оплатит или не оплатит их.
    Ответ написан
  • Как разобраться в битовых масках или как их там?

    sergiks
    @sergiks Куратор тега ВКонтакте
    ♬♬
    Про двоичное представление чисел вы же в курсе?
    0 = 0000 0000
    1 = 0000 0001
    2 = 0000 0010
    3 = 0000 0011
    4 = 0000 0100
    5 = 0000 0101
    6 = 0000 0110
    7 = 0000 0111
    8 = 0000 1000
    9 = 0000 1001

    ... и так далее. До 232 или даже до 264 - зависит от системы, 32- или 64-битной и языка программирования.

    Позиции битов считаются справа налево. Крайний правый бит имеет позицию 0. Позиция бита – это степень двойки. Если бит установлен в 1, надо прибавить 2 в степени этой позиции.

    Например, число 3 = 0000 0011 означает 20 + 21 = 1 + 2 = 3.

    Примечательно, что степени двойки – 0, 1, 2, 4, 8, 16, 32, 64, ... – выражаются всего одним включённым битом, одной единичкой, остальные биты – нули.

    Битовые маски – это договорённость, что каждый бит (каждая позиция) значит что-то определённое, что может быть включено или выключено, 1 или 0. Как линейка выключателей.

    Например, с разрешениями ВКонтакте:
    1 - бит 0 - notify
    2 - бит 1 - friends
    4 - бит 2 - photos
    8 - бит 3 - audio

    У ВК линейка длинная, состоит из 32 «выключателей».

    Допустим, вашему приложению требуются разрешения photos и audio – биты 2 и 3 надо установить в 1, остальные 0. Это можно сделать простым сложением: 22 + 23 = 4+8 = 12. В двоичной системе: 12 = 0000 0000 0000 1100

    Для удобства вычисления ВК прямо пишут значения, которые надо прибавить, чтобы получить нужную битовую маску – итоговое число, которое вы передадите в метод АПИ для запроса разрешения.

    Ещё один пример, вам требуется стена wall и offline доступ в любое время. Смотрите в таблице, какие там числа: wall (+8192) и offline (+65536). Значит, вам нужно просить разрешения для маски 73728
    Ответ написан
    Комментировать
  • Как найти необходимую ширину и высоту трех изображений?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    W ширина области, в которую надо вписать комплект картинок
    H высота области.

    У n-й картинки:
    • iwn - своя ширина
    • ihn - своя высота
    • kn = iw / ih пропорция


    Для каждой, в итоге, надо найти индивидуальный коэффициент масштабирования sn.

    Сложив пропорции w/h картинок, получим пропорцию их блока, когда все одной высоты:
    K = k0 + k1 + k2
    • К == W/H области, куда надо вписать конструкцию значит что картинки идеально впишутся
    • К > W/H значит, высота будет недостаточна, останется место сверху и снизу.
    • К < W/H значит, высота впишется, а слева+справа останется лишнее место - его за счёт межкартиночных интервалов можно распределить.


    Исходя из сравнения считаем высоту блока Hb. Она либо равна W / K, когда K > W/H; либо равна H.

    Теперь остаётся сосчитать индивидуальные коэффициенты:
    sn = Hb / ih

    На этот коэффициент нужно умножить начальные размеры картинки.
    Ответ написан
    1 комментарий
  • Как вывести даты в заданном диапазоне, конкретных дней недели?

    sergiks
    @sergiks Куратор тега JavaScript
    ♬♬
    Метод объекта Date setDate() устанавливает день месяца, при необходимости обновляя и месяц.

    Т.е. алгоритм простой: в включённым дням недели прибавлять по 7 дней, и считывать получившуюся дату.
    Примерно так:
    /**
     * Make Dates according to selected days of week till the specified date
     * @param Array weekdays: 0 - Sunday, 1 - Monday, ..
     * @param Mixed Date or String - last day of range
     *
     * @return Array of Date objects
     */
    function getDates( weekDays, lastDate) {
      if(typeof lastDate === 'string') lastDate = new Date(lastDate);
      
      var today = new Date(), dow, i, D, datesPool = [], result = [];
      today.setHours(0);
      today.setMinutes(0);
      today.setSeconds(0);
      dow = today.getDay(); 
      for(i=0; i<7; i++) {
    	  if( !~weekDays.indexOf( (dow + i)%7)) continue;
    	  D = new Date();
    	  D.setTime( today.getTime());
    	  D.setDate( D.getDate() + i);
    	  if( D.getTime() > lastDate.getTime()) continue;
    	  datesPool.push( D);
      }
      
      if( datesPool.length === 0) return result;
      
      while(true) {
    	  for( i = 0; i < datesPool.length; i++) {
    		  D = datesPool[i];
    		  if( D.getTime() > lastDate.getTime()) return result;
    		  if( result.length > 1000) return result;
    		  result.push( "" + D.getDate() + "." + (1 + D.getMonth()) + "." + D.getFullYear().toString().substr(2));
    		  D.setDate( D.getDate() + 7);
    	  }
      }
    }
    
    getDates( [2,3], '2017-07-31') // 19.7.17,25.7.17,26.7.17

    Ответ написан
    Комментировать
  • Как рассчитать необходимую ширину и высоту двух изображений?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Есть 2 изображения со значениями ширины и высоты (w1,h1) и (w2,h2). Известна суммарная ширина двух изображений после трансформации: W.

    Требуется найти коэффициенты k1 и k2 пропорционального масштабирования двух изображений, чтобы изменённые изображения:
    1. имели одинаковую высоту: k1 * h1 = k2 * h2
    2. в сумме дали нужную ширину W: k1 * w1 + k2 * w2 = W


    Решите эту систему уравнений. У меня получилось
    k1 = W / ( w2 * ( h1/h2 + w1/w2))
    k2 = k1 * (h1/h2)
    Ответ написан
    7 комментариев
  • Как равномерно разыграть подарки?

    sergiks
    @sergiks Куратор тега PHP
    ♬♬
    Уточнения:
    нужно N событий псевдослучайно распределить по времени так, чтобы в «ячейку» одного дня не попадало больше, чем K событий. При этом запрос с параметрами приходит разово, и нужно сразу ответить выигрышный он или нет.

    Решение: динамически считать вероятность выигрыша, в зависимости от текущей даты, числа выигрышей в этот день и остатков: призов и дней до окончания.

    Вероятность, в итоге может быть нулевой (если достаточно выигрышей в этот день), 100%, если остаток призов велик, а дней недостаточен, и где-то между 0 и 100% в остальных случаях. Формулу составьте сами.

    Для вероятности $prob от 0 до 100% выигрыш определять примерно так:
    $win = rand(1, 100) <= $prob;
    if( $win) { // вы выиграли! }


    Старый ответ:
    Действительно случайное распределение не исключает попадания в т.ч. и 10 розыгрышей на 1 день. Но т.к. ваша аудитория не искушена в теории вероятностей, просто воспользуйтесь N раз сервисом random.org:
    1. если N < числа дней выберите N дней из диапазона;
    2. в эти дни разыгрывайте по 1 призу – на том же change.org с прямой видеотрансляцией процесса.
    Ответ написан
  • Как взять элементы по парам?

    sergiks
    @sergiks Куратор тега JavaScript
    ♬♬
    Последовательно разбить в пары можно, например, так:
    var data = [{x:0,y:1}, {x:1,y:1}, {x:4,y:1}, {x:5, y:7}]
      , pairs = []
      , i
    ;
    
    for( i = 0; i < data.length; i++) { // перебираем входные элементы
      if( i % 2 === 0) pairs.push([]); // четный – добавляем новую пустую «пару»
      pairs[ pairs.length - 1].push( data[i]); // в последнюю пару добавляем элемент
    }
    
    JSON.stringify( pairs ) // [[{"x":0,"y":1},{"x":1,"y":1}],[{"x":4,"y":1},{"x":5,"y":7}]]


    Если же вы хотите разбить их в пары не по положению в исходном массиве, а в зависимости от расстояния между ними на поле, это совсем другая история. Уточните вопрос.
    Ответ написан
  • Как аутентифицировать пользователя используя HMAC?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Пример использования – ВКонтакте и его iFrame приложения. Когда пользователь запускает приложение, нажав ссылку в ВК, открывается iframe сервера разработчика. ВК отправляет туда пользователя с некоторыми параметрами – среди них id пользователя ВКонтакте и прочие. И подпись (параметр auth_key), вычисляемый как md5 хэш от параметров, которые важно защитить от подделки пользователем, и «секрета» приложения.

    Т.е. схема приемлема, когда есть три стороны: сервер ВК, сервер приложения и «ненадёжный» юзер, который, возможно, захочет подделать передаваемые от ВК приложению параметры. «Секрет» известен только серверу ВК и серверу приложения. Вычисляемый на его основе хэш гарантирует целостность и неподдельность данных.

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

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Парабола подойдёт? y = 100 - 100 * sqrt( x / N) (N – время, когда результат становится нулём)
    80e67e9beec44172b96322f4d832ea83.png
    Примерно в ваши точки ложится парабола с такими параметрами:
    y = 100 - 100 * sqrt( x / 176000)
    be47111e76a34a82b135672a3ee25914.png
    (здесь проценты в 1000 раз больше для пропорционального графика)

    Или, чтобы не так резко падало значение в первые моменты, можно взять смещённую логарифмическую кривую y = 100 - 30 ln( 1 + x / 10000)
    ab5f3ddc2f2d43eca10a1b7867704089.png
    Ответ написан
    2 комментария
  • Как разделить значения массива на разные части?

    sergiks
    @sergiks Куратор тега PHP
    ♬♬
    Похоже на задачу об упаковке в контейнеры (англ. "bin packing"). Алгоритмов много. Можно решить быстро и неоптимально (first fit), получше (best fit) или очень долго и оптимально (алгоритм MTP (8Mb pdf, на англ.)).

    First fit – идти последовательно по числам и класть их в текущий контейнер, пока помещаются. При наполнении/переполнении переходить к следующему контейнеру.

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

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Вы хотите построить упрощённую модель распространения заболевания? Чтобы что получить на выходе – число больных по дням, визуализировать как-то процесс? Я представил себе два разных подхода:

    1. брать исходную «конфигурацию» социума, этих 1000 человек – как граф их связей, через которые происходит заражение. Генерировать этот граф случайным образом. Выбирать исходного заражённого. И далее обходить граф по каким-то правилам. Можно ещё добавить вероятность передачи заражения, чтобы случайным образом определять на каждом звене – состоялась передача в этот день или нет. Усложнить можно, разбив людей на классы. Например, для ИППП как минимум, мужчины/женщины и только гетеросексуальная передача. Или для инфекций, передающихся бытовым путём рассмотреть распространение от работника заведения массового питания.

    2. без графа, просто добавить вероятности заражения от каждого каждому. Можно все сделать одинаковыми, напр., 60%. И каждую передачу в каждый день пробрасывать через генерацию очередного случайного числа – состоялась или нет.

    Ну и погуглите научные исследования распространения эпидемий (например), или визуализации / игры на эту тему.
    Ответ написан
    Комментировать
  • Как эффективно определить сближения траекторий с учетом времени?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Двигаться по оси времени, считать взаимные расстояния во всех комбинациях. Для пар, где расстояние оказалось меньше 250 м записать пару и timestamp
    {
        timestamp1: [ [id1, id2], [id35,id42], ... ],
        timestamp2: [ [id1, id2], [id23,id24], ... ],
    }

    Потом по этим данным можно снова вытащить нужные координаты и отобразить участки сближений.

    Оптимизировать можно с учётом доп. условий – напр. известно, что это воздушные шары и их скорость не может превышать некое значение. И тогда если какой-то шар удалён на значительное расстояние, его можно не проверять следующие X секунд, например.
    Ответ написан
  • Алгоритм превращения одноуровневого списка в двухуровневый?

    sergiks
    @sergiks Куратор тега JavaScript
    ♬♬
    Надо двигаться по значениям, по одному, запоминая текущий «класс» значения. При смене создавать новый подмассив, в который пихать очередное значение.

    Рабочий пример:

    // классификатор – возвращает название класса
    // к которому относится переданное значение
    // неважно, как называть классы, лишь бы по-разному
    function classify(i) {
    	if(  typeof i === "number") return "my_number";
    	return "my_string";  
    }
    
    // группирует в подмассивы идущие подряд
    // значения одного класса
    function group(a) {
      var i, item, c={prev:null, curr:null}, result=[], to;
      
      for(i=0; i<a.length; i++) {
        item = a[i];
        c.curr = classify(item);
        if(!c.prev || c.prev !== c.curr) {
          c.prev = c.curr;
          result.push([]);
          to = result[result.length-1];
        }
        to.push(item);
      }
      return result;
    }
    Ответ написан
    Комментировать
  • Какой есть алгоритм вывода средств с банкомата?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Приоритет алгоритма – стараться выровнять кол-во остающихся купюр.

    Надо посчитать разброс количеств номиналов после выдачи, и выбрать вариант, после которого этот разброс минимален среди всех вариантов. Под словом «разброс» понимать среднее квадратичное отклонение.

    Когда каких-то купюр не осталось, надо показывать предупреждение, что «Банкомат выдаёт купюры достоинством X и Y», и если запрошенная сумма не составляется имеющимся набором, предлагать ближайшую больше, и ближайшую меньше, которые выдать может.
    Ответ написан
  • Как определить функцию линейного графика?

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Берём бесплатную программу GeoGebra. Запускаем. В строке внизу вводим первую точку:
    A = (0.5, -85)
    Появляется эта точка на графике, только её не видно сразу – она далеко внизу. Поэтому зумом отъезжаем назад, чтобы точку А стало видно. Вводим вторую точку:
    B = (0.75, 0)
    На графике теперь видны обе точки. Теперь надо через них провести прямую. В палитре линий выбираем иконку линии-через-две точки:
    2ba2e4d629ea445380b095bbaaf3a951.png
    и кликаем по разу на каждой – появляется линия a и её уравнение:
    661d4b2c14de442fa43ed64d0e8b3609.png
    Которое можно через правый клик мышки привести к виду y = ax + b:
    y = 340x - 255
    Ответ написан
    2 комментария