Решение задач с использованием массивов
Задания
1.Дан массив целых чисел. Количество запросить с клавиатуры. Найти:
•сумму элементов массива, больших данного числа А (А вводить с клавиатуры).
Экспериментальный раздел работы
Измените программу, для определения:
•суммы элементов массива, принадлежащих промежутку от А до В (А и В вводить с клавиатуры);
•суммы элементов массива, принадлежащих промежутку от А до В (А и В вводить с клавиатуры);
•суммы элементов массива с k1-ro по k2-й, где k1 и k2 вводятся с клавиатуры;
•суммы последних пяти элементов массива
•количества нечетных элементов массива;
•количества отрицательных элементов массива;
• количества элементов массива, которые превосходят по модулю заданное число А;
• наличие в данном массиве два соседних положительных элемента;
• наличие 2 пар соседних элементов с одинаковыми знаками;
• номер последней пары соседних
элементов с разными знаками.
Сортировка элементов массива
При работе с массивами данных не редко возникает задача их сортировки по возрастанию или убыванию, т.е. упорядочивания. Это значит, что элементы нужно расположить строго по порядку.
Элементы массива можно сортировать:
· по возрастанию — каждый следующий элемент больше предыдущего — А[1] < А[2] <... < A[N];
· по не убыванию — каждый следующий элемент не меньше предыдущего, то есть больше или равен А[1 ] ≤ А[2] ≤... ≤A[N];
· по убыванию — каждый следующий элемент меньше предыдущего А[1 ] > А[2] > ... > A[N];
· по не возрастанию — каждый следующий элемент не больше предыдущего, то есть меньше или равен А[1] ≥ А[2] ≥ ... ≥ A[N].
Алгоритмы сортировки отличаются друг от друга степенью эффективности, под которой понимается количество сравнений и количество обменов, произведенных в процессе сортировки.
Достаточно простой для понимания является сортировка методом пузырька, который также называют методом простого обмена.
Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).
Метод пузырька (простой обмен):
• При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.
Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.
• При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.
• На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.
• В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.
• После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно n-1, где n – это количество элементов массива.
• Количество сравнений в каждом проходе равно n-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).
• При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.
0
|
1
|
4
|
6
|
2
|
0
|
1
|
4
|
2
|
6
|
0
|
1
|
2
|
4
|
6
|
program sort1;
const
mn = 10;
var
a: array[1..mn] of integer;
i, j, k,n: integer;
begin
readln(n);
readln(n);
randomize;
for i := 1 to n do
begin
a[i] := random(256);
write (a[i]:4);
end;
writeln;
for i := 1 to n-1 do
for j := i+1 to n do
if a[i] > a[j] then
begin
k := a[i];
a[i] := a[j];
a[j] := k
end;
for i := 1 to n do
write (a[i]:4);
end.
Экспериментальная часть
1. Выполните программу для n=10.
2. Выполните программу для n=5.
3. Добавьте в окно просмотра a[1], a[2], a[3], a[4], a[5]. Выполните программу по шагам.
4. Измените программу, чтобы элементы располагались от большего к меньшему.
Задания
1. Рассмотреть сортировку простым выбором:
Program Sort2;
Const mn=10;
Var A:Array[1..mn] of real;
i, j, m,n: Integer; k,max:real;
begin
readln(n);
readln(n);
randomize;
for i := 1 to n do
begin
a[i] := random(256);
write (a[i]:8:1);
end;
writeln;
For i:=n DownTo 2 Do
Begin
m:=i; max:=a[i];
For j:=1 to i-1 Do
If A[j ] >max Then Begin m:=j; max:=A[j] End;
If m<>i Then Begin A[m] :=A[i] ;A[i] :=max; End;
End;
for i := 1 to n do
write (a[i]:8:1);
End.
Каким образом выполняется сортировка простым выбором?
2. Изменить решения в двух рассмотренных методах так, чтобы осуществлялась сортировка:
1) четных элементов массива;
2) отрицательных элементов массива;
3) элементов, записанных на нечетных местах.
3. Определить есть ли в массиве равные элементы. Вывести их на экран.
3. Определить есть ли в массиве равные элементы. Вывести их на экран.
Задания для самостоятельного решения
•максимальный элемент массива и его номер, при условии, что все элементы различные;
•минимальный элемент массива.
2. Дан массив из 10 элементов. Первые 4 упорядочить по возрастанию, последние 4 по убыванию.
3. Измените алгоритм предыдущей задачи для n элементов.
4. Дан массив 20 целых чисел на отрезке [-2;5]. Упорядочить массив, удалив нули со сдвигом влево, ненулевыми элементами.