Выполняя второе кодовое ката (которое просит вас реализовать алгоритм двоичного поиска пять раз, каждый раз с другим методом), я придумал немного другое решение, которое работает следующим образом: Если у меня есть отсортированный массив длины 100, и я вижу, что его начальное поле содержит число...
Предположим, у нас есть множество из N кодеров.S= { а1,2,3, ... ,N}Sзнак равно{a1,a2,a3,...,aN}S = \{ a_1,a_2,a_3,\ldots , a_N \}NNN Каждый кодер имеет рейтинг и количество золотых медалей E i , которые они выиграли до сих пор.ряряR_iЕяЕяE_i Компания-разработчик программного обеспечения хочет...
У меня есть алгоритмическая проблема. Дан массив (или набор) из неотрицательных целых чисел. Найти максимальное множество из , что для всех ,,н STTTnNnSSSTTTa∈Sa∈Sa\in Sa⩾|S|a⩾|S|a\geqslant |S| Например: Если TTT = [1, 3, 4, 1, 3, 6], то SSS может быть [3, 3, 6] или [3, 4, 6] или [4, 3, 6]. В = [7,...
Я читаю о проблеме максимального потока здесь . Я не мог понять интуицию, стоящую за остаточным графиком. Почему мы учитываем задние края при расчете потока? Может ли кто-нибудь помочь мне понять концепцию остаточного графа? Как меняется алгоритм в неориентированных...
Я пытаюсь решить следующую проблему покрытия. Есть передатчиков с зоной покрытия 1 км и n приемников. Определите в O ( n log n ), что все приемники охвачены любым передатчиком. Все приемники и передатчики представлены своими координатами x и y .NNnNNnO ( n logн )О(NжурналN)O(n\log n)ИксИксxYYy...
Мы получаем поток из n−1n−1n-1 попарно различных чисел из множества {1,…,n}{1,…,n}\left\{1,\dots,n\right\} . Как я могу определить пропущенное число с помощью алгоритма, который читает поток один раз и использует память только O(log2n)O(log2n)O(\log_2 n)...
В Частичном тесте для подготовки к GATE возник вопрос: f(n): if n is even: f(n) = n/2 else f(n) = f(f(n-1)) Я ответил: «Это прекратится для всех целых чисел», потому что даже для некоторых отрицательных целых чисел это прекратится как ошибка переполнения стека . Но мой друг не согласился, сказав,...
Учитывая массив из целых чисел, каждый элемент в массиве может быть увеличен на фиксированное число с некоторой вероятностью , . Я должен найти ожидаемое количество перестановок, которые будут иметь место для сортировки массива с помощью пузырьковой сортировки...
У меня проблема: Покажите, что существует действительное число, для которого не существует ни одной программы, которая работает бесконечно долго и записывает десятичные цифры этого числа. Я полагаю, что это можно решить, сведя его к проблеме остановки, но я понятия не имею, как это сделать. Буду...
Предположим, что у нас есть множество DDD и каждый член DDD является парой данных и ключей. Нам нужна структура данных, которая бы поддерживала следующие операции: Вставьте (d,k)(d,k)(d,k) в DDD , Удалить член eee (не нужно искать, чтобы найти eee , например, eee указывает на члена в DDD ),...
У меня есть группа из n наборов, для которых мне нужно вычислить значение типа «уникальность» или «сходство». Я остановился на индексе Жакара как на подходящей метрике. К сожалению, индекс Жакара работает только с двумя наборами одновременно. Для того чтобы вычислить сходство между всеми...
Алгоритм Беллмана-Форда определяет кратчайший путь от источника до всех других вершин. Первоначально расстояние между и всеми остальными вершинами установлено в . Затем вычисляется кратчайший путь от до каждой вершины; это продолжается для итераций. Мои вопросы:ssssss∞∞\inftysss|V|−1|V|−1|V|-1...
Можно ли использовать алгоритм сортировки с нетранзитивным сравнением, и если да, почему транзитивность указана в качестве требования для сортировки компараторов? Фон: Алгоритм сортировки обычно сортирует элементы списка в соответствии с функцией сравнения C (x, y), с...
Я пытаюсь решить проблему с графиком (это не для домашней работы, просто для тренировки моих навыков). Дана DAG , где V - множество вершин, а E - ребра. Граф представлен в виде списка смежности, поэтому A v - это множество, содержащее все соединения v . Моя задача состоит в том, чтобы найти , какие...
Предположим, у меня есть автономное надводное судно на солнечной энергии где-то во фьордах Норвегии, снабженное довольно недавним набором карт, приемником GPS и никакими средствами для передачи подробных команд от меня. Это судно должно достичь, скажем, острова Хайнань в кратчайшие возможные сроки....
Я интересно, что это лучший известный алгоритм, в терминах big- нотации, для решения целочисленных линейного программирования?OOO Я знаю, что проблема в полном, поэтому я не ожидаю ничего полиномиального. И я знаю, что есть много эвристик и тому подобного, которые используются в практических...
Какой алгоритм вы бы использовали, чтобы найти кратчайший путь графа, который вложен в евклидову плоскость, чтобы путь не содержал каких-либо самопересечений (во вложении)? Например, на графике ниже вы хотите перейти от . Обычно такой алгоритм, как алгоритм Дейкстры, выдает такую...
Учитывая невзвешенный DAG (направленный ациклический граф) D=(V,A)D=(V,A)D = (V,A) и две вершины sss и ttt , возможно ли найти кратчайший и самый длинный путь от sss до ttt за полиномиальное время? Длина пути измеряется количеством ребер. Я заинтересован в поиске диапазона возможных длин пути за...
Предположим, что нам дано различных целых чисел , таких что для некоторой константы и для всех .a 1 , a 2 , … , a n 0 ≤ a i ≤ k n k > 0 innna1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_n0≤ai≤kn0≤ai≤kn0 \le a_i \le knk>0k>0k \gt 0iяi Нас интересует нахождение отсчетов всех возможных попарных сумм...
Существует жадный алгоритм поиска минимального покрытия вершин дерева, который использует обход DFS. Для каждого листа дерева выберите его родителя (т.е. его родитель находится в минимальном покрытии вершин). Для каждого внутреннего узла: если ни один из его дочерних элементов не выбран, выберите...