2.3. Классы задач по обработке массивов
1) К задачам 1 класса относятся задачи, в которых выполняется однотипная обработка всех или указанных элементов массива. Решение таких задач сводится к установлению того, как обрабатывается каждый элемент массива или указанные элементы, затем подбирается подходящая схема перебора, в которую вставляются операторы обработки элементов массива. Примером такой задачи является нахождение среднего арифметического элементов массива.
2) К задачам 2 класса относятся задачи, в которых изменяется порядок следования элементов массива. Обмен элементов внутри массива выполняется с использованием вспомогательной переменной: R:=a[I];a[I]:=a[J]; a[J]:=R; - обмен a[I] и a[J] элементов массива.
3) К задачам 3 класса относятся задачи, в которых выполняется обработка нескольких массивов или подмассивов одного массива. Массивы могут обрабатываться по одной схеме – синхронная обработка или по разным схемам – асинхронная обработка массивов.
4) К задачам 4 класса относятся задачи, в которых требуется отыскать первый элемент массива, совпадающий с заданным значением – поисковые задачи в массиве.
Сортировка – это процесс перегруппировки заданного множества объектов в некотором установленном порядке.
2.4.1. Сортировка с помощью включения
Элементы массива делятся на уже готовую последовательность и исходную. При каждом шаге, начиная с I=2, из исходной последовательности извлекается I-ый элемент и вставляется на нужное место готовой последовательности, затем I увеличивается на 1 и т. д. В процессе поиска нужного места осуществляются пересылки элементов больше выбранного на одну позицию вправо, т. е. выбранный элемент сравнивают с очередным элементом отсортированной части, начиная с J:=I-1. Если выбранный элемент больше a[I], то его включают в отсортированную часть, в противном случае a[J] сдвигают на одну позицию, а выбранный элемент сравнивают со следующим элементом отсортированной последовательности. Процесс поиска подходящего места заканчивается при двух различных условиях:
- если найден элемент a[J]>a[I];
- достигнут левый конец готовой последовательности, в этом случае используется барьер a[0], куда записывается элемент a[I].
For I:=1 to N do begin
X:=a[I];a[0]:=X;{барьер}
J:=I-1;
While X<a[J] do begin
a[J+1]:=a[J]; {сдвиг}
J:=J+1;
End;
A[J+1]:=x;{вставка на нужное место}
End;
2.4.2. Сортировка методом простого выбора
Выбирается минимальный элемент массива и меняется местами с первым элементом массива. Затем процесс повторяется с оставшимися элементами и т. д.
For I:=1 to N-1 do begin
K:=I; Min:=a[I];
For J:=I+1 to N do
If a[j]<Min then begin
K:=J; Min:=a[J];
End;
a[K]:=a[I];
a[I]:=Min;
end;
2.4.3. Сортировка методом простого обмена
Сравниваются и меняются местами пары элементов, начиная с последнего. В результате самый маленький элемент массива оказывается самым левым элементом массива. Процесс повторяется с оставшимися элементами массива.
For I:=2 to N do
For J:=N downto I do
If a[J]<a[J-1] then begin
R:=a[J];
a[J]:=a[j-1];
a[j-1]:=R;
end;
Является улучшенной модификацией метода простого выбора. В ней чередуются направления просмотров и запоминается место последнего обмена элементов массива.
L:=2;{левая граница}R:=N;{правая граница}
Repeat
For J:=R to L do{справа налево}
If a[J]<a[J-1] then begin
K:=J;
T:=a[J];
a[J]:=a[j-1];
a[j-1]:=T;
end;
L:=K+1;
For J:=L to R do{слева направо}
If a[J]<a[J-1] then begin
K:=J;
T:=a[J];
a[J]:=a[j-1];
a[j-1]:=T;
end;
R:=K-1;
Until L>R;
2. 5.1. Поиск в неупорядоченном массиве
Если массив неупорядочен, то для того, чтобы найти первый элемент массива, совпадающий с заданным элементом Х, надо последовательно просматривать элементы массива и сравнивать каждый элемент массива с Х до тех пор, пока либо искомый элемент не будет найден, либо массив не закончится.
I:=0;
Repeat
I:=I+1;
Until (a[I]=X)or(I=N);
If a[I]=X then Rez:=I else Rez:=0;
2.5.2. Поиск в упорядоченном массиве (бинарный или дихотомический)
Массив делится пополам S:=(L+R)div 2 и определяется в какой части массива находится нужный элемент Х. Т .к. массив упорядочен, то если a[S]<X, то искомый элемент находится в правой части массива, иначе - находится в левой части. Выбранную часть массива снова надо разделить пополам и т. д., до тех пор, пока границы отрезка L и R не станут равны.
L:=1; R:=N;
Repeat
S:=(L+R)div 2;
If a[S]<X then L:=S+1 else R:=S
Until L=R;
If a[L]=X then Rez=L else Rez:=0;
1) Сформировать с помощью датчика случайных чисел одномерный массив размерности М, которая задается пользователем.
2) Полученный массив напечатать.
3) Выполнить обработку и преобразование массива в соответствии со своим вариантом.
4) Напечатать преобразованный массив.
1.
1) Вычислить количество четных чисел в массиве.
2) Заменить все элементы массива, совпадающие с числом Х, на число У.
2.
1) Вычислить максимальный элемент массива.
2) Заменить отрицательные элементы в массиве на положительные.
3.
1) Найти сумму положительных чисел в массиве.
2) Заменить все четные числа на 1. Если четных чисел нет, то вывести сообщение об этом.
4.
1) Определить есть ли в массиве хотя бы одна пара совпадающих по величине чисел.
2) Преобразовать массив так, чтобы все нули оказались в начале массива.
5.
1) Найти количество чисел, попадающих в диапазон от А до В, где А и В задаются пользователем. Если таких чисел нет , то вывести сообщение об этом.
2) Упорядочить массив по возрастанию методом простого включения.
6.
1) Найти количество элементов массива, в которые входит цифра «5». Если таких элементов нет, то вывести сообщение об этом.
2) Заменить все элементы совпадающие с минимальным на среднее арифметическое массива.
7.
1) Вычислить произведение всех элементов массива, имеющих четные индексы и определить является ли оно четным числом.
2) Сдвинуть циклически элементы массива на количество элементов равное первому элементу массива.
8.
1) Вычислить сумму минимального и максимального элементов массива.
2) Преобразовать этот массив в двумерный массив N x K, где N и К задаются пользователем, недостающие элементы заполнить нулями.
9.
1) Найти количество элементов массива, которые являются простыми числами. Если таких чисел нет, то вывести сообщение об этом.
2) Преобразовать массив так, чтобы в начале массива были записаны все нули, потом все положительные элементы, а потом - отрицательные.
10.
1) Найти третий по величине элемент массива.
2) Преобразовать массив так, чтобы в начале массива были записаны все отрицательные элементы, потом все нули, а потом - положительные элементы.
11.
1) Найти количество одинаковых элементов в массиве.
2) Отсортировать массив по убыванию методом простого обмена.
12.
1) Найти количество чисел, которые заканчиваются цифрой «3». Если таких чисел нет, то вывести сообщение об этом.
2) Заменить в массиве все отрицательные числа на «0».
13.
1) Найти сумму элементов массива, в которые входит цифра «7». Если таких чисел нет, то вывести сообщение об этом.
2) Поменять местами первый и последний элементы массива.
14.
1) Найти количество чисел в массиве, меньших заданного числа У. Если таких чисел нет, то вывести сообщение об этом.
2) Упорядочить массив по убыванию методом простого выбора.
15.
1) Вычислить количество элементов массива кратных 5.
2) Упорядочить массив по возрастанию методом шейкер- сортировки.
16.
1) Найти первое вхождение элемента Х в массив. Если такого числа нет, то вывести сообщение об этом.
2) Преобразовать массив так, чтобы все положительные элементы были записаны в начале массива, потом все отрицательные, а потом - нули.
17.
1) Найти количество элементов массива, которые превышают число Х, заданное пользователем. Если таких чисел нет, то вывести сообщение об этом.
2) Поменять местами максимальный и минимальный элементы массива.
18.
1) Найти минимальную длину подмассива, расположенного между двумя нулями.
2) Заменить все четные числа на ноль.
19.
1) Вычислить сумму элементов массива и определить из сколько в ней цифр.
2) Заменить все отрицательные числа на их модуль.
20.
1) Найти количество различных чисел в массиве .
2) Преобразовать массив в двумерный массив N x N, где N задается пользователем. «Лишние» числа отбросить.
21.
1) Определить сколько элементов массива отличается от среднего значения на 10 процентов.
2) Используя метод бинарного поиска найти номер первого вхождения элемента Х в массив.
22.
1) Найти два наибольших элемента в массиве.
2) Все простые числа в массиве заменить на значение максимального элемента.
23.
1) Определить сколько в массиве чисел Фибоначчи.
2) Если число является числом Фибоначчи, то заменить его нулем.
24.
1) Найти количество элементов массива, у которых сумма цифр является четным числом.
2) Удалить из массива элементы, индексы которых кратны 5. Оставшиеся элементы сдвинуть в начало массива, конец массива заполнить нулями.
25.
1) Определить номера трех наименьших элемента в массиве.
2) Удалить из массива все четные элементы. Оставшиеся элементы сдвинуть в начало массива, конец массива заполнить нулями.
1) Постановка задачи (общая и конкретного варианта).
2) Анализ поставленного задания: определить к какому классу задач относится задача варианта и объяснить почему.