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

    но про что обычно не пишут в книжках

    Что вы, в книжках как раз такое и пишут. Вот например, ваш вопрос про хранение хэшей паролей, а не их plain-text представления, наверняка прекрасно рассмотрен в книге https://www.amazon.com/Web-Application-Security-Be... . Это первое что мне попалось в поиске, но судя по индексу и содержанию, там это всё 100% будет.

    прочитав учебник, начинает чтото писать и только потом случайно узнает

    Да, возможно такое, учебник ведь не один нужно прочитать.

    Вы наверное уже хотите сказать - а прочитал ли я хотя бы по одной из книг на каждый приведённый вами пример? Нет, в целом я прочитал не так много книг. В какой-то момент я: а) начал делать законченные работающие вещи (приложения/скрипты/etc); б) устроился на работу; в) ещё до всего этого научился вовремя задавать себе вопрос "а правильно ли я делаю?". Количество источников информации повышалось: к книгам и лекторам добавились коллеги, потом добавилось чувство "что-то я говнокод пишу, нельзя ли получше". После этого гуглить и совершенствоваться приходится каждый день.

    Вы по большому счёту спрашиваете - где я могу найти сайт, чтобы пройти этот путь за N дней/недель. Вы не одиноки - все так хотят. Более того, многие думают, что "тот чувак" когда-то нашёл такой "сайт" и поэтому такой молодец теперь.

    Если бы был такой "сайт", сеньорам с 10-летним опытом, которые лет 15 (10 лет полноценного стажа ПЛЮС лет 5 обучения и подработок) собирали информацию из тысяч истоничков и испытывали её на себе, не предлагали бы зарплаты в сотни тысяч рублей.
    Ответ написан
    1 комментарий
  • Как посчитать координаты для дерева?

    На вашей картинке некий нелистовой узел располагается посередине того интервала (по оси X), который занимают его дочерние узлы.

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

    Прежде чем отрисовать неравномерную окружность, нужно выработать для себя определение неравномерной окружности. Лично я о такой не слышал.

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

    На практике не всегда удобно проходить по всему множеству точек и проверять принадлежность каждой из них к эллипсу. Бывает, что проще перевести уравнения кривой в параметрический вид, и вычислять значения точек для некоторого набора дискретных значений параметра. Вот параметрическое уравнение эллипса:
    https://wikimedia.org/api/rest_v1/media/math/rende...
    в котором параметр t это угол между осью абсцисс и лучом, проходящим через центр координат и некоторую точку на эллипсе (при этом мы условимся, что центр эллипса совпадает с центром координат).

    Таким образом, меняя значения t с 0 до 2*PI, мы получим множество пар (x, y) - это как раз и есть те точки, которые следует закрасить.

    Попытавшись реализовать эту идею, вы вероятно, спросите - с каким шагом изменять параметр t. Это хороший вопрос и ответ на него зависит от вашей задачи и от того, насколько точно вы желаете нарисовать эллипс. Кроме того, если вы будете рисовать отдельные точки, как написано выше, то даже при относительно небольшом шаге у вас не будет получаться непрерывная линия. Уменьшая шаг параметра, вы рано или поздно добьетесь непрерывно выглядящей линии, однако это может значительно увеличить время отрисовки. В качестве простой оптимизации, можете вместо отдельных точек рисовать линии между двумя последовательными точками. Тогда, вместо эллипса вы, фактически, будете рисовать многоугольник. Однако, с увеличением числа точек (т.е. с уменьшением шага параметра t), он все более будет похож на эллипс.

    Это самое простое, с чего вы можете начать.
    Ответ написан
    3 комментария
  • Как обойти максимальное количество ребер неориентированного взвешенного графа?

    Есть неориентированный взвешенный цикличный граф, задана вершина входа. Необходимо обойти максимальное число вершин а затем вернуться в исходную, при этом не привысив максимально допустимый вес (который тоже задан).

    Если я ничего не путаю но ночь глядя, то это задача коммивояжёра. Странно, что до сих пор про неё никто ничего не упомянул.

    Задача NP-полная, достаточно быстро (что-то около 60-70 вершин) становится трансвычислительной, для 200 вершин ни о каком полном переборе не может быть и речи. Советую посмотреть метод ветвей и границ.
    Ответ написан
    1 комментарий
  • Как организовать обработку сообщений от нескольких серверов?

    Nipheris
    @Nipheris Куратор тега C#
    Общая концепция и модель: раз и два.
    Конкретные реализации и протоколы: обмен сообщениями в чистом виде, независимо от платформы: AMQP, ZeroMQ; также, если речь про дотнет, можно попробовать WCF.
    Ответ написан
    4 комментария
  • Чем отличается архитектура приложения от его алгоритмов?

    Архитектура - это про то, из каких элементов ("черных ящиков") собирается система/подсистема.
    Алгоритмы - это про то, как наиболее низкоуровневые элементы ("черные ящики") и выполняемые ими функции реализованы с помощью последовательности действий.

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

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

    Точное определение алгоритма можно найти в других источниках.
    Ответ написан
    Комментировать
  • Как определить координаты тела, если оно движется по эллипсу?

    https://ru.wikipedia.org/wiki/%D0%AD%D0%BB%D0%BB%D...

    Отличие от окружности только в различающихся радиусах-коэффициентах a и b.
    Ответ написан
    Комментировать
  • Как найти разницу двух чисел в массиве рекурсивно?

    Навскидку:
    const D = 10
    int N = ...
    int a[N] = ...
    
    find(i, j, N):
    	d := a[j] - a[i]
    	if d = D then
    		return (i, j)
    	else if d < D then
    		if j + 1 == N then
    			return nil
    		else
    			return find(i, j + 1, N)
    		end
    	else if d > D then
    		if i + 1 == N - 1 then
    			return nil
    		else
    			return find(i + 1, j, N)
    		end
    	end
    
    find(0, 1, N);

    Сложность по идее O(2n). Вообще не очень красиво для рекурсивной реализации, но вроде рабочий вариант.
    Вторую задачу - сами.
    Ответ написан
    5 комментариев
  • Создание свого аудиоформата, с чего начать?

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

    Почему? Потому что чтобы превзойти существующие решения хотя бы в какой-то нише (напр., приемлемое качество речи при очень низком битрейте, или lossless-кодирование с высокой степенью сжатия) нужно хорошо поработать. Потом еще провести десяток-другой серьезных экспериментов, чтобы доказать преимущества вашего подхода в конкретных случаях (см. выше). Тогда в вашем кодеке будет реальная ценность, и вас, возможно, услышат серьезные люди.
    А "для себя" - Stalker_RED уже все сказал: изучите теорию, и существующие решения. Узнаете столько всего, что с вероятностью 98% перехочется делать свое. Зато будете знать, как делают другие.
    Ответ написан
    Комментировать
  • Необходим найти совпадающие участки в двух битовых массивах, как это сделать?

    Наибольшая общая подпоследовательность

    Прям как вам надо.

    Если проблема извлечь битики откуда-то, или как-то их представлять - то язык программирования в студию. Или даже можно отдельный вопрос задать.

    UPD: Вот еще точнее: Наибольшая общая подстрока - для случая, когда разрывов в цепочке быть не должно ( Mrrl правильно заметил, что в подпоследовательности они могут быть).
    Ответ написан
    3 комментария
  • Какая функция может выдавать случайные значения от 0 до 1 разной длинны?

    0.14812561761131
    0.057436987123556


    0.148125617611310
    0.057436987123556

    Не?

    А вообще что мешает сгенерить целое число и поделить его на INT_MAX? или на максимальное число, которое может быть сгенерено? Как раз получите интервал [0; 1)
    Ответ написан
    Комментировать
  • Как построить сбалансированное бинарное дерева поиска, в котором данные хранятся в листах?

    Nipheris
    @Nipheris Куратор тега C++
    Если хотите хранить данные только в листах, храните в нелистовых вершинах интервал. Например, в дереве на рисунке вместо нелистовой вершины 37 храните интервал [30, 49]. Подобная идея используется в https://en.wikipedia.org/wiki/R-tree - почитайте про него тоже, если вам нужно для точек. Это как раз дерево для пространственной индексации.
    Ответ написан
  • Как создать мастер-трек из большого набора координат, полученных от gps-трекеров?

    Подумайте над таким вариантом:
    1) руками на карте грубо рисуете геометрию области (не обязательно прямоугольную), где фигурирует четко один трек (чтобы выделить массив точек, относящихся к одному треку). Врядли это просто сделать автоматически
    2) бьете всю обозначенную вручную область на небольшие квадраты. Для каждого из таких квадратов будем искать среднее значение. Вот как раз тут и можно учесть тот самый шестой знак - т.е. построить квадраты так, чтобы в координатах границ квадрата шестой знак был равен нулю (т.е. на каждый квадрат будет 10 возможных значений реальной координаты).
    3) для каждого квадрата делаем выборку координат из базы (если есть нормальный пространственный индекс, должно быть быстро). Если в квадрат не попала ни одна координата, пропускаем его (таких будет большинство, но их будет тем меньше, чем точнее вы вручную выделили область одного трека). Если попала хотя бы одна (а лучше несколько) - считаем среднее значение. Это среднее значение становится частью мастер-трека.

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

    Ваша сочетаемость цветов - это обычный граф в чистом виде. Вершины - цвета, ребро - факт сочетаемости двух цветов. Как хранить этот граф - дело десятое. Как вносить его в систему - тоже отдельный вопрос, хотя забивать конечно это все придется вручную, т.к. сочетаемость - это на 80-90% субъективное восприятие.

    Для подбора N предметов разного цвета (ну или просто N различных цветов для M >= N различных предметов) найдите подграф с нужным количеством вершин, где все вершины связаны друг другом, включающий некоторые заданные вершины. Например, подграф из 3-х вершин, содержащий вершину "зеленый", при этом каждая вершина подграфа связана с другой вершиной ребром (т.е. длина пути всегда равна 1). Это значит, что в комплекте у вас будут только совместимые друг с другом цвета, один из которых - зеленый.
    Можно увеличить длину пути до 2-х, тогда, если белый будет совместим с черным, черный - с зеленым, но белый НЕ совместим с зеленым, то тем не менее такой набор цветов будет приемлемым.
    Ответ написан
    Комментировать
  • Как построить полную сетку из не полной?

    Nipheris
    @Nipheris Куратор тега C#
    Тоже не совсем поменял что такое неравномерная сетка, может вам просто брать среднее из ближайших значений в той точке, где значения нет? Ну или как-то иначе интерполировать..
    Ответ написан
    Комментировать
  • Как реализовать скелетную модель?

    Nipheris
    @Nipheris Куратор тега C#
    Сергей Иванов дал хорошую идею, только не раскрыл до конца. В общем вам действительно будет полезна иерархия - если какая-то кость связана с другой, то эта другая будет для первой точкой отсчета - своей системой координат. Даже ваш рисунок подсказывает, что каждая кость - это вектор, а точка привязки - это начало кости. Т.о. вам достаточно для каждой кости хранить "родительскую" кость (к которой мы привязаны) - для пальцев это будет кисть или локтевой сустав, и вектор - направление кости. Тогда для перемещения группы костей вам достаточно будет переместить ТОЛЬКО родительскую для этой группы (модифицировать ее вектор). А алгоритм определения положения дочерних костей должен будет идти по дереву костей и складывать родительские и дочерние вектора, пока не дойдет до листьев костяного дерева.
    update: собственно, у Дмитрий Макаров то же самое)
    Ответ написан
  • Как увеличить высоту повернутого прямоугольника математически (быстрый алгоритм)?

    1) находим середину отрезка AD - среднее арифметическое по x и по y
    2) для простоты будем считать середину отрезка началом координат
    3) находим k, которое из уравнения прямой y = kx: k = y1/x1
    4) решаем систему:
    - у = kx
    - sqrt(x^2 + y^2) / sqrt(x_1^2 + y_1^2) = scale
    Ответ написан
    Комментировать
  • Какие есть методы защиты приложения ограничением по времени?

    На стойкость не претендую, решение из собственного опыта:
    1) организовываем защищенное хранилище (напр, зашифрованный файл), который нельзя просто так прочесть и поменять - в нем мы будем хранить, сколько времени программе осталось работать, т.е. временной ресурс;
    2) придумываем, как этот файл генерировать - создавать самой программой при отстутствии этого файла - плохая идея, т.к. юзер просто удалит его и триал сбросится. Неплохой вариант - генерить на сервере, сделать эдакий "запрос триальной лицензии"; после установки лицензия запрашивается, далее с этим файлом работает сама программа;
    3) при каждом запуске файл читаем (с расшифровкой), смотрим сколько лицензированного времени осталось, ставим таймер (системное время использовать нельзя!), каждые N секунд вычитаем лицензированное время, обновляем файл. 30-60 секунд обычно вполне достаточно. Погрешность счета времени соотв. тоже будет до N секунд. Теоретически, каждые N-1 секунду прогу можно убивать и перезапускать, и тогда она не будет успевать вычитать счетчик времени, но я сомневаюсь, что в таких условиях программой вообще можно будет пользоваться.
    Довольно нелохой вариант, если конечно на взлом вашего софта не претендует толпа людей, умеющих дебажить в Olly с закрытыми глазами.
    А, ну да, и упаковщик какой-нибудь возьмите - еще немного усложните жизнь (хотя не сильно конечно).
    Ответ написан
    3 комментария
  • Существует ли универсальный алгоритм разбора УРЛа?

    Nipheris
    @Nipheris Куратор тега C++
    Если вам так нужен самописный сервер на плюсах, попробуйте для разбора урла использовать вот это: cpp-netlib.org/0.11.1/in_depth/uri.html#generic-ur... , а вообще можете и сервер попробовать оттуда взять.
    Ответ написан