Классы задач по обработке массивов

1) К задачам 1 класса относятся задачи, в которых выполняется однотипная обработка всех или указанных элементов массива. Решение таких задач сводится к установлению того, как обрабатывается каждый элемент массива или указанные элементы, затем подбирается подходящая схема перебора, в которую вставляются операторы обработки элементов массива. Примером такой задачи является нахождение среднего арифметического элементов массива.

2) К задачам 2 класса относятся задачи, в которых изменяется порядок следования элементов массива. Обмен элементов внутри массива выполняется с использованием вспомогательной переменной: R:=a[I];a[I]:=a[J]; a[J]:=R; - обмен a[I] и a[J] элементов массива.

3) К задачам 3 класса относятся задачи, в которых выполняется обработка нескольких массивов или подмассивов одного массива. Массивы могут обрабатываться по одной схеме – синхронная обработка или по разным схемам – асинхронная обработка массивов.

4) К задачам 4 класса относятся задачи, в которых требуется отыскать первый элемент массива, совпадающий с заданным значением – поисковые задачи в массиве.

Сортировка массивов

Сортировка – это процесс перегруппировки заданного множества объектов в некотором установленном порядке.

Сортировка с помощью включения

Элементы массива делятся на уже готовую последовательность и исходную. При каждом шаге, начиная с 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;

Сортировка методом простого выбора

Выбирается минимальный элемент массива и меняется местами с первым элементом массива. Затем процесс повторяется с оставшимися элементами и т. д.

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;

Сортировка методом простого обмена

Сравниваются и меняются местами пары элементов, начиная с последнего. В результате самый маленький элемент массива оказывается самым левым элементом массива. Процесс повторяется с оставшимися элементами массива.

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;

Поиск в массиве

Поиск в неупорядоченном массиве

Если массив неупорядочен, то для того, чтобы найти первый элемент массива, совпадающий с заданным элементом Х, надо последовательно просматривать элементы массива и сравнивать каждый элемент массива с Х до тех пор, пока либо искомый элемент не будет найден, либо массив не закончится.

I:=0;

Repeat

I:=I+1;

Until (a[I]=X)or(I=N);

If a[I]=X then Rez:=I else Rez:=0;

Поиск в упорядоченном массиве (бинарный или дихотомический)

Массив делится пополам 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;

 

3. Постановка задачи:

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) Удалить из массива все четные элементы. Оставшиеся элементы сдвинуть в начало массива, конец массива заполнить нулями.

5. Содержание отчета:

1) Постановка задачи (общая и конкретного варианта).

2) Анализ поставленного задания: определить к какому классу задач относится задача варианта и объяснить почему.

3) Словесный алгоритм решения задачи.

4) Текст программы.

5) Результаты тестов.

6. Пример выполнения работы и оформления отчета

Лабораторная работа №3
«Работа с массивами»

1. Постановка задачи:

1) Сформировать с помощью датчика случайных чисел одномерный массив размерности М, которая задается пользователем.

2) Полученный массив напечатать.

3) Выполнить обработку и преобразование массива в соответствии со своим вариантом.

4) Напечатать преобразованный массив.

Вариант №26.

1) Вычислить количество четных чисел в массиве.

2) Удалить из массива все четные элементы. Оставшиеся элементы сдвинуть в начало массива, конец массива заполнить нулями.

2. Анализ задания:

1 задача относится к первому классу задач, т. к. для каждого элемент массива требуется проверить условие четности элемента.

2 задача относится к 3 классу, т. к. для ее решения будет использоваться вспомогательный массив, массивы будут обрабатываться с помощью различных схем перебора, т. е. обработка асинхронная.

3. Алгоритм решения 1 задачи:

Организуем перебор массива от начала к концу по одному элементу, для каждого элемента проверим условие четности a[I] mod 2 =0. Ели условие выполнится, то счетчик четных чисел увеличим на 1.

Алгоритм решения 2 задачи:

Организуем перебор массива от начала к концу по одному элементу, для каждого элемента проверим условие нечетности a[I] mod 2 <>0. Ели условие выполнится, то запишем этот элемент во вспомогательный массив B. Затем оставшиеся элементы массива B заполним нулями.

