Информатика. Текстовый редактор
Аналогично,
если узел i
имеет двух
сыновей (т. е.
если 2i+1
n)
и наибольший
из элементов
в А [2i] и в А
[2i+1] больше
элемента в A
[i], то, рассуждая,
как и выше, можно
показать, что
после вызова
процедуры
ПЕРЕСЫПКА(i,n)
все узлы i,
i+1,..., n будут
корнями сортирующих
деревьев.
Теорема 3.5. Алгоритм 3.3 преобразует А в сортирующее дерево за линейное время.
Доказательство.
Применяя лемму
3.2, можно с помощью
простой возвратной
индукции по
i показать,
что узел i
становится
корнем какого-нибудь
сортирующего
дерева для всех
i, 1
i
n
Пусть Т (h)
— время выполнения
процедуры
ПЕРЕСЫПКА на
узле высоты
h. Тогда Т
(h)
Т
(h — 1)+с для
некоторой
постоянной
с. Отсюда вытекает,
что Т (h) есть
О (h).
Алгоритм
3.3 вызывает
процедуру
ПЕРЕСЫПКА, если
не считать
рекурсивных
вызовов, один
раз для каждого
узла. Поэтому
время, затрачиваемое
на ПОСТРСОРТДЕРЕВА,
имеет тот же
порядок, что
и сумма высот
всех узлов. Но
узлов высоты
i не больше,
чем
.
Следовательно,
общее время,
затрачиваемое
процедурой
ПОСТРСОРТДЕРЕВА,
имеет порядок
in/2
,
т.е O(n)
Теперь можно завершить детальное описание алгоритма СОРТДЕРЕВОМ. Коль скоро элементы массива А преобразованы в сортирующее дерево, некоторые элементы удаляются из корня по одному за раз. Это делается перестановкой А[1] и А[n] и последующим преобразованием A[1], А[2], ..., А[n - 1] в сортирующее дерево. Затем переставляются А[1] и А[n - 1], а A[1], А[2], ..., А [п - 2] преобразуется в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда А[1], А[2], ..., А[n] — упорядоченная последовательность.
Алгоритм 3.4. Сортдеревом
Вход. Массив
элементов А[i],
1
i
n.
Выход. Элементы массива А, расположенные в порядке неубывания.
Метод. Применяется процедура ПОСТРСОРТДЕРЕВА, т. е. алгоритм 3.3. Наш алгоритм выглядит так:
begin
ПОСТРСОРТДЕРЕВА;
For i
n
step -1 until 2
do
Begin
переставить А[1] и А[i];
ПЕРЕСЫПКА(i,i - 1)
End end
Теорема 3.6. Алгоритм 3.4 упорядочивает последовательность из п элементов за время 0(n log п).
Доказательство. Корректность алгоритма доказывается индукцией по числу выполнений основного цикла, которое обозначим через m. Предположение индукции состоит в том, что после m итераций список A[n-m+1], ..., А [n] содержит m наибольших элементов, расположенных в порядке неубывания, а список A[1], ..., А[n-m] образует сортирующее дерево. Детали доказательства оставляем в качестве упражнения. Время выполнения процедуры ПЕРЕСЫПКА(1, i) есть 0(log i)- Следовательно, алгоритм 3.4 имеет сложность О (n log i ).
Следствие.
Алгоритм Сортдеревом
имеет временную
сложность
O
(nlog
n)
3.5. БЫСТРСОРТ — УПОРЯДОЧЕНИЕ ЗА СРЕДНЕЕ ВРЕМЯ О(n log n)
До сих пор мы рассматривали поведение сортирующих алгоритмов только в худшем случае. Для многих приложений более реалистичной мерой временной сложности является усредненное время работы. В случае сортировки с помощью деревьев решений мы видим, что никакой сортирующий алгоритм не может иметь среднюю временную сложность, существенно меньшую n 1оg n. Однако известны алгоритмы сортировки, которые работают в худшем случае сn2 времени, где с — некоторая постоянная, но среднее время работы, которых относит их к лучшим алгоритмам сортировки. Примером такого алгоритма служит алгоритм Быстрсорт, рассматриваемый в этом разделе.
Чтобы можно было рассуждать о среднем времени работы алгоритма, мы должны договориться о вероятностном распределении входов. Для сортировки естественно допустить, что мы и сделаем, что любая перестановка упорядочиваемой последовательности равновероятна в качестве входа. При таком допущении уже можно оценить снизу среднее число сравнений, необходимых для упорядочения последовательности из n элементов.
Общий метод
состоит в том,
чтобы поставить
в соответствие
каждому листу
v дерева
решений вероятность
быть достигнутым
при данном
входе. Зная
распределение
вероятностей
на входах, можно
найти вероятности,
поставленные
в соответствие
листьям. Таким
образом, можно
определить
среднее число
сравнений,
производимых
данным алгоритмом
сортировки,
если вычислить
сумму взятую
по всем листьям
дерева решений
данного алгоритма,
в которой рi
— вероятность
достижения
i-го листа,
а d
,
- его глубина.
Это число называется
средней глубиной
дерева решений.
Итак, мы пришли
к следующему
обобщению
теоремы 3.4.
Теорема 3.7. В предположении, что все перестановки п-элементной последовательности появляются на входе с равными вероятностями, любое дерево решений, упорядочивающее последовательность из п элементов, имеет среднюю глубину не менее log n!.
Доказательство.
Обозначим через
D (Т) сумму
глубин листьев
двоичного
дерева Т. Пусть
D (Т) — ее
наименьшее
значение, взятое
по всем двоичным
деревьям Т с
m листьями.
Покажем индукцией
по m, что
D(m)
m
log m.
Базис, т. е.
случай /п=1, тривиален.
Допустим, что
предположение
индукции верно
для всех значений
m, меньших
k. Рассмотрим
дерево решений
Т с и листьями.
Оно состоит
из корня с левым
поддеревом
Т с k листьями
и правым поддеревом
T
с k – 1 листьями
при некотором
i, 1
i
k.
Ясно, что
D(T)=i+D(T
)+(k-i)+D(T
)
Поэтому наименьшее значение D (Т) дается равенством
D(k)=
[k+D(i)+D(k-1)]. (3.1)
Учитывая предположение индукции, получаем отсюда
D(k)
k+
[i
log i+(k-i)log(k-i)] (3.2)
Легко показать,
что этот минимум
достигается
при i=k/2.
Следовательно,
D(k)
k+k
log
=k log k
Таким образом,
D (m)
m
log m для
всех m
1.
Теперь мы
утверждаем,
что дерево
решений Т,
упорядочивающее
n случайных
элементов,
имеет не меньше
/г! листьев. Более
того, в точности
п листьев появляются
с вероятностью
1/n! каждый,
а остальные
— с вероятностью
0. Не изменяя
средней глубины
дерева Т можно
удалить из него
все узлы, которые
являются предками
только листьев
вероятности
0. Тогда останется
дерево Т' с n!
листьями, каждый
из которых
достигается
с вероятностью
1/п!. Так как D(Т')
n!
log n!, то
средняя глубина
дерева Т' (а значит,
и Т) не меньше
(1/n!) n! log
n! = log n!.
Следствие. Любая сортировка с помощью сравнений выполняет в среднем не менее сп log n сравнений для некоторой постоянной с>0.
Заслуживает упоминания эффективный алгоритм, называемый Быстрсорт, поскольку среднее время его работы, хотя и ограничено снизу функцией сn lоg n для некоторой постоянной с (как и у всякой сортировки с помощью сравнений), но составляет лишь часть времени работы других известных алгоритмов при их реализации на большинстве существующих машин. В худшем случае Быстрсорт имеет квадратичное время работы, но для многих приложений это не существенно.
Procedure БЫСТРСОРТ(S):
if S содержит не больше одного элемента then return S
else
begin выбрать произвольный элемент a из S;
пустьS1, S2 и S3 — последовательности элементов из S,
соответственно меньших, равных и больших а;
return (БЫСТРСОРТ(S1), затем S2, затем БЫСТРСОРТ (S3))
end
Рисунок 3.7. Программа Быстрсорт.
Алгоритм 3.5. Быстрсорт
Вход. Последовательность S из n элементов aь a2, ... , aп.
Выход. Элементы последовательности S, расположенные по порядку.
Метод. Рекурсивная процедура БЫСТРСОРТ определяется на рис. 3.7. Алгоритм состоит в вызове БЫСТРСОРТ(S).
Теорема 3.8. Алгоритм 3.5. упорядочивает последовательность из п элементов за среднее время О (п log п).
Доказательство. Корректность алгоритма 3.5 доказывается прямой индукцией по длине последовательности S. Чтобы проще было анализировать время работы, допустим, что все элементы в S различны. Это допущение максимизирует размеры последовательностей S1 и S3, которые строятся в строке 3, и тем самым максимизирует среднее время, затрачиваемое в рекурсивных вызовах в строке 4. Пусть Т (n) — среднее время, затрачиваемое алгоритмом БЫСТРСОРТ на упорядочение последовательности из n элементов. Ясно, что Т(0)=Т(1)=b для некоторой постоянной b.
Допустим, что элемент а, выбираемый в строке 2, является 1-м наименьшим элементом среди n элементов последовательности S. Тогда на два рекурсивных вызова БЫСТРСОРТ в строке 4 тратится среднее время Т(i - 1) и Т (n - i) соответственно. Так как i равновероятно принимает любое значение между 1 и n, а итоговое построение последовательности БЫСТРООРТ(S) очевидно занимает время cn для некоторой постоянной с, то
T(n)
cn+
[T(i-1)+T(n-1)]
для n
2
(3.3)
Алгебраические преобразования в (3.3) приводят к неравенству
T(n)
cn+![]()
T(i) (3.4)
Покажем, что
при n
2
справедливо
неравенство
Т (n)<kn
1n n, где
k=2с+2b и
b=Т(0)=T(1).
Для базиса
(n=2) неравенство
Т(2)
2с+2b
непосредственно
вытекает из
(3.4). Для проведения
шага индукции
запишем (3.4) в виде
T(n)
cn
+
+
![]()
ki
ln i (3.5)
Так как функция i ln i вогнута, легко показать, что
i
ln i
x
ln x dx
![]()
(3.6)
Подставляя (3.6) в (3.5), получаем
T(n)
cn
+
+ kn ln n
-
![]()
Поскольку
n
2
и k=2с+2b,
то сn+4 b/n
kn/2.
Таким образом,
неравенство
Т (n)
kn
1n n следует
из (3.7).
Рассмотрим две детали, важные для практической реализации алгоритма. Первая — способ "произвольного" выбора элемента а в строке 2 процедуры БЫСТРСОРТ. При реализации этого оператора может возникнуть искушение встать на простой путь, а именно всегда выбирать, скажем, первый элемент последовательности S. Подобный выбор мог бы оказаться причиной значительно худшей работы алгоритма БЫСТРСОРТ, чем это вытекает из (3.3). Последовательность, к которой применяется подпрограмма сортировки, часто бывает уже "как-то" рассортирована, так что первый элемент мал с вероятностью выше средней. Читатель может проверить, что в крайнем случае, когда БЫСТРСОРТ начинает работу на уже упорядоченной последовательности без повторений, а в качестве элемента а всегда выбирается первый элемент из S, в последовательности S всегда будет на один элемент меньше, чем в той, из которой она строится. В этом случае БЫСТРСОРТ требует квадратичного числа шагов.
Лучшей техникой для выбора разбивающего элемента в строке 2 было бы использование генератора случайных чисел для порождения целого числа i, 1<i<|S| 1), и выбора затем i-го элемента из S в качестве а. Более простой подход — произвести выборку элементов из S, а затем взять ее медиану в качестве разбивающего элемента. Например, в качестве разбивающего элемента можно было бы взять медиану выборки, состоящей из первого, среднего и последнего элементов последовательности S.
Вторая деталь
— как эффективно
разбить S
на три последовательности
S1, S2 и
S3? Можно (и
желательно)
иметь в массиве
А все n исходных
элементов. Так
как процедура
БЫСТРСОРТ
вызывает себя
рекурсивно,
ее аргумент
S всегда
будет находиться
в последовательных
компонентах
массива, скажем
A[f], A[f+1],
..., A[l] для некоторых
f и l,
1<f<n.
Выбрав "произвольный"
элемент а, можно
устроить разбиение
последовательности
S на этом
же месте. Иными
словами, можно
расположить
S1 в компонентах
A[f], A[f+1],
... A[k], а
S2
S3—
в A[k+1],
A[k+2], ..., A[l]
при некотором
k, f
k
lЗатем
можно, если
нужно, расщепить
S2
S3,
но обычно эффективнее
просто рекурсивно
вызвать БЫСТРСОРТ
на S1 и S2
S3,
если оба этих
множества не
пусты.
По-видимому, самый легкий способ разбить S на том же месте — это использовать два указателя на массив, назовем их i и j. Вначале
begin
i
f;
while i
j
do
begin
while A[i]>а
и j>f do j
j
- 1;
while A[j]<а
и i
l
do i
i
+ 1;
if < j then
begin
переставить А[i] и A[j];
i
i
+ 1;
i
j
-1
end
еnd
еnd
Рис. 3.8. Разбиение
S на S1
и S2
S3
на месте их
расположения.
i=f,
и все время в
A [f], ..., А
[i-1] будут
находиться
элементы из
S1. Аналогично
вначале i=f,
а в A[j+1],
..., A[l] все
время будут
находиться
элементы из
S2
S3.
Это разбиение
производит
подпрограмма
на рис. 3.8.
Затем можно
вызвать БЫСТРСОРТ
для массива
A[f], ... A[i—1],
т.е. S1 и для
массива A[j+1],
..., А[1], т.е. S2
S3.
Но если i=f
то надо сначала
удалить из
S2
S3
хотя бы один
элемент, равный
а. Удобно удалять
тот элемент,
по которому
производилось
разбиение.
Следует также
заметить, что
если это представление
в виде массива
применяется
для последовательностей,
то можно подать
аргументы для
БЫСТРСОРТ,
просто поставив
указатели на
первую и последнюю
ячейку используемого
куска массива.
Пример 3.5. Разобьем массив А
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 6 | 9 | 3 | 1 | 2 | 7 | 1 | 8 | 3 |
по элементу
а=3. while-оператор
(строка 4) уменьшает
j с 9 до 7, поскольку
числа A[9]=3
и A[8]=8 оба не
меньше а, но
A[7]=1<а. Строка
5 не увеличивает
i с его начального
значения 1, поскольку
A[1]=6
а.
Поэтому мы
переставляем
A[1] и A
[7], полагаем i=2,
j=6 и получаем
массив на рис.
3.9, а. Результаты,
получаемые
после следующих
двух срабатываний
цикла в строках
3—9, показаны
на рис. 3.9, б и в. В
этот момент
i>j, и
выполнение
while-оператора,
стоящего в
строке 3, заканчивается.
a)
| 1 | 9 | 3 | 1 | 2 | 7 | 6 | 8 | 3 |
![]()
i
j
б)
| 1 | 2 | 1 | 3 | 9 | 7 | 6 | 8 | 3 |
![]()
j
i
Рис. 3.9. Разбиение массива.
2.2.4 Вывод
Проделав индивидуальное задание, были получены основные умения по набору текстового и графического материала, приведя материал в соответствии с ГОСТ.
2.3 Средство обработки информации MS Excel
MS Exсel - мощное средство обработки информации корпорации Майкрософт, которая имеет множество утилит необходимых для набора и обработки информации.
2.3.1 Тема, задание, цель
Тема - работа с электронными таблицами MS Excel.
Цель - получить основные умения по работе с электронными таблицами.
Задания индивидуальные в рабочем порядке.
2.3.2 Исходные данные и индивидуальное задание
Дан файл Excel, содержащий данные о студентах группы с указанием номера зачетки, ФИО студента, размера стипендии, года рождения и пола. На другом листе вывести список, упорядоченный по увеличению стипендии. Форматирование и заполнение итоговых ячеек выполнить в модуле.
2.3.3 Отчет о выполнении
Отчетом о выполнении данного задания будет электронный вид листа excel, предоставленный руководителю практики. В данном отчете будет предоставлен рисунок работы exel файла, а также следующий пункт содержит листинг модуля.
|
ФИО |
Номер зачетной книжки |
Стипендия |
Год рождения |
Пол |
| Азаров Игорь | 87934 | 150.5 | 16.10.1988 | м |
| Анцибор Наталья | 87967 | 151.0 | 13.05.1988 | ж |
| Бандорчук Алексей | 65477 | 143.5 | 03.07.1987 | м |
| Булавин Александр | 77685 | 155.5 | 04.05.1988 | м |
| Гуляева Мария | 67545 | 120.5 | 12.07.1989 | ж |
| Давыдова Екатерина | 45654 | 160.0 | 01.07.1988 | ж |
| Дандыкин Александр | 65465 | 130.0 | 23.12.1988 | м |
| Звада Инна | 56765 | 110.0 | 25.11.1987 | ж |
| Калашников Максим | 86985 | 123.5 | 19.10.1988 | м |
| Морчук Станислав | 65365 | 143.0 | 25.10.1988 | м |
| Полярова Ксения | 35676 | 150.0 | 13.05.1989 | ж |
| Солодовник Михаил | 35686 | 147.0 | 18.08.1988 | м |
| Усенко Тарас | 45676 | 159.5 | 23.11.1987 | м |
Рисунок 2.3.1 Лист Excel, содержащий данные о студентах группы с указанием номера зачетки, ФИО студента, размера стипендии, года рождения и пола.
|
ФИО |
Номер зачетной книжки |
Стипендия |
Год рождения |
Пол |
| Звада Инна | 56765 | 110.0 | 25.11.1987 | ж |
| Гуляева Мария | 67545 | 120.5 | 12.07.1989 | ж |
| Калашников Максим | 86985 | 123.5 | 19.10.1988 | м |
| Дандыкин Александр | 65465 | 130.0 | 23.12.1988 | м |
| Морчук Станислав | 65365 | 143.0 | 25.10.1988 | м |
| Бандорчук Алексей | 65477 | 143.5 | 03.07.1987 | м |
| Солодовник Михаил | 35686 | 147.0 | 18.08.1988 | м |
| Полярова Ксения | 35676 | 150.0 | 13.05.1989 | ж |
| Азаров Игорь | 87934 | 150.5 | 16.10.1988 | м |
| Анцибор Наталья | 87967 | 151.0 | 13.05.1988 | ж |
| Булавин Александр | 77685 | 155.5 | 04.05.1988 | м |
| Усенко Тарас | 45676 | 159.5 | 23.11.1987 | м |
| Давыдова Екатерина | 45654 | 160.0 | 01.07.1988 | ж |
Рисунок 2.3.2 Лист excel выводящий список, упорядоченный по увеличению стипендии.
Рисунок 2.3.1 и рисунок 2.3.2 – предоставляют отчет о выполнении индивидуального задания, предоставленный в пункте 2.3.2.
2.3.4 Листинг модуля
Sub практика()
'
'Сочетание клавиш : Ctrl+w
'
Sheets("Лист2").Select
Range("A1:E14").Sort Key1:=Range("C2"), Order1:=xlAscending, Header:= _
xlGuess, OrderCustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, _
DataOption1:=xlSortNormal
End Sub
Данный листинг модуля показывает, что при нажатии сочетании клавиш Ctrl + w происходит переход на другой лист, где происходит сортировка личностей по возрастанию стипендий.
2.3.4 Вывод
Проделав индивидуальное задание, были получены основные умения по работе с электронными таблицами.
2.4 Средство обработки информации VISUAL BАSIC
Visual Basic - средство программирования информации корпорации Майкрософт в Microsoft Worde. Данный программный продукт является мощным дополнения Microsoft Word, который служит для составления программ и макросов в Microsoft Worde.
2.4.1 Тема, задание, цель
Тема - работа с макросам VBA.
Задание – индивидуальное задание.
Цель – получить навыки работа с макросам VBA.
2.4.2 Исходные данные и индивидуальное задание
Дан текст. Сформировать файл report.txt со словами данного текста (каждое слово с новой строки), исходный текст отформатировать по ширине, шрифт Arial 14 .
2.4.3 Алгоритм
Макрос записывается на поиске и замене пробелов в тексте. В случае, если существует пробелы они заменяются на enter, что переводит каждое слово на новую