Исправленные упражнения Алгоритм разделяй и властвуй

Следующие исправленные упражнения касаются создания алгоритмов в соответствии со структурой разделяй и властвуй (разделяй и властвуй). Также будут изучены алгоритмы типа дихотомии.

разделяй и властвуй

Упражнение 1

Мы будем играть в игру «меньше, больше». Цель состоит в том, чтобы угадать число от 1 до n (целое число). Мы считаем, что алгоритм принимает в качестве входных данных значение n и число x, которое нужно угадать, и что он возвращает количество ходов, чтобы найти это число.

а – Сформулируйте проблему более формально.

б – Напишите итерационный алгоритм решения этой задачи.

в – Напишите алгоритм рекурсивный решение этой проблемы.

г – Сравните сложности.

а – Задачу можно было бы переписать следующим образом: Дан массив, отсортированный в порядке возрастания целых чисел, как определить, принадлежит элемент этому массиву или нет? Принцип известен: искомый элемент сравнивается с медианным элементом, и при необходимости поиск повторяется в левой или правой части массива.

алгоритм бинарного поиска

б- Итерационный алгоритм выглядит следующим образом:

алгоритм бинарного поиска

Поскольку массив каждый раз разрезается на две части, мы пройдем не более log n элементов, прежде чем найдем нужный или узнаем, что он не существует. сложность поэтому O (log n)

против - По умолчанию ответ алгоритма является ложным, если только не будет возвращено истинное значение, которое даст в основном метод:

алгоритм бинарного поиска

Поскольку операция точно такая же, как и итерационный алгоритм, можно предположить, что сложность такая же.

Упражнение 2

Мы ищем сумму массива B из n целых элементов.

1 — Напишите алгоритм «разделяй и властвуй», решающий эту проблему.

2 — Проанализировать его сложность и составить дерево вызовов для массива [3,4,2,3,4].

3 – Сравните его с итеративным алгоритмом, который вы описываете.

Мы определяем функцию Sum(B,i,j), которая является суммой элементов B между позициями i и j. Таким образом, искомое значение равно Sum(B,1,n). Мы вычислим Sum(B,i,j), разделив массив B[i..j] на две половины; подсчет сумм за каждую половину; и складывая эти две суммы. Это дает следующий код:

рекурсивный алгоритм суммирования массивов

Для сложности, поскольку мы еще не видели Основную теорему, мы будем использовать дерево вызовов:

рекурсивный алгоритм суммирования массивов

Мы понимаем, что каждый раз разрезаем картину надвое. Вычисление простое, поэтому сложность зависит только от глубины дерева p такого, что 2^п > n (размер массива), следовательно, p > log n и сложность O (log n).

Итерационный алгоритм выглядит следующим образом:

рекурсивный алгоритм суммирования массивов

Здесь сложность O(n).

Упражнение 3

Мы говорим, что массив имеет мажоритарный элемент, если значение массива присутствует не менее n/2 раз из n элементов.

1 – Предложите итерационный алгоритм для решения этой задачи.

2 – Предложите метод решения проблемы «разделяй и властвуй».

3 – Напишите метод, описанный алгоритмом.

Измените свой алгоритм с учетом следующих свойств:

  • если только одна из половин обеспечивает большинство, только этот элемент может быть большинством в полном массиве.
  • если два рекурсивных вызова обеспечивают большинство, они разные, с разным количеством вхождений: единственный, который может быть большинством, - это тот, у которого наибольшее количество вхождений.
  • в случае, когда n является степенью двойки и, следовательно, половины всегда одинакового размера, если есть два разных большинства с одинаковым количеством вхождений, то в полной таблице не может быть большинства.

1 — Считаем количество вхождений каждого элемента (не нужно считать влево, потому что если он существует, то он уже был подсчитан ранее). Для первого цикла мы могли бы остановиться на n/2 + 1, потому что даже если бы все последующие элементы были одинаковыми, это все равно не было бы большинством.

мажоритарный рекурсивный алгоритм

2 – Начнем с принципа «разделяй и властвуй»:

мажоритарный рекурсивный алгоритм

Если в E есть мажоритарный элемент x, то x находится в большинстве хотя бы в одном из двух списков E1 и E2 (действительно, если x не имеет большинства ни в E1, ни в E2, то в E число x ≤ n/4 + n/4 = n/2).

