Классы задач по обработке массивов

1.6.1 Задачи 1-ого класса

К задачам 1 класса относятся задачи, в которых выполняется однотипная обработка всех или указанных элементов массива. Решение таких задач сводится к установлению того, как обрабатывается каждый элемент массива или указанные элементы, затем подбирается подходящая схема перебора, в которую вставляются операторы обработки элементов массива. Примером такой задачи является нахождение максимального элемента массива или среднего арифметического массива.

// описание массива ………… // ввод массива ………… int Sum=0; for (i=0; i<n; i++) Sum+=a[i]; cout<<”Среднее арифметическое = ”<<Sum/n”; }

 

1.6.2 Задачи 2-ого класса

К задачам 2 класса относятся задачи, в которых изменяется порядок следования элементов массива. Обмен элементов внутри массива выполняется с использованием вспомогательной переменной:

int R=a[I];a[I]=a[J]; a[J]:=R; // обмен a[I] и a[J] элементов массива

Пример 1.Перевернуть массив. //формирование массива for(int i=0,j=n-1;i<j;i++,j--) {int r=a[i]; a[i]=a[j]; a[j]=r;} //вывод массива   Пример 2.Поменять местами пары элементов в массиве: 1 и 2, 3 и 4, и т. д. for(int i=0;i<n-1;i+=2) {int r=a[i]; a[i]=a[i+1]; a[i+1]=r;}   Пример 3.Циклически сдвинуть массив на к элементов влево (вправо). int k,i,t,r; cout<<"K=";cin>>k; for(t=0;t<k;t++) { r=a[0]; for(int i=0;i<n-1;i++) a[i]=a[i+1]; a[n-1]=r; }

1.6.3 Задачи 3-ого класса

К задачам 3 класса относятся задачи, в которых выполняется обработка нескольких массивов или подмассивов одного массива. Массивы могут обрабатываться по одной схеме – синхронная обработка или по разным схемам – асинхронная обработка массивов.

Пример 1. Заданы два массива из n целых элементов. Получить массив c, где c[i]=a[i]+b[i]. for (int i=0; i<n; i++) c[i] = a[i] + b[i];   Пример 2. В массиве целых чисел все отрицательные элементы перенести в начало массива. int b[10]; //вспомогательный массив int i,j=0; for(i=0;i<n;i++) if(a[i]<0){b[j]=a[i];j ++;} //переписываем из а в b все отрицательные элементы for(i=0;i<n;i++) if(a[i]>=0){b[j]=a[i];j++;} // переписываем из а в b все положительные элементы for(i=0;i<n;i++) cout<<b[I]<<” “;   Пример 3.Удалить из массива все четные числа. int b[10]; int i,j=0; for(i=0;i<n;i++) if(a[i]%2!=0){b[j]=a[i];j++;}   for(i=0;i<j;i++) cout<<b[i]<<" "; cout<<"\n";

1.6.4 Задачи 4-ого класса

К задачам 4 класса относятся задачи, в которых требуется отыскать первый элемент массива, совпадающий с заданным значением – поисковые задачи в массиве. Для этого требуется организовать перебор массива и проверку условия. Но при этом существует две возможности выхода из цикла:

· нужный элемент найден;

· элемент не найден, но просмотр массива закончен.

Пример1. Найти первое вхождение элемента К в массив целых чисел. int k; cout<<"K=?";cin>>k; int ok=0; //признак найден элемент или нет int i, nom; for(i=0;i<n;i++) if(a[i]==k){ok=1; nom=i; break;} if(ok==1) cout<<"nom="<<nom; else cout<<"\nthere is no such element!";

1.7 Работа с массивами в С++. Примеры

Пример 1. Ввести вещественный массив и вычислить среднее значение.

#include ”iostream” using namespace std; void main() {const int n=10; int i; double A[n],SA;   //ввод массива cout<<”Vvesti elementi massiva:”; for(i=0; i<n; i++) { сout<<”A[“<<i<<”]=”; cin>>A[i]; }   SA=0;   for(i=0; i<n; i++) SA=SA+A[i]; // вычисление суммы элементов массива SA=SA/n;   сout<<”Среднее значение = ”<<SA; }

Пример 2. Составить программу нахождения минимального элемента линейной таблицы. Выдать на экран значение и номер этого элемента.

