1й курс / Konspekt_lektsiy_Informatika_6

1

Тема №7. ПРОГРАММИРОВАНИЕ НА С++. ОБРАБОТКА ОДНОМЕРНЫХ МАССИВОВ

7.1. Описание одномерных массивов

Массив – это последовательность однотипных элементов, каждый из которых имеет одно и тоже имя, но однозначно определяется своим номером(индексом). Массив – это не скалярная величина, а структурированный тип данных.

Обычно используются одномерные (вектор) и двумерные (матрица) массивы. В одномерном массиве каждый элемент имеет один индекс, определяющий положение элемента в массиве. Соответственно в двумерном массиве каждый элемент имеет два индекса.

Например, массив Х, состоящий из N элементов:

Основными характеристиками массива являются:

–размерность – количество элементов в массиве;

–значения и тип элементов массива.

Структура описания массива в С++:

тип имя_массива [размерность];

Размерность массива и тип его элементов определяют объем памяти, который необхо-

дим для хранения массива. Размерность – это целое положительное число или константа.

1-й способ описания массива(размерность задается целым положительным числом). Например:

int X[10]; //Описан массив X – 10 целых элементов

float a[20]; //Описан массив a – 20 вещественных элементов

2-й способ описания массива (размерность задается целочисленной константой). Напри-

мер:

const int N=15; //Описана целочисленная константа

double B[N]; //Описан массив B – 15 вещественных элементов

Нумерация элементов массива в С++ начинается с нуля. Например:

char C[5]; //Описан массив С из 5 символов, нумерация элементов от 0 до 4

7.2. Принципы обработки массивов

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

имя_массива [индекс]

Например:

const int N=15; double C[N],S; S=C[0]+C[N-1];

Недопустимо обращение к несуществующему элементу массива, например, C[15], C[N]. Элементам массива можно присвоить начальные значения(инициализировать) следую-

щим образом:

тип имя_мас[размер]={знач_0, знач_1, …};

Например, формируется массив из шести вещественных чисел, значения элементам присваиваются по порядку:

float a[6]={1.2,(float)3/4,5./6,6.1};

ÓЕфименко К.Н.

2

Элементы значения, которых не указаны, обнуляются; для элементов a[1] и a[2] выполняется преобразование типов. В результате получим массив

a[0]=1.2,

a[1]=(float)3/4=0.75,

a[2]=5./6=0.83333,

a[3]=6.1,

a[4]=0,

a[5]=0.

Обработка массива обычно заключается в последовательном переборе его элементов и выполнении над ними однотипных операций, т.е. обработка массива является циклическим вычислительным процессом. Для этого достаточно организовать цикл по перебору индексов элементов массива от 0 до N-1 (N – размерность массива). Наиболее рационально для этой цели использовать цикл «Для» на основе блока модификации. В общем виде алгоритм обработки одномерного массива выглядит следующим образом:

Цикл «Для» на основе блока модификации по перебору элементов одномерного массива работает следующим образом:

При входе в блок модификации(линия 1) автоматически выполняются следующие действия. Параметру цикла i присваивается начальное значение 0 (i=0) и проверяется, не превышает ли оно конечного значения N (i < N). Если результатом проверки условия является true, то происходит переход к выполнению тела цикла (линия 2). В теле цикла выполняется обработка i-го элемента массива. После этого осуществляется возврат в блок модификации(линия 3), увеличение параметра цикла i на значение шага 1 (i++) и проверка условия продолжения цикла(i < N) и т.д. Когда текущее значение параметра циклаi превысит конечное значениеN–1, цикл завершит свою работу (линия 4).

В цикле происходит последовательное обращение к нулевому, первому, второму и т.д. элементам. Таким образом, за один шаг цикла обрабатывается один элемент массива.

Соответствующий этой структуре оператор С++ имеет вид:

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

{

операторы_тела_цикла;

}

Если тело цикла состоит более чем из одного оператора, то используется составной опе-

ратор {}.

Оператор цикла с параметром for работает аналогично циклу «Для» на основе блока модификации.

7.3. Ввод-вывод элементов массива

Ввод элементов массива выполняется в два этапа. Вначале вводится размерность массива N, а затем в цикле вводятся значения для каждого элемента массива.

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

ÓЕфименко К.Н.

3

Ввод N

i=0; i<N; i++

Ввод Xi

Варианты ввода одномерного массива:

Вариант 1. Ввод массива с помощью функции scanf. int main()

{int i,N; float X[10];

//Ввод размерности массива N printf("\n N="); scanf("%d",&N); //Ввод элементов массива X в цикле

for(i=0; i<N; i++) {printf("X[%d]=",i); scanf("%f",&X[i]); }

}

Вариант 2. Ввод массива с помощью оператора cin. int main()

{int i,N; float X[10];

//Ввод размерности массива N cout<<"\n N="; cin>>N; //Ввод элементов массива X в цикле for(i=0; i<N; i++)

{cout<<"X["<<i<<"]="; cin>>X[i]; }

}

