Лабораторная работа № 8 алгоритмы обработки массивов

Теоретические положения.

1 Алгоритм определения максимального (минимального) значения элементов массива

Пусть требуется определить максимальное значение элементов одномерного массива А, состоящего из 100 чисел. Схема алгоритма приведена на рис. 2.1 Максимальное значение элементов массива определяется переменной Amax , которой первоначально присваивается значение первого элемента массива A(1). Все элементы массива, начиная со второго, последовательно сравниваются со значением переменной Amax. В случае, если значение текущего элемента массива A(i) окажется больше значения Amax, то Amax присваивается новое значение, равное А(i).

Дня определения минимального значения элементов массива Amin, необходимо в алгоритме, изменить энак неравенства на противоподожннй (т. е. записать A(i)<Amin ).

2 Алгоритм нахождения суммы и произведения элементов массива

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

S = S+A(i)

где S - текущее значение суммы;

A (i) i-тый элемент массива,

задать начальное значение суммы, как правило, равное нулю /3/.

Для решения задачи накопления произведения необходимо перед циклом задать начальное значение произведения, равным единице, а внутри цикла накапливать произведение, используя оператор присваивания вида

P=P * A(i)

где Р - текущее значение произведения.

3 Алгоритмы сортировки элементов массива

Сортировка – это последовательное упорядочивание элементов массива. Существует множество методов сортировок. В данном методическом указании разматриваются различные методы сортировок. А именно:

1.Метод сортировки Шелла.

2.Метод сортировки: линейный выбор.

3.Метод челночной сортировки.

4.Быстрая сортировка (метод Хаара).

В данной работе содержится два примера: метод сортировки Шелла и линейного выбора.

Метод сортировки Шелла:

Суть его состоит в том, что выбирается интервал h между сравниваемыми элементами, который увеличивается после каждого прохода. Для последовательности интервалов выполняются условия:

h(p)=1; h(i+1)>h(i); i=1,2,…,p-1;

Сначала, сравниваются (и если нужно, переставляются ) соседние элементы , а на последнем проходе – далеко стоящие элементы.

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

Рассмотрим программную реализацию метода Шелла.

Что, наверно не все понятно, но ничего сейчас я тебе все объясню и даже нарисую.

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

Сначала по циклу берется первый элемент массива: For i = 0 To (rasmer - 1);

Потом начинается подцикл: For k = i +1 To (rasmer - 1);

Дальше у нас идет сравнение и перестановка: If mas(i) > mas(k) Then

g = mas(i)

d = mas(k)

mas(i) = d

mas(k) = g

End If

Т.е. сначала 1-ый элемент массива сравнивается с оставшимися 5-ю элементами, там где надо – перестанавливается; потом берется 2- элемент массива и сравнивается с оставшимися 4-мя элементами массива; соответственно 3-ий с оставшимися 3-мя и т.д.

Это все что тебе надо знать по этому методу. Удачи!!!

Метод сортировки: линейный выбор

Метод предполагает наличие рабочего массива, в который помещается отсортированный массив. Количество просмотров определяется количеством элементов массива. Сортировка посредством линейного выбора сводится к следующему:

1.Найти наименьший элемент, переслать его в рабочий массив и заменить его в исходном массиве величиной, которая больше любого реального элемента.

2.Повторить шаг 1. На этот раз будет выбран наименьший из оставшихся элементов.

3.Повторять шаг 1 до тех пор, пока не будут выбраны все n элементов.

Схема алгоритма приведена ниже на рисунке 1.

amax = a(i)

imax = i

amin = a(i)

imin = i

amax = a(1)

imax = 1

amin = a(1)

imin = 1

r(j) = amin a(imin) = amax

ListBox2.AddItem (r(j))

Программа алгоритма процедуры сортировки

Dim imin As Integer

Dim amin As Integer

Dim intmax As Integer

Dim amax As Integer

Dim a(1 To 10) As Integer

Dim r(1 To 10) As Integer

Dim j As Integer

Dim p As Integer

Dim t As Integer

Dim i As Integer

Private Sub CommandButton1_Click()

ListBox1.Clear

If IsNumeric(TextBox1.Text) = False Then

Exit Sub

Else

If t > 10 Then

TextBox1.Text = ""

Else

t = CInt(TextBox1.Text) ‘ввод размерности массива

For i = 1 To t

