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

 

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

 

Блок-схема алгоритма удаления элемента с номером 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+1.

 

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

 

Блок-схема алгоритма вставки элемента, равного 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. Варианты индивидуальных заданий

№ п/п	Задание
	Дан массив действительных чисел Z1,...,Z20. Заменить в массиве все отрицательные элементы их модулями и упорядочить массив по возрастанию.
	Задан массив действительных чисел A1,...,A40. Вставить в него элемент, равный минимальному, слева от максимального элемента. Если максимальным является первый элемент, то вставку элемента выполнить справа.
	Задан массив целых чисел d1,...,d25. Вставить в него элемент, равный максимальному, справа от последнего отрицательного элемента.
	Задан массив действительных чисел a1,...a30. Удалить из массива элементы, значения которых находятся в интервале [ ; ].
	Задан массив целых чисел b1,...,b40. Удалить из него все элементы, которые находятся между максимальным и минимальным элементами.
	Дан массив действительных чисел a1,...,a50. Удалить из него элемент, значение которого повторяется наибольшее количество раз.
	Дан массив действительных чисел Z1,...,Z20. Получить новый массив Y из тех элементов массива Z, значение которых больше (max+min)/2.
	Задан массив целых чисел d1,...,d30. Удалить из него элементы, равные максимальному элементу.
	Задан массив действительных чисел a1,...a30. Получить новый массив x из тех элементов массива a, которые расположены между элементами с минимальным и максимальным значениями.
	Задан массив действительных чисел b1,...b30. Удалить из него элементы, расположенные между первым и последним нулевыми элементами.
	Задан массив целых чисел b1,...,b30. Выполнить сортировку первых 15 элементов массива по возрастанию, а последних 15 элементов – по убыванию.
	Дан массив действительных чисел P1,...,P20. Вставить в каждую четную позицию массива элемент, равный предыдущему.
	Дан массив X1,...,X30. Удалить из него те элементы, которые меньше (min+max)/2.
	Задан массив действительных чисел b1,...,b40. Удалить из него все элементы, которые находятся до максимального элемента.
	Дан массив целых чисел D1,...,D30. Удалить из него те элементы, которые больше среднего арифметического.
	Дан массив действительных чисел f1,...,f40. Удалить из него те элементы, которые равны минимальному элементу.
	Задан массив целых чисел с1,...,с20. Вставить в него нулевые элементы справа и слева от максимального элемента.
	Задан массив действительных чисел C1,...,C35. Найти и удалить из него самую длинную возрастающую последовательность элементов.
	Задан массив действительных чисел R1,...,R40. Упорядочить его по возрастанию и выполнить вставку элемента, равного , не нарушив упорядоченности массива.
	Задан массив действительных чисел B1,...,B20. Получить новый массив С1,...,C20, четные элементы которого равны соответствующим элементам массива B, а нечетные равны сумме элементов массива B.
	Дан массив действительных чисел a1,...,a40. Удалить из него элементы, расположенные до первого нулевого элемента.

	Задан массив целых чисел a1,...a30. Заменить в массиве каждый нулевой элемент на собственный индекс и упорядочить массив по убыванию.
	Дан массив целых чисел a1,...,a40. Получить новый массив z из всех элементов исходного массива, кроме элементов с максимальным и минимальным значениями.
	Дан массив действительных чисел f1,...,f40. Удалить из него те элементы, которые равны минимальному элементу.
	Задан массив целых чисел с1,...,с40. Найти в нем максимальный элемент и его номер и выполнить сортировку по возрастанию элементов массива, которые находятся до максимального элемента.
	Дан массив действительных чисел P1,...,P20. Вставить в каждую четную позицию массива элемент, равный предыдущему.
	Задан массив действительных чисел k1,...,k45. Найти в нем минимальный элемент и его номер и упорядочить по убыванию элементы массива, которые находятся после минимального.

6.3 Контрольные вопросы и практические задания:

 

1. Приведите варианты ввода численных значений элементов массива.

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

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

4. Приведите алгоритмы вставки элементов в массив.

5. Приведите алгоритмы упорядочения элементов массива по возрастанию.

6. Приведите алгоритмы упорядочения элементов массива по убыванию.

7. Приведите алгоритмы копирования элементов массива в новый массив.