Основные алгоритмы преобразования одномерных массивов

Алгоритм удаления элемента из массива

Блок-схема алгоритма удаления элемента с номером M из массива A, в котором N элементов выглядит следующим образом:

Соответствующий фрагмент текста программы на языке C++:

for (i=M;i<N–1;i++) A[i]=A[i+1];

N= N–1;

Алгоритм удаления из массива серии элементов с заданными номерами

Блок-схема алгоритма удаления серии элементов с номерами от M1 до M2 из массива A, в котором N элементов, выглядит следующим образом:

Соответствующий фрагмент текста программы на языке C++:

k=M2-M1+1;

for (i=M1;i<N–k:i++) A[i]=A[i+k];

N= N–k;

Алгоритм удаления из массива элементов с заданным значением

Блок-схема алгоритма удаления всех элементов, равных заданному значению X, из массива A, в котором N элементов, выглядит следующим образом:

Соответствующий фрагмент текста программы на языке С++:

i=1;

while (i<N)

{

if (A[i]==X)

{

for (j=i;j<N-1;j++) A[j]=A[j+1];

N=N-1;

}

else i=i+1;

}

Алгоритм копирования элементов массива в новый массив

Блок-схема алгоритма копирования элементов, удовлетворяющих заданному условию (в данном случае – элементов, значение которых больше, чем X), из массива A, в котором N элементов, в массив B выглядит следующим образом:

В результате массив B будет содержать K элементов.

Соответствующий фрагмент текста программы на языке C++:

K=0;

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