#include ”iostream” using namespace std; void main() {const int n=10; int i; int A[n],nomer, min;   //ввод массива cout<<”Vvesti elementi massiva:”; for(i=0; i<n; i++) { сout<<”A[“<<i<<”]=”; cin>>A[i]; }   min = A[0]; for(i=1; i<n; i++) if (A[i]<min){ min = A[i]; nomer = i;}   сout<<”Minimalnij element = ”<<min<<endl; сout<<”Nomer elementa = ”<<nomer<<endl; }

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

#include ”iostream” #include <iomanip.h> using namespace std; void main() {const int n=12; int i, j; int A[n];   // ввод массива cout<<”Vvesti elementi massiva:”<<endl; for(i=0; i<n; i++) { сout<<”A[“<<i<<”]=”; cin>>A[i]; } cout<<”Element”<<setw(13)<<”Znachenie”<<setw(17)<<”Bar graph”<<endl;   for(i=0; i<n; i++) {cout<<setw(7)<<i<<setw(13)<<A[i]<<” ”; for(j=1; j<=A[i]; j++) cout<<”*”; // печать строки cout<<endl; } } Результат выполнения программы: Vvesti elementi massiva: 12 3 25 7 11 5 14 4 16 2 19 3 Element Znachenie Bar graph 0 12 ************ 1 3 *** 2 25 ************************* 3 7 ******* 4 11 *********** 5 5 ***** 6 14 ************** 7 4 **** 8 16 **************** 9 2 ** 10 19 ****************** 11 3 ***

Пример 4. Составить программу, позволяющую в заданной линейной таблице посчитать число отрицательных, нулевых и положительных элементов.

#include ”iostream” using namespace std; void main() {const int n=10; int i; int A[n], kol_pol, kol_otr, kol_num;   // ввод массива cout<<”Vvesti elementi massiva:”; for(i=0; i<n; i++) { сout<<”A[“<<i<<”]=”; cin>>A[i]; }   kol_pol = kol_otr = kol_nul = 0;   // подсчет нулевых элементов for(i=1; i<n; i++) if (A[i]==0){ kol_nul = kol_nul + 1; } cout<<”Kolichestvo nulevih elimentov = ”<< kol_nul<<endl;   // подсчет отрицательных элементов for(i=1; i<n; i++) if (A[i]<0){ kol_otr = kol_otr + 1; } cout<<”Kolichestvo otricatelnih elimentov = ”<< kol_otr<<endl;   // подсчет положительных элементов for(i=1; i<n; i++) if (A[i]>0){ kol_pol = kol_pol + 1; } cout<<”Kolichestvo polojitelnih elimentov = ”<< kol_pol<<endl; }

Пример 5. Дан массив из 10 элементов; увеличить элементы с 3 по 7 элемент на 5. Четные элементы заменить на противоположные по знаку. Вывести новый массив на экран.

#include ”iostream” using namespace std; void main() { int i; int A[10];   // ввод массива cout<<”Vvesti elementi massiva:”; for(i=0; i<10; i++) { сout<<”A[“<<i<<”]=”; cin>>A[i]; }   // перебираем элементы с номером от 2 до 6 и прибавляем к ним 5 for(i=2; i<7; i++) A[i] = A[i] + 5;   // четные элементы меняем на противоположные по знаку for(i=0; i<10; i++) if (A[i]%2==0) A[i]= - A[i];   // вывод измененного массива for(i=0; i<10; i++) сout<<”A[“<<i<<”]<<A[i]<<endl; }

Пример 6. Сортировка массива пузырьковым методом.

Задача сортировки пузырьковым методом (с англ. bubble sorting) состоит в изменении порядка элементов таким образом, чтобы они находились в порядке убывания. Алгоритм пузырьковой сортировки решает эту задачу, выполняя серии проходов внутри последовательности. При каждом проходе элементы просматриваются в направлении увеличения разряда, от разряда 0 до конца последовательности. В каждой позиции элемент сравнивается с соседним элементом, и если их порядок неверен (т.е. предыдущий элемент больше последующего), эти элементы меняются местами.

