Во многих текстах нижняя граница для нахождения го наименьшего элемента выводится с использованием аргументов, использующих медианы. Как я могу найти один, используя аргумент противника?Кkk Википедия говорит, что алгоритм турнира работает в , и n - k + ∑ n j = n + 2 - k ⌈ lgO ( n + k logн...
Хорошо известно, что монотонные полигоны играют решающую роль в триангуляции полигонов . Определение: Многоугольник на плоскости называется монотонным относительно прямой , если каждая прямая, ортогональная пересекает не более двух раз.PPPLLLLLLPPP При заданной прямой и многоугольнике существует ли...
Для данного плоского графа встроены в плоскости, определяется набором отрезков Е = { е 1 , . , , , e m } , каждый сегмент e i представлен своими конечными точками { L i , R i } . Создайте структуру данных DCEL для плоского подразделения, опишите алгоритм, докажите его правильность и покажите...
Я не уверен, принадлежит ли этот вопрос здесь, и я прошу прощения, если нет. Что я хочу сделать, так это разработать программный способ, с помощью которого я могу вероятностно определить, принадлежит ли данная строка «сумке строк». Например, если у меня есть сумка из 10 000 названий городов США, а...
\newcommand\ldotd{\mathinner{..}} Учитывая, что A[1..n]A[1..n]A[1\ldotd n] являются целыми числами, такими, что 0≤A[k]≤m0≤A[k]≤m0\le A[k]\le m для всех 1≤k≤n1≤k≤n1\le k\le n , и вхождением каждого число, кроме определенного числа в A[1..n]A[1..n]A[1\ldotd n] является нечетным числом. Попробуйте...
В Википедии дается реализация восходящей схемы динамического программирования для расстояния редактирования. Это не следует определению полностью; внутренние ячейки вычисляются следующим образом: if s[i] = t[j] then d[i, j] := d[i-1, j-1] // no operation required else d[i, j] := minimum ( d[i-1, j]...
Ради интереса я пытаюсь сделать каркасный просмотрщик для DCPU-16 . Я понимаю, как сделать все, кроме как скрыть линии, которые скрыты в каркас. Все вопросы здесь, касающиеся SO, предполагают, что у вас есть доступ к OpenGL, к сожалению, у меня нет доступа ни к чему подобному для DCPU-16 (или к...
Я ищу быстрый алгоритм сопоставления строк k-несоответствие. Учитывая строку шаблона P длины m и текстовую строку T длины n, мне нужен быстрый (линейное время) алгоритм, чтобы найти все позиции, где P соответствует подстроке T с не более чем k несоответствиями. Это отличается от проблемы k-отличий...
У меня есть проблема, которая может быть сведена к проблеме назначения. (В предыдущем вопросе я узнал, как это сделать.) Это означает, что у нас есть набор агентов и набор задач а также функция стоимости . Нам нужно найти назначение, чтобы общая стоимость была минимальной.AAAc ( i , j...
Предположим, у меня есть ориентированный граф с весами ребер, взятыми из диапазона где - константа. Если я пытаюсь найти кратчайший путь, используя алгоритм Дейкстры , как я могу изменить алгоритм / структуру данных и повысить сложность времени до ?K O ( | V | + | E | )[1,…,K][1,…,K][1,\dots,...
Эта страница, посвященная алгоритму Кнута-Мориса-Пратта по сравнению с Бойером-Муром, описывает возможный случай, когда алгоритм Бойера-Мура страдает небольшим пропуском, а KMP может работать лучше. Я ищу хороший пример (текст, шаблон), который может четко продемонстрировать этот...
Недавно я наткнулся на статью, описывающую технику синтаксического анализа, упомянутую в заголовке. К сожалению, терминология, использованная в упомянутой статье, немного за пределами моего понимания, поэтому я пытался понять алгоритм построения более интуитивно. Я полагаю, что мне это удалось (...
Это проблема с практической сессии Польского студенческого соревнования по программированию 2012 года . Хотя я мог найти решения для основного конкурса, я не могу найти решение этой проблемы где-либо. Проблема в том, что: учитывая набор из различных положительных целых чисел, не превышающих ,...
С точки зрения асимптотического поведения, что считается «эффективным» алгоритмом? Каков стандарт / причина для рисования линии в этой точке? Лично я бы подумал, что все, что я могу наивно назвать «подполиномом», такое, что такое как , будет эффективным, а все, что будет "неэффективным". Однако я...
Граф является хордальным, если он не имеет индуцированных циклов длиной и более. Клика дерево из является деревом , в котором вершина дерева являются максимальными кликами . Ребро в соответствует минимальному разделителю. Число различных деревьев клик может быть экспоненциальным по количеству...
Pebbling - это пасьянс, в который играют на неориентированном графе , где каждая вершина имеет ноль или более камешков. Один шаг гальки состоит из удаления двух камешков из вершины и добавления одного камешка к произвольному соседу . (Очевидно, что у вершины v должно быть как минимум два камешка...
Или, по крайней мере, сгенерируйте набор строк, которые принимает один NFA, чтобы я мог передать их в другой NFA. Если я сделаю поиск по каждому пути NFA, это будет работать? Хотя это займет много...
Двоичная последовательность длины просто упорядоченная последовательность , так что каждый является либо или . Чтобы сгенерировать все такие двоичные последовательности, можно использовать очевидную структуру двоичного дерева следующим образом: корень «пустой», но каждый левый дочерний элемент...
Эта проблема возникла в результате тестирования программного обеспечения. Проблему немного сложно объяснить. Сначала я приведу пример, а затем постараюсь обобщить проблему. Есть 10 предметов для тестирования, скажем, от A до J, и инструмент для тестирования, который может проверять 3 предмета...
Обозначение Big-O скрывает постоянные коэффициенты, поэтому существуют некоторые алгоритмы , которые недопустимы для любого разумного размера входных данных, потому что коэффициент по члену очень велик.nO ( n )O(n)O(n)Nnn Существуют ли какие-либо известные алгоритмы, для которых время выполнения...