Алгоритмы обработки одномерных массивов

Тема 4.7

Алгоритмы обработки одномерных массивов

 

 

Структурированные данные

Средства описания и работы с одномерными массивами данных

 

Динамические массивы

4.7.4. Базовые алгоритмы обработки одномерных массивов и примеры их программирования

Элементы управления для работы со списками

4.7.6. Тестовые задания

4.7.7. Лабораторная работа по теме «Программирование алгоритмов формирования и обработки одномерных массивов»

4.7.7.1. Вопросы, подлежащие изучению

 

4.7.7.2. Общее задание на разработку проекта

4.7.7.3. Варианты индивидуальных заданий

 

4.7.7.4. Содержание отчёта

 

4.7.7.5. Пример выполнения задания

 

4.7.7.6. Контрольные вопросы

 

 

Структурированные данные

Часто приходится обрабатывать не одиночные данные, а совокупность данных одного типа. Например, задача табулирования функции, которая состоит в получении последовательности значений заданной функции при нескольких значениях аргумента. Для промежуточного хранения каждого значения полученных данных требуется объявить собственную переменную с уникальным именем.

Обращение к каждой переменной последовательности по имени превращается в длинную вереницу однотипных операций с каждой переменной. Программный код становится плохо обозримым. Для размещения такой программе требуется много памяти.

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

Массив – это совокупность однотипных переменных (элементов массива). Имя у всех переменных одно и то же, а для доступа к конкретному элементу массива используется дополнительный идентификатор – его порядковый номер (индекс), который начинается с 0.

Кроме массивов в программировании для построения эффективных алгоритмов могут использоваться и другие стандартные структуры данных, такие структуры данных, как стеки, очереди, связанные списки и другие.

Наряду со стандартными структурами данных, могут использоваться структуры данных, определяемые пользователем. Эти структуры данных определяются средствами объектно-ориентированного программирования с помощью классов.

 

 

4.7.2. Средства описания и работы с одномерными
массивами данных

 

Массив – последовательность переменных одинакового типа, объединенных общим именем. Например: одномерный массив а(9) состоит из 10 элементов с общим именем а: a(0), a(1), a(2), a(3),..., a(9), упорядоченных по индексу i, который принимает значения от 0 до 9:

 

a(i)
i

 

Массив в программе VBобъявляется точно так же, как объявляются простые переменные. Если массив объявлен локальным, его можно использовать только в той процедуре, в которой он объявлен. Если массив объявлен как глобальный, он может быть использован в любом месте программы.

При объявлении массива оператор объявления должен включать следующую информацию:

· имя массива – имя (идентификатор), которое используется для представления массива в программе;

· тип данных – тип данных, который имеют элементы массива;

· размерность (ранг) – количество измерений объявляемого массива (т.е. количество индексов при объявлении; одномерные массивы имеют одно измерение);

· количество элементов – количество элементов, которые будут содержаться в массиве.

 

Рассмотрим примеры некоторых описаний массивов:

 

 

В этих примерах объявлены следующие массивы:

· одномерный массив d, состоящий из 31 элемента типа Integer с индексами от 0 до 30;

· одномерный массив a, состоящий из 11 элементов типа Double с индексами от 0 до 10;

· двумерный массив b, состоящий из 14х11=151 элемента типа Single с индексами по строкам от 0 до 13 и по столбцам от 0 до 10.

Обратите внимание, что значением нижней границы массива в VB может быть только 0.

Таким образом, массив состоит из элементов, которые могут быть доступны при помощи индексов. При обращении к элементам массива индексы записываются вслед за именем в круглых скобках и могут представлять собой любое допустимое целочислен­ное выражение. Например, d(24), a(2*i+1).

Обратите внимание, что количество индексов указывает на размерность массива. Так, в приведенном выше примере размерность массива a(10) равна единице. Массив b(2,3) имеет размерность 2.

