Вопросы по теме 'divide-and-conquer'

Алгоритм умножения целых чисел с использованием подхода «разделяй и властвуй»?
В качестве домашнего задания я должен реализовать целочисленное умножение чисел из 1000 цифр, используя подход «разделяй и властвуй», который работает ниже O (n). Какой алгоритм я должен изучить?
5140 просмотров
algorithm biginteger divide-and-conquer
schedule 05.05.2023
Интересные примеры Fork/Join или Divide and Conquer
Мы хотим продемонстрировать новый JDK7 Fork/Join Framework на семинаре конференции. Для этого мы сейчас ищем интересный пример того, что можно сделать с помощью фреймворка. Есть очевидные, такие как сортировка или матричные вычисления, но есть и...
291 просмотров
fork-join java-7 divide-and-conquer
schedule 10.08.2022
Перестановка строк в массиве для устранения возрастающих подпоследовательностей
Следующая задача взята из Problems on Algorithms (Проблема 653): Вам дана матрица n x 2 чисел. Найдите алгоритм O(n log n), который переставляет строки в массиве таким образом, что ни один из столбцов массива не содержит возрастающую...
387 просмотров
algorithm dynamic-programming greedy divide-and-conquer
schedule 16.11.2022
Сравните разделяй и властвуй с рекурсией
Когда мы говорим о разделяй и властвуй, мы всегда используем рекурсию. Я уже знал, что разделяй и властвуй - это метод разработки алгоритмов, но у меня есть один вопрос: Все ли рекурсии алгоритмов «разделяй и властвуй», или, другими словами,...
945 просмотров
recursion divide-and-conquer
schedule 21.08.2022
какова сложность рекурсивного линейного поиска (с использованием метода «разделяй и властвуй»)?
хотел проанализировать сложность рекурсивного линейного поиска (используя технику разделяй и властвуй). Это log(n) или n? если не log(n), то какова на самом деле сложность и как? int linear_search(int *a,int l,int h,int key){ if(h == l){...
3739 просмотров
algorithm time-complexity complexity-theory divide-and-conquer
schedule 09.10.2023
Разделяй и властвуй - покупай или продавай? (Максимальный последовательный подмассив)
Суть программы заключается в том, чтобы найти максимальный подмассив одномерного массива с колеблющимися ценами на акции, используя как метод грубой силы (который работает!), так и метод «разделяй и властвуй» (который не работает). Цель программы —...
1288 просмотров
c++ recursion divide-and-conquer
schedule 09.05.2022
кратчайшее расстояние в ряду координат xy
У меня есть задание, которое сравнивает 2 разных алгоритма для проблемы. Вот проблема: Предположим, у меня есть ряд таких координат xy: A(2,3), B(5,6), C(7,8), D(6,2), E(5,5) и т.д.. И я хочу найти 2 координаты, которые имеют кратчайшее...
1279 просмотров
c# algorithm brute-force divide-and-conquer
schedule 28.02.2023
Сложность конкретного алгоритма разделяй и властвуй
Алгоритм декомпозирует (делит) проблему размера n на b подзадач, каждая из которых имеет размер n/b, где b — целое число. Стоимость разложения равна n, а C(1)=1. Покажите, используя повторную замену, что для всех значений 2≥b сложность алгоритма...
328 просмотров
algorithm math big-o complexity-theory divide-and-conquer
schedule 03.11.2022
Какой подход к хранению элементов в связанном списке быстрее?
В моем учебнике по алгоритмам для практики есть вопрос, в котором я не уверен, и надеялся, что кто-то сможет уточнить/объяснить: Когда вы разрабатываете алгоритм «разделяй и властвуй» для хранения элементов в связанном списке размера n, будет ли...
90 просмотров
algorithm linked-list divide-and-conquer
schedule 14.07.2023
Алгоритм ближайшей пары для сравнения точек из двух разных массивов
Я хотел бы сравнить точки из одного массива с точками из другого массива и найти ближайшую пару. До сих пор все, с чем я сталкивался, было с одним массивом. Я не хочу сравнивать точки из одного массива. Алгоритм грубой силы работает, но слишком...
840 просмотров
java arrays algorithm closest-points divide-and-conquer
schedule 23.05.2023
Алгоритмы: разделяй и властвуй (применение быстрой сортировки ?!)
Мы будем благодарны за любую помощь относительно того, как можно подойти к указанной ниже проблеме. Я также опубликовал некоторые мысли по проблеме. Вы - ТА класса, в котором обучается n студентов. У вас есть их окончательные оценки (без...
779 просмотров
algorithm quicksort divide-and-conquer partial-sort
schedule 20.03.2022
C - Бесконечный процесс в функции. Найдите элемент большинства с помощью метода «разделяй и властвуй».
как упоминалось в заголовке, моя функция не заканчивается хорошо. Я пытаюсь сделать следующее: «Реализовать с помощью метода DC функцию, которая имеет этот интерфейс: Возвращает основной элемент заданной последовательности, если он существует...
76 просмотров
c divide-and-conquer
schedule 01.12.2023
C Сортировка слиянием застряла в бесконечном цикле
Моя программа использует рекурсию для разделяй и властвуй, но я получаю бесконечный цикл по неизвестным причинам. и я все еще получаю несортированный массив в качестве ответа /** * MergeSort.c * * Uses recursion for divide and conquer * *...
164 просмотров
recursion mergesort divide-and-conquer
schedule 06.03.2022
Алгоритм разделения и владения для поиска максимального подмассива - как также предоставить индексы подмассивов результатов?
Извините, у меня есть задание решить проблему максимального подмассива с помощью Алгоритм грубой силы O (n ^ 2) , Разделяй и властвуй O (nlogn) и Алгоритм Кадана O (n) . (У меня другой код). « Например, для последовательности значений...
2474 просмотров
c++ recursion logic algorithm divide-and-conquer
schedule 14.03.2022
Решение уравнения с использованием обобщения основной теоремы
Прошу помощи в объяснении того, как работает доказательство. Я видел примеры этого, но не могу понять. Докажите следующее Решение уравнения T(n) = aT(n/b) + Θ(n k log p n), где a ≥ 1, b > 1, p ≥ 0 T(n) = O(n log b a ), если a > b...
315 просмотров
algorithm math master-theorem divide-and-conquer proof
schedule 26.05.2023
Поиск в отсортированном по свопингу массиве различных целых чисел
Контекст: Массив A[1..n] различных целых чисел называется отсортированным с перестановкой, если существует некоторое k, 1 ≤ k ≤ n, так что перемещение последних n − k элементов A ( в том порядке, в котором они появляются в A), прежде чем первые k...
368 просмотров
arrays search algorithm computer-science divide-and-conquer
schedule 12.01.2024
Разработайте алгоритм «разделяй и властвуй», чтобы найти настоящую карту
Я думаю о задаче D&S, чтобы найти настоящую карту в группе карт. Все настоящие карты имеют одинаковый код, а поддельные карты имеют много кодов (могут быть одинаковыми или разными). Количество реальных карт больше половины. Я могу только сравнить...
189 просмотров
algorithm divide-and-conquer
schedule 13.02.2023
Двоичное умножение Python. Разделяй и властвуй
Мне нужно понять, почему мой код дает неправильные ответы. Задача состоит в том, чтобы создать двоичное умножение методом разделяй и властвуй. Я нашел несколько документов, описывающих этот тип проблемы: алгоритмы викиучебников документ UTSC...
1564 просмотров
python binary multiplication divide-and-conquer
schedule 01.09.2023
Вычисление максимального количества массивов по алгоритму разделяй и властвуй
Я сделал программу, которая вычисляет максимальное значение массива, используя алгоритм разделяй и властвуй, но на выходе 0. #include <iostream> using namespace std; int array[50]; void maximum(int index1, int index2, int&max_number) {...
873 просмотров
c++ arrays recursion algorithm divide-and-conquer
schedule 23.01.2023
как рассчитать свертку XOR (двоичную) с временной сложностью O (n log n)
введите здесь описание изображения «⊕» — это побитовая операция XOR. Я думаю, что алгоритм Карацубы можно использовать для решения проблемы, но когда я пытаюсь использовать XOR вместо + в алгоритме Карацубы, трудно получить подзадачу.
1142 просмотров
algorithm divide-and-conquer
schedule 21.10.2022