Описание тега divide-and-conquer
Разделяй и властвуй - это нисходящий метод разработки алгоритмов, который состоит из разделения проблемы на более мелкие подзадачи в надежде, что решения подзадач будет легче найти, а затем из частичных решений составить решение исходной проблемы.
3
ответа
Разделить и захватить бинарный поиск в C
Я пытаюсь создать бинарный поиск типа "разделяй и властвуй", но тот, который разделяет массив на два подмассива и выполняет поиск, похожий на слияние в сортировке слиянием, поэтому я хочу сделать это, потому что хочу использовать его в cilk, но Я до…
28 май '12 в 13:24
1
ответ
Как избежать умножения переполнения очень больших чисел с помощью рекурсивной функции (C#, D&C)
Когда рекурсивная функция запускает и возвращает результаты в нужном направлении, происходит сбой из-за переполнения данных. Как я могу использовать этот алгоритм D&C; и избежать этой проблемы? static long long zarb(long a, long b, int n) { Int64 w,…
08 апр '15 в 14:10
2
ответа
Максимальная прибыль от цен на акции
Я пытаюсь выяснить алгоритм "разделяй и властвуй" за O(nlogn) время, чтобы решить следующую реальную проблему - Предположим, у нас есть массив цен на акции. Придумайте алгоритм, который распечатывает массив с максимальной прибылью за каждый день в м…
03 май '16 в 21:45
1
ответ
Динамическое программирование и разделяй и властвуй
Я читал заметки о динамическом программировании и столкнулся со следующим комментарием. Если подзадачи не являются независимыми, то есть подзадачи имеют общие подзадачи, то алгоритм "разделяй и властвуй" многократно решает общие подзадачи. Таким обр…
24 янв '12 в 04:21
1
ответ
Решение уравнения с использованием обобщения основной теоремы
Я прошу помощи в объяснении, как работает доказательство. Я видел примеры этого, но мне трудно понять это. Докажите следующее Решение уравнения T (n) = aT (n / b) + Θ (nk logp n), где a ≥ 1, b> 1, p ≥ 0 T (n) = O (nlogb a), если a> bk T (n) = O (nk …
29 ноя '16 в 05:07
1
ответ
Алгоритм разделяй и властвуй - результат NullPointerException
Я делаю программу, которая использует методы разделяй и властвуй. К сожалению, я не могу использовать find(...) метод. Я не знаю, что делать вместо нуля в этой строке: find(null, 0, 100, 34), Заранее спасибо. public class Main { static int find (dou…
08 янв '19 в 15:12
1
ответ
Пример свойства алгоритмов "разделяй и властвуй"
У меня возникли проблемы с пониманием следующего свойства алгоритмов "разделяй и властвуй". Рекурсивный метод, который разделяет проблему размера N на две независимые (непустые) части, которые он решает рекурсивно, называет себя меньше, чем N раз. Д…
30 янв '14 в 14:26
0
ответов
Нахождение подпоследовательности (маленький-большой-средний)
Учитывая список из n неповторяющихся целых чисел L:=(x1,...,xn), разработать алгоритм, который решает, есть ли в L xi1, xi2, xi3, так что i1 ниже, чем i2, i2 ниже, чем i_3, xi1 ниже, чем xi3, а xi3 ниже, чем xi2. Требуется только ответ "да-нет". В з…
17 мар '18 в 20:24
1
ответ
Разделяй и властвуй алгоритм для генерации n-битных строк?
Может кто-нибудь сказать, пожалуйста, как генерировать n-битные строки (все возможные комбинации), т.е. подсчитывать биты от 0 до 2^n-1, используя подход "разделяй и властвуй". Я смог сделать это с помощью следующего алгоритма, но сложность простран…
16 сен '12 в 18:24
3
ответа
Алгоритм поиска рекурсивного несортированного массива в C?
Допустим, мы хотим написать функцию на C, которая находит указанное целевое значение в несортированном массиве целых чисел. В общем, это просто и выполняется за O(n) раз: int search(int *data, int len, int target) { int i; for(i = 0; i < len; i++…
07 ноя '13 в 09:05
1
ответ
Размер наибольшего сбалансированного двоичного поддерева
Я пытаюсь создать алгоритм "разделяй и властвуй", который при запуске в корне двоичного дерева возвращает размер наибольшего сбалансированного двоичного поддерева, содержащегося в дереве, или, другими словами, размер наибольшего возможного поддерева…
24 июл '17 в 16:23
2
ответа
Учитывая файл, содержащий 4,30 миллиарда 32-разрядных целых чисел, как мы можем найти число, которое появилось как минимум дважды?
Я придумал алгоритм "разделяй и властвуй" для этого. Просто хотел узнать, сработает ли это или нет? Первая середина вычисляется из целочисленного диапазона, т.е. (0+(1<<32-1))>>1, а затем применяется эта идея: диапазон чисел от начала до середины ил…
16 фев '16 в 11:54
3
ответа
Покупка и продажа акций с O( n log n) сложностью по времени
РЕДАКТИРОВАТЬ:Я ценю помощь от вас обоих, но я должен придерживаться границы O( n log n) временной полноты и должен использовать технику "разделяй и властвуй" с двоичной рекурсией. Я не очень ясно изложил это в первоначальной публикации У меня есть …
04 июл '15 в 07:55
0
ответов
Распечатать все изображение алгоритма сортировки слиянием
Я новичок в C++, и я пытаюсь распечатать пошаговый процесс сортировки слиянием, как показано ниже А ниже приведен код C++, который я сделал с помощью функции "разделяй и властвуй". #include <iostream> using namespace std; //prototype void merg…
14 апр '18 в 13:50
1
ответ
"Дерево" для оценки полинома быстрого преобразования Фурье?
Я пытаюсь оценить полином A(x) с помощью алгоритма "разделяй и властвуй", используя БПФ. Я в основном разбиваю многочлен на его нечетные корни и четные корни, а затем рекурсирую по двум меньшим многочленам (что позволяет мне оценивать двойные числов…
15 май '12 в 01:07
0
ответов
Разработка алгоритма, обеспечивающего равномерное распределение трафика по сети.
Мой вопрос не связан с тем, как кодировать конкретную вещь или каким-либо техническим вопросом программирования. Мне нужна помощь в разработке логики алгоритма, над которым я работаю, и который я расскажу чуть позже. Я здесь, потому что я не мог при…
15 апр '16 в 06:15
2
ответа
Как работает рекурсия быстрой сортировки?
Приведенные ниже функции являются реализацией быстрой сортировки. Здесь мы берем последний элемент в качестве оси. Я поняла partition функция (где ось приходит в свою сортированную позицию), но я не могу понять рекурсивную функцию qs, Функция qs выз…
13 дек '15 в 15:12
1
ответ
Одинакова ли сложность следующих двух повторений?
У меня есть два рекуррентных отношения как: T(n) = T(n/2) + c // complexity O(logn) T(n) = 2T(n/2) + c // is the complexity O(logn)???? с является константой в обоих случаях, т. е. мы выполняем постоянную работу в части повторения слияния. Первое по…
11 фев '18 в 11:21
3
ответа
Алгоритмы: Найти рекурсивное уравнение "разделяй и властвуй"
У меня есть следующий алгоритм "разделяй и властвуй" A1. A1 делит задачу с размером n на 4 подзадачи с размером n / 4. Затем решите их и составьте решения за 12n раз. Как я могу написать рекурсивное уравнение, которое дает время выполнения алгоритмо…
26 мар '17 в 17:52
0
ответов
Как найти тета-границу без использования метода подстановки: доказательство по индукции?
k - положительная постоянная и 1 ≤ z Как я могу решить эту проблему, используя индукцию, чтобы доказать оценку тэты для T(m, n). Но я не могу использовать метод подстановки. Я не имею права. который правильный? T(m, n) = Θ(mn), T(m, n) = Θ(m^2n^2)
29 окт '17 в 01:14