В отличие от размерности, размер массива – это количество элементов в массиве. В нашем примере размер массива, а(10) равен 11.

Перед использованием массива в программе его необходимо объявить с помощью оператора Dim, а элементам массива присвоить конкретные значения. Оператор Dim выделяет место в памяти компьютера для размещения элементов массива, обнуляет элементы числовых массивов или заполняет элементы строковых массивов пустыми строками ('''').

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

Заполнить элементы массива конкретными значениями можно с помощью ввода значений элементов массива, с помощью оператора присваивания или с помощью инициализации элементов массива.

Инициализация элементов массива – это поэлементное присваивание значения в операторе объявления массива. В этом случае размер массива не указывается в круглых скобках после имени массива, а определяется неявно размером списка значений. Список значений начинается с элемента с индексом 0 и заключается в фигурные скобки, например:

 

Dim Город () As String = {"Рязань", "Тула", "Калуга"}

 

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

 

Fori = 0 То КоличествоЭлементовМассива – 1 ИмяМассива (i) = выражение или Переменная = ИмяМассива (i) Next i

 

Чтобы облегчить работу с массивами в процедурах, для определения верхней границы массива используется встроенная функция
Bound (ИмяМассива).

Эта функция возвращает (определяет) номер последнего элемента массива и позволяет обрабатывать массивы в процедурах, не передавая в них в качестве параметра количество элементов массива. Например,

 

For i = 0 То UBound(ИмяМассива) ИмяМассива (i) = выражение или Переменная = ИмяМассива (i) Next i

Кроме того, для определения верхней границы одномерного массива можно использовать метод GetUpperBound(). Поскольку массив одномерный, то в скобках следует указывать значение 0. Например:

 

For i = 0 To a.GetUpperBound(0) sum = sum + a(i) Next i

 

Если имя массива, является формальным параметром процедуры, то после имени массива необходимо поместить пустые круглые скобки:

 

ByVal ИмяМассива ()As Тип или ByRef ИмяМассива ()As Тип

 

Кроме того, известно, что ключевое слово ByVal указывает передачу аргумента-массива по значению, а ключевое слово ByRef указывает, что аргумент-массив передается по ссылке. Заметим, что если ключевые слова ByVal или ByRef опущены, то аргумент-массив переда­ется по ссылке.

Таким образом, при описании формальных параметров любой процедуры после ИмяМассива не­обходимо всегда включать пустые круглые скобки, так как они указывают, что этот параметр являет­ся одномерным массивом.

 

Sub Show1(ByRef Lines() As Single, ByVal NLines As Integer) … End Sub Function Sort(ByRef List() As String) NLines As Integer … End Sub

 

Обращение к этим процедурам может, например, быть следующим:

 

Show1(Lines, 5) N1 = Sort(List)

 

Обратите внимание на то, что после имени массива, который является фактическим параметром, скобки отсутствуют.

 

Как известно, передача аргументов по значению (с помощью ключевого слова ByVal) приводит к тому, что VB передает копию данных процедуре. Поэтому не следует передавать массивы по значению, если в этом нет особой необходимости.

 

Пример 4.7.2-1. Написать процедуры ввода/вывода, которые могут использоваться в алгоритмах формирования и отображения одномерных массивов.

Процедуры ввода и вывода для одномерных массивов представлены на
рис. 4.7.2-1–4.7.2-3.

 

'Процедура ввода элементов массива типа Single с клавиатуры Sub vvodSngMac15(ByRef a() As Single, ByVal L As ListBox) Dim i As Integer For i = 0 To UBound(a) a(i) = CSng(Val(InputBox("Введите" & i & "-й элемент")) Next i End Sub

 

Рис. 4.7.2-1. Процедура ввода элементов массива Single с клавиатуры

Примера 4.7.2-1

 

 

'Процедура формирования массива случайным образом на интервале [2;4] Sub vvodSngRnd16(ByRef a() As Single) Dim i As Integer For i = 0 To UBound(a) a(i) = 2 + 2 * Rnd() Next i End Sub

Рис. 4.7.2-2. Процедура формирования массива случайным образом

Примера 4.7.2-1

'Процедура форматного вывода массива типа Single в ListBox Sub vivodSngMac17(ByRef a() As Single, ByVal L As ListBox) Dim i As Integer Dim m As String = "" For i = 0 To UBound(a) m = m + Format(a(i), "0.000") + Space(4) Next i If m ="" Then m = "массив пуст" L.Items.Add(m) End Sub

 

Рис. 4.7.2-3. Процедура форматного вывода массива Single в ListBox

Примера 4.7.2-1

Динамические массивы

 

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

 

Dim Sigma(5) As Integer, m(3) As Single

 

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

Одно из решений проблемы – выделять память под массив не на этапе компиляции – статически, а после определения его размера – динамически. В качестве размера массива может быть использована переменная, значение которой вычисляется или вводится перед объявлением массива:

 

РазмерМассива = Выражение или РазмерМассива = Cint(TextBox1.Text) Dim ИмяМассива(РазмерМассива) As Тип

 

Другое решение проблемы – разделить в программе объявление массива и определение его размера – выделение памяти под него.

При объявлении массива размер не указывается:

 

Dim ИмяМассива() As Тип

 

Значение размерности определяется позже (вычисляется или вводится) непосредственно перед его использованием, и тогда для выделения памяти уже объявленному массиву с указанием конкретной размерности массива используется оператор ReDim или ReDim Preserve:

 

ReDim ИмяМассива (РазмерМассива), ReDim Preserve ИмяМассива (РазмерМассива)

 

Таким образом, динамические массивы имеют весьма полезное свойство – их размеры могут изменяться в процессе выполнения программ. При этом оператор ReDim изменяет размер массива и очищает его (обнуляет его элементы), а оператор ReDim Preserve изменяет размер массива и сохраняет значения существующих элементов.

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

 

n = n + 1 ReDim Preserve Mas(n) Mas(n) = n + 4

 

Таким образом, для создания динамического массива его необходимо предварительно объявить, не указывая количество элементов массива:

 

Dim Мас() As String 'объявление динамического массива

 

Затем, в момент, когда необходимо распределить под него память, используется оператор ReDim:

 

ReDim Мас(9) ' или ReDim Preserve Мас(9)

 

Второй вариант используется для изменения размера массива и для сохранения содержимого.

На рис. 4.7.4-7, рис. 4.7.4-9 и рис. 4.7.4-10 приведены примеры программных кодов, использующие динамические массивы.

 

 

4.7.4. Базовые алгоритмы обработки одномерных массивов и примеры их программирования

 

Типичными задачами работы с одномерными массивами являются определение факта наличия в них заданного элемента и отбор элементов, удовлетворяющих определённым условиям. В обоих случаях используется циклическое сравнение элементов массива с заданным образцом. Для определения факта наличия заданного образца в массиве достаточно единственного совпадения, после чего дальнейший просмотр прекращается. Если условие отбора может выполняться для нескольких элементов массива, то необходим просмотр всего массива до конца. Для досрочного прекращения просмотра элементов массива в цикле используется оператор
Exit For.

В массивах больших размеров для сокращения времени просмотра применяется упорядоченное хранение элементов. Для числовых массивов используется упорядочение элементов по значению, для текстовых – по алфавиту (точнее, по значению кода символов). Упорядочение обычно производиться путём сортировки элементов неупорядоченного массива.

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

· Нахождение суммы значений элементов массива при заданных условиях (Пример 4.7.4-1).

· Нахождение произведения значений элементов массива при заданных условиях (Пример 4.7.4-2).

· Нахождение максимального и минимального значений элементов массива и их индексов (Пример 4.7.4-3).

· Формирование нового массива из элементов одного или нескольких массивов в соответствии с заданными критериями (Примеры 4.7.4-3 – 4.7.4-4).

· Формирование массива в соответствии с определенными правилами (Пример 4.7.4-7).

· Вставка элемента по заданному критерию в массив
(Пример 4.7.4-5).

· Удаление элемента по заданному критерию из массива
(Пример 4.7.4-6).

· Обмен значений элементов массива по заданному критерию
(Пример 4.7.4-8).

· Сортировка (упорядочивание) элементов массива (Пример 4.7.4-9).

 

Пример 4.7.4-1. Разработать процедуру, которая вычисляет произведение положительных и сумму отрицательных элементов массива x().

Схема алгоритма и программный код процедуры приведены на
рис. 4.7.3-1.

Напомним, что вычисление суммы и произведения обычно осуществляется по рекуррентным формул: s₀ = 0; s_i+1 = s_i + x_i+1; p₀ = 1;
p_i+1 = p_i * x_i+1.

 

Sub Pr741(ByRef x() As Single, _ ByRef s As Single, ByRef p As Single) Dim i As Integer s = 0: p = 1 For i = 0 To UBound(x) If x(i) > 0 Then p = p * x(i) Else s = s + x(i) End If Next End Sub   Private Sub Button1_Click(…) Dim s,p, a() As Single vvodSngMac15(а) vivodSngMac17(а, ListBox1) Pr741(а, s, p) vivod3(s, TextBox1): Vivod3(p, TexBox2) End Sub

 

Рис. 4.7.4-1. Схема алгоритма и программный код процедуры Pr741()

Примера 4.7.4-1

 

Пример 4.7.4-2. Разработать процедуру, в которой вычисляется произведение ненулевых элементов вещественного массив a().

Схема алгоритма и программный код приведены на рис. 4.7.4-2.

 

Function Pr742(ByRef a() As Single) As Single Dim i As Integer, z Fs Single z = 1 For i = 0 To Ubound(a) If a(i) <> 0 Then z = z * a(i) Next i End Sub Private Sub Button1_Click(…) Dim z As Single vvodSngMac15(a): vivodSngMac17(a, ListBox1) z = Pr742(a): vivodSngMac17 (z, TextBox1) End Sub

Рис. 4.7.4-2. Схема алгоритма и программный код процедуры Pr742()

Примера 4.7.4-2

Пример 4.7.4-3. Разработать процедуру-Function, которая находит максимальное значения элементов массива t().

Схема алгоритма и программный код приведены на рис. 4.7.4-3.

 

Sub Pr743(ByRef t() As Double) As Double Dim i, n, j, k As Integer Dim xmax As Single n = UBound(t) xmax = x(0) For i = 1 To n If x(i) > xmax Then xmax = x(i) End If Next i Return xmax End Sub

Рис. 4.7.4-3. Схема алгоритма и программный код процедуры Pr743()

Примера 4.7.4-3

Пример 4.7.4-4. Разработать процедуру-Function, которая находит индекс минимального значения элементов массива t().

 

Sub Pr744(ByRef t() Double) As Integer Dim i, n, j, k As Integer Dim xmin As Double n = UBound(t) xmin = x(0): k = 0 `For i = 1 To n If x(i) < xmin Then xmax = x(i) k = i End If Next i Return к End Sub

Рис. 4.7.4-4. Схема алгоритма и программный код процедуры Pr744()

Примера 4.7.4-4

Пример 4.7.4-5. Разработать процедуру, которая в заданном массиве c() переставляет элементы с целыми значениями в начало массива.

Sub Pr745(ByRef с() As Single) Dim temp As Single, i, k As Integer For i = 0 To UBound(c) If c(i) - Fix(c(i)) = 0 Then temp = c(k): c(k) = c(i) c(i) = temp: k = k + 1 End If Next i End Sub Private Sub Button1_Click(…) Dim с(9) As Single vvodSngMac15(с): vivodSngMac17(с,ListBox1) Pr7475(с): vivodSngMac17(с,ListBox2) End Sub

Рис. 4.7.4-5. Схема алгоритма и программный код процедуры Pr745()

Примера 4.7.4-5

Для того чтобы переставить целые элементы в начало массива, в переменной k будем хранить номер элемента, в который переписывается очередное целое значение. Чтобы определить, является ли очередной элемент массива целым числом, проводится сравнение разности значения целой части очередного элемента и значения очередного элемента массива c(i) с нулем.

Целая часть значения c(i) выделяется с помощью функции Fix(). Если очередной элемент массива c(i) содержит целое значение, то производится обмен значений двух элементов массива c(k) и c(i) c помощью temp.

Схема алгоритма и программа приведены на рис. 4.7.4-5.

 

Пример 4.7.4-6. Разработать процедуру-Sub, в которой необходимо сформировать массив c(), по следующему правилу:

Схема алгоритма и программный код приведены на рис. 4.7.4-6.

 

Sub Pr746(ByRef c()As Single) Dim i, k As Integer For i = 0 To UBound(c) If i < 5 Then c(i) = (i^3 - 4)/(i + 1) Else c(i) = (i^2 - 36) / i End If Next i End Sub Private Sub Button1_Click(…) Dim с(9) As Single Pr746(с) vivodSngMac17(с, ListBox1) End Sub

 

Рис. 4.7.4-6. Схема алгоритма и программный код процедуры Pr746()

Примера 4.7.4-6

 

Пример 4.7.4-7. Разработать процедуру-Sub, в которой необходимо сформировать массив y(), переписав в него положительные элементы исходного массива x().

 

Sub Pr747(ByRef x() As Single, _ ByRef y() As Single) Dim i, n As Integer For i = 0 To UBound(x) If x(i) > 0 Then ReDim Preserve y(n) y(n) = x(i): n = n + 1 End If Next i End Sub Private Sub Button1_Click(…) Dim x(), y() As Single vvodSngMac15(x) vivodSngMac173(x, ListBox1) Pr747(x, y) vivodSngMac17(y, ListBox2) End Sub

Рис. 4.7.4-7. Схема алгоритма и программный код процедуры Pr747()

Пример 4.7.4-7

Для решения поставленной задачи необходимо проверить знак у всех элементов массива х(). При этом текущий индекс n формируемого массива y() меняется независимо от индекса i исходного массива х(). Индекс n увеличивается на единицу только при появлении положительного элемента х().

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

Схема алгоритма и программный код приведены на рис. 4.7.4-7.

 

Пример 4.7.4-8. Разработать процедуру-Sub, в которой необходимо из двух исходных массивов p() и r() с одинаковым числом элементов получить массив v() путем последовательного попарного переписывания в него элементов массивов p() и r().

В данной задаче для формирования массива v() используется переменная k, которая представляет собой номер очередного элемента массива v(). В цикле одновременно заполняются два элемента массива v(): в элемент с номером k переписывается i -й элемент из массива p(), а в элемент с номером (k+1) переписывается i -й элемент из массива r().

На рис. 4.7.4-8 приведены алгоритм и процедура и решения задачи.

 

Sub Pr748(ByRef p() As Single, _ ByRef r() As Single, ByRef v() As Single) Dim i, k As Integer For i = 0 To UBound(p) v(k) = p(i) v(k + 1) = r(i) k = k + 2 Next End Sub Private Sub Button1_Click(…) Dim p(), r(), v() As Single vvodSngMac15(p) vivodSngMac17(p, ListBox1) vvodSngMac15(r) vivodSngMac17(r, ListBox2) Pr748(p, r, v) vivodSngMac17(v, ListBox3) End Sub

 

Рис. 4.7.4-8. Схема алгоритма и программный код процедуры Pr748()

Пример 4.7.4-8

Пример 4.7.4-9. Разработать программный код процедуры-Sub, который из массива вещественных чисел x(n) удаляет все отрицательные элементы и подсчитывает их количество k.

Удаление всех отрицательных элементов массива реализуется в процедуре Pr748() по так называемому алгоритму «сжатия». Метод заключается в поиске удаляемого отрицательного элемента, фиксации его номера, а затем в последовательной перезаписи всех последующих элементов массива так, чтобы значение следующего i+1 элемента записывалось на место предыдущего, и так до конца массива.

 

Sub Pr749(ByRef x() As Single, ByRef k As Integer) Dim i, n, j As Integer k = 0 i = 0 n = UBound(x) Do If x(i) < 0 Then k = k + 1 'сжатие массива For j = i To n - 1 x(j) = x(j + 1) Next n = n - 1 ReDim Preserve x(n) Else i = i + 1 Loop Until i > n End Sub Private Sub Button1_Click(…) Dim n, k As Intege n = CInt(InputBox("Введите" & _ "количество элементов ")) Dim x(n - 1) As Double vvodSngRnd16(x) vivodSngMac17(x, ListBox1) Pr749(x, k) vivodSngMac17(x, ListBox2) TextBox1.Text = CStr(k) End Sub

 

Рис. 4.7.4-9. Схема алгоритма и программный код процедуры Pr749()

Пример 4.7.4-9

Из последовательности исчезает удаляемый элемент, однако последний элемент повторяется дважды, поэтому после выхода из внутреннего цикла по перезаписи элементов длина массива (число n) должна быть уменьшена на единицу. Для изменения размерности массива используется оператор ReDim Preserve. уменьшена на единицу. Для изменения размерности массива используется оператор ReDim Preserve.

Так как отрицательные элементы могут идти подряд, то i+1 элемент, который перешел на место i -го, тоже может быть меньше нуля. Поэтому необходимо снова проверить текущий i -й элемент (бывший i+1) и, возможно, тоже удалить его «сжатием». Переход к следующему элементу по параметру i (т.е. увеличение i на 1) происходит, только если проверяемый i -й элемент оказался неотрицательным, поэтому алгоритм «сжатия» может

быть реализован с помощью внешнего итеративного (не регулярного) цикла.

Ввод исходного одномерного массива случайными числами из диапазона [-10;5] осуществляет процедура vvod(), а вывод массива на форму в элемент управления ListBox осуществляет процедура vivod(), которая по вычисляемому методом Length количеству элементов массива проводит проверку, не является ли выводимый массив пустым.

На рис. 4.7.4-9 приведены алгоритм и программа решения задачи.

Пример 4.7.4-10. Разработать процедуру-Sub, действие которой заключается в удалении из массива x() одинаковых элементов.

 

Sub Pr7410(ByRef x() As Double) Dim i, n, j, k As Integer i = 0 n = UBound(x) Do While i < n j = i + 1 Do If x(i) = x(j) Then For k = j To n - 1 x(k) = x(k + 1) Next n = n - 1 Else j = j + 1 If Loop While j <= n i = i + 1 Loop ReDim Preserve x(n) End Sub Private Sub Button1_Click(…) Dim n As Integer n = CInt(InputBox("введите кол." _ &"элементов исходного массива")) Dim x(n - 1) As Double vvod(x, n): vivod(x, ListBox1) Pr7410(x): vivod(x, ListBox2) End Sub

Рис. 4.7.4-10. Схема алгоритма и программный код процедуры Pr7410()

Пример 4.7.4-10

Решения задачи заключается в последовательном сравнении каждого элемента исходного массива со всеми остальными. В цикле происходит формирование массива x(j). Если элемент массива x(i) равен элементу x(j), то j -й элемент удаляется, а длина массива уменьшается на единицу.

Алгоритм «сжатия» для получения массива с уникальными элементами и программа, реализующая данный алгоритм, приведены на рис. 4.7.4-10.

Пример 4.7.4-11. Разработать процедуры-Sub, в которых осуществляется сортировка по убыванию значений элементов массива.

Сделаем несколько общих замечаний по поводу сортировки элементов массива.

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

1) Упорядочивание по возрастанию. Каждый следующий элемент в массиве должен быть больше предыдущего.

2) Упорядочивание по убыванию. Каждый следующий элемент в массиве должен быть меньше предыдущего.

3) Упорядочивание по неубыванию. Каждый последующий элемент в массиве должен быть больше или равен предыдущему.

4) Упорядочивание по невозрастанию. Каждый последующий элемент в массиве должен быть меньше или равен предыдущему.

 

Во-вторых, необходимо отметить, что главным показателем качества алгоритма сортировки считается его быстродействие, реальные программы работают с большими объемами данных, сохраняемыми в массивах. Повышение быстродействия, под которым понимается уменьшение количества просмотров массива от начала до конца (проходов) с целью определения упорядоченности, может быть достигнуто за счет применения различных методов сортировки.

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

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

Рассмотрим «сортировку выбором» (метод «прямого выбора»).

Алгоритм и программа сортировки массива по убыванию методом «прямого выбора» приведены на рис. 4.7.4-11.

Sub Pr7411(ByRef x() As Single) Dim i, n, j, k As Integer Dim xmax As Single n = UBound(x) 'Внешний цикл сортировки For i = 0 To n - 1 xmax = x(i) k = i 'Поиск xmax и k For j = i + 1 To n If x(j) > xmax Then xmax = x(j) k = j End If Next j x(k) = x(i) x(i) = xmax Next i End Sub

Рис. 4.7.4-11. Схема алгоритма и программный код процедуры Pr7411()

Пример 4.7.4-11

 

Суть этого метода сортировки состоит в следующем.

Сортировка элементов массива по убыванию производится с помощью вложенных циклов. Сначала осуществляется поиск наибольшего элемента массива и его индекса среди всех элементов, начиная с 1-го. Найденный максимальный элемент меняется с первым элементом. Затем вновь осуществляется поиск наибольшего элемента массива и его индекса, но уже со второго элемента, и найденный максимальный элемент обменивается со 2-м элементом, и т.д. Таким образом, число найденных максимумов (поисков) равно n. При этом во внешнем цикле, начиная с первого и до предпоследнего элемента массива, сначала очередной элемент принимается за максимальный, а затем, после выполнения внутреннего цикла, обеспечи­вается заполнение этого очередного элемента массива наибольшим «среди оставшихся элементов».

Внут­ренний цикл осуществляет перебор и сравнение последующих эле­ментов, начиная с (i+1) -го до последнего элемента массива. В результате выполнения внутреннего цикла, в переменной xmax фиксируется значение наибольшего элемента, а в переменной k - его номер. Далее, во внешнем цикле выполняется перестановка найденного максимального эле­мента на место очередного i -го элемента массива.

Рассмотрим сортировку элементов массива модифицированным методом «пузырька» (прямого обмена).

Алгоритм и программа упорядочения массива по модифицированному методу «пузырька» приведены на рис. 4.7.4-12.

 

Sub Pr7412(ByRef x() As Single) Dim i, n, j As Integer Dim xx As Single n = UBound(x) For i = 0 To n-1 For j = i + 1 To n If x(i) > x(j) Then xx = x(i) x(i) = x(j) x(j) = xx End If Next j Next i End Sub

 

Рис. 4.7.4-12. Схема алгоритма и программный код процедуры Pr7412()

Пример 4.7.4-11

 

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

Продолжая таким же образом, вплоть до предпоследнего элемента, сортируют весь массив.

Обратите внимание, что в схемах алгоритмов обмен значениями обозначается символом «↔», а в примере обмен реализован через дополнительную переменную xx.

Массив - это

1) совокупность данных одного типа, объединенных общим именем

2) совокупность данных одного типа

3) набор индексированных данных

4) набор разных данных

5) набор однотипных файлов на диске

Индексом массива может быть

1) выражение любого типа

2) любое целочисленное выражение

3) только целочисленные переменные

4) переменные любого типа

Оператор Dim

1) резервирует область памяти для элементов массива

2) резервирует имя для элементов массива

3) выстраивает элементы массива в линейку

4) подсчитывает количество элементов массива

Сортировка массива – это

1) упорядочивание элементов массива либо по возрастанию, либо по убыванию

2) перезапись элементов массива в обратном порядке

3) удаление нулевых элементов массива

4) в списке нет правильного ответа

Фрагмент программы

For i = k To n - 1 a(i) = a(i+1) Next i

выполняет

1) сжатие массива «сдвигом влево»

2) сжатие массива «сдвигом вправо»

3) удаление первых K элементов массива

4) удаление последних N-K элементов массива

Фрагмент программы

i=0 Do If a(i) = 0 Then For j = i To n-1 a(j) = a(j+1) Next j n = n-1 Else i = i + 1 End If Loop While i <= n

1) удаляет из массива нулевые элементы

2) перемещает нулевые элементы влево

3) перемещает нулевые элементы вправо

4) оставляет все по-прежнему

Вопросы, подлежащие изучению

1) Способы описания и объявления одномерных массивов.

2) Возможности резервирования памяти и хранения элементов массива.

3) Способы задания значений элементам массива: присваиванием; инициализацией; вводом по запросу с клавиатуры; заполнением массива данных случайными числами в заданном диапазоне.

4) Базовые алгоритмы обработки одномерных массивов: вычисление суммы (произведения) элементов массива; нахождение номера (и значения) минимального (максимального) значения элемента массива; формирование нового массива из исходного массива по заданному критерию; сортировка элементов массива от большего к меньшему (или от меньшего к большему); удаление элементов массива, имеющих равные значения (сжатие массива); удаление элементов массива по заданному критерию (сжатие по признаку).

5) Методы класса Array.

6) Методы работы с элементами управления ListBox и ComboBox.

4.7.7.2. Общее задание на разработку проекта

1) Изучите вопросы программирование алгоритмов формирования и обработки одномерных массивов (Тема 7).

2) Создайте приложениес именем Проект-4.7.

3) Выберите вариант задания из табл. 4.7.7-1.

4) Разработайте графический интерфейс пользователя.

5) Разработайте схемы алгоритмов процедур пользователя в соответствии с индивидуальным заданием, предварительно проведя формализацию.

6) Напишите программный код процедур по разработанным алгоритмам.

7) Разработайте проект приложения, решающий поставленную задачу, который состоит из интерфейса пользователя и соответствующего программного кода, а также написанных ранее процедур обработки, ввода и вывода элементов массива. Все пользовательские процедуры должны находиться в модуле формы. Обмен данными между пользовательскими процедурами должен осуществляться через параметры, без использования глобальных переменных.

8) Подготовьте входные массивы чисел для решения задачи, если исходные данные не заданы.

9) Выполните приложение и получите результат.

10) Докажите правильность результата.

 

Варианты индивидуальных заданий

Таблица 4.7.7-1

1)	Ввести одномерный массив x= {-1.5, 0.1, 12, 0, -2.2, 0.5, -1, 0.3}. Заменить в нем все отрицательные элементы значением минимального элемента, а все положительные – максимальным значением.
2)	Ввести одномерный массив a = {5, -2, 0, 3, 4, 12, 7}. Вычислить и вывести среднее арифметическое значение положительных элементов массива и заменить этим значением те элементы массива, которые больше среднего арифметического.
3)	Ввести одномерный массив x = {-1.5, 0, 0.8, 2.2, 3, 0.5, 0.1}. Переписать элементы массива, принадлежащие отрезку [-1;1], в массив y и найти сумму элементов, расположенных после макси