a(i) = InputBox("Введите" + Str(i) + -й элемент массива")

ListBox1.AddItem (a(i))

Next i

End If

End If

End Sub

Private Sub CommandButton2_Click()

ListBox2.Clear

For j = 1 To t

amax = a(1)

imax = 1

For i = 2 To t

If a(i) > amax Then

amax = a(i)

imax = i

End If

Next i

amin = a(1)

imin = 1

For i = 2 To t

If a(i) < amin Then

amin = a(i)

imin = i

End If

Next i

r(j) = amin

a(imin) = amax

ListBox2.AddItem (r(j))

Next j

End Sub

Private Sub CommandButton3_Click()

Unload UserForm1

End Sub

Задание 1.

Нахождение максимального и минимального элемента массива

Варианты заданий к лабораторной работе 1

1.1. Найти номер наименьшего элемента массива (X1,X2,…,X10)

1.2.Найти наибольшее значение (Xi+Yi) для массивов

(X1,X2,…,X40) и (Y1,Y2,…,Y40)

1.3. Записать +I вместо максимального элемента массива

(X1,X2,…,X50),a-1 вместо минимального.

1.4.. Найти и записать вместо X1 наибольший элемент, а вместо Х2 - наименьший для массива (X1,X2,…,X100)

1.5. Дня массива (a1,a2,…,a80) вычислить на­ибольшее и наименьшее значение модуля разности между соседними элементами.

1.6. Найти наибольший элемент главной диагонали матрицы А(20х20) и вывести на печать всю строку, в которой он находится.

1.7. Найти наименьший из положительных элементов массива (X1,X2,…,X40)

1.8. Определить максимальный из элементов массива А, имеющих четные индексы. Количество элементов в массиве - 25.

1.9. Определить минимальный из элементов массива А, имеющих нечетные индексы. Количество элементов в массиве - 30.

1.10. Дан массив (a1,a2,…,a40) . Найти min (a2,a4,…)+max(a1,a3,…).

1.11. В массиве (X1,X2,…,X10) найти максимальный по модулю элемент.

1.12. Дан массив (б1, б2,…,630) . Найти max (- б1,б2,-б3,…,-б29,б30)

1.13. Дан массив (a1,a2,…,a50). Найти величину (min(a1,…,a50))^2-min(a1^2,…,a50^2)

1.14. Дано натуральное число П , целые числа a1,…,an. Найти наименьшее из четных чисел, входящих в последо­вательность

1.15. Даны натуральное число П , целые числа b1.b2,…,bn. Найти наибольшее из нечетных и количество четных чисел, входящих в последовательность b1,…,bn.

Пример решения задачи

Найти минимальный элемент массива

Public min As Long

Dim a(40) As Long

Dim i As Integer

Private Sub CommandButton1_Click()

’Ввод элементов массива и вывод их в список

For i = 1 To 10

Title = "Ввод " + Str(i) + " элемента"

Message=”Введите элемент массива”

a(i) = InputBox(Message, Title, Default)

ListBox1.AddItem a(i)

Next i

End Sub

Private Sub CommandButton2_Click()

‘Поиск минимального элемента

min = a(1)

For i = 2 To 10

If a(i) > min Then min = a(i)

Next i

‘Вывод результата

ListBox1.AddItem ("минимальный элемент =" & str(min))

End Sub

Private Sub CommandButton4_Click()

‘Закрытие формы

Unload Me

End Sub

Private Sub CommandButton3_Click()

‘Очистка списка элементов

ListBox1.Clear

End Sub

Задание 2.

Вычисление суммы и произведения элементов динамического массива

Варианты заданий к лабораторной работе 2

Все предложенные массивы считать динамическими, а указанную размерность вводить в контрольном варианте решения задачи

2.1. Вычислить сумму положительных элементов массива (x1,x2,…,x55)

2.2. Вычислить среднее арифметическое элементов массива

(x1,x2,…,x70)

2.3. Вычислить сумму элементов массива (а1,a2,…,a78) стоящих на четных местах.

2.4. Вычислить среднее арифметическое отрицательных эле­ментов массива (с1,c2,…,c30), полагая, что в массиве есть отрицательные значения.

2.5. Вычислить среднее арифметическое элементов S мас­сива (a1,a2,…,a80),удовлетворяющих условию 1<=ai<=2. Если таких элементов нет, то считать S = 0 .

2.6. Подсчитать количество положительных и количество отрицательных элементов массива (x1,x2,…,x75)

2.7. Вычислить сумму элементов главной диагонали матрицы А(20x20).

2.8. Вычислить сумму элементов диагонали матрицы А(10х10). Элементами i-ой строки, лежащими на диагоналях, являются аi,i и ai,11-i .

2.9. Вычислить среднее геометрическое элементов массива (у1,у2,….,у35), удовлетворяющих условию уi >a, считая, что в массиве есть элементы, для которых выполняется это условие.

2.10. Вычислить среднее геометрическое положительных элементов массива (а1,а2,…,а40), имеющих четные индексы. Если таких элементов нет, то вывести на печать сообщение об этом.

2.11. Подсчитать количество элементов целочисленного массива (х1,х2,…,х20), кратных трем.

2.12. Для целочисленного массива (а1,а2,…,а35) определить, является ли сумма его элементов четным числом, и вывести на печать ДА или НЕТ.

2.13. Подсчитать для массива (х1,х2,…,х20) количество элементов, ближайшим целым числом для которых является 1.

2.14. Даны натуральное число n , целые числа а1,…,аn. Найти количество и сумму тех членов данной последовательности, которые делятся на пять и не делятся на семь.

2.15. Даны натуральные числа n,p целые числа а1,…,аn. Получить произведение членов последовательности а1,…,аn, кратных p.

Пример решения задачи

Вычислить среднее арифметическое элементов динамического массива целых чисел

Private Sub CommandButton1_Click()

Dim arr() As Integer ’ Объявление динамического массива

Dim sum As Integer

mx = InputBox("Введите размер массива.")

If IsNumeric(mx) = False Then

MsgBox ("Введите число!!!")

Exit Sub

End If

ReDim arr(1 To mx) ’ Указание размерности динамического массива

For i = 1 To mx

arr(i) = InputBox("Введите " + Str(i) + " элемент массива.")

sum = sum + arr(i)

Next i

MsgBox ("Среднее арифмитическое " & sum / mx)

End Sub

Private Sub CommandButton2_Click()

uf.Hide

End Sub

Private Sub UserForm_Click()

End Sub

Сортировка элементов массива

Варианты заданий.

1. Дана действительная матрица А (n*m). Упорядочить строки матрицы по возрастанию значений первых элементов строк.

2. Дана действительная матрица А (n*m). Упорядочить строки матрицы по убыванию сумм элементов строк.

3. Упорядочить строки матрицы по возрастанию значений наименьших элементов строк.

4. Дана действительная матрица А (n*m). Упорядочить строки матрицы по убыванию значений наибольших элементов строк.

5. Массив (b1,b2,….,b10) упорядочить таким образом, чтобы в ней располагались сначала положительные элементы, а потом отрицательные в таком же порядке, как и в исходном массиве.

6. Упорядочить по возрастанию элементы каждой строки матрицы А(4*4).

7. Упорядочить элементы четных строк матрицы А( 8*8 ) по возрастанию , а нечетных - по убыванию.

8. Дана вещественная матрица размером 7*4.Переставляя ее строки и столбцы , добиться того , чтобы наибольший элемент ( один из них ) оказался в левом верхнем углу.

9. Дана матрица А(10*10 ) и вектор В(10) .Координаты вектора принимают значения 0,1 или -1.Преобразовать матрицу А по следующему правилу: если bi=-1 , то i-ю строку матрицы А упорядочить по возрастанию ; если bi=0 , то i-ю строку матрицы А упорядочить по убыванию; если bi=0 , то i-ю строку не изменять.

10. Упорядочить матрицу А(6*6 ) по правилу: первый столбец меняется местами с последним столбцом, второй - с предпоследним и т.д.

11. Упорядочить матрицу В( 8*8 ) по правилу : первая строка меняется местами с последней строкой , вторая - с предпоследней и т.д.

Разбор решения варианта 7.

Упорядочить элементы четных строк матрицы А( 8*8 ) по возрастанию , а нечетных - по убыванию.

Dim n As Long

Dim a(1 To 8, 1 To 8) As Long

Private Sub CommandButton2_Click()

ListBox1.AddItem ("Исходный массив:")

n = 4

For i = 1 To n

s = ""

For y = 1 To n

Message = ""

Title = " Элемент массива A[" + Str(i) + "," + Str(y) + "]"

Default = ""

myvalue = InputBox(Message, Title, Default)

a(i, y) = myvalue

s = s + Str(a(i, y)) + " "

Next y

ListBox1.AddItem (s)

Next i

End Sub

Private Sub CommandButton3_Click()

For i = 1 To n

If i Mod 2 = 0 Then

For i1 = 1 To n

For y1 = 1 To n

If a(i, i1) < a(i, y1) Then

z = a(i, i1)

a(i, i1) = a(i, y1)

a(i, y1) = z

End If

Next y1

Next i1

Else

For i1 = 1 To n

For y1 = 1 To n

If a(i, i1) > a(i, y1) Then

z = a(i, i1)

a(i, i1) = a(i, y1)

a(i, y1) = z

End If

Next y1

Next i1

End If

Next i

ListBox1.AddItem ("Полученный массив:")

For i = 1 To n

s = ""

For y = 1 To n

s = s + Str(a(i, y)) + " "

Next y

ListBox1.AddItem (s)

Next i

End Sub

Private Sub CommandButton4_Click()

Unload Me

End Sub

Private Sub CommandButton5_Click()

ListBox1.Clear

E nd Sub