#include ”iostream” #include <iomanip.h> using namespace std; void main() {const int n = 10; int A[n]={9, - 6, 89, 4, 7, - 4, 95, 2, 3, 12}; int t;   // элементы в исходном порядке cout<<”Elements in the initial order:”<<endl; for(int i=0; i<n; i++) сout<< setw(5) << A[i];   for(int pass=n-1; pass>1; pass--) for(i=0; i<pass; i++) if (A[i]>A[i+1]) {t = A[i]; A[i] = A[i+1]; A[i+1] = t; } // элементы массива в порядке возрастания cout<<endl<<”Elements in the ascending order:”<<endl;   for(int i=0; i<n; i++) сout<< setw(5) << A[i]; cout<<endl; } Результат выполнения программы: Elements in the initial order: 9 -6 89 4 7 -4 95 2 3 12 Elements in the ascending order: -6 -4 2 3 4 7 9 12 89 95

Пример 7. Вычислить количество положительных элементов между минимальным и максимальным элементами массива.

#include ”iostream” using namespace std; void main() {const int n = 10; int a[n]={1, 3, -9, -5, 1, -2, 1, -3, 8, 4}; int i, imax, imin, kol;   for(i = imax = imin = 0; i<n; i++) {if (a[i]>a[imax]) imax=i; if (a[i]<a[imin]) imin=i;}   cout<<”max = ” << a[imax] << “ min = “ << a[imin] << endl;   int ibeg = imax < imin? imax: imin; int iend = imax < imin? imin: imax; cout<<”ibeg = ” << ibeg << “ iend = “ << iend << endl;   for(kol = 0; i = ibeg + 1; i < iend; i++) if (a[i]>0) kol++; cout<<endl<<”The number of positive elements:” << kol<<endl; } Результат выполнения программы: max = 8 min = - 9 ibeg = 2 iend = 8 The number of positive elements: 2

Пример 8. В одномерном массиве A размерностью n, вычислить среднее геометрическое ненулевых элементов массива.

Решение. Среднее геометрическое k элементов массива – это корень степени k из произведения этих элементов. Таким образом, сначала необходимо вычислить произведение Р ненулевых элементов массива и их количество k, а затем среднее геометрическое Sg по формуле: .

Например, если элементы массива равны A= {1, 0, 2, 4, 0}, то P = 8, k = 3,

Графическая схема алгоритма решения задачи изображена на рис. 2. В приведенном алгоритме в цикле по i ( блоки 5 – 9) помимо вычисления произведения вычисляется и количество ненулевых элементов массива. После цикла с помощью ветвления, проверяется, есть ли в массиве ненулевые элементы (k>0 – условие наличия в массиве ненулевых элементов), в этом случае вычисляется и выводится среднее геометрическое. В противном случае выводится сообщение " В массиве все элементы равны нулю ". В программе переменные Р и Sg имеют вещественный тип двойной точности (double), т.к. произведение вещественных чисел может быть очень большим числом.

Используемые переменные: n – число элементов массива; a[] – статический массив; P – произведение не нулевых элементов массива; k – количество не нулевых элементов массива; Sg – среднее геометрическое элементов массива; i – параметр цикла;   Рис. 2 #include ”iostream” using namespace std; void main() {const int n = 10; float a[n]; int n, i, k; double P, Sg; cout<<”Vvesti elementi massiva:”; for(i=0; i<n; i++) { сout<<”A[“<<i<<”]=”; cin>>A[i]; }   P=1; k=0; for(i=0;i<n;i++) if(a[i]!=0) {P*=a[i]; k++;} сout<<”P=”<<P<<” ”<<”k=”<<k<<endl;   if(k>0) { if(P>0) Sg=pow(P,1.0/k); else Sg= –pow(fabs(P),1.0/k); cout <<"Среднее геометрическое ненулевых элементов массива = ”<< Sg; } else cout<<"В массиве все элементы равны нулю! "; }

Пример 9. Даны два одномерных массива X и Y. Необходимо сформировать массив Z из положительных элементов массива X стоящих на четных местах и элементов массива Y больших первого элемента массива X.

Решение. Если число элементов массива X – n, а массива Y – m, то с учетом того, что из первого массива выбираются элементы стоящие только на четных местах, максимальное число элементов в новом массиве Z может достигать m+n/2 элементов. Поэтому для массива Z с помощью оператора динамического выделения памяти (new) выделим m+[n/2] ячейки памяти ([n/2] – целая часть от деления). Начальное значение счетчика элементов нового массива k принимается равным нулю.