4. Программа

Var a:array[1..100]of integer;

I,J,K,M:integer;

Begin

Writeln (‘Введите количество элементов массива’);

Read(M);

Writeln(‘Сформирован массив целых чисел’);

For I:= 1 to M do begin

a[I]:=random(100)-50;

Write(a[I],’ ‘);

End;

Writeln;

K:=0;

For I:=1 to M do

If a[I]mod 2=0 then K:=K+1;

If k>0 then

Writeln(‘в массиве ‘, K, ‘ четных элементов’)

Else begin

Writeln (‘Четных элементов нет’);

exit;{выход из программы}

Writeln(‘Удаление четных элементов из массива’);

J:=0;

For I:=1 to M do

If a[I]mod 2<>0 then begin

J:=J+1;

b[J]:=a[I];

end;

K:=J;

For I:=K to M do b[J]:=0;

For I:=1 to M do write(b[I],’ ‘);

Writeln;

End.

5. Тесты:

N	Исходный массив	Результат
	34 –56 45 2 7	К=3 45 7 0 0 0
	34 2 62 8 18	К=5 0 0 0 0 0
	33 5 47 –15 -9	Четных чисел нет

Лабораторная работа №4
«Использование процедур и функций»

1. Цель работы:

1) Использование структур данных при решении задач;

2) Использование подпрограмм при решении задач.

Теоретические сведения

Подпрограммы

Подпрограммы представляют собой относительно самостоятельные фрагменты программ, оформленные особым образом и имеющие имя. С их помощью программист может оформить часто используемый фрагмент в виде удобном для многократного исполнения. Подпрограммы позволяют разбить любую программу на несколько независимых частей. Такое разбиение необходимо по двум причинам:

1) Это средство экономии памяти, т. к. каждая подпрограмма существует в программе в единственном экземпляре, а обращаться к ней можно многократно из различных точек программы.

2) Использование методики нисходящего проектирования программ, когда алгоритм представляется в виде относительно крупных подпрограмм, реализующих более менее самостоятельные части алгоритма. Подпрограммы в свою очередь могут разбиваться на более мелкие подпрограммы нижнего уровня и т. д. – до тех пор пока реализуемые подпрограммами алгоритмы не станут настолько простыми, что их можно будет легко запрограммировать.

Работа с подпрограммой состоит из двух этапов:

1) описание подпрограммы;

2) вызов ее в основной программе для исполнения.

Описание подпрограммы:

<заголовок>

<описание данных>

begin

<тело подпрограммы>

end;

Заголовок процедуры имеет вид:

Procedure <имя>[(<список_формальных_параметров>)];

Заголовок функции имеет вид:

Function <имя>[(<список_формальных_параметров>)]:<тип>;

<имя> - имя подпрограммы;

<список_формальных_параметров> - список передаваемых или возвращаемых подпрограммой данных;

<тип> - тип возвращаемого функцией результата.

Список формальных параметров может отсутствовать.

Параметры

При вызове подпрограммы формальные параметры заменяются фактическими. Фактические и формальные параметры должны соответствовать друг другу по количеству, типу и порядку следования.

Параметры подразделяются на параметры-значения, параметры-переменные и параметры-константы. Если параметр определен как параметр-переменная (перед ним ставится слово Var), то при вызове подпрограммы передается адрес соответствующей переменной, следовательно, изменение такого параметра приводит к изменению значения по указанному адресу, и фактический параметр тоже меняется. Если параметр определен как параметр-значение, то перед вызовом подпрограммы это значение вычисляется, полученный результат копируется во временную память и передается в подпрограмму. Любые возможные изменения этого параметра не воспринимаются вызывающей программой, следовательно, фактический параметр не меняется. При использовании параметров констант (перед ним ставится слово Const) в подпрограмму будет передаваться адрес области памяти, в которой располагается переменная или вычисляемое значение, но компилятор блокирует присваивание нового значения параметру-константе в теле программы.