информатика. Игнатьева Елена Александровна, Измайлова Елена Ивановна. Информатика. Электронный ресурс методические указания
 Скачать 4.32 Mb.
|
|
Сортировка методом прямого обмена Оба разбиравшихся выше метода можно тоже рассматри- вать как "обменные" сортировки. Для рассматриваемого ниже метода обмен местами двух элементов представляет собой характерную особенность процес- са. Изложенный ниже алгоритм прямого обмена основан на сравнении и смене мест для пары соседних элементов и продол- жении этого процесса до тех пор, пока не будут упорядочены все элементы. Как и в методе прямого выбора, мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент "оставшейся" части последовательности к левому концу массива. Если мы будем рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпрети- ровать как пузырьки в чане с водой, причем вес каждого пузырь- ка соответствует значению элемента. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответст- вующего его весу. Такой метод широко известен под именем "пу- зырьковая сортировка". Текстовый алгоритм: 1. Начало. 2. Выполнить цикл, пока i имеет значения от 2 до N, шаг = +1: а) выполнить цикл, пока j имеет значения от N до i, шаг = -1: тело цикла: если А(j-1) > А(j), то меняем местами эти два элемента. 3. Конец. На рисунке 5 представлена блок-схема сортировки методом прямого обмена. 153 Рис. 5. Блок-схема сортировки методом прямого обмена Если сравнивать свойства алгоритмов первых двух методов, то оказывается, что при сортировке прямым выбором число про- изводимых сравнений больше, а число перемещений элементов – меньше, чем при сортировке прямым включением. В целом же большой разницы в эффективности этих методов нет. Сортировка методом прямого обмена имеет меньшую эф- фективность. Число шагов просмотра с обменом ≤ (n – 2), и из-за того, что "легкие" элементы "всплывают" по несколько сразу, то кажется, что сортировка происходит быстро. Но с другой сторо- ны, "тяжелые" элементы, если они находятся наверху, переме- щаются вниз на одну позицию при каждом шаге, что увеличивает время сортировки. Число обменов элементов оказывается до- вольно большим. На рисунке 6 приведен пример сортировки методом прямого обмена. i = 2, N, 1 A(j-1) > A(j) ет j = N, i, -1 X = A(j-1) A(j-1) = A(j) а A(j) = X 154 Исходн ая последовате I = 1 I = 2 I = 3 I = 4 I = 5 I = 6 I = 7 I = 8 44 0 6 0 6 0 6 0 6 0 6 0 6 0 6 0 6 55 4 4 1 2 1 2 1 2 1 2 1 2 1 2 1 2 12 5 5 4 4 1 8 1 8 1 8 1 8 1 8 1 8 42 1 2 5 5 4 4 4 2 4 2 4 2 4 2 4 2 94 4 1 8 5 5 4 4 4 4 4 4 4 4 4 4 18 9 4 4 2 4 2 5 5 5 5 5 5 5 5 5 5 06 1 8 9 4 6 7 6 7 6 7 6 7 6 7 6 7 67 6 7 6 7 9 4 9 4 9 4 9 4 9 4 9 4 Рис. 6. Пример сортировки методом прямого обмена Сортировка бинарными включениями Идея метода сходна с сортировкой прямыми включениями. Так же из неотсортированной части на i-ом шаге извлекается i-ый элемент, которому ищется место в уже "готовой" части последо- вательности. Однако процесс поиска места включения протекает в несколько раз быстрее. Суть метода заключается в следующем: Часть последовательности до испытуемого (i-ого) элемента ("готовая" часть) делится пополам и i-ый элемент сравнивается с элементом, стоящим на середине, после чего границы поиска уменьшаются в два раза. Получившийся полуинтервал делится пополам, и процесс повторяется до тех пор, пока не будет опре- делено место включения i-ого элемента. Затем происходит сдвиг вправо на одну позицию тех элементов, которые расположены от места включения до i-ого элемента, освобождая таким образом позицию для i-ого элемента. Текстовый алгоритм: 1. Начало. 2. Выполнить цикл, пока I имеет значение от 2 до N с ша- гом = 1 а) X = A(i), l = 1, r = i-1 б) Если l > r, то: 155 1) выполнить цикл, пока j имеет значение от (i-1) до l с ша- гом = -1 тело цикла: A(j + 1) = A(j) 2) присвоить A(l) = X иначе: 1) присвоить m = (l + r) \ 2 2) если X < A(m), то r = m – 1 иначе l = m + 1 3) перейти к пункту б). 3. Конец. На рисунке 7 приведен пример выполнения сортировки би- нарными включениями. Исходн ая последовате 4 4 5 5 1 2 4 2 9 4 1 8 0 6 6 7 I = 2 4 4 5 5 1 2 4 2 9 4 1 8 0 6 6 7 I = 3 1 2 4 4 5 5 4 2 9 4 1 8 0 6 6 7 I = 4 1 2 4 2 4 4 5 5 9 4 1 8 0 6 6 7 I = 5 1 2 4 2 4 4 5 5 9 4 1 8 0 6 6 7 I = 6 1 2 1 8 4 2 4 4 5 5 9 4 0 6 6 7 I = 7 0 6 1 2 1 8 4 2 4 4 5 5 9 4 6 7 I = 8 0 6 1 2 1 8 4 2 4 4 5 5 6 7 9 4 Резуль- тат 0 6 1 2 1 8 4 2 4 4 5 5 6 7 9 4 Рис. 7. Пример выполнения сортировки бинарными включениями На рисунке 8 представлена блок-схема сортировки бинар- ными включениями. 156 Рис. 8. Блок-схема сортировки бинарными включениями Шейкер – сортировка Как и алгоритм сортировки прямого обмена, алгоритм шей- кер – сортировки основан на сравнении и смене мест пары сосед- них элементов. Однако в рассматриваемом методе каждый шаг состоит из двух этапов. 157 На первом этапе наименьший элемент неотсортированной части последовательности сдвигается к левому краю этой части, а наибольший элемент из оставшейся неотсортированной части сдвигается к правому краю этой части массива. После выполне- ния данных этапов неотсортированная часть массива уменьшает- ся на два элемента. Шаги выполняются, пока не будет отсортиро- ван весь массив. Текстовый алгоритм: 1. Начало. 2. Присвоить переменной t (слева массива) значение 2, пе- ременной r (справа массива) и переменной k – значение количе- ства элементов массива. 3. Выполнить цикл, пока i имеет значение от r до t с ша- гом = -1: а) если A(i-1) > A(i), то меняем местами эти два элемента и переменной k присваиваем значение = i. 4. Присвоить переменной t значение = k + 1. 5. Выполнить цикл, пока i имеет значение от t до r с ша- гом = 1: а) если A(i-1) > A(i), то меняем местами эти два элемента и переменной k присваиваем значение = i. 6. Присвоить переменной r значение = k – 1. 7. Если t > r, то идти к пункту 8, иначе идти к пункту 3. 8. Конец. На рисунке 9 представлен пример выполнения шейкер – сортировки по шагам. Исходн ая последовател 4 4 5 5 1 2 4 2 9 4 1 8 0 6 6 7 1-й этап 06 44 55 12 42 94 18 67 1-й шаг 2-й этап 06 44 12 42 55 18 67 94 1-й этап 06 12 44 18 42 55 67 94 2-й шаг 2-й этап 06 12 18 42 44 55 67 94 3-й шаг 1-й этап 06 12 18 42 44 55 67 94 Резуль- тат 0 6 1 2 1 8 4 2 4 4 5 5 6 7 9 4 Рис. 9. Пример выполнения шейкер – сортировки 158 На рис. 10 приведена блок-схема шейкер – сортировки. Рис. 10. Блок-схема шейкер – сортировки 159 Из примера, приведенного на рисунке 9 видно, что после первого шага длина неотсортированной части уменьшилась на два элемента, а после второго шага длина неотсортированной части вместо двух уменьшилась сразу на 4 элемента. Это допол- нительное уменьшение обеспечивает переменная k, показываю- щая при каком значении i был совершен последний обмен места- ми двух элементов. Благодаря переменной k быстрее увеличива- ется и быстрее уменьшается левая (t = k + 1) и правая (r = k – 1) границы неотсортированной части. 3. ПОРЯДОК ВЫПОЛНЕНИЯ 1. Получить задание у преподавателя. 2. Выполнить задание в соответствии с вариантом. 3. Ответить на контрольные вопросы. 4. ЗАДАНИЕ Выполнить сортировку одномерного массива, на языке про- граммирования, указанного преподавателем в соответствии с за- данным вариантом. 1. Известен список фамилий и рост учеников класса. Напе- чатать в порядке возрастания роста список детей, используя ме- тод шейкер – сортировки. 2. Известен список спортсменов и результат их прыжков в длину. Напечатать общий список в порядке возрастания резуль- тата, используя метод сортировки бинарными включениями. 3. Известен список биатлонистов и результаты их стрельбы на двух огневых рубежах (попадания). На каждом рубеже пять мишеней. Напечатать общий список биатлонистов в порядке убывания результата на втором огневом рубеже, используя метод прямого выбора. 4. Известен список студентов группы и количество пропу- щенных часов каждым из студентов. Напечатать список студен- тов в порядке возрастания количества пропущенных часов (если пропуски имеют место), используя сортировку прямыми включе- ниями. 160 5. Известен список рабочих и их месячный заработок. На- печатать список рабочих в порядке убывания зарплаты, исполь- зуя метод сортировки прямыми включениями. 6. Задан числовой массив, состоящий из J элементов. На- печатать отрицательные числа в порядке возрастания по модулю, используя шейкер – сортировку. 7. Задан числовой массив, состоящий из J элементов. На- печатать положительные числа в порядке убывания, используя метод прямого выбора. 8. Известен список фамилий и вес студентов вашей груп- пы. Напечатать в порядке возрастания список студентов, вес ко- торых не меньше среднего веса всей группы. Для этого использо- вать метод сортировки бинарными включениями. 9. Дан одномерный массив из I целых чисел. Напечатать отрицательные числа в порядке возрастания по модулю, а поло- жительные числа в порядке убывания, используя метод прямого обмена. 10. Известен список студентов группы и количество пропу- щенных часов каждым из студентов. Напечатать в порядке воз- растания тех, кто пропустил более 10 часов, используя метод сор- тировки прямыми включениями. 11. Известен список спортсменов и результат их прыжков в длину. Напечатать в порядке убывания тех, чей результат меньше 3 метров, используя сортировку прямого выбора. 12. Известен список спортсменов и результат их прыжков в длину. Напечатать в порядке возрастания тех, чей результат больше 3 метров, используя шейкер – сортировку. 13. Известен список фамилий и рост учеников класса. Напе- чатать в порядке убывания тех, чей рост меньше 160 см, исполь- зуя сортировку бинарными включениями. 14. Известен список фамилий и рост учеников класса. На- печатать в порядке возрастания тех, чей рост больше 160 см, ис- пользуя сортировку прямого обмена. 161 5. КОНТРОЛЬНЫЕ ВОПРОСЫ 1. Что такое сортировка? 2. Объясните суть метода сортировки методом прямого включения. 3. Объясните суть метода сортировки методом прямого вы- бора. 4. Объясните суть сортировки методом прямого обмена. 5. Объясните суть сортировки бинарными включениями. 6. Объясните суть шейкер – сортировки. 7. Что обеспечивает дополнительное уменьшение неотсор- тированной части в шейкер – сортировки? 162 Лабораторная работа № 9 Работа со строками 1. ЦЕЛЬ РАБОТЫ Изучение синтаксиса стандартных строковых процедур и функций, встроенных в язык программирования высокого уровня Visual Basic for Applications (VBA), получение навыков примене- ния строковых процедур и функций в программах пользователя при работе с данными строкового типа. 2. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ Общие положения VBA – великолепное сочетание одного из самых простых языков программирования BASIC со специальным механизмом, позволяющим программам, написанным на этом языке, обра- щаться к объектам всех основных приложений Microsoft Office — Excel, Word, Power Point, Access и прочих. VBA – мощное средство разработки настоящих полнофунк- циональных программ, работающих в среде приложений Microsoft Office. VBA поддерживает важнейшие современные концепции разработки программных систем — объектно-ориентированное и событийно-управляемое программирование, а также важнейшие технологии – поддержку элементов управления на базе ActiveX, интеграцию с базами данных, системами электронной почты и Интернетом. VBA содержит все средства, характерные для современных средств разработки программного обеспечения: интегрирован- ную среду разработки, конструктор форм, мощный отладчик, не уступающий по возможностям отладчикам некоторых современ- ных компиляторов. Данные в VBA характеризуются своими типами, которые определяют: формат представления данных в памяти компьютера; область возможных значений; множество допустимых операций, применимых к данным. 163 В свою очередь типы данных делятся на простые (встроен- ные и определяемые) и на структурные. Переменную можно объявлять или не объявлять, и тогда тип ей будет присвоен по умолчанию, или по первой букве име- ни, или по специальному символу объявления типа, которым мо- жет заканчиваться имя. Явно объявить переменную можно как в начале блока, так и в том произвольном месте, где возникла не- обходимость использовать новую переменную. Соображения повышения надежности программ рекомен- дуют использовать методику, при которой все переменные объ- являются явно и, как правило, в начале блока. При включении в начало модуля оператора Option Explicit (опция "Явно") предва- рительное объявление переменных становится обязательным. При объявлении переменной определяется ее тип и область видимости – область, где имя переменной видимо и, значит, воз- можен доступ к её значению. Переменные можно объявлять на двух уровнях – уровне процедуры и уровне модуля. Для объявле- ния переменных используются операторы Dim, Public, Private и Static. Первый можно использовать на обоих уровнях, Public и Private – на уровне модуля, Static – только на уровне процедуры. Переменные, объявленные на уровне процедуры, называют- ся локальными по отношению к данной процедуре. Их областью видимости является только та процедура, в которой они объявле- ны. Локальные переменные можно объявлять в любом месте процедуры, но до выполняемых операторов, использующих эти переменные. Переменные уровня модуля являются глобальными. Они объявляются в разделе Declarations, который есть у каждого мо- дуля. Область видимости глобальных переменных может распро- страняться: на все процедуры одного модуля, в котором они объяв- лены; такие глобальные переменные, называемые закрытыми (Private), должны быть объявлены на уровне модуля либо опера- тором Private либо оператором Dim; на все приложение – все процедуры всех модулей дан- ного приложения, такие глобальные переменные, называемые от- крытыми, должны быть объявлены оператором Public. 164 Локальные переменные уровня процедуры могут быть объ- явлены оператором Static, что делает их статическими. Для локальных переменных, объявленных таким образом, изменяется механизм хранения их (переменных) в оперативной памяти и время существования соответствует времени с момента первого запуска процедуры/функции, в которой определена ста- тическая переменная, до окончания работы программы. Обычные локальные переменные создаются и инициализируются (им при- сваивается значение) в "своей" процедуре/функции, видимы только в ней и удаляются при завершении этой процеду- ры/функции (память под переменные отводится при входе в про- цедуру/функцию, а при выходе она освобождается). Область ви- димости статической переменной такая же, но время существова- ния иное, так как статическая переменная не удаляется из памяти при завершении процедуры/функции, просто переменная стано- вится временно недоступной. Поэтому при повторном вызове процедуры/функции статические переменные восстанавливают те значения, которые они имели при завершении работы процеду- ры/функции при предыдущем вызове. Статические переменные – это хранители информации между многократными вызовами од- ной и той же процедуры/функции. Чтобы статические перемен- ные имели смысл, необходима первоначальная инициализация переменных – они должны иметь хоть какие-то значения уже при первом вхождении в процедуру/функцию. Вот как VBA инициа- лизирует переменные в момент их объявления: 0 – для числовых значений; пустая строка («») – для строк переменной длины; строка, содержащая нули, – для строк фиксированной длины; Empty (значение, указывающее на отсутствие инициа- лизации) - для статических переменных типа Variant; для массивов каждый элемент инициализируется в со- ответствии с указанными правилами. Объявление простых переменных имеет следующий синтак- сис: {Dim | Private | Public | Static }<имя переменной> [ As <имя типа>] [, <имя переменной> [ As <имя типа>]]; 165 Вначале идет имя оператора, а потом список объявлений переменных, где роль разделителя играет запятая. Объявление связывает имя переменной с ее типом, заданным конструкцией As. Когда она опущена, переменная получает тип Variant. Одним оператором Dim можно объявить произвольное число перемен- ных, но конструкция As должна быть указана для каждой из них, иначе переменным без As будет присвоен тип Variant. Строковый тип данных String Строкой называется не только последовательность симво- лов, заключённых в кавычки, но и переменная строкового типа, объявленная с помощью ключевого слова String. Строка как переменная может иметь переменную или по- стоянную длину. Строка переменной длины характеризуется тем, что зани- маемый ею объём оперативной памяти может меняться в процес- се выполнения программы. Строка постоянной длины занимает фиксированный объём оперативной памяти. При её объявлении после ключевого слова String ставится значок * (звёздочка) и указывается объём памяти (в байтах), выделяемый этой строке. Пример: Dim A As String Dim B As String*15 A = "Информатика" В = "Информатика" В примере переменная А – строка переменной длины, пере- менная В – строка постоянной длины. После выполнения опера- тора А = "Информатика" строка А занимает 21 байт, так как раз- мер строки переменной длины равен 10 байт плюс 1 байт на сим- вол. После выполнения оператора В = "Информатика" строка В будет занимать 15 байт, так как объём оперативной памяти, за- нимаемый строкой постоянной длины не зависит от количества содержащихся в ней символов. Значение, присваиваемое строке постоянной длины, может содержать количество символов как меньшее указанного в опи- сании, так и большее. В первом случае в конце строки вместо не- |