Xreferat.com » Рефераты по информатике и программированию » Информатика. Текстовый редактор

Информатика. Текстовый редактор

процедуры ПЕРЕСЫПКА переставляет А[i] и А[2i]. В строке 4 вызывается ПЕРЕСЫПКА (2i, n); поэто­му из предположения индукции вытекает, что дерево с корнем 2i будет переделано в сортирующее. Что касается узлов i+1, i+2, . . . . . ., 2i — 1, то они и не переставали быть корнями сортирующих деревьев. Так как после этой новой перестановки в массиве А вы­полняется неравенство A[i]>A[2i], то дерево с корнем i также оказывается сортирующим.

Аналогично, если узел 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, что переводит каждое слово на новую

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: