Описание тега clrs
CLRS ссылается на учебник "Введение в алгоритмы" Томаса Х. Кормена, Чарльза Э. Лейзерсона, Рональда Р. Ривеста и Клиффорда Стейна. Это стандартный учебник по алгоритмам и структурам данных.
1
ответ
Красное Черное Дерево в С
Я пытаюсь реализовать красное черное дерево в C. Для справки я использую CLRS. Но когда я запускаю код, я получаю сообщение об ошибке "Ошибка сегментации (ядро сброшено)". Я не могу понять, что не так в моем коде, так может ли кто-нибудь сказать мне…
04 сен '17 в 02:59
2
ответа
Граф - квадрат ориентированного графа
Да, это будет вопрос домашней работы (я учусь не в университете), но я не прошу решения. Вместо этого я надеюсь уточнить сам вопрос. В CLRS 3-е издание, стр. 593, акциз 22.1-5, Квадрат ориентированного графа G = (V, E) - это граф G^2 = (V, E^2) тако…
11 мар '12 в 18:37
1
ответ
Почему мы не добавляем черный узел вместо красного узла при вставке красного черного дерева?
При вставке красного черного дерева мы всегда выбираем новый узел красного цвета, чтобы избежать изменения высоты черного дерева. Почему это более желательно, чем добавить черный узел?
31 дек '12 в 02:15
1
ответ
Это правильный инвариант для этого цикла?
Это псевдокод для линейного поиска в массиве, возвращающего индекс i если желаемый элемент e в массиве A найден, NIL в противном случае (это из книги CLRS, 3-е издание, упражнение 2.1-3): LINEAR_SEARCH (A, e) for i = 1 to A.length if A[i] == e retur…
03 мар '16 в 16:59
1
ответ
Какая интуиция дает оптимальную субструктуру?
Этот вопрос связан с динамическим программированием и, в частности, с проблемой резки прутка из CLRS Pg 362. Общее оптимальное решение включает в себя оптимальные решения для двух связанных подзадач. Полное оптимальное решение получается путем нахож…
24 окт '12 в 05:28
3
ответа
Лучшее решение для моего подхода к созданию процедуры Rand(a,b) с использованием процедуры Rand(0,1)
Я читал CLRS и столкнулся с проблемой написания процедуры Rand(a,b), которая генерирует случайное число между a и b равномерно случайным образом, используя процедуру Rand(0,1), которая генерирует 0 или 1 с вероятностью 50%., Я подумал о следующем ре…
16 фев '14 в 12:13
2
ответа
Проблема сортировки слиянием Python
Не уверен, где я ошибаюсь с моей реализацией сортировки слиянием в Python. import sys sequence = [6, 5, 4, 3, 2, 1] def merge_sort(A, first, last): if first < last: middle = (first + last) / 2 merge_sort(A, first, middle) merge_sort(A, middle+1, …
26 янв '16 в 12:29
1
ответ
Я пытаюсь реализовать очередь из книги clrs, но она не работает, как ожидалось? что не так с моим кодом
Я пытаюсь реализовать очередь из книги clrs, но она не работает, как ожидалось. Что не так с моим кодом? Может ли быть проблема с размером очереди или операцией постановки в очередь? Однако очень ясно, что операция очереди в очереди не работает долж…
13 янв '17 в 15:18
1
ответ
Операции над битами при выполнении двоичного длинного деления
Это из главы теории чисел в CLRS. Нас просят доказать, что двоичное "бумага и карандаш" длинное деление a/b с результатом q и напоминание r делает O((1+lgq)lgb) операции над битами. То, как я вижу это, мы делаем 1 вычитание b за каждый бит в q, Итак…
14 сен '13 в 16:07
1
ответ
Анализ размера кучи Фибоначчи (x) в CLRS имеет недостаток?
Во 3-м издании CLRS "Введение в алгоритмы", стр.525, когда анализируется нижняя граница размера (x), есть предложение, которое я цитирую как "поскольку добавление дочерних элементов в узел не может уменьшить размер узла, значение Sk увеличивается мо…
03 сен '11 в 06:32
1
ответ
Метод Sort в STL не может поменять содержимое в векторе
Я пытался реализовать алгоритм Крускала (реализация Введение в алгоритмы CLRS), используя C++. Но при попытке отсортировать набор Edge (который является классом, который я создал) (который я реализовал как вектор) с использованием std::sort, он не р…
13 янв '19 в 10:25
1
ответ
Время выполнения R-Select против Select в среднем случае?
В худшем случае R-выбор - O(n^2), где выбор - O(n). Может кто-то объяснить и противопоставить свое поведение в средних случаях. Ps - я не уверен, что это повторяющийся вопрос. Я могу удалить, если это так! Спасибо!!
23 окт '16 в 06:26
1
ответ
Инварианты петли с перерывами
Я пытаюсь понять, как инварианты цикла взаимодействуют с разрывами. CLRS 3e (pg19) описывает инвариант цикла как требующий, чтобы Если он равен true до итерации цикла, он остается истинным до следующей итерации. Итак, учитывая следующий тривиальный …
04 янв '19 в 22:46
2
ответа
Удаление случайного элемента из кучи
Я прочитал несколько статей, в которых говорилось, что в куче может быть удален только корневой элемент. Однако, почему мы не можем удалить элементы, используя следующий подход? Найдите индекс ключевого элемента, который вы хотите удалить Поменяйте …
19 окт '16 в 02:54
5
ответов
Реализация таблицы прямых адресов
В качестве домашней работы мне дали упражнение " Введение в алгоритмы " 11.1-3 что выглядит следующим образом: Предложите, как реализовать таблицу прямого доступа, в которой ключи хранимых элементов не должны различаться, а элементы могут иметь спут…
03 янв '10 в 19:08
3
ответа
Как найти предшественника узла в BST, где каждый узел имеет 3 атрибута -succ,left и right?
Проблема из CLRS, 3ed. 12.3-5 Предположим, что вместо каждого узла x, хранящего атрибут xp, указывающий на родителя x, он сохраняет x.succ, указывая на преемника x. Дайте псевдокод для SEARCH,INSERT и DELETE в двоичном дереве поиска T, используя это…
29 авг '15 в 07:02
1
ответ
Решение рецидива методом подстановки
Изучая алгоритмы и обращаясь к CLRS, я столкнулся с проблемой T(n) = T(n-a) + T(a) + cn ; a >= 1 and c > 0 it is Big-theta(n^2), can be easily proved by recursion tree method Я могу решить это методом дерева рекурсии. Обсуждая с друзьями в мое…
27 сен '17 в 12:31
3
ответа
Максимальная сумма подмножества размера K с суммой меньше M
Дано: массив целых чисел K,M Вопрос: Найти максимальную сумму, которую мы можем получить из всех K подмножеств элемента данного массива, чтобы сумма была меньше значения M? Есть ли решение для не динамического программирования для этой проблемы? или…
05 авг '13 в 19:56
1
ответ
Расчет результатов при нарезке стержней
Я изучаю алгоритм резки стержней из книги CLRS. Я верю, что понимаю логику, и мое решение ниже было принято на этом OJ. #include <climits> #include <iostream> using namespace std; int prices[101]; int result[101]; int function(int length…
28 авг '18 в 19:20
3
ответа
Рекурсивное матричное умножение
Я читаю Введение в алгоритмы CLRS. Книга показывает псевдокод для простого умножения матрицы "разделяй и властвуй": n = A.rows let c be a new n x n matrix if n == 1 c11 = a11 * b11 else partition A, B, and C C11 = SquareMatrixMultiplyRecursive(A11, …
16 окт '12 в 19:24