Методическая разработка по теме: «Обработка массивов» (стр. 5 )

Партнерка на США и Канаду по недвижимости, выплаты в крипто

30% recurring commission
Выплаты в USDT
Вывод каждую неделю
Комиссия до 5 лет за каждого referral

Массив A является отсортированным (упорядоченным) по возрастанию, если для всех i из интервала [1..n-1] выполняется условие A[i]<=A[i+1].

Существует множество методов сортировки, мы же воспользуемся один из самых простых - метод сортировки выбором (поиском минимального).

Суть этого метода сортировки заключается в следующем:

1. В массиве находим минимальный элемент.

2. Меняем минимальный элемент с первым.

3. В усеченном (исключая первый элемент) массиве находим минимальный элемент.

4. Ставим его на второе место. И так далее n-1 раз.

Пример:

Массив A, исходное состояние 1 3 0 9 2

Процесс сортировки

0: 1 3 0 9 2 min=a[3]=0 Переставляем a[1]<->a[3]

1: 0 | 3 1 9 2 min=a[3]=1 Переставляем a[2]<->a[3]

2: 0 1 | 3 9 2 min=a[5]=2 Переставляем a[3]<->a[5]

3: 0 1 2 | 9 3 min=a[5]=3 Переставляем a[4]<->a[5]

НЕ нашли? Не то? Что вы ищете?

4: 0 1 2 3 9 Готово

Здесь знак | отделяет уже отсортированную часть массива от еще не отсортированной.

На Turbo Pascal этот алгоритм будет выглядеть следующим образом:

Var

buf: integer; {через buf будем менять значения двух элементов массива}

imin:IndexEl; {индекс минимального элемента неотсортированной части массива}

…

Begin

…

{n-1 раз ищем минимальный элемент массива}

for i:=1 to n-1 do

begin

{Ищем минимальный элемент в несортированной части массива (от i-го элемента)}

imin:=i; {imin - это индекс минимального элемента массива}

for j:=i+1 to n do

if A[j]<A[imin] then imin:=j;

{переставляем i-ый и imin-ый элементы}

buf:=A[i];

A[i]:=A[imin];

A[imin]:=buf;

End;

…

Задача 21. Вставить в упорядоченный по возрастанию массив новый элемент таким образом, чтобы сохранилась упорядоченность.

Алгоритм решения задачи следующий:

1. Ищем в массиве тот элемент, который больше вставляемого, – для этого последовательно просматриваем все элементы, начиная с первого.

2. Увеличиваем длину массива на 1.

3. После этого все элементы, стоящие правее от найденного, включая его самого, сдвигаются вправо.

4. На освободившуюся позицию вставляется искомый элемент.

Замечание: если все элементы массива меньше вставлямого, то новый элемент надо вставить в конец массива. Если все элементы массива больше вставляемого, то новый элемент надо вставить в начало массива.

Пример: Надо вставить 5 в массив A: 3 4 7 9

1. Ищем элемент, больший вставляемого. Это элемент A[3]=7.

2. Увеличиваем длину массива на 1.
Получаем массив A: 3 4 7 9 X

3. Сдвигаем элементы, начиная с 3-го, вправо.

Получаем массив A: 3 4 7 7 9

4. В элемент A[3] заносим 5.

Получаем массив: 3 4 5 7 9

Фрагмент программы, реализующей данный алгоритм:

…

{считываем число, которое надо вставить в массив}

read(g);

{1. Ищем элемент больше вставляемого }

k:=1; {k – индекс сравниваемого элемента}

while (k<=n) and (g>=a[k]) do {если k не вышла за границу n, и вставляемый
элемент меньше или равен A[k]}

k:=k+1; {то переходим к следующему элементу}

{2. Увеличиваем длину массива на 1}

n:=n+1;

{3. Сдвигаем элементы начиная с k-го вправо}

for i:=n downto k+1 do

a[i]:=a[i-1];

{4. В A[k] заносим g}

a[k]:=g;

…

ЗАДАЧИ ДЛЯ ИЗУЧАЮЩИХ

ПРОГРАММИРОВАНИЕ САМОСТОЯТЕЛЬНО

Этот раздел предназначен для тех, кто самостоятельно изучает программирование или готовится к сдаче экзамена. В разделе собраны задачи от простейших до весьма сложных, причем выстроены они по темам, а внутри тем от простых к сложным. Желательно решать эти задачи последовательно и пропускать их только в том случае, если решение для Вас очевидно. Если Вам удалось решить все задачи, то можете поставить себе "отлично" и смело переходить к изучению следующей темы программирования – обработке двумерных массивов…

Общее задание:

Во всех задачах требуется написать, отладить и протестировать программу, обеспечивающую выполнение следующих действий:

1. Ввод с клавиатуры одномерного массива A[N] целых чисел, 1<=N<=20.

2. Вывод исходного, т. е. только что введенного, массива.

3. Обработка массива в соответствии с заданием.

4. Вывод параметров массива, которые требуется найти по заданию.

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

5. Вывод массива после внесенных изменений.

Замечания:

1. При обработке вспомогательными массивами по возможности не пользоваться.

2. Если по заданию требуется использовать больше одного массива, то каждый из массивов – это массив целых чисел. Первый массив называется А, второй массив называется B, третий массив называется C. Все они могут содержать от 1 до 20 элементов.

Задачи на сканирование всего массива

1. Подсчитать количество нечетных элементов массива.