Тогда принцип рекурсии заключается в следующем: вычислите большинство элементов E1 и E2 (если они существуют) с общим количеством вхождений каждого и сделайте вывод, является ли один из двух большинством в E.

Следующий алгоритм Majority(i, j) возвращает пару, которая равна (x, cx), если x является большинством в подмассиве E[i..j] с вхождениями cx, и которая равна (−, 0), если она существует. не является большинством в E[i..j], первоначальным вызовом является Majority(1, n). Функция Occurence(x, i, j) вычисляет количество вхождений x в подмассиве E[i..j].

мажоритарный рекурсивный алгоритм

Это не так просто понять, давайте возьмем пример массива из 8 элементов с 5 одинаковыми элементами, чтобы полностью понять, как это работает.

мажоритарный рекурсивный алгоритм

Вот мажоритарный алгоритм с учетом новых свойств:

большинство разделяй и властвуй

Упражнение 4

1 – Предложите алгоритм «разделяй и властвуй» для поиска минимума массива.

2 – Аналогично с максимальным.

3 – Аналогично, ища как минимум, так и максимум.

Я дам ответ непосредственно на вопрос 3, так как он содержит ответ на два предыдущих. В этом методе необходимо запомнить позиции в таблице, а также значение min и max.

мин макс разделяй и властвуй

Упражнение 5

Вот формула матричного произведения:

матричное произведение

1 – Предложите итерационный алгоритм и укажите его сложность.

Чтобы разложить матрицу на дихотомию, это нужно сделать как по строкам, так и по столбцам, поэтому на 4 части, как на следующей диаграмме:

стразы

Каждый элемент представляет собой квадратную матрицу. Обозначим r=ae+bg, s=af+bh, t=ce+dg и u=cf+dh.

2 — Штрассен нашел способ еще больше сократить количество вычислений. Предлагается вычислять r, s, t, u с помощью линейной комбинации (сложения или вычитания) следующих матриц:

Алгоритм Штрассена

Выразите r, s, t, u через число пи.

3 – Предложите рекурсивный алгоритм, основанный на вычислениях Штрассена для матричного произведения.

1 — Замечаем в формуле, что нам придется сделать три петли по i, j и k. 

алгоритм матричного произведения

Глубоко внутри итерационных структур есть три вложенных цикла от 1 до n, поэтому сложность O(n^3)

2 – Это дает следующие линейные отношения:

алгоритм Штрассена

3 – Алгоритм «разделяй и властвуй» выглядит следующим образом:

алгоритм Штрассена

Упражнение 6

Написать псевдокод для алгоритма «разделяй и властвуй», чтобы найти позицию самого большого элемента в массиве чисел. Напишите псевдокод для алгоритма перебора, сравните с предыдущим. Показать дерево процесса алгоритма «разделяй и властвуй». Каков максимальный уровень дерева для чисел?

разделяй и властвуй динамическое программирование исправленные упражнения

Алгоритм грубой силы тривиален: цикл.

На каждом уровне l полное бинарное дерево состоит из 2^(l-1) листьев. Таким образом, сумма вершин равна 2 ^ l -1. Пусть l будет уровнем дерева, поэтому l=sup(log_2 (n)).

Упражнение 7

Напишите псевдокод для алгоритма «разделяй и властвуй» для задачи возведения в степень вычисления a^n, где a>0 и n — положительное целое число. Напишите псевдокод для алгоритма перебора, сравните с предыдущим. Покажите дерево процессов алгоритма «разделяй и властвуй». Какой максимальный уровень дерева для n не задан? Проверить прекращение, точность и полнота.

Упражнение 8

Чтобы умножить два целых числа из n цифр, наивный метод состоит в том, чтобы умножить каждую цифру первого числа на каждую цифру второго и сделать правильные смещения и правильные суммы. Тогда время расчета составляет O (n²).

Алгоритм Карацубы использует тот же принцип, что и при расчете, используемом в этом наивном подходе:

(a × 10^k+ b)(c × 10k+ d) = ac × 10^2k+ (ad + bc) × 10^k+ bd

требующих четырех продуктов (ac, ad, bc и bd), можно выполнить только с тремя продуктами, сгруппировав вычисления в следующем виде:

(a × 10 ^ k + b) (c × 10 ^ k + d) = ac × 10 ^ 2k + (ac + bd - (a - b) (c - d)) × 10 ^ k + bd

Конечно, вычитания были введены, но теперь необходимы только три произведения больших чисел: ac, bd и (a − b)(c − d).

Поскольку сложения и вычитания недороги (незначительны по сравнению с умножениями), мы сэкономим время вычислений. Для справки: умножение на степень базы вычислений соответствует сдвигу разряда и очень быстро выполняется на машине.

Напишите код функции karatsuba(), позволяющей умножать два больших целых числа из n цифр по этому принципу.

Упражнение 9

Учитывая набор реальных точек, найдите минимальное расстояние между двумя точками, используя алгоритм типа «разделяй и властвуй». Для этого воспользуемся евклидовым расстоянием между двумя точками.

Очевидным решением является создание матрицы расстояний между каждой парой точек. Алгоритм «разделяй и властвуй» рекурсивно разрезает пространство на 2 блока и смотрит на минимальное расстояние в каждом блоке. Более того, тогда необходимо искать наименьшее расстояние между точками двух разных блоков.

минимальная дистанция разделяй и властвуй

Решение по принципу «разделяй и властвуй»
— Сортировать точки относительно их координат x.
— Разделите точки на две группы: левая половина и правая половина.
— Используйте рекурсию, чтобы найти dg, минимальное расстояние между точками
оставил.
— Используйте рекурсию, чтобы найти dd, минимальное расстояние между точками линии.
— Оптимальное решение:
     — либо дг,
     — либо дд,
     — пусть будет расстоянием между двумя точками A и B такими, что A находится в части
слева и B находится в правой части.

Пусть midx будет координатой x самой правой точки среди левых точек. Обратите внимание, что в третьем случае, упомянутом выше, две точки A и B расположены в тонкой полосе шириной min(dg, dd) с центром в середине x.

Заметим в центральной полосе две точки, расположенные по одну сторону от
границы midx находятся на расстоянии не менее d друг от друга. Эта информация используется следующим образом:

— Начнем с сортировки всех точек, присутствующих в центральной полосе, по их координате y.

 Для каждой точки А центральной полосы смотрим расстояние, отделяющее ее от точек, расположенных в ее радиусе.

минимальная дистанция разделяй и властвуй

Упражнение 10

В этом упражнении нас интересует сложность в худшем случае и количество сравнений алгоритмов.

1. Чтобы найти наибольший и второй по величине элемент из n целых чисел, укажите наивный алгоритм и его сложность.

2. Для повышения производительности предлагаем рассмотреть решение, заключающееся в расчете максимума по принципу Разделяй и Властвуй

1.

двойной максимум

2.

Принцип довольно прост, так как он близок к алгоритму сортировки слиянием. Во время правления поднимается кортеж из двух элементов (max1, max2) или max1 > max2. Правление состоит из сравнения левого и правого кортежей и возврата двух самых больших. Таким образом, каждая ветвь будет возвращать два самых больших из своего подмассива, пока не получит два самых больших из массива целиком.

Упражнение 11

Дан массив целых чисел, найти максимальную сумму среди всех возможных подмассивов. Подмассивы должны занимать последовательные позиции в исходном массиве.

Ввод: числа[] = [2, -4, 1, 9, -6, 7, -3]

Выход: максимальная сумма подмассива равна 11 (отмечено в смелый)

Идея состоит в том, чтобы использовать метод «разделяй и властвуй», чтобы найти максимальную сумму подмассивов. Алгоритм работы следующий:

  1. Разделите массив на два равных подмассива.
  2. Рекурсивно вычислить максимальную сумму подмассивов для левого подмассива,
  3. Рекурсивно вычислить максимальную сумму подмассивов для правого подмассива,
  4. Найдите максимальную сумму подмассива, пересекающего средний элемент.
  5. Возвращает максимум из трех указанных выше сумм.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <limits.h>
 
// Вспомогательная функция для нахождения максимального из двух чисел
int max(int x, int y) {
    return (x > y) ? x : y;
}
 
