Методичка Программирование
.pdf3.Если число (не 0) находится на диагонали или ниже, то оно равно [N]
– [номер столбца].
Текст программы (результат на рис. 20)
{$DEFINE DEBUG} //Объявляем режим отладки const NMAX=50; //Максимальное кол-во
//элементов в массиве. type mas=array[1..NMAX,1..NMAX] of Integer;
//"скрываем" массив, для сохранности индексов
procedure FillArray(var m:mas;N:integer);
var i,j:integer; |
//используется, как индексы |
|
begin |
//элементов массива |
|
|
|
|
Randomize(); |
|
|
for i:=1 to N do |
//последовательный перебор |
|
for j:=1 to N do |
//всех строк массива |
|
//последовательный перебор |
||
|
//всех столбцов массива |
|
if ((i+j) mod 2 = 0) then |
//Если сумма |
|
|
//индексов четная |
|
begin m[i,j]:=0 end
else //Если сумма индексов не четная begin
if (i>j) then //Определяем где находится элемент m[i,j]:=N-i+1 //относительно главной диагонали
else m[i,j]:=N-j+1;
end;
end;
procedure FillArrayRandom(var m:mas;min,max,N:integer);
var i,j:integer; //используется, как //индексы элементов массива
begin
Randomize();
for i:=1 to N do //последовательный перебор //всех строк массива
for j:=1 to N do //последовательный перебор //всех столбцов массива
m[i,j]:=min+random(max-min+1); //случ. числа
//генерируем в диапазоне
71
end;
procedure PrintArray(var m:mas;N:integer); var i,j:integer; //используется, как индекс
//элементов массива
begin
for i:=1 to N do //последовательный перебор //всех строк массива
begin
for j:=1 to N do //последовательный перебор //всех столбцов массива
write(m[i,j]:3); //вывод элементов одной строки writeln; //отделяем одну строку от другой
end; end;
var a:mas; //объявили массив
n:integer; //кол-во элементов в массиве i:integer; //для обхода массива
sum,prz:integer; //сумма и произведение элементов begin
{$IFDEF DEBUG} //Для упрощения отладки используем //условные директивы компилятора
n:=4;
{$ELSE} //если не отладка
Write(Rus('Введите кол-во элементов в массиве:')); Readln(n); //с каким кол-вом элементов
//программа будет работать
{$ENDIF}
if ((n>NMAX) or (n<=0)) then begin
Writeln(Rus('Элементов не может быть менее 1 и более
'),NMAX);
exit; //Выход из программы end;
FillArray(a,n);//заполнение массива случайными числами
PrintArray(a,n); writeln('==========');
FillArrayRandom(a,-5,5,n);//генерируем случ. числа
//от -5 до 5
PrintArray(a,n);
sum:=0;
prz:=1;
for i:=1 to N do begin
72
sum:=sum+a[i,i];
prz:=prz*a[i,i]; end;
writeln(Rus('Сумма='),sum,Rus(' Произведение='),prz); if (sum>prz) then
writeln(Rus('Сумма больше произведения')) else if (sum=prz) then
writeln(Rus('Сумма равна произведению')) else
writeln(Rus('Сумма меньше произведения')); end.
Рис. 20. Результат работы программы
Варианты домашних заданий
|
|
4 |
0 |
4 |
0 |
|
|
1. |
Вид массива: |
0 |
3 |
0 |
3 |
. |
|
2 |
0 |
2 |
0 |
||||
|
|
|
|||||
|
|
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, перевернуть все нечетные столбцы массива.
|
|
1 |
0 |
0 |
0 |
|
|
2. |
Вид массива: |
1 |
2 |
0 |
0 |
. |
|
1 |
2 |
3 |
0 |
||||
|
|
|
|||||
|
|
1 |
2 |
3 |
4 |
|
|
|
|
|
|
|
|
|
73
Сгенерировать массив из случайных чисел, переставить элементы массива так, чтобы нули в каждой строке стояли в конце.
|
|
4 |
3 |
2 |
1 |
|
|
3. |
Вид массива: |
0 |
3 |
2 |
1 |
. |
|
0 |
0 |
2 |
1 |
||||
|
|
|
|||||
|
|
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, перевернуть все четные строки массива.
|
|
0 |
0 |
1 |
1 |
|
|
4. |
Вид массива: |
0 |
0 |
2 |
2 |
. |
|
3 |
3 |
0 |
0 |
||||
|
|
|
|||||
|
|
4 |
4 |
0 |
0 |
|
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, упорядочить элементы, находящиеся выше диагонали по убыванию в строках.
|
|
0 |
0 |
0 |
1 |
|
|
5. |
Вид массива: |
4 |
3 |
2 |
1 |
. |
|
0 |
3 |
2 |
1 |
||||
|
|
|
|||||
|
|
0 |
0 |
2 |
1 |
|
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, найти сумму элементов расположенных выше главной диагонали в строках, начинающихся с нуля.
|
|
4 |
4 |
4 |
4 |
|
|
6. |
Вид массива: |
3 |
3 |
3 |
0 |
. |
|
2 |
2 |
0 |
0 |
||||
|
|
|
|||||
|
|
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, перевернуть строку, содержащую максимальное число нулей, и столбец, содержащий минимальное число нулей.
|
|
1 |
1 |
1 |
1 |
|
|
7. |
Вид массива: |
0 |
2 |
2 |
2 |
. |
|
0 |
0 |
3 |
3 |
||||
|
|
|
|||||
|
|
0 |
0 |
0 |
4 |
|
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, найти сумму элементов, расположенных ниже главной диагонали, и сумму отрицательных элементов, расположенных выше главной диагонали.
74
|
|
4 |
4 |
4 |
4 |
|
|
8. |
Вид массива: |
3 |
3 |
3 |
3 |
. |
|
2 |
2 |
2 |
2 |
||||
|
|
|
|||||
|
|
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, найти произведение последних элементов строк.
|
|
1 |
0 |
3 |
0 |
|
|
9. |
Вид массива: |
0 |
2 |
0 |
4 |
(заполняется построчно). |
|
1 |
0 |
3 |
0 |
||||
|
|
|
|||||
|
|
0 |
2 |
0 |
4 |
|
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, переставить элементы массива так, чтобы все нули оказались в конце строк.
|
0 |
0 |
0 |
1 |
|
|
10. Вид массива: |
0 |
0 |
1 |
2 |
. |
|
0 |
1 |
2 |
3 |
|||
|
|
|||||
|
1 |
2 |
3 |
4 |
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, в каждом столбце найти наименьший элемент, затем найти их произведение.
|
4 |
3 |
2 |
1 |
|
|
11. Вид массива: |
3 |
2 |
1 |
0 |
. |
|
2 |
1 |
0 |
0 |
|||
|
|
|||||
|
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, выяснить, сколько в массиве совпадающих по величине чисел.
|
0 |
0 |
0 |
1 |
|
|
12. Вид массива: |
0 |
0 |
2 |
1 |
. |
|
0 |
3 |
2 |
1 |
|||
|
|
|||||
|
4 |
3 |
2 |
1 |
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, в каждой строке найти наибольший элемент, затем найти их сумму.
|
0 |
0 |
0 |
0 |
|
|
13. Вид массива: |
0 |
0 |
0 |
2 |
. |
|
0 |
0 |
2 |
3 |
|||
|
|
|||||
|
0 |
2 |
3 |
4 |
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, найти сумму максимального и минимального элементов.
75
|
0 |
0 |
0 |
0 |
|
|
14. Вид массива: |
0 |
0 |
0 |
1 |
. |
|
0 |
0 |
2 |
1 |
|||
|
|
|||||
|
0 |
3 |
2 |
1 |
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, найти количество чисел, входящих в массив только один раз.
|
1 |
1 |
1 |
1 |
|
|
15. Вид массива: |
2 |
2 |
2 |
0 |
. |
|
3 |
3 |
0 |
0 |
|||
|
|
|||||
|
4 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, найти произведение элементов в первой строке, а затем в последней и сравнить их.
|
4 |
4 |
4 |
4 |
|
|
16. Вид массива: |
0 |
3 |
3 |
3 |
. |
|
0 |
0 |
2 |
2 |
|||
|
|
|||||
|
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, упорядочить массив по возрастанию элементов в каждой строке.
|
0 |
4 |
0 |
3 |
|
|
17. Вид массива: |
2 |
0 |
1 |
0 |
(заполняется построчно). |
|
0 |
4 |
0 |
3 |
|||
|
|
|||||
|
2 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, упорядочить массив по убыванию элементов в каждом столбце.
|
1 |
2 |
3 |
4 |
|
|
18. Вид массива: |
1 |
2 |
3 |
0 |
. |
|
1 |
2 |
0 |
0 |
|||
|
|
|||||
|
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, найти максимальный элемент среди элементов, сумма индексов которых нечетна.
1 0 1 0
0 3 0 3
19.Вид массива: (массив заполняется по столбцам).
2 0 2 0
0 4 0 4
76
Сгенерировать массив из случайных чисел, сравнить сумму произведений элементов строк и произведение сумм элементов столбцов и вывести соответствующее сообщение.
0 1 0 2
3 0 4 0
20.Вид массива: (массив заполняется по строкам).
0 1 0 2
3 0 4 0
Сгенерировать массив из случайных чисел, найти суммы чисел в первом и последнем столбцах и сравнить их.
1 0 3 0
0 2 0 4
21.Вид массива: (массив заполняется по столбцам).
2 0 4 0
0 3 0 1
Сгенерировать массив из случайных чисел, сравнить суммы элементов, сумма индексов которых нечетна и сумма индексов которых четна.
|
1 |
1 |
2 |
2 |
|
|
22. Вид массива (до N+1): |
2 |
2 |
3 |
3 |
(массив заполняется по строкам). |
|
4 |
4 |
0 |
0 |
|||
|
|
|||||
|
1 |
1 |
2 |
2 |
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, найти номер строки с максимальной суммой модулей элементов строк.
|
2 |
0 |
4 |
0 |
|
|
23. Вид массива: |
0 |
4 |
0 |
6 |
. |
|
4 |
0 |
6 |
0 |
|||
|
|
|||||
|
0 |
6 |
0 |
8 |
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, найти номера строк, сумма элементов которых больше среднего арифметического всех элементов массива.
|
1 |
2 |
3 |
4 |
|
|
24. Вид массива: |
2 |
1 |
2 |
3 |
. |
|
3 |
2 |
1 |
2 |
|||
|
|
|||||
|
4 |
3 |
2 |
1 |
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел, поменять местами столбец и строку суммы элементов которых минимальны.
77
|
0 |
3 |
0 |
1 |
|
|
25. Вид массива: |
3 |
0 |
1 |
0 |
. |
|
0 |
1 |
0 |
3 |
|||
|
|
|||||
|
1 |
0 |
3 |
0 |
|
|
|
|
|
|
|
|
Сгенерировать массив из случайных чисел таким образом, чтобы соотношение сумм элементов выше главной диагонали и ниже её стремилось к 1/3.
Задания к лабораторной работе № 6
Сортировка массивов
Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого. Тип данных ключа должен допускать использование операции сравнения («=», «>», «<», «>=» и «<=»). Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа.
Метод сортировки называется устойчивым, если при его применении не изменяется относительное положение записей с равными значениями ключа.
Мерой эффективности алгоритма сортировки являются число требуемых сравнений значений ключа (C) и число перестановок элементов (M).
Алгоритм сортировки является универсальным, если эта сортировка может быть применена к любому типу данных, для которого определены операции сравнения. Алгоритм сортировки является специализированным, если эта сортировка может быть применена к определенному типу данных, например, только для целых чисел.
При изучении алгоритмов сортировки будем считать, что значение каждого элемента – это ключ, по которому необходимо сортировать массив.
Алгоритмы сортировки
Рассматриваемые алгоритмы сортировки являются универсальными. Большинство приведенных алгоритмов имеют сложность O(n2)12, существуют более быстрые универсальные алгоритмы сортировки, например быстрая сортировка (Quick sort), имеющая сложность O(n∙log n).
Сортировка выбором (сложность O(n2))
1.Между первым и последним элементом найти минимальный, меняем местами первый и минимальный.
2.Между вторым и последним элементом найти минимальный, меняем местами второй и минимальный.
3.Между третьим и последним элементом найти минимальный, меняем местами третий и минимальный.
12 Сложность O(n2) означает, что при больших n время работы алгоритма (или общее количество операций) будет не более чем C ∙ n2, где C – некая положительная константа (обычно в качестве параметра n берется размер массива).
78
…
N–1. Между N–1-м и последним элементом найти минимальный, меняем местами N–1-й и минимальный.
N. Массив отсортирован
Изменение последовательности элементов происходит следующим образом:
1 шаг |
2 |
5 |
2 |
1 |
3 |
2 шаг |
1 |
5 |
2 |
2 |
3 |
3 шаг |
1 |
2 |
2 |
5 |
3 |
4 шаг |
1 |
2 |
2 |
5 |
3 |
5 шаг |
1 |
2 |
2 |
3 |
5 |
Условные обозначения:
|2 5| - диапазон для поиска минимального элемента.
Пузырьковая (сложность O(n2))
1.Сравнить соседние элементы, если первый больше второго, то поменять их местами.
2.Перейти к следующему элементу.
3.При достижении конца массива перейти к началу и обнулить количество перестановок.
4.Повторять шаги 1 – 3, пока количество перестановок при одном полном прохождении массива больше 0.
Изменение последовательности элементов происходит следующим образом:
2 |
5 |
2 |
1 |
3 |
2 |
2 |
5 |
1 |
3 |
2 |
2 |
1 |
5 |
3 |
2 |
2 |
1 |
3 |
5 |
Переход к началу
2 1 2 3 5
Переход к началу
1 2 2 3 5
Условные обозначения:
|2 5| – элементы, которые поменяли местами.
Пустая строка – переход к началу массива.
Гномья сортировка (сложность O(n2))
1.Сравнить соседние элементы, если первый больше второго:
a)поменять их местами;
b)если это не первый элемент массива, перейти к предыдущему элементу, иначе перейти к следующему элементу массива.
2.Если достигнут конец массива, то массив уже отсортирован.
Изменение последовательности элементов происходит следующим образом:
79
2 |
5 |
2 |
1 |
3 |
2 |
2 |
5 |
1 |
3 |
2 |
2 |
1 |
5 |
3 |
2 |
1 |
2 |
5 |
3 |
1 |
2 |
2 |
5 |
3 |
1 |
2 |
2 |
3 |
5 |
Условные обозначения:
|2 5| – элементы, которые поменяли местами.
Глупая сортировка (сложность O(n3))
1.Текущий элемент сравнивается со следующим,
2.Если следующий меньше, то производится обмен и возврат в начало массива.
3.Если достигнут конец массива, то массив отсортирован.
Изменение последовательности элементов происходит следующим образом:
2 |
5 |
2 |
1 |
3 |
2 |
2 |
5 |
1 |
3 |
2 |
2 |
1 |
5 |
3 |
2 |
1 |
2 |
5 |
3 |
1 |
2 |
2 |
5 |
3 |
1 |
2 |
2 |
3 |
5 |
Условные обозначения:
|2 5| – элементы, которые поменяли местами.
Текст программы:
//вспомогательная процедура. Перестановка //значений двух переменных
procedure swap(var a,b:integer);
var t:integer; //объявляем временную переменную begin
t:=a; //сохраняем значение первой a:=b; //переставляем вторую b:=t; //переставляем первую
end;
//глупая сортировка
procedure dummy_sort(var m:mas;N:integer); var i:integer;
begin |
|
|
i:=1; |
//Встаем на первый элемент |
|
while (i <= N-1) do |
//выполняем цикл, пока |
|
|
|
//не дойдем до предпоследнего |
80