Например, так будет выглядеть процесс ввода элементов массива Х размерностью 4.

Вывод массива также выполняется поэлементно с помощью цикла «Для».

Алгоритм вывода одномерного массива:

i=0; i<N; i++

Вывод Xi

ÓЕфименко К.Н.

4

Варианты вывода одномерного массива:

Вариант 1. Вывод массива в виде строки. for(i=0; i<N; i++)

printf("%f \t",X[i]); printf("\n");

for (i=0; i<N; i++) cout<<"X["<<i<<"]="<<X[i]<<"\t";

cout <<endl;

Вариант 2. Вывод массива в виде столбца. for(i=0; i<N; i++)

printf("%f \n",X[i]);

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

cout <<"X["<<i<<"]="<<X[i]<<endl;

Результаты вывода элементов массива в строку и в столбец:

7.4.Типовые действия над массивами

7.4.1.Вычисление суммы и количества элементов массива

Пример 7.1. Дан вещественный массив X[N]. Найти сумму элементов массива и количество элементов, превышающих среднее арифметическое элементов массива.

Блок-схема алгоритма:

ÓЕфименко К.Н.

5

Описание работы алгоритма.

Вводится размерность массива (блок 2). Задаются начальные значения для переменных,

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

Спомощью блока модификации (блок 4) организовывается цикл по перебору элементов массива (блоки 4-6 – тело цикла). На каждом шаге цикла вводится значениеi-го элемента массива Х (блок 5), которое затем добавляется к сумме S (блок 6). Таким образом, в результате первого перебора элементов массива(блоки 4-6) будет сформирован массив Х и вычислена сумма значений его элементов S, на основе которой будут вычислено среднее арифметическое элементов массива (блок 7).

Спомощью блока модификации (блок 8) организовывается цикл по перебору элементов массива Х (блоки 8-10 – тело цикла). На каждом шаге цикла, если текущий элемент массива Xi превышает среднее арифметическое значение S (блок-9), то такой элемент учитывается в количестве k (блок 10). После завершения второго перебора элементов массива Х выводится среднее арифметическое элементов массива и количество элементов превышающих S (блок 11).

Программа на С++ int main()

{float X[100], S; int i,k,N;

cout<<"\nInput N="; cin>>N; S=0; k=0;

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

{cout<<"X["<<i<<"]="; cin>>X[i]; S+=X[i];

}

S/=N;

for(i=0; i<N; i++) if (X[i]>S) k++;

cout<<"S="<<S<<"\t k="<<k<<endl; }

7.4.2. Вычисление произведения элементов массива

Пример 7.2. Дан вещественный массив X[N]. Найти произведение отличных от нуля эле-

Ввод N

P = 1

i=0; i<N; i++

Ввод Xi

Вывод P

–

Xi ≠ 0

КОНЕЦ

+

P = P × Xi

ÓЕфименко К.Н.

7

(блок 9), вычисляется произведение положительных элементов массива Y (блоки 10-11). На 3-м этапе (блоки 12-14) перебираются элементы массивов Х и Y, и определяется количество точек с координатами (xi , yi), расположенных в I квадранте.

Текст программы:

#include <iostream> #include <math.h> int main()

{

float x[100], y[100], S, P; int i, N, k;

cout<<"\nInput N="; cin>>N; for(i=0; i<N; i++)

{ cout<<"X["<<i<<"]="; cin>>x[i]; } cout<<endl;

S=0; P=1; k=0; for(i=0; i<N; i++)

{

y[i]=sin(x[i])+0.1*exp(x[i]);

cout<<"Y["<<i<<"]="<<y[i]<<"\t";

S=S+y[i];

if (y[i]>0) P*=y[i];

}

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

if (x[i]>0 && y[i]>0) k++; cout<<"S="<<S<<endl; cout<<"P="<<P<<endl; cout<<"k="<<k<<endl; }

7.4.3. Поиск максимального элемента массива

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

ÓЕфименко К.Н.

8

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

if (X[i]>X[imax]) imax=i; else if (X[i]<X[imin]) imin=i;

cout<<"Max=X["<<imax<<"]="<<X[imax]<<endl;

cout<<"Min=X["<<imin<<"]="<<X[imin]<<endl;

7.4.4. Сортировка элементов массива

Под сортировкой элементов массива понимается упорядочение элементов массива в по-

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

Для этого необходимо организовать два вложенных цикла. Внешний цикл будет перебирать элементы, начиная с 0-го и до предпоследнего, и выбирать так называемый«главный» элемент. Внутренний цикл будет перебирать элементы, начиная со следующего после текущего «главного» и до последнего и сравнивать их.

Пусть массив Х состоит из четырех элементов {5; 7; 3; 2}. Пошаговое выполнение внутреннего цикла, при выбранном в качестве «главного» 0-го, а затем 1-го элементов массива, приведено ниже:

ÓЕфименко К.Н.

9

for(j=i+1; j<N; j++) if (X[i]>X[j])

{ a=X[i]; X[i]=X[j]; X[j]=a; }

ÓЕфименко К.Н.