{

if (A[i]>X)

{

B[K]=A[i];

K=K+1;

}

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

Блок-схема алгоритма вставки элемента с номером M, равного X, в массив A, который содержит N элементов, выглядит следующим образом:

Соответствующий фрагмент текста программы на языке С++:

N=N+1;

for (i=N-1;i>M;i--) A[i]=A[i-1];

A[M]=X;

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

Блок-схема алгоритма упорядочения по возрастанию элементов массива A, состоящего из N элементов, методом «пузырька» выглядит следующим образом:

Соответствующий фрагмент текста программы на языке C++:

for (i=1;i<N;i++)

for (j=1;j<=N-i;j++)

if (A[j-1] > A[j])

{

P=A[j];

A[j]=A[j-1];

A[j-1]=P;

}

Алгоритм упорядочения элементов массива по убыванию отличается только знаком в условии сравнения соседних элементов, в этом случае необходимо проверять A_j < A_j₊₁.

Алгоритм вставки элемента в упорядоченный массив

Блок-схема алгоритма вставки элемента, равного X, в упорядоченный массив A, который содержит N элементов, без нарушения упорядоченности массива выглядит следующим образом:

Соответствующий фрагмент текста программы на языке C++:

if (X>=A[N-1]) A[N]=X;

else {

K=0;

while (X>A[K])K=K+1;

for (i=N-1;i>=K;i--) A[i+1]=A[i];

A[K]=X;

}

N=N+1;

6.1.2 Пример составления алгоритма и программы на языке C++ для преобразования одномерного массива.

Задание: Дан массив действительных чисел F₁,...,F₄₀. Упорядочить в нем по возрастанию элементы, которые находятся между максимальным и минимальным элементами.

Решение.

Для работы с массивом F сначала необходимо сформировать его элементы. Выполним формирование элементов массива с помощью генератора случайных чисел rand(). Для обозначения размерности массива F введем переменную N. В цикле сразу после формирования элемента массива выполним вывод его на экран.

Далее в одном цикле выполним поиск максимального и минимального элементов массива Fmax и Fmin и их номеров nmax и nmin. Затем определим, какой из номеров меньше: nmax или nmin, меньший из номеров запомним в переменной k1, больший – в переменной k2. После этого упорядочим по возрастанию элементы от k1 до k2 по аналогии с сортировкой элементов массива от 1-го до N-го. При упорядочении элементов массива необходимо организовать 2 цикла. Внешний цикл всегда организовывается, начиная с 1 и выполняется число раз, на единицу меньшее количества сортируемых элементов (в случае сортировки всего массива из N элементов внешний цикл организовывался от 1 до N – 1). В данном случае необходимо упорядочить (k2 – k1 + 1) элементов. Поэтому внешний цикл необходимо организовать от 1 до k2 – k1. В качестве переменной внешнего цикла будем использовать переменную i. Поскольку необходимо упорядочить элементы с номерами от k1 до k2, внутренний цикл организуем, начиная с k1 до k2 – i (в случае сортировки всего массива из N элементов внутренний цикл организовывался от 1 до N – i). В качестве переменной внутреннего цикла будем использовать переменную j.

После упорядочения преобразованный массив F выведем на экран.

Блок-схема алгоритма решения данной задачи выглядит следующим образом:

Текст программы на языке C++ выглядит следующим образом:

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

int main()

{ float F[40],Fmax,Fmin,P;

int i,j,k1,k2,nmin,nmax,N;

clrscr();

randomize();

N=40;

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

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

{

F[i]=100.0*rand()/RAND_MAX-50;

printf("%8.2f",F[i]);

}

Fmax=-10000;

Fmin=10000;

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

{

if (F[i]>Fmax)

{

Fmax=F[i];

nmax=i;

}

if (F[i]<Fmin)

{

Fmin=F[i];

nmin=i;

}

printf("\n\nМаксимальный элемент номер %d равен %.2f",nmax,Fmax);

printf("\n Минимальный элемент номер %d равен %.2f",nmin,Fmin);

if (nmax>nmin)

{

k1=nmin;

k2=nmax;

}

else {

k2=nmin;

k1=nmax;

}

for (i=1;i<=k2-k1;i++)

for (j=k1;j<=k2-i;j++)

if (F[j]>F[j+1])

{

P=F[j];

F[j]=F[j+1];

F[j+1]=P;

}

printf("\nРезультат:\n");

for (i=0;i<N;i++) printf("%8.2f",F[i]);

getch();

return 0;

}

Результаты работы программы:

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

-47.34 0.30 -31.91 -17.82 38.40 7.93 -45.38 4.23 -6.69 28.25

23.55 35.54 19.14 11.13 18.54 -12.78 -34.82 42.40 -19.17 22.95

35.96 -41.60 48.42 -26.81 24.89 37.18 23.42 -37.94 20.87 -49.13

-20.49 -43.66 -15.52 13.65 31.19 -4.16 40.86 9.40 36.95 14.62

Максимальный элемент номер 22 равен 48.42

Минимальный элемент номер 29 равен -49.13

Результат:

-47.34 0.30 -31.91 -17.82 38.40 7.93 -45.38 4.23 -6.69 28.25

23.55 35.54 19.14 11.13 18.54 -12.78 -34.82 42.40 -19.17 22.95

35.96 -41.60 -49.13 -37.94 -26.81 20.87 23.42 24.89 37.18 48.42

-20.49 -43.66 -15.52 13.65 31.19 -4.16 40.86 9.40 36.95 14.62

Из результатов работы программы видно, что в преобразованном массиве элементы, начиная с 22 по 29, упорядочены по возрастанию.

Практическая часть

6.2.1 Требования к выполнению работы:

Составить блок-схему алгоритма и программу для решения индивидуального задания.

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

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

Порядок выполнения работы.

1. Выполнить анализ задания, сформулировать постановку задачи.

2. Составить блок-схему алгоритма.

3. Составить программу на языке C++. Предусмотреть ввод исходных данных и вывод результатов на экран.

4. Выполнить проверку работоспособности программы на различных исходных данных.

5. Выполнить анализ полученных результатов.

Варианты индивидуальных заданий.

Варианты индивидуальных заданий выбираются из таблицы 6 в соответствии с номером студента в списке группы в журнале преподавателя.

Таблица 6. Варианты индивидуальных заданий

№ п/п	Задание

	Дан массив действительных чисел Z₁,...,Z₂₀. Заменить в массиве все отрицательные элементы их модулями и упорядочить массив по возрастанию.
	Задан массив действительных чисел A₁,...,A₄₀. Вставить в него элемент, равный минимальному, слева от максимального элемента. Если максимальным является первый элемент, то вставку элемента выполнить справа.
	Задан массив целых чисел d₁,...,d₂₅. Вставить в него элемент, равный максимальному, справа от последнего отрицательного элемента.
	Задан массив действительных чисел a₁,...a₃₀. Удалить из массива элементы, значения которых находятся в интервале [ ; ].
	Задан массив целых чисел b₁,...,b₄₀. Удалить из него все элементы, которые находятся между максимальным и минимальным элементами.

	Дан массив действительных чисел a₁,...,a₅₀. Удалить из него элемент, значение которого повторяется наибольшее количество раз.
	Дан массив действительных чисел Z₁,...,Z₂₀. Получить новый массив Y из тех элементов массива Z, значение которых больше (max+min)/2.
	Задан массив целых чисел d₁,...,d₃₀. Удалить из него элементы, равные максимальному элементу.
	Задан массив действительных чисел a₁,...a₃₀. Получить новый массив x из тех элементов массива a, которые расположены между элементами с минимальным и максимальным значениями.
	Задан массив действительных чисел b₁,...b₃₀. Удалить из него элементы, расположенные между первым и последним нулевыми элементами.
	Задан массив целых чисел b₁,...,b₃₀. Выполнить сортировку первых 15 элементов массива по возрастанию, а последних 15 элементов – по убыванию.
	Дан массив действительных чисел P₁,...,P₂₀. Вставить в каждую четную позицию массива элемент, равный предыдущему.
	Дан массив X₁,...,X₃₀. Удалить из него те элементы, которые меньше (min+max)/2.
	Задан массив действительных чисел b₁,...,b₄₀. Удалить из него все элементы, которые находятся до максимального элемента.
	Дан массив целых чисел D₁,...,D₃₀. Удалить из него те элементы, которые больше среднего арифметического.
	Дан массив действительных чисел f₁,...,f₄₀. Удалить из него те элементы, которые равны минимальному элементу.
	Задан массив целых чисел с₁,...,с₂₀. Вставить в него нулевые элементы справа и слева от максимального элемента.
	Задан массив действительных чисел C₁,...,C₃₅. Найти и удалить из него самую длинную возрастающую последовательность элементов.
	Задан массив действительных чисел R₁,...,R₄₀. Упорядочить его по возрастанию и выполнить вставку элемента, равного , не нарушив упорядоченности массива.
	Задан массив действительных чисел B₁,...,B₂₀. Получить новый массив С₁,...,C₂₀, четные элементы которого равны соответствующим элементам массива B, а нечетные равны сумме элементов массива B.
	Дан массив действительных чисел a₁,...,a₄₀. Удалить из него элементы, расположенные до первого нулевого элемента.


	Задан массив целых чисел a₁,...a₃₀. Заменить в массиве каждый нулевой элемент на собственный индекс и упорядочить массив по убыванию.
	Дан массив целых чисел a₁,...,a₄₀. Получить новый массив z из всех элементов исходного массива, кроме элементов с максимальным и минимальным значениями.
	Дан массив действительных чисел f₁,...,f₄₀. Удалить из него те элементы, которые равны минимальному элементу.
	Задан массив целых чисел с₁,...,с₄₀. Найти в нем максимальный элемент и его номер и выполнить сортировку по возрастанию элементов массива, которые находятся до максимального элемента.
	Дан массив действительных чисел P₁,...,P₂₀. Вставить в каждую четную позицию массива элемент, равный предыдущему.
	Задан массив действительных чисел k₁,...,k₄₅. Найти в нем минимальный элемент и его номер и упорядочить по убыванию элементы массива, которые находятся после минимального.