// Функция для нахождения максимальной суммы подмассивов с использованием метода разделяй и властвуй
int maximum_sum(int nums[], int low, int high)
{
    // Если массив содержит 0 или 1 элемент
    if (high <= low) {
        return nums[low];
    }
 
    // Находим средний элемент массива
    int mid = (low + high) / 2;
 
    // Находим максимальную сумму подмассива для левого подмассива,
    // включая средний элемент
    int left_max = INT_MIN;
    int sum = 0;
    for (int i = mid; i >= low; i)
    {
        sum += nums[i];
        if (sum > left_max) {
            left_max = sum;
        }
    }
 
    // Находим максимальную сумму подмассива для правого подмассива,
    // исключаем средний элемент
    int right_max = INT_MIN;
    sum = 0;    // сбрасываем сумму в 0
    for (int i = mid + 1; i <= high; i++)
    {
        sum += nums[i];
        if (sum > right_max) {
            right_max = sum;
        }
    }
 
    // Рекурсивно находим максимальную сумму подмассива для левого
    // и правый подмассив, и берем максимум
    int max_left_right = max(maximum_sum(nums, low, mid),
                            maximum_sum(nums, mid + 1, high));
 
    // вернуть максимум из трех
    return max(max_left_right, left_max + right_max);
}
 
int main(void)
{
    int arr[] = { 2, 4, 1, 9, 6, 7, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    printf(« The maximum sum of the subarray is %d »,
            maximum_sum(arr, 0, n 1));
 
    return 0;
}

Мы можем легко решить эту задачу за линейное время, используя алгоритм Кадане. Идея состоит в том, чтобы поддерживать максимальный (положительную сумму) подмассив, «заканчивающийся» на каждом индексе данного массива. Этот подмассив либо пуст (в этом случае его сумма равна нулю), либо состоит из одного элемента больше, чем максимальный подмассив, заканчивающийся предыдущим индексом.

алгоритм каданеса

Упражнение 12

Дан массив целых чисел, найти содержащийся в нем пиковый элемент. Пиковый элемент — это элемент, превосходящий своих соседей. В массиве может быть несколько пиковых элементов, и решение должно сообщать о любом пиковом элементе.

Элемент A[i] массива A является пиковым элементом, если он не меньше своего соседа (соседей).
A[i-1] <= A[i] >= A[i+1] для 0 < i < n-1
A[i-1] <= A[i], если i = n – 1
А[я] >= А[я+1], если я = 0

Например,
Запись: [8, 9, 10, 2, 5, 6]
Выход: пиковый элемент равен 10 (или 6)


Запись: [8, 9, 10, 12, 15]
Выход: пиковый элемент равен 15


Запись: [10, 8, 6, 5, 3, 2]
Выход: пиковый элемент равен 10

Наивным решением было бы проверить все элементы на пик, запустив линейный поиск в массиве и вернув элемент, больший, чем его соседи. Необходимо рассмотреть два частных случая. Если массив отсортирован в порядке убывания, его пиковый элемент является первым элементом. Если массив отсортирован в порядке возрастания, пиковый элемент является последним. Проблема с этим подходом заключается в том, что его временная сложность в наихудшем случае составляет O(n), где n — размер входных данных.

Мы можем легко решить эту задачу за время O(log(n)), используя идею, аналогичную алгоритму бинарного поиска. Идея состоит в том, чтобы вычислить медианный индекс и, если средний элемент больше, чем два его соседа, вернуть элемент, поскольку он является пиком. Если правый сосед медианного индекса больше среднего элемента, рекурсивно ищите пик в правой части массива. Если левый сосед медианного индекса больше среднего элемента, рекурсивно ищите пик в левой части массива.

пиковый элемент разделяй и властвуй

Упражнение 13

Учитывая отсортированный массив с возможными повторяющимися элементами, задача состоит в том, чтобы найти индексы первого и последнего вхождений элемента x в данном массиве.

Примеры:

Ввод: вкладка [] = {1, 3, 5, 5, 5, 5, 67, 123, 125}, х = 5
Вывод: первое появление = 2
Последнее появление = 5

Ввод: вкладка [] = {1, 3, 5, 5, 5, 5, 7, 123, 125}, х = 7
Вывод: первое появление = 6
Последнее появление = 6

Идея решения этой проблемы заключается в переборе элементов заданного массива, проверке заданных элементов в массиве и отслеживании первого и последнего вхождения индекса найденного элемента.

Запустите цикл for и for i = 0 to n-1
Возьмите первый = -1 и последний = -1
Когда мы находим элемент в первый раз, мы сначала обновляем = i
Мы всегда обновляем last=i каждый раз, когда находим элемент.
Мы печатаем первый и последний.

найти вхождение

Эффективный подход с использованием бинарного поиска:

1. Для первого появления числа

а) Если (высокий >= низкий)
б) Рассчитать средний = низкий + (высокий – низкий)/2;
c) Если ((middle == 0 || x > arr[middle-1]) && arr[middle] == x)
средняя часть спины;
d) В противном случае, если (x > arr[medium])
вернуть сначала (прибытие, (средний+1), верх, x, n);
д) В противном случае
вернуть сначала (прибытие, низкий, (середина-1), x, n);
е) иначе вернуть -1;

