Так как функция i ln i вогнута, легко показать, что

i ln i x ln x dx (3.6)

Подставляя (3.6) в (3.5), получаем

T(n)cn + + kn ln n -

Поскольку n2 и k=2с+2b, то сn+4 b/nkn/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], а S2S3-- в A[k+1], A[k+2], ..., A[l] при некотором k, fklЗатем можно, если нужно, расщепить S2S3, но обычно эффективнее просто рекурсивно вызвать БЫСТР-СОРТ на S1 и S2S3, если оба этих множества не пусты.

По-видимому, самый легкий способ разбить S на том же месте -- это использовать два указателя на массив, назовем их i и j. Вначале

begin

i f;

while ij do

begin

while A[i]>а и j>f do jj - 1;

while A[j]<а и il do ii + 1;

if < j then

begin

переставить А[i] и A[j];

ii + 1;

ij -1

end

еnd

еnd

Рис. 3.8. Разбиение S на S1 и S2S3 на месте их расположения.

i=f, и все время в A [f], ..., А [i-1] будут находиться элементы из S1. Аналогично вначале i=f, а в A[j+1], ..., A[l] все время будут находиться элементы из S2S3. Это разбиение производит подпрограмма на рис. 3.8.

Затем можно вызвать БЫСТРСОРТ для массива A[f], ... A[i--1], т.е. S1 и для массива A[j+1], ..., А[1], т.е. S2S3. Но если i=f то надо сначала удалить из S2S3 хотя бы один элемент, равный а. Удобно удалять тот элемент, по которому производилось разбиение. Следует также заметить, что если это представление в виде массива применяется для последова-тельностей, то можно подать аргументы для БЫСТРСОРТ, просто поставив указатели на первую и последнюю ячейку используемого куска массива.

Пример 3.5. Разобьем массив А

по элементу а=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)

i j

б)

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 файла, а также следующий пункт содержит листинг модуля.

Рисунок 2.3.1 Лист Excel, содержащий данные о студентах группы с указанием номера зачетки, ФИО студента, размера стипендии, года рождения и пола.

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

Затем происходит форматирование текста по заданному индивидуальному заданию, которое осуществляется просто записью макроса.

2.4.4 Листинг работы макроса

Sub практика()

'

' практика Макрос

'

'

Selection.Find.ClearFormatting

Selection.Find.Replacement.ClearFormatting

With Selection.Find

.Text = " "

.Replacement.Text = _

" "

.Forward = True

.Wrap = wdFindContinue

.Format = False

.MatchCase = False

.MatchWholeWord = False

.MatchWildcards = False

.MatchSoundsLike = False

.MatchAllWordForms = False

End With

Selection.Find.Execute Replace:=wdReplaceAll

Selection.WholeStory

With Selection.Font

.Name = "Arial"

.Size = 14

.Bold = False

.Italic = False

.Underline = wdUnderlineNone

.UnderlineColor = wdColorAutomatic

.StrikeThrough = False

.DoubleStrikeThrough = False

.Outline = False

.Emboss = False

.Shadow = False

.Hidden = False

.SmallCaps = False

.AllCaps = False

.Color = wdColorAutomatic

.Engrave = False

.Superscript = False

.Subscript = False

.Spacing = 0

.Scaling = 100

.Position = 0

.Kerning = 0

.Animation = wdAnimationNone

End With

Selection.ParagraphFormat.Alignment = wdAlignParagraphJustify

End Sub

2.4.5 Отчет о выполнении

Рисунок 2.4 а) Запись до выполнения макроса

Рисунок 2.4 б) Запись после выполнения макроса

На рисунках 2.4 а) и б) наглядно изображено работа макроса.

2.4.6 ВЫВОД

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

ЗАКЛЮЧЕНИЕ

Пройдя учебную практику :

- освоены способы ускоренного набора текста на примере десятипальцевого метода;

- закреплены навыки самостоятельного оформления технической документации по специальности в соответствии с ГОСТом и иными требованиями, предъявляемыми к ним законодательством,

- сформированы умения и закреплены навыки работы в текстовом редакторе MS Word в задачах оформления технической документации;

- сформированы умения и закреплены навыки работы с электронными таблицами MS Excel в задачах обработки, анализа и визуализации статистического и графического материала технической документации;

- закреплены умения автоматизировать рутинные процессы формирования технической документации с использованием макроязыка VBA и формул электронных таблиц.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Шахиджанян В.В. Соло на пишущей машинке. - М.: СП Вся Москва, 1992. - 172 с.

2. Егоренков А.А. Изучаем Microsoft Office XP: Word XP для начинающих. - М.: Лист Нью, 2004 - 288 с.

3. Шпак Ю.А. Microsoft Office 2003. Русская версия / Под ред. Ковтанюка Ю.С. - К.: Юниор, 2005 - 768 с.

4. Мюррей К. Microsoft Office System 2003 / Пер. c англ. Рожевского В. - СПб.: Питер, 2005 - 368 с.

5. Кронан Д. Microsoft Office Excel 2003 / Пер. c англ. Вереиной О.Б. - М.: НТ Пресс; Мн.: Харвест, 2005 - 224 с.

Страницы: 1, 2, 3