Вставка новых элементов в массив

Задача 11: В массив после максимального элемента вставить элемент, равный 0.

Пример исходного массива A: 1 2 5 1 0 1 2

максимальный элемент A[3]=5

Массив после вставки элемента: 1 2 5 0 1 0 1 2

Алгоритм вставки элемента в массив:

1. Сдвинуть элементы от позиции вставляемого элемента в конец.

2. В позицию вставляемого элемента вписать нужное значение.

3. Количество элементов n увеличить на 1 .

Общий алгоритм программы следующий:

1 . Введем массив А.

2 . Найдем индекс max элемента.

3 . Вставим после max 0.

4 . Выведем получившийся массив.

Приведем полный текст программы:

{Пример обработки одномерного массива}

{ Задание: В массив после максимального элемента

вставить элемент, равный 0}

Program InsertExample;

Const {определение констант}

maxN = 20; {максимально возможное количество элементов

в массиве}

Type {определение типов}

IndexEll = 1 .. maxN; {индексы массива лежат в интервале

от 1 до maxN}

arrInt = array[interval] of integer; {массив целых чисел,

содержащий до maxN элементов}

Var

a:arrInt; {массив}

n:integer; {количество элементов в массиве}

i:IndexEl; {переменная для сканирования массива}

max: IndexEl; {номер max элемента массива}

Begin

{1 - ввод массива - генерируем случайные элементы}

randomize;

n:=random(6)+5; {n в интервале 5..10}

for i:=1 to n do

A[i]:=random(19)-9; {Генерируем элементы массива}

{ каждый элемент имеет значение в интервале -9..9}

{2 - ищем индекс max элемента}

max:=1;

for i:=2 to n do

if A[i]>A[max] then max:=i;

{3- вставляем 0 после максимального элемента}

{сначала сдвигает “хвост” массива вправо}

for i:=n downto max+1 do

A[i+1]:=A[i];

{заносим в следующий за максимальным элемент 0}

A[max+1]:=0;

{увеличиваем количество элементов массива}

Inc(n);

{4 - выводим массив}

writeln('Массив А после вставки:');

for i:=1 to n do

write(A[i]:3);

readln; {ждем нажатия клавиши Enter}

End.

Данная программа демонстрирует модульный подход к решению задач - задача разбивается на подзадачи, полученные подзадачи решаются отдельно. Если подзадача не решается непосредственно, то она снова разбивается на подзадачи и т.д. Такой подход называется "программирование сверху вниз". Замечание: данная программа таит в себе ошибку. Если n=20, то после вставки еще одного элемента n станет равной 21, и, скорее всего, программа повиснет (потому что элементов в массиве может быть НЕ БОЛЬШЕ 20). Следовательно, при вставке элементов необходимо следить, чтобы было n<=maxN .

Удаление нескольких элементов массива

Задача 12: Удалить из массива все элементы между k-м и z-м

элементами.

Рассмотрим задачу на примере при количестве элементов в массиве n=10, k=3, z=7 (т.е. надо удалить элементы между третьим и седьмым). Будем использовать переменную d - количество удаляемых элементов. Значение d можно вычислить по формуле: d = z - k – 1 ( в нашем примере получится d = 7 - 3 - 1 = 3).

Массив A до удаления:

a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]

1 3 9 1 0 1 3 2 7 2

^ ^ ^

a[k] a[z] a[n]

Массив A после удаления:

a[1] a[2] a[3] a[4] a[5] a[6] a[7]

1 3 9 3 2 7 2

^ ^ ^

a[k] a[z] a[n]

После удаления n стало меньше на d (в нашем примере на 3).

Общий алгоритм решения:

1 . Сдвинуть элементы вперед на d элементов, начиная с z-го.

2 . Уменьшить n на d.

Фрагмент программы:

Var {дополнительные переменные}

k: integer; {индекс элемента, после которого удаляем}

z: integer; {индекс элемента, до которого удаляем}

d: integer; {количество удаляемых элементов}

…

Begin

…

{вычисляем количество удаляемых элементов}

d:=z-k-1;

{1 - сдвигаем элементы}

for i:=z to n do

A[i-d]:=A[i];

{2 - уменьшаем n на d}

Dec(n,d);

…

Задача 13: Из массива удалить все элементы, которые меньше 0.

Рассмотрим два решения этой задачи.

Алгоритм первого решения:

1. Просматриваем массив .

2. Если элемент<0, то удаляем его и n уменьшаем.

3. Если элемент>=0, то переходим к следующему.

Фрагмент программы:

… {

в

цикле просматриваем элементы массива}

i:=1;

while i<=n do

begin

{проверяем ,не нужно ли i-ый элемент удалять}

if A[i]<0 then

begin

{если нужно – удаляем i-ый элемент}

for j:=i to n-1 do {сдвигаем}

A[j]:=A[j+1];

Dec(n); {уменьшаем количество элементов}

end

else Inc(i); {если удалять не нужно, то переходим

к следующему элементу}

end;

Пример прогона алгоритма:

Исходный массив:

0: i=1, n=6: -1 -2 2 -3 -4 3

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

массива:

1: i=1, n=5: -2 2 -3 -4 3 (удален -1)

2: i=1, n=4: 2 -3 -4 3 (удален -2)

3: i=2, n=4: 2 -1 -2 3 (перешли на следующий)

4: i=2, n=3: 2 -4 3 (удален -3)

5: i=2, n=2: 2 3 (удален -4)

6: i=3, n=2: 2 3 (перешли на следующий)

Алгоритм второго решения:

1. Счетчик переписанных элементов k=0.

2. Просматриваем элементы массива.

3. Если элемент A[i] не меньше 0, k увеличиваем на 1 и

переписываем элемент A[i] на k-ое место.

4. После просмотра всего массива количество переписанных

элементов k заносим в n.

Фрагмент программы:

Var {дополнительные переменные}

k:IndexEl; {количество переписанных элементов}

…

Begin

...

{1 - переписанных элементов пока не было}

k:=0;

{2 - в цикле просматриваем элементы массива}

for i:=1 to n do

{3 - если A[i] не <0}

if not(A[i]<0) then

begin

Inc(k); {увеличиваем значение k на 1}

A[k]:=A[i]; {переписываем i-ый элемент в позицию k}

end;

{4 - в массиве оставляем k элементов}

n:=k;

Пример прогона алгоритма:

Исходный массив: -1 -2 2 -3 -4 3

Состояния массива после просмотра очередного элемента

массива:

0: k=0, i=1, n=6: -1 -2 2 -3 -4 3 {не переписываем}

1: k=0, i=2, n=6; -1 -2 2 -3 -4 3 {не переписываем}

2: k=1, i=3, n=6; 2 -2 2 -3 -4 3 {переписываем

a[1]:=a[3]}

3: k=1, i=4, n=6; 2 -2 2 -3 -4 3 {не переписываем}

4: k=1, i=5, n=6; 2 -2 2 -3 -4 3 {не переписываем}

5: k=2, i=6, n=6; 2 3 2 -3 -4 3 {переписываем

a[2]:=a[6]}

6: k=2, i=7, n=6: 2 3 2 -3 -4 3 {выход из цикла}

7: n=2: 2 3 {значение k переписываем в n}