При обработке массива X необходимо проверять только элементы, стоящие на четных местах, т.е. параметр цикла i изменяется от 1 до n с шагом 2. Условие отбора элементов из первого массива X[i]>0. При обработке массива Y учитываются все его элементы, т.е. параметр цикла i изменяется от 0 до m с шагом 1. Условие отбора элементов из второго массива – Y[i]> X[0].

Описанный алгоритм формирования нового массива и программа представлены на рис. 3.

Используемые переменные: x[] – статический (исходный) массив; n – число элементов массива X; y[] – статический (исходный) массив; m – число элементов массива; z[] – динамический (формируемый) массив k – счетчик элементов нового массива Z; i – параметр цикла;     Рис. 3   #include ”iostream” using namespace std; void main() {const int n = 10, m = 8; int k, i, x[n], y[m];   cout<<”Vvesti elementi massiva X:”; for(i=0; i<n; i++) { сout<<”x[“<<i<<”]=”; cin>>x[i]; }   cout<<”Vvesti elementi massiva Y:”; for(i=0; i<m; i++) { сout<<”y[“<<i<<”]=”; cin>>y[i]; } int *z=new int[15]; // выделение памяти под массив Z k=0; for(i=1;i<n;i+=2) { if(x[i]>0) { z[k]=x[i]; k++; } } for(i=0;i<m;i++) { if(y[i]>x[0]) { z[k]=y[i]; k++; } } if(k==0) cout<<"Массив Z не сформирован.”; else { cout<<"Массив Z:"; for(i=0;i<k;i++) cout << z[i] << endl; } delete[] z; // освобождение памяти }

Пример 10. Написать программу, прибавляющую единицу ко всем элементам двумерного массива.

#include ”iostream” using namespace std; void main() {int i, j; int A[5][5];   //ввод двумерного массива cout<<”Vvesti jlementi massiva:”; for(i=0; i<5; i++) for(j=0; j<5; j++) { сout<<”A[“<<i<<”][“<<j<<”]=”; cin>>A[i][j]; }   for(i=0; i<5; i++) for(j=0; j<5; j++) A[i][j]=A[i][j]+1;//прибавляем 1 к элементу массива   //вывод массива for(i=0; i<5; i++) for(j=0; j<5; j++) { сout<<”A[“<<i<<”][“<<j<<”]=”<<A[i][j]; }

Пример 11. Определить среднее арифметическое элементов целочисленной матрицы размером и количество положительных элементов в каждой строке.

#include ”iostream” #include <iomanip.h> using namespace std; void main() {const int m = 4, n = 6; int a[m][n]; int i,j, int kol;   // ввод элементов cout<<”Vvesti elementi massiva:”<< endl; for(i=0; i<m; i++) for(j=0; j<n; j++) cin>>a[i][j];   // вывод элементов в виде таблицы for(i=0; i<m; i++) {for(j=0; j<n; j++) cout<< setw(4) << a[i][j] << “ ”; cout<< endl;}   float S = 0;   for(i=0; i<m; i++) {kol = 0; for(j=0; j<n; j++) {S += a[i][j]; if (a[i][j] > 0) kol++; } cout<<”String: “ << i <<” Number: “ << kol << endl; } s/= m*n; cout << “Srednee arifmeticheckoe: ” << S << endl;} Результат выполнения программы: Vvesti elementi massiva: 5 -3 0 4 6 2 0 7 -5 -8 1 0 -1 0 3 0 -5 0 1 1 -3 8 0 1   -3             -5 -8     -1       -5       -3       String: 0 Number: 4 String: 1 Number: 2 String: 2 Number: 1 String: 3 Number: 4 Srednee arifmeticheckoe: 0.583333

Пример 13.Заполнить двумерный массив размером следующим образом:

#include ”iostream” using namespace std; void main() { int a[4][4]; int i,j; for(i=0; i<4; i++) for(j=0; j<4; j++) if (i = = j) a[i][j] = 1; else a[i][j] = 0;   for(i=0; i<4; i++) {for(j=0; j<4; j++) cout<< a[i][j]; cout<< endl;} }