12. Алгоритм нахождения минимума и максимума
Задача 1. Ввести в ЭВМ последовательность из n чисел x1, х2,..., хn, n<200. Найти минимальное и максимальное из них.
При поиске минимума или максимума используется дополнительная переменная min (или max), которой:
1) вначале присваивается значение первого числа из последовательности (x1), т.е. принимается, что первое число является текущим минимумом (максимумом);
2) начиная со второго числа, производится сравнение этого числа со значением переменной min (или max) и если число из массива меньше min (больше max), то на место min (max) записывается это число. Теперь это число будет текущим минимумом (максимумом).
Ясно, что после просмотра всех чисел последовательности в переменной min (или max) будет находиться окончательное значение минимума (или максимума). Программа для этого алгоритма будет иметь вид
Program Minmax;
Const
Nmax=200;
Var
X : Array [1..Nmax] Of Real;
Min, Max : Real;
N, i : Integer;
Begin
Writeln('Введите количество чисел');
Readln(n);
Writeln('Вводите элементы массива');
For i := 1 To n Do
Read(X[i]);
Min := X[1];
Max := X[1];
For i : =2 To n Do
If Max < X[i] Then
Max := X[i]
Else
If Min > X[i] Then
Min :=X [i];
Writeln ('Min= ', Min:8;2,'Max= ', Max:8:2);
End.
В некоторых случаях бывает необходимо не только найти минимальное или максимальное число в последовательности, но и запомнить его номер (индекс).
Задача 2. Найти минимум в последовательности из n чисел (n>=100) и номер минимального числа. В этой задаче необходимо использовать ещё одну переменную: не только Min, но и номер, – например Imin. Каждый раз, когда Min присваивается очередное значение, нужно запомнить и индекс (номер) числа. Соответствующая программа может быть представлена в виде
Program Minimum;
Const
Nmax = 100;
Var
X : Array[1..Nmax] Of Real;
Min : Real;
n, i, Imin : Integer;
Begin
Writeln('Введите количество чисел');
Readln(n);
Writeln('Вводите элементы массива');
For i:=1 To n Do
Read(X[i]);
Min := X[1];
Imin := 1;
For i := 2 To n Do
If Min > X[i] Then
Begin
Min := X[i];
Imin := i;
End;
Writeln('Минимум = ', Min:8:2, ' Номер = ', Imin)
End.
13. Задача сортировки
Сортировка – это расположение чисел в порядке возрастания или убывания.
Наиболее распространенный и простой метод сортировки – метод "пузырька". Он требует минимального объема памяти для данных, но затраты времени на реализацию этого метода велики. Суть метода "пузырька" в следующем.
Пусть дано n чисел, которые необходимо расположить (для определенности) в порядке возрастания. При упорядочении выполняются следующие операции:
1) числа сравниваются попарно: первое со вторым; второе с третьим; i-тое – с (i+1) - тым;
2) если меньшее стоит в паре на втором месте (числа в паре не упорядочены по возрастанию), то сравниваемые числа меняются местами.
За один такой просмотр массива минимальное число "вытолкнется", по крайней мере, на одно место вверх (вперед), а максимальное – переместится в самый конец (вниз), т.е. минимальное число как легкий пузырек воздуха в жидкости постепенно "всплывает" в начало последовательности. Отсюда – название метода. За n-1 просмотр произойдет полное упорядочение массива при любом исходном расположении чисел в нем. Рассмотрим работу метода на примере, приведенном на рис. 2.8.
19 13 5 31 1 26 7 Исходный массив
1 Перестановки
в
первом
просмотре
5 19
1 31
26 31
7 31
1
После
первого просмотра
5
13
Перестановки
во
втором
просмотре
После
второго просмотра
5 13 1 19 7 26 31
Перестановки
в третьем
просмотре
После третьего
просмотра
7 19
5 1 13 7 19 26 31
1
Перестановки
в четвертом просмотре
После четвертого
просмотра
5
7 13
1 5 7 13 19 26 31
В пятом просмотре перестановок нет. Сортировка окончена.
1 5 7 13 19 26 31 Отсортированный массив
Рис. 2.8. Иллюстрация метода сортировки "пузырьком"
Алгоритм сортировки
1. Ввести n чисел.
2. Для номера_просмотра от 1 до n-1 выполнить
2.1. Для номера_числа (i) от 1 до n-1 выполнить
Если число[i] > число[i+1], то поменять их местами.
3. Вывести отсортированную последовательность.
4. Закончить.
Программа для этого алгоритма будет иметь вид
Program Sort;
Const
Nmax = 100;
Var
X : Array [1..Nmax] Of Real;
A : Real;
n, k, i : Integer;
Begin
Writeln('Введите количество чисел');
Readln(n);
Writeln('Введите массив чисел');
For i := 1 To n Do
Read (X[i]);
{ Сортировка }
For k := 1 To n-1 Do
For i := 1 To n-1 Do
If X[i] > X[i+1] Then
Begin
A:=X[i];
X[i]:=X[i+1];
X[i+1]:=A
End;
Writeln('Отсортированный массив чисел:');
For i:=1 To n Do
Write (X[i]);
End.
Глубину просмотра можно уменьшать, основываясь на том, что большие числа "опускаются" вниз (в конец последовательности) и затем не переставляются:
For k := 1 To n-1 Do
For i := 1 To n-k Do
If X[i] > X[i+1] Then
. . . . . . . .
Сокращение количества просмотров улучшает временные характеристики метода. Из алгоритма можно понять, что если на одном из просмотров не было перестановок, то их не будет и потом – данные уже отсортированы, процесс сортировки следует закончить. Такой подход дает значительную экономию времени при работе с большими "почти отсортироваными" массивами. Примером такого массива может быть упорядоченный по алфавиту список сотрудников фирмы, на которую время от времени принимают новых работников.
Приведем алгоритм для этого метода.
В этом алгоритме используется переменная "Перестановка_есть", которой сначала присваивается значение "истина", а как только в одном из просмотров не будет перестановок – ей присвоится значение "ложь". Это позволит прервать выполнение цикла "Пока".
1. Ввести массив.
2. Перестановка_есть = истина.
3. Номер_просмотра = 1.
4. Пока перестановка_есть = истина выполнить
сортировку массива.
5. Вывести результат.
6. Закончить.
Уточним отдельные пункты этого алгоритма.
1. Ввести массив.
2. Перестановка_есть = истина
3. Номер_просмотра (к)=1
4. Пока перестановка_есть = истина выполнить
4.1. Количество_перестановок = 0
4.2. Для i от 1 до n-k выполнить
Если x[i] > x[i+1], то
4.2.1. поменять x[i] и x[i+1]
4.2.2. количество_перестановок = количество_перестановок + 1
4.3. Если количество_перестановок = 0, то
перестановка_есть =ложь.
4.4. к=к+1
5. Для i от 1 до n выполнить
Вывести x[i].
6. Закончить.
Программа для этого алгоритма будет иметь вид
Program SortUsk;
Const
Nmax = 100;
Var
X : Array [1..Nmax] Of Real;
A : Real;
P : Boolean;
L, K, I, N : Integer;
Begin
Writeln('Введите количество чисел');
Readln(n);
Writeln('Введите массив чисел');
For i := 1 To n Do
Read(X[i]);
P := True; {Перестановка есть}
K := 1; {Номер просмотра}
While P Do
Begin
L:=0; {Кол. перестановок}
For i := 1 To n-k Do
If X[i] > X[i+1] Then
Begin
A := X[i];
X[i]:=X[i+1];
X[i+1]:=A;
L:=L+1
End;
If L=0 Then
P:=False;
k:=k+1;
End;
Writeln('Отсортированный массив чисел');
For i := 1 To n Do
Write(X[i]);
End.