Учебное пособие 800203
.pdfУдаление элементов из массива и вставка элементов
вмассив
Ксожалению, классический язык Pascal не имеет средств для создания массивов переменной длины. Длина массива указывается на этапе создания программы при описании массива. В ходе выполнения программы. Длина массива меняться не может. Поэтому при необходимости работы с массивами переменной длины описывают массив заведомо большего размера. Вместе с тем описывают целую переменную, смысл которой — фактическая длине массива, то есть размер используемой части массива. Хотя этот путь и нерационален, мы будем использовать его для работы с массивами переменной длины, чтобы отработать алгоритмы удаления и вставки элементов.
Чтобы удалить элемент с номером g из массива mas, необходимо каждый элемент, начиная с g+1 и до последнего, переместить на место предыдущего элемента и уменьшить на 1 размер массива. Описанный алгоритм реализуется следующим фрагментом программы:
var
mas: array[1..100] of real; {Описание массива}
i: |
integer; |
{параметр цикла for} |
n: |
integer; |
{Фактический размер массива} |
…
for i:=g to n-1 do mas[i]:=mas[i+1];
Dec(n); {Уменьшение n на 1}
…
Для вставки элемента в массив на место с номером g необходимо предварительно освободить для него это место. Для этого начиная с конца массива и до элемента с номером g, каждый элемент перемещается на следующее за ним место и размер массива увеличивается на 1. Затем присваивается новое значение элементы с номером g:
for i:=n downto g do mas[i+1]:=mas[i];
mas[g]:=… |
{Увеличение n на 1} |
Inc(n); |
40
Многомерные массивы
Элементы многомерных массивов нумеруются не одним, а несколькими (как минимум двумя) индексами. Например, массив
x2 : array [1..10,1..20] of Real;
представляет собой двумерный массив, который можно интерпретировать как матрицу из 10 строк и 20 столбцов. Элементы этого массива могут принимать вещественные значения. Массив
x3 : array [1..10,1..20,1..5] of Real;
представляет собой трёхмерный массив из 1000 элементов. Чаще всего в программах не используют массивов размерностью больше 2. Поскольку двумерные массивы по смыслу являются матрицами, им следует уделить больше внимания.
Двумерный массив — структура данных, хранящая прямоугольную матрицу. В матрице каждый элемент определяется номером строки и номером столбца, на пересечении которых он расположен. В Паскале двумерный массив представляется массивом, элементами которого являются одномерные массивы. Два следующих описания двумерных массивов тождественны:
Var a: array [1..10] of array [1.. 20] of real; Var a: array [1..10, 1..20] of real;
Чаще всего при описании двумерного массива используют второй способ. Доступ к каждому отдельному элементу осуществляется обращением к имени массива с указанием индексов (первый индекс – номер строки, второй индекс – номер столбца). Все действия над элементами двумерного массива идентичны действиям над элементами одномерного массива. Только для инициализации двумерного массива используется вложенный цикл for.
Например,
For i:= 1 to 10 do For j:= 1 to 20 do
A[i, j] := 0;
41
Для иллюстрации принципов работы с двумерными массивами разберем несколько примеров.
Пример. Сформировать таблицу Пифагора (таблица умножения) и вывести ее на экран.
Program Pifagor; Uses crt;
Var p: array[1..9, 1..9] of integer;
i, j:integer; |
|
|
|
Begin |
|
|
{Очистка экрана} |
Clrscr; |
9 do |
|
|
for i:=1 to |
do |
{Цикл по строкам} |
|
for j:= 1 |
to 9 |
{Цикл по столбцам} |
|
p[i,j]:= i*j; |
|
|
|
for i:=1 to 9 do begin
for j:=1 to 9 do write(p[i,j],’ ’); writeln; {Перевод курсора на сл. строку} end;
end.
Пример. Задан двумерный массив В(10, 10), заполненный случайными числами из отрезка [-10,10]. Найти и вывести на экран те элементы массива, которые больше заданного числа k.
Program massiv; Var
b: array[1..10, 1..10] of integer; i, j, k :integer;
Begin
for i:=1 to 10 do begin
for j:= 1 to 10 do begin
b [i,j]:= random(20)-10; write(b[i,j], ’ ’);
end;
42
writeln;
end;
write(’Введите число k’); readln (k);
For i:=1 to 10 do For j:=1 to 10 do
If b[i,j]>k then write (b[i, j],’ ’); End.
Пример. Задать и распечатать массив 10 на 10, состоящий из целых случайных чисел в интервале [1,100]. Найти сумму элементов, лежащих выше главной диагонали.
При отсчете, начиная с левого верхнего угла таблицы, главной будем считать диагональ из левого верхнего угла таблицы в правый нижний. При этом элементы, лежащие на главной диагонали будут иметь одинаковые индексы, а для элементов выше главной диагонали номер столбца будет всегда превышать номер строки.
Program M5;
Var
A : Array[1..10,1..10] Of Integer;
I, K : Byte;
S : Integer;
Begin
S:=0;
For I:=1 To 10 Do
Begin
For K:=1 To 10 Do
Begin
A[I,K]:=Trunc(Random*100)+1;
Write(A[I,K]:6);
If K>I Then S:=S+A[I,K]
End;
Writeln;
43
End;
Writeln('Сумма элементов выше гл. диагонали равна',S)
End.
Практические задания
При выполнении практического задания придерживайтесь следующий последовательности действий:
7)Обязательно изучите описание, предлагаемое выше.
8)Разберите примеры, приводимые в описании.
9)Осмыслите задачу, предлагаемую в вашем варианте. Задаете вопросы преподавателю по сути решаемой задачи.
10)Составьте словесный алгоритм решения задачи. Покажите его преподавателю.
11)Представьте алгоритм решения в виде блок-схемы, покажите ее преподавателю.
12)Переведите алгоритм на язык программирования.
Варианты заданий
Вариант 1.
1.В одномерном массиве переставить местами элементы, находящиеся на четных и нечетных местах. Начальный и преобразованный массивы выдать на печать.
2.В двумерном массиве подсчитать и выдать на печать максимальные и минимальные элементы по каждой строке. Вычислить значение логарифма элемента [1,1] и прибавлять к нему последовательно все оставшиеся элементы 1-й строки, затем - все элементы 2-й строки, начиная с 1-го элемента, и т.д. до тех пор, пока начальное значение (логарифма) не увеличится в 5 раз. Выдать на печать индексы элемента, на котором процесс закончится.
44
Вариант 2.
1.Преобразовать одномерный массив таким образом, чтобы сумма элементов в его первой половине была бы как можно ближе к сумме элементов его второй половины. Исходный и преобразованный массивы выдать на печать.
2.В заполненном случайно двумерном массиве a[n,m] заменить его элементы вещественными числами, вычисляе-
мыми по формуле a[i, j] = a[i, j] * Cos(i / (i + j)). Для каждого столбца найти и выдать на печать количество положительных
иотрицательных элементов в нем. Элементы начального и образованного массивов выдать на печать.
Вариант 3.
1. Элементы случайно заполненного одномерного массива d[n] преобразовать по формуле d[i] = e -i / d[i]. В новом мас-
сиве найти и выдать на печать сумму элементов, порядковый номер которых делится на 3.
2. Элементы двумерного массива a[m,n] вычисляются по формуле a[i, j] = i j, если i > j и a[i, j] = j i - в ином случае. В этом массиве найти и выдать на печать квадратную матрицу m[3,3], сумма диагональных элементов в которой - минимальна.
Вариант 4.
1.Сопоставить одномерному массиву a[n] другой одно-
мерный массив f[n], элементы которого вычисляются по формуле f[i] = Ln(a[i]) / ArcTg(ei/10). Элементы этого массива переставить таким образом, чтобы меньшему номеру соответствовал бы меньший элемент. Элементы всех массивов выдать на печать.
2.В двумерном массиве найти и выдать на печать 4 наибольших элемента с указанием их адресов.
45
Вариант 5.
1.В одномерном массиве переставить элементы таким образом, чтобы на 3 месте стояло бы наибольшее, а на 7 - наименьшее число.
2.В двумерном массиве b[n,m] найти 4 последовательные элемента, сумма которых - максимальна. Обход для поиска выполнить против часовой стрелки, начиная с элемента b[1,1].
Вариант 6.
1.Выяснить, имеется ли среди элементов двумерного массива простые числа? Сообщить их индексы, подсчитать их количество и среднее арифметическое их корней.
2.В одномерном массиве найти среднее значение элементов и построить новый одномерный массив из разностей соответствующих элементов и полученного среднего.
Вариант 7.
1.Заменить в одномерном массиве каждый из элементов суммой его делителей включая единицу.
2.В двумерном массиве найти квадрат размером 3х3, в котором сумма диагональных элементов максимальна. Выдать на печать весь массив на печать с выделенным квадратом.
Вариант 8.
1.Каждый из элементов одномерного массива заменить суммой цифр этого элемента. Найти максимальный и минимальный элементы. Исходный и преобразованный массивы выдать на печать.
2.Преобразовать исходный двумерный массив a[m,n] в одномерный f[m*n] и, считая каждый из элементов длиной стороны треугольника, найти такую тройку элементов, которые образуют треугольник с наибольшей площадью.
46
Вариант 9.
1.В двумерном массиве заменить каждый элемент частным от деления самого элемента на сумму его делителей.
2.Найти все цифры в элементах одномерного массива и подсчитать, сколько раз встречается каждая.
Вариант 10.
1.Элементы одномерного массива преобразовать в новый одномерный массив, в котором каждый элемент равен наибольшему делителю исходного. Оба массива выдать на печать.
2.Для каждой строки двумерного массива подсчитать и выдать на печать количество элементов, кратных 4 и кратных 9.
Вариант 11.
1.В двумерном массиве переставить строки таким образом, чтобы среднее значение элементов каждой строки возрастало с убыванием ее номера.
2.Выяснить, содержатся ли в одномерном массиве совершенные числа. Преобразовать этот массив таким образом, чтобы все элементы, не являющиеся совершенными числами, были заменены суммами их делителей. Исходный и преобразованный массивы выдать на печать.
Вариант 12.
1.Создать одномерный целочисленный массив. Упорядочить массив по возрастанию элементов методом пузырька.
2.Найти произведение двух целочисленных матриц 3х3.
Вполученной матрице перестановкой строк и столбцов добиться, чтобы минимальный элемент имел координаты [1,1].
Вариант 13.
1. Сформировать вещественную матрицу 5х5. Вычислить произведение отрицательных элементов, находящихся над и под главной диагональю матрицы.
47
2. Ввести одномерный вещественный массив из 20 элементов. Упорядочить массив по убыванию элементов методом перебора.
Вариант 14.
1.Сформировать вещественную матрицу 5х5. Упорядочить по возрастанию элементы каждой строки матрицы.
2.Вычислить сумму квадратов нечетных элементов целочисленного массива из 20 элементов.
Вариант 15.
1.Ввести целочисленную квадратную матрицу NхN. Найти максимум среди сумм элементов диагоналей, параллельных побочной диагонали.
2.Задан одномерный массив из N вещественных чисел. Определить образуют ли элементы массива возрастающую последовательность. Если последовательность не возрастает, то упорядочить ее по возрастанию любым способом.
Вариант 16.
1.Задан одномерный массив. Определить сколько раз меняется знак элементов в данном массиве, запомнить номера позиций, в которых меняется знак.
2.Упорядочить матрицу построчно по возрастанию.
Вариант 17.
1.Заданы два массива с N и M элементами, упорядоченными по неубыванию, объединить элементы этих массивов в один массив так, чтобы элементы снова оказались упорядоченными по неубыванию
2.Осуществить поворот матрицы против часовой стрелки на 90 градусов.
48
Вариант 18.
1.Дан одномерный массив А, состоящий из N элементов. Сколько значений элементов в массиве А встречается более одного раза?
2.Определить, является ли заданная матрица ортонормированной, т.е. скалярное произведение каждой пары различных строк (или столбцов) равно нулю.
Вариант 19.
1.Дан одномерный массив А, состоящий из N элементов. Подсчитать максимальное количество подряд идущих нулей.
2.Заполнить квадратную матрицу В(10,10) единицами т нулями в шахматном порядке.
Вариант 20.
1.Дан одномерный массив А, состоящий из N элементов. Исключить из массива первый положительный элемент, следующий за максимальным.
2.Для матрицы С(m,n), 1<m, n<10, найти сумму элементов, больших 3.2. Переставить столбцы по возрастанию количества отрицательных элементов в столбцах.
Вариант 21.
1 . Дан одномерный массив А, состоящий из N элементов. Подсчитать максимальное количество положительных элементов, заключенных между нулями.
2. |
Сформировать матрицу с треугольником Паскаля (би- |
||||||
номинальные коэффициенты) |
0 |
0 |
0 |
||||
1 |
0 |
0 |
0 |
0 |
|||
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
3 |
3 |
1 |
0 |
0 |
0 |
0 |
1 |
4 |
6 |
4 |
1 |
0 |
0 |
0 |
49