2. Для последнего вхождения числа

а) если (высокий >= низкий)
б) рассчитать средний = низкий + (высокий – низкий)/2;
c)if( ( middle == n-1 || x < arr[middle+1]) && arr[middle] == x )
средняя часть спины;
г) иначе если (x < arr [середина])
return last(arr, low, (mid-1), x, n);
д) иначе
вернуть последний (приб, (середина + 1), высокий, x, n);
е) иначе вернуть -1;

найти вхождение

Упражнение 14

Имея n прямоугольных зданий в двухмерном городе, вычислите линию горизонта этих зданий, убрав скрытые линии. Основная задача — просмотреть здания с одной стороны и убрать все невидимые участки.

Все здания имеют общий фон, и каждое здание представлено тройкой (слева, сверху, справа).

'left': координата x левой стороны (или стены).
'right': координата x правой стороны
«ht»: высота здания.
Линия горизонта представляет собой набор прямоугольных полос. Прямоугольная полоса представлена парой (left, ht), где left — координата x левой стороны полосы, а ht — высота полосы.

Примеры:

Вход: массив зданий
{ (1, 11, 5), (2, 6, 7), (3, 13, 9), (12, 7, 16), (14, 3, 25),
(19, 18, 22), (23, 13, 29), (24, 4, 28) }

Продукт: Skyline (набор прямоугольных полос)
Полоса имеет координату x левой стороны и высоту
(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18),
(22, 3), (25, 0)

Изображение ниже для входа 1:

Проблема SkyLine

Мы можем найти линию горизонта за время Θ(nLogn), используя метод «Разделяй и властвуй». Идея похожа на сортировку слиянием, разделяя данный набор зданий на два подмножества. Рекурсивно построить горизонт для двух половин и, наконец, объединить два горизонта.

Идея аналогична сортировке слиянием, начните с первых полос двух горизонтов, сравните координаты x. Выберите полосу с наименьшей координатой x и добавьте ее к результату. Высота добавляемой полосы принимается как максимальная из текущих высот skyline1 и skyline2.

Высота новой полосы всегда определяется следующим максимальным значением:

(a) Текущая высота горизонта1, скажем, «h1».
(b) Текущая высота skyline2, скажем, «h2»

h1 и h2 инициализируются равными 0. h1 обновляется, когда к результату добавляется полоса SkyLine1, а h2 обновляется, когда добавляется полоса SkyLine2.

Skyline1 = {(1, 11), (3, 13), (9, 0), (12, 7), (16, 0)}
Skyline2 = {(14, 3), (19, 18), (22, 3), (23, 13), (29, 0)}
Результат = {}
h1 = 0, h2 = 0

Сравните (1, 11) и (14, 3). Поскольку первая полоса имеет меньший левый x, добавьте его к результату и увеличьте индекс для Skyline1.
h1 = 11, новая высота = max(11, 0)
Результат = {(1, 11)}

Сравните (3, 13) и (14, 3). Поскольку первая полоса имеет меньший левый x, добавьте его к результату и увеличьте индекс для Skyline1.
h1 = 13, новая высота = max(13, 0)
Результат = {(1, 11), (3, 13)}

Аналогично добавляются (9, 0) и (12, 7).
h1 = 7, новая высота = max(7, 0) = 7
Результат = {(1, 11), (3, 13), (9, 0), (12, 7)}

