Задача 34. Вставка элемента в массив

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

Для того, чтобы в массив из n элементов вставить новый элемент перед элементом массива x с номером k, необходимо выполнить следующие действия: первые k-1 элементов массива оставить без изменения, а все элементы, начиная с k -го до n -го необходимо сдвинуть на одну позицию вправо. Причём сдвиг элементов надо начинать с конца, чтобы при сдвиге не потерять (не затереть) элементы. Для этого используется цикл, в котором управляющая переменная изменяется от большего значения к меньшему с отрицательным шагом -1. Затем на место элемента с номером k записать необходимое значение.

В задачах, где необходимо вставить в массив новый элемент следует учесть, что количество элементов массива после вставки будет на один элемент больше, т.е. если в исходном массиве было n элементов, то при объявлении массива в программе нужно предусмотреть место для n+1 элемента.

Количество элементов массива n и сам массив x – исходные данные в этой задаче. Например, пусть n =6, а элементы массива имеют значения: 9, 3, 8, 4, 7, 2. Нужно выделить переменную, в которую следует помесить сумму 1-го и последнего элементов массива s= x [1]+ x [6]. При таких данных s= 11. Таким образом, после элемента с номером 2 надо вставить значение 11. Для того, чтобы вставить элемент со значением 11 перед третьим элементом массива, организуем цикл с отрицательным шагом i=6, 3, -1 для перемещения элементов вправо. В цикле будем на i +1 место записывать i-й элемент массива (x [ i +1]= x [ i ]). Так на первом шаге при i =6 на 7 -ое место в массиве встанет 6-ой элемент 2, при i =5 на 6-ое место встанет 5-й элемент 7 и т.д. Таким образом, после сдвига получим массив: 9, 3, 8, 8, 4, 7, 2. Теперь в элемент массива с номером 3 запишем 11(x [3])=s). Измененный массив теперь будет иметь значения: 9, 3, 11, 8, 4, 7, 2. Размер массива станет на 1 больше.

Заметим, что если бы сдвиг элементов производился слева направо в цикле i=3,6, то при i=3 на 4-е место попадет значение 3-го элемента 8, а прежнее значение 4-го элемента пропадёт, затем при i=4 на 5-е место попадет значение 4-го элемента, а оно теперь равно 8, и т.д. Тогда после сдвига элементов массив теперь будет содержать значения 9, 3, 8, 8, 8, 8, 8, что, конечно, будет неправильно.

Следовательно, для решения задачи потребуется следующая последовательность действий. С клавиатуры вводится количество элементов массива n и массив х. В программной реализации при объявлении массива надо учесть, что при решении задачи количество элементов массива будет увеличено на 1. В переменную s записывается сумма первого и последнего элементов массива s=x[1]+x[ n ]. Для того, чтобы вставить элемент, равный s, в массив, необходимо предусмотреть место для нового элемента, т. е. раздвинутьмассив. Первые два элемента по условию задачи должны остаться без изменения, а остальные элементы, начиная с 3-его надо сдвинуть на одну позицию вправо. Для этого организуется цикл i=n,3,-1, в котором управляющая переменная i изменяется от n до 3 с отрицательным шагом -1. В теле цикла для каждого значения i выполняется оператор x[i+1]=x[i], в результате которого происходит перестановка (сдвиг) элементов. После завершения цикла на место 3-го элемента массива записывается значение суммы первого и последнего элементов x [3]= s. Т.к. размер массива после вставки увеличился на единицу, то значение n изменяется n=n+1. В заключение полученный массив выводится на экран.

Структурированная запись алгоритма 34

1. Ввод количества элементов массива n и значений элементов массива x

2. В переменную s записывается сумма первого и последнего элементов массива s=x[1]+x[ n ]

3. В цикле для i=n, 3, -1 повторять

3.1. Сдвиг элементов x[i+1]=x[i]

4. На место 3-го элемента массива записывается новое значение x [3]= s

5. n=n+1

6. Вывод массива

Схема алгоритма

Программа на языке Си

#include <stdio.h>

#define N 20

int main()

{

int i,n,s,x[N];

printf("n=");

scanf("%d",&n);

printf("\n Введите массив \n");

for(i=0;i<n;i++)

scanf("%d",&x[i]);

printf("Исходный массив \n");

for(i=0;i<n;i++)

printf("%d ",x[i]);

s=x[0]+x[n-1];

for(i=n-1;i>=2;i--)

  x[i+1]=x[i];

x[2]=s;

printf("\n Новый массив \n");

n++;

for(i=0;i<n;i++)

printf("%d ",x[i]);

return 0;

}

Программа на языке Паскаль

Program main_34;

Var

x: array [1..20] of integer;

i,n,s:integer;

begin

writeln('n=');

readln(n);

writeln('Введите массив');

for i:=1 to n do readln (x[i]);

writeln('Исходный массив');

for i:=1 to n do write(x[i]:3,' ');

writeln;

s:=x[1]+x[n];

for i:=n downto 3 do x[i+1]:=x[i];

x[3]:=s;

n:=n+1;

writeln('Новый массив');

for i:=1 to n do write(x[i]:3,' ');

end.

Программа на языке Фортран

Program main_34

Implicit none

integer, allocatable::x(:)

integer i,n,s

print*,'n='

 read*,n

 allocate(x(n+1))

 print*,'Введите массив'

 read*,(x(i), i=1, n)

 print *,'Исходный массив',(x(i),i=1,n)

 s=x(1)+x(n)

 do i=n,3,-1

x(i+1)=x(i)

 enddo

 x(3)=s

 n=n+1

 print *,'Новый массив ',x

 deallocate (x)

end program main_34

Программа на языке Python

print("Введите N -- число элементов массива: ")

n=int(input())                                  

x = [] # Создаем пустой список

for i in range(1,n+1): # i = 1,..., N -- всего N

print("Введите {0}-й элемент массива: ".format(i))

x.append(float(input()))

print("Исходный массив ")

for i in range(0, n):

print("A[{0}]={1}".format(i+1, x[i]))

s = x[0] + x[n-1] # В алгоритме s = x(1) + x(n)

# но в Python списки индексируются с 0

x.append(0.0) # добавляем в список еще один элемент,

for i in range(n-1, 1, -1):

# i = n-1,..., 2 -- 2 - индекс третьего элемента

x[i + 1] = x[i]

x[2] = s

n = n + 1

print("Новый массив ")

for i in range(0, n):

print("A[{0}]={1}".format(i+1, x[i]))

Программа в системе Матлаб

n=input('введите n=');

for i=1:n

X(i)=input('X(i)=');

End

Disp('исходный массив’)

Disp(X)

s=X(1)+X(n);

for i=n:-1:3 

X(i+1)=X(i);

end

X(3)=s;

n=n+1;

disp('Измененный массив');

for i=1:n

disp(X(i));

end