Сравните (16, 0) и (14, 3). Поскольку вторая полоса имеет меньший левый x, она добавляется к результату.
h2 = 3, новая высота = max(7, 3) = 7
Результат = {(1, 11), (3, 13), (9, 0), (12, 7), (14, 7)}

Сравните (16, 0) и (19, 18). Поскольку первая полоса имеет меньший левый x, она добавляется к результату.
h1 = 0, новая высота = max(0, 3) = 3
Результат = {(1, 11), (3, 13), (9, 0), (12, 7), (14, 7), (16, 3)}

Поскольку элементов Skyline1 больше нет, добавляются все оставшиеся элементы Skyline2.
Результат = {(1, 11), (3, 13), (9, 0), (12, 7), (14, 7), (16, 3),
(19, 18), (22, 3), (23, 13), (29, 0)}

Замечание относительно приведенного выше вывода состоит в том, что полоса (14, 7) избыточна (уже есть полоса такой же высоты). Убираем все лишние элементы
группы.
Результат = {(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18),
(22, 3), (23, 13), (29, 0)}

В приведенном ниже коде избыточность обрабатывается путем отказа от добавления полосы, если предыдущая полоса в результате имеет ту же высоту.

линия горизонта разделяй и властвуй

линия горизонта разделяй и властвуй

Упражнение 15

Учитывая массив цитаты целых чисел, где citations[i] — количество цитирований, полученных исследователем для его i-й статьи, причем цитирования отсортированы в порядке возрастания, возвращаются для расчета h-индекса исследователя.

Согласно определению h-индекса Википедии: ученый имеет h-индекс, если каждая из его n статей имеет не менее h цитирований, а остальные n − h статей имеют не более h цитирований каждая.

Если возможных значений h несколько, то в качестве индекса h берется максимальное значение.

Ввод: кавычки = [0,1,3,5,6]
Выход: 3
Объяснение: [0,1,3,5,6] означает, что всего у исследователя 5 статей и каждая из них получила 0, 1, 3, 5, 6 ссылок соответственно.

Поскольку у исследователя есть 3 статьи, каждая из которых цитируется не менее чем по 3 раза, и две другие статьи, каждая из которых цитируется не более чем по 3 раза, их индекс Хирша равен 3.

Просто бинарный поиск, каждый раз проверяйте кавычки[mid]

случай 1: citations[mid] == len-mid, тогда это означает, что есть статьи citation[mid], которые имеют хотя бы Quotes[mid] цитирования.

случай 2: quotes[mid] > len-mid, тогда это означает, что существуют quotes[mid] статьи, в которых цитаты quote[mid] больше, поэтому нам следует продолжать искать в левой половине

случай 3: Quotes[mid] < len-mid, необходимо продолжить поиск в правой части

После итерации, право+1 гарантированно будет тем, что нам нужно найти (т.е. len-(право+1) статьи имеют по крайней мере len-(право+1) цитирования)

Следующий алгоритм написан в итеративной форме, но это принцип «разделяй и властвуй»:

H-индекс разделяй и властвуй

Упражнение 16

В задаче «Коко ест бананы» нам дан массив размера n, содержащий количество бананов в каждой стопке. За час Коко может съесть максимум K бананов. Если в куче бананов меньше K, то, если Коко съест все бананы в этой куче, она не сможет начать есть бананы из другой кучи в тот же час.

Коко хочет съесть все бананы за H часов. Требуется найти минимальное значение К.

батареи = [30,11,23,4,20], Н = 6. Здесь ответ 23.

Исправленные упражнения Разделяй и властвуй алгоритм разделяй и властвуй

Коко будет есть бананы таким образом, чтобы съесть все бананы за 6 часов:

Первый час: 23

Второй час: 7

Третий час: 11

Четвертый час: 23

Пятый час: 4

Шестой час: 20

Первое и самое важное, что нужно сделать для решения этой проблемы, — это произвести наблюдения. Вот некоторые наблюдения для нашего диапазона поиска:

Коко должен съедать хотя бы один банан в час. Итак, это минимальное значение K. Назовем его Start

Мы можем ограничить максимальное количество бананов, которое Коко может съесть за один час, до максимального количества бананов в куче среди всех куч. Следовательно, это максимальное значение K. Назовем его End.

Теперь у нас есть диапазон поиска. Предположим, что размер интервала равен Length, а количество стеков равно n. Наивный подход может состоять в том, чтобы проверять каждое промежуточное значение. если для этого значения K Коко может успешно съесть все бананы за час H, то выберем минимальное из них. Временная сложность для наивного подхода в худшем случае будет равна Length*n.

Мы можем улучшить временную сложность, используя бинарный поиск вместо линейного поиска. Алгоритм написан итеративно, но это действительно подход «разделяй и властвуй».

Исправленные упражнения Разделяй и властвуй алгоритм разделяй и властвуй

Упражнение 17

Дан отсортированный массив неотрицательных различных целых чисел, найти в нем наименьший отсутствующий неотрицательный элемент.

Например,

Ввод: числа [] = [0, 1, 2, 6, 9, 11, 15]
Результат: наименьший недостающий элемент равен 3


Ввод: числа[] = [1, 2, 3, 4, 6, 9, 11, 15]
Вывод: наименьший недостающий элемент равен 0


Ввод: числа [] = [0, 1, 2, 3, 4, 5, 6]
Результат: наименьший недостающий элемент равен 7.

Наивным решением было бы запустить линейный поиск по массиву и вернуть первый индекс, который не соответствует его значению. Если несовпадения не происходит, вернуть размер массива. Проблема с этим подходом заключается в том, что его временная сложность в наихудшем случае составляет O(n), где n — размер входных данных. Это решение также не использует тот факт, что ввод отсортирован.

Мы можем легко решить эту проблему за время O(log(n)), изменив алгоритм бинарного поиска (эквивалентно разделяй и властвуй). Идея состоит в том, чтобы сравнить медианный индекс с медианным элементом. Если они одинаковы, то несоответствие находится в правильном подмассиве; в противном случае он находится в левом подмассиве. Поэтому мы соответственно отбрасываем одну половину и возвращаемся за другой.

наименьший недостающий элемент

Упражнение 18

Дан массив целых чисел nums и целое число k, возвращает k-й по величине элемент массива.

Обратите внимание, что это k-й по величине элемент в отсортированном порядке, а не k-й отдельный элемент.

Вы должны решить это за O(nlogn) временную сложность.

Пример 1:

Вход: числа = [3,2,1,5,6,4], k = 2
Выход: 5

Пример 2:

Вход: числа = [3,2,3,1,2,4,5,5,6], k = 4
Выход: 4

Для решения этой задачи надо идти к самому простому. Отсортируйте массив за O(nlogn), затем выполните итерацию по нему от наибольшего к наименьшему. Счетчик увеличивается, как только мы меняем номер, мы возвращаем номер k-го изменения.

Упражнение 19

Учитывая массив целых чисел nums, вернуть массив целых чисел counts, где counts[i] — это количество меньших элементов справа от nums[i].

Ввод: числа = [5,2,6,1]
Вывод: [2,1,1,0]

Объяснение:
Справа от 5 есть 2 меньших элемента (2 и 1).
Справа от 2 находится только один меньший элемент (1).
Справа от 6 находится 1 меньший элемент (1).
Справа от 1 находится 0 меньший элемент.

Наименьшие числа справа от числа — это в точности те, которые прыгают справа налево во время стабильной сортировки. Поэтому я делаю сортировку слиянием с дополнительным отслеживанием этих переходов справа налево. Вот алгоритмы в их итеративной форме.

Сортируем пары (индекс, значение). Значение используется для сортировки, а индекс используется для отслеживания переходов.

Исправленные упражнения Разделяй и властвуй алгоритм разделяй и властвуй

Вы также можете сортировать только индексы и искать фактические числа для сравнения на лету. Может быть, немного проще понять и портировать на другие языки:

Исправленные упражнения Разделяй и властвуй алгоритм разделяй и властвуй

Упражнение 20

Для двух отсортированных массивов nums1 и nums2 размера m и n соответственно возвращает медиану двух отсортированных массивов.

Общая сложность времени выполнения должна быть O (log (m + n)).

Пример 1:

Ввод: nums1=[1,3], nums2=[2]
Выход: 2.00000
Объяснение: объединенный массив = [1,2,3], а медиана равна 2.

Пример 2:

Ввод: nums1=[1,2], nums2=[3,4]
Выход: 2.50000
Объяснение: объединенный массив = [1,2,3,4], а медиана равна (2 + 3)/2 = 2,5.

Давайте сначала посмотрим на понятие «МЕДИАНА» несколько нетрадиционным способом. Это сказать:

«если мы разрежем отсортированный массив на две половины РАВНОЙ ДЛИНЫ, то медианой будет СРЕДНЕЕ МАКСИМАЛЬНОЕ (нижняя_половина) и минимальное (верхняя_половина), то есть два числа, непосредственно следующие за разрезом».

Например, для [2 3 5 7] мы вырезаем между 3 и 5:
[2 3 / 5 7]
тогда медиана = (3+5)/2.

Вот алгоритм «разделяй и властвуй»:

Исправленные упражнения Разделяй и властвуй алгоритм разделяй и властвуй

найти k-й элемент в двух отсортированных массивах: A[aMid] <= B[bMid], x: середина длины a, y: середина длины b, тогда мы можем узнать

(1) перед bMid будет не менее (x + 1 + y) элементов
(2) будет не менее (m – x – 1 + n – y) = m + n – (x + y +1) элементов после aMid

Так

если k <= x + y + 1, найти k-й элемент в a и b, но не учитывать bMid и его суффикс

если k > x + y + 1, найти k – (x + 1)-й элемент в a и b, но без учета aMid и его префикса

Исправленные упражнения Разделяй и властвуй алгоритм разделяй и властвуй

Упражнение 21

Ваша задача состоит в том, чтобы вычислить a^b по модулю 1337, где a — положительное целое число, а b — очень большое положительное целое число, представленное в виде массива.

Знакомый: ab % k = (a%k)(b%k)%k

Поскольку мощность здесь представляет собой массив, нам лучше обрабатывать его цифра за цифрой. Вывод:

a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k = (a^123456 % k)^10 % k * (a^7 % k) % k

Вам это кажется сложным? Позвольте мне сказать по-другому:

Предположим, что f(a, b) вычисляет a^b % k; Затем переведите приведенную выше формулу, используя f:

f(a,1234567) = f(a,1234560) * f(a, 7)% k = f(f(a, 123456),10) * f(a,7)%k ;

Реализация этой идеи:

супер сила

Упражнение 22

Чтобы вычислить площадь под кривой, можно окружить кривую прямоугольником и сделать вывод, что площадь кривой по порядку величины площади прямоугольника.

Метод прямоугольников – это метод алгоритмический что позволяет получить оснащение интеграла. Как напоминание ; положительная функция на интервале [a,b], интегралом которой по этому интервалу является площадь под кривой, представляющей f и ось абсцисс.

В алгоритме «Разделяй и властвуй» интервал [a,b] разбивается на n интервалов шириной меньше порога k (k — точность вычисления интеграла).

Пусть I — середина интервала, поэтому площадь под кривой на этом интервале равна прямоугольнику, высота которого определяется f(I). Таким образом, площадь в исходном интервале равна сумме всех разделенных площадей.

Также можно ограничить площадь под кривой, считая, что она имеет тот же размер, что и сумма прямоугольников высоты f(a), и того же размера, что и сумма прямоугольников высоты f(b).

Существует третий метод моделирования площади под кривой: метод трапеций. 

Исправленные упражнения Разделяй и властвуй алгоритм разделяй и властвуй

Для вычисления площади трапеции ABED складываем площади прямоугольника ABCD и прямоугольного треугольника BEC. Площадь трапеции — это представление площади под кривой на интервале [a,b].

Алгоритмы очень простые. Пока пороговый размер не достигнут, мы возвращаем метод (a, (a+b)/2, функция) + метод ((a+b)/2, b, функция).

Это вычисление позволяет суммировать левую и правую части деления интервала. После достижения порога метод возвращает расчет площади, соответствующей изучаемому утверждению.

Для прямоугольников, указанных справа, мы будем иметь общую сумму:

метод прямоугольника

Для прямоугольников, указанных слева, мы будем иметь общую сумму:

метод прямоугольника

Для метода трапеций расчет каждого подинтервала осуществляется по следующей формуле:

Исправленные упражнения Разделяй и властвуй алгоритм разделяй и властвуй

Делиться
ru_RURU