mp1

6. Дана матрица А и вектор X соответствующих размерностей. Нечетные строки матрицы заменить элементами вектора X.

#include <iostream> using namespace std;

int ** creat(int &n, int &m)

{cout « " n - c i n » n ; cout <<"m="; cin » m ; int **mas=new int *[n];

for (int i=0; i<n; ++i) mas[i]=new int [m]; for (int i=0; i<n; ++i)

for (int j=0; j<m; ++j) {cout«"m asf «i«"]["«j<<"]="; cin»mas[i][j];} return mas;}

int main()

{cout «"n="; cin » n ; cout <<"m="; cin » m ; int **a=creat(n, m);

int *b=new int [m]; //создаем массив b

for (int i=0;i<m; ++i) cin»b[i]; //заполняем массив b

for (int i=1 ;i<n; i+=2) //каждую нечетную строку массива а заменяем на массив Ь

7. Даны две матрицы Ат хПи B„,v соответствующих размерностей, элементами кото­ рых являются целые числа. Найти произведение этих матриц.

Указания по решению задачи. Операция произведения двух матриц определена только для матриц соответствующих размерностей Л„,„, и В„„. то есть количество столбцов первой матрицы должно совпадать с количеством строк второй. В качестве результата операции получается матри­ ца С„„г = Атт* В„„.. Как видим, количество строк матрицы С совпадает с количеством строк мат­ рицы А , а количество столбцов матрицы С равно количеству столбцов матрицы В. Каждый эле-

л

мент искомой матрицы С определяется по формуле с [ /,/] = ]Г а [/, &] * 6 [£ ,у ], где индекс / при-

*=!

нимает значения от 1 до т, а индексj - от 1 до v.

#include <iostream> using namespace std;

int ** creat(int &n, int &m)

{cout « ”n - '; cin » n ; cout «"m="; cin » m ; int **mas=new int *[n];

for (int i=0; i<n;++i) mas[i]=new int [m]; for (int i=0; i<n; ++i)

81

for (int j=0; j<m; ++j){cout<<"mas["<<i«"]["«j«"]="; cin»mas[i][j],} return mas;}

/*функция в качестве р е зу ль та та возвращает произведение двух матриц или NULL, если таков произведение вычислить невозможно'/

int **mu!t(int "a , int па, int т а , int **b, int nb, int mb)

{if (ma!=nb) return NULL; //если размерности матриц не совпадают, т о возвращается О else {int "c=new int '[па],//иначе создается матрица размерностью па строк и

for (int i=0; i<na;++i) c[i]=new int [mb]; //mb столбцов

for (int i=0; i<na;++i) //выполняем подсчет произведения матриц for (int j=0; j<mb;++j)

{с[Ш=0;

for (int k=0; k<ma;k++) c[i][j]+=a[i][k]*b[k][j];}

return с ;} //в качестве ре зульта та возвращаем матрицу с

}

//функция выводит двумерную матрицу на экран в виде таблицы void print (int **mas, int n, int m)

{for (int i=0; i<n; \++, cout«endl)

for (int j=0; j<m; j++) cout«m as[i]0]«"\t";}

//функция освобождает память, выделенную под параметр массив void deleteMas(int *'mas, int n)

{for (int i=0;i<n, i++) delete [) mas[i]; delete [] m as;}

int main()

{int па, та , nb,mb;

int **a=creat(na,ma); //создаем и заполняем матрицу а int **b=creat(nb, mb); //создаем и заполняем матрицу b

int *’c=mult(a, па,та, b, nb,mb); //вычисляем произведение матриц а и b

if (с) print (с,па,mb) ;//если указатель с не пустой, т о выводим на экран матрицу с else cout « " к данным матрицам операция неприменима, не совпадает размерность"; //освобождаем память, выделенную под динамические массивы

deleteMas(a, па); deleteMas(b, nb); de!eteMas(c, па); return 0;}

Замечание. Обратите внимание на то, что использование вспомогательных функций повы­ шает читаемость программы. Поэтому если вы видите, что один и тот же фрагмент программы бу­ дет выполняться несколько раз, то оформите его в виде функции.

6.7. Вставка и удаление элементов в массивах

При объявлении массива мы определяем его максимальную размерность, ко­ торая в дальнейшем изменена быть не может. Однако с помощью вспомогательной переменной можно контролировать текущее количество элементов, которое не мо­ жет быть больше максимального.

82

Пример. Рассмотрим фрагмент программы:

int*a=newint [10]; int n=5;

for (int i=0; i<5;i++) a[i]:=i*i;

В этом случае массив можно представить следующим образом:

Так как во время описания был определен массив из 10 элементов, а заполне­ но только первые 5, то оставшиеся элементы будут заполнены случайными числами.

Что значит удалить из одномерного массива элемент с номером 3? Удаление должно привести к физическому «уничтожению» элемента с номером 3 из массива, при этом общее количество элементов должно быть уменьшено. В этом понимании удаления элемента итоговый массив должен выглядеть следующем образом

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

Однако «удаление» можно смоделировать сдвигом элементов влево и умень­ шением значения переменной, которая отвечает за текущее количество элементов в массиве, на единицу:

В общем случае, если мы хотим удалить элемент массива с номером к (всего в массиве п элементов, а последний элемент имеет индекс п-1), то нам необходимо произвести сдвиг элементов, начиная с к+ /-го на одну позицию влево. Т.е. на к-ое место поставить к + 1-й элемент, на место к+1 - к+2-й элемент, ..., на место п-2 - п-1 -й элемент. После чего значение п уменьшить на 1. В этом случае размерность массива не изменится, изменится лишь текущее количество элементов, и у нас соз­ дастся ощущение, что элемент с номером к удален. Рассмотрим данный алгоритм на примере:

#include <iostream> using namespace std; int main()

{int n; cout«"n="; cin»n; //ввели размерность массива int ’a=new int [n]; //создали и заполнили массив

for (int i=0; i<n;i++) {cout«"a["«i«"]="; cin>>a[i];}

int k; cout«"k="; cin»k; //ввели номер удаляемого элемента

if (k<0 || k>n-1) / / если номер отрицательны й или больше номера последнего элемента, cout«"error"; //то выводим сообщение об ошибке, иначе

else {for (int i=k; i<n-1;i++) a[i]=a[i+1]; //выполняем сдвиг элементов массива

п~; //уменьшаем текущую размерность массива

for (int i=0; i<n;i++) cout«a[i]«"\t";} //выводим измененный массив на экран return 0;}

83

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

#include <iostream> using namespace std;

//функция создает и замолняем двумерный массив int ** creat(int &n, int &m)

{cout «"n="; cin » n ; cout « " m - c i n » m ; int **mas=new int *[n];

for (int i=0; i<n;++i) mas[i]=new int |m]; for (int i=0; i<n; ++i)

for (int j=0; j<m, ++j){cout<<"mas["«i«"]["<<j<<"]="; cin>>mas[i][j]1} return mas;}

//функция выводит двумерную матрицу на экран в виде таблицы void print (int **mas, int n, int m)

{ for (int i=0; i<n; i++, cout<<endl)

for (int j=0; j<m; j++) cout<<mas[i]0]«"\t";}

//функция освобождает память, выделенную под параметр массив void deleteMas(int **mas, int n)

{for (int i=0;i<n; i++) delete [] mas[i]; delete [] m as;}

int mainQ {int n, m, k;

int **a=creat(n,m);

print(a,n,m); //выводим первоначальный массив cout«"k="; cin»k; //вводим номер строки для удаления

if (k<0 || k>n-1) cout«"error", Лесли номер строки отрицательный или больше номера последнего элемента, то выводим сообщение об ошибке*/

else {delete [] a[k]; //освобождаем память, выделенную для k-ой строки массива for (int i=k; i<n-1; ++i)a[i]=a[i+1]; //переадресуем указатели, начиная с k-ой строки a[n-1]=NULL; //указатель на п-1 строку обнуляем

~п; //уменьшаем текущ ее количество строк print(a,n,m); //выводим измененный массив

}

deleteMas(a, п); //освобождаем память return 0;}

Однако, т.к. у нас нет указателей на столбцы массива, сдвиг столбцов нужно будет проводить поэлементно.

#include <iostream> using namespace std;

84

int ** creat(int &n, int &m)

{cout «"n="; cin » n ; cout «"m="; cin » m ; int **mas=new int *[n];

for (int i=0; i<n;++i) mas[i]=new int [m]; for (int i=0; i<n; ++i)

for (int j=0; j<m; ++j){cout«"mas["«i<<"]["<<j«"]="; cin»mas[i][j];}

for( int i=0; i<n; ++i)a[i)[j]=a[i]0+1);

-m; //уменьшаем текущее количество столбцов в массиве print(a,n,m);} //выводим измененный массив

deleteMas(a, п); return 0;}

Вернемся к массиву, определенному в самом первом примере. И подумаем те­ перь, что значит добавить элемент в одномерный массив в позицию с номером к? В

этом случае все элементы, начиная с к-ого, должны быть сдвинуты вправо на одну позицию. Однако сдвиг нужно начинать с конца, т.е. на первом шаге на n-е место поставить n-1-ый элемент, потом на n -1-oe место поставить п-2-й элемент, ..., нако­ нец, на к+1 место вставить к-й элемент. Таким образом, копия k-го элемента будет на к+1-м месте и на к-е место можно поставить новый элемент. Затем необходимо увеличить текущее количество элементов на 1.

Рассмотрим массив из примера 1 и в качестве к зададим значение равное 3. В этом случае массив будет выглядеть следующим образом:

Теперь в позицию с номером 3 можно поместить новое значение. А текущее количество элементов в массиве становится равным 6. Подумайте, почему сдвиг нужно выполнять с конца массива, а не с начала, как мы это делали в случае удале­ ния элемента из массива.

Рассмотрим программную реализацию данного алгоритма: ^include <iostream>

85

using namespace sld; int main()

ность массива станет больше допустимой, то выдаем сообщение об ошибке, иначе */ else { int х; cout«"x="; cin>>x; //вводим значение для вставки

for (int i=n; i>k;i—) a[i]=a[i-1]; //выполняем сдвиг в массиве

а[к]=х; //записываем в позицию к значение х п++; //увеличиваем текущую размерность массива

for (int i=0; i<n;i++) cout<<afi}<<"\t";} //выводим измененный массив return 0;

}

Теперь рассмотрим добавление столбца в двумерный массив. Для этого все столбцы после столбца с номером к передвигаем на 1 столбец вправо. Затем увели­ чиваем количество столбцов на 1. После этого копия столбца с номером к будет на­ ходиться в столбце с номером к+1. И, следовательно, к-ый столбец можно запол­ нить новыми значениями. Рассмотрим программную реачизацию алгоритма:

#include <iostream> using namespace std;

int ** creat(int &n, int &m)

{cout «"n="; cin » n ; cout «"m =”; cin »m ; int **mas=new int *[n];

for (int i=0; i<n;++i) mas[i]=new int [2*m],//определили максимальную количество столбцов for (int i=0; i<n; ++i)

for (int j=0; j<m; ++j){cout<<"mas["«i«"]["«j«"]="; cin»mas[i][j];} return mas;}

void print (int **mas, int n, int m) { for (int i=0; i<n; i++, cout«endl)

for (int j=0; j<m; j++) cout«mas[i][j]«"\t";}

void deleteMas(int **mas, int n) {for (int i=0;i<n; i++) delete [] mas[i]; delete [] m as;}

int main() {int n, m, k;

int **a=creat(n,m); //создаем и заполняем матрицу а

int m2=2*m; //т- текущее количество столбцов, m2 -максимально возможное print(a,n,m); //выводим первоначальный массив

c o u t« “k="; cin»k; //вводим номер столбца для добавления

if (к<0 || к>т-1 ||т + 1> т 2) cout«"error"; /*есло введенный номер столбца

отрицательный или больше номера последного значимого столбца в массиве, или после вставки столбца размерность массива станет больше допустимой, то выдаем сообщение об ошибке, '/

else {for (int j=m; j>k; --j) //иначе выполняем поэлементный сдвиг столбцов

for( int i=0; i<n; ++i)a[i][j]=a[i][j-1];

++m; //увеличиваем текущее количество столбцов в массиве

86

for (int i=0; i<n; ++i) //вводим новые данные в к-ый столбец

{cout «"a["«i<<"]["«k«"]="; cin»a[i][k];} print(a,n,m);,.} //выводим измененный массив

deleteMas(a, n); return 0;}

Аналогичным образом можно провести вставку новой строки в двумерный массив. Однако, если вспомнить, что двумерный массив - это одномерный массив указателей на одномерные массивы, например, целых чисел, то поэлементный сдвиг строк можно заменить на сдвиг указателей.

#include <iostream> using namespace std;

int ** creat(int &n, int &m)

{cout <<"n="; cin >>n; cout <<"m="; cin » m ;

int **mas=new int *[2*n]; //определяем максимальное количество строк for (int i=0; i<n;++i) mas[i]=new int [m];

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

for (int j=0; j<m; ++j){cout«"mas["«i«"]["«j«"]="; cin»mas[i][j];} return mas;}

void print (int **mas, int n, int m) {for (int i=0; i<n; i++, cout«endl)

for (int j=0; j<m; j++) cout<<mas[i][j)«"\t";}

void deleteMas(int **mas, int n)

{for (int i=0;i<n; i++) delete [] mas[i]; delete [] m as;}

int main() {int n, m, k;

int **a=creat(n,m); //создаем и заполняем матрицу а

int n2=2*n; //п- текущее количество строк, п2 -максимально возможное print(a,n,m); //выводим первоначальный массив

cout«''k="; cin»k; //вводим номер строки для добавления if (k<0 || k>n-1 ||n+1>n2) cout«"error”;

else {for (int i=n; i>k; -i) a[i]=a[i-1]; //выполняем сдвиг строк

++n; //увеличиваем текущее количество строк в массиве

a[k]=new int [m); //выделяем память под новую строку массива и заполняем ее for (int j=0; j<m; ++j) {cout «"a["<<k<<")["<<j<<"]="; cin»a[k][j];}

print(a,n,m);} //выводим измененный массив deleteMas(a, n);

return 0;}

87

6.8.Упражнения

I.Дана последовательность целых чисел.

Замечание. Задачи из данного пункта решить двумя способами, используя одномерный массив, а затем двумерный.

1.Заменить все положительные элементы противоположными им числами.

2.Заменить все элементы, меньшие заданного числа, этим числом.

3.Заменить все элементы, попадающие в интервал [а. Ь], нулем.

4.Заменить все отрицательные элементы, не кратные 3, противоположными им числами.

5.Все элементы, меньшие заданного числа, увеличить в два раза.

6. Подсчитать среднее арифметическое элементов.

7. Подсчитать среднее арифметическое отрицательных элементов.

8. Подсчитать количество нечетных элементов.

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

Ю.Подсчитать сумму элементов, кратных 9.

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

13.Вывести на экран номера всех элементов больших заданного числа. 14.Вывести на экран номера всех нечетных элементов.

15.Вывести на экран номера всех элементов, которые не делятся на 7.

16.Вывести на экран номера всех элементов, не попадающих в заданный интервал. 17.Определить, является ли произведение элементов трехзначным числом. 18.Определить, является ли сумма элементов двухзначным числом.

19.Вывести на экран элементы с четными индексами (для двумерного массива - сумма индексов должны быть четной).

20.Вывести на экран положительные элементы с нечетными индексами (для дву­ мерного массива - первый индекс должен быть нечетным).

II. Дана последовательность из п действительных чисел.

Замечание. Задачи из данного пункта решить, используя одномерный массив.

1.Подсчитать количество максимальных элементов.

2.Вывести на экран номера всех минимальных элементов.

3.Заменить все максимальные элементы нулями.

4.Заменить все минимальные элементы на противоположные.

5.Поменять местами максимальный элемент и первый.

6. Вывести на экран номера всех элементов, не совпадающих с максимальным. 7. Найти номер первого минимального элемента.

8. Найти номер последнего максимального элемента.

88

9.Подсчитать сумму элементов, расположенных между максимальным и мини­ мальным элементами (минимальный и максимальный элементы в массиве един­

ственные). Если максимальный элемент встречается позже минимального, то вы­ дать сообщение об этом.

10.Найти номер первого максимального элемента.

11.Найти номер последнего минимального элемента.

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

И.Поменять местами первый минимальный и последний максимальный элементы. 14.Найти максимум из отрицательных элементов.

15.Найти минимум из положительных элементов.

16.Найти максимум из модулей элементов.

17.Найти количество пар соседних элементов, разность между которыми равна за­ данному числу.

18.Подсчитать количество элементов, значения которых больше значения предыду­ щего элемента.

19.Найти количество пар соседних элементов, в которых предыдущий элемент кра­ тен последующему.

20.Найти количество пар соседних элементов, в которых предыдущий элемент меньше последующего.

III. Дан массив размером п*п (если не оговорено иначе), элементы которого целые числа.

1.Подсчитать среднее арифметическое нечетных элементов, расположенных выше главной диагонали.

2.Подсчитать среднее арифметическое четных элементов, расположенных ниже главной диагонали.

3.Подсчитать сумму элементов, расположенных на побочной диагонали.

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

5.Подсчитать среднее арифметическое элементов, расположенных под побочной диагональю.

6. Поменять местами столбцы по правилу: первый с последним, второй с предпо­ следним и т.д.

7.Поменять местами две средних строки, если количество строк четное, и первую со средней строкой, если количество строк нечетное.

8.Поменять местами два средних столбца, если количество столбцов четное, и пер­ вый со средним столбцом, если количество столбцов нечетное.

9.Если количество строк в массиве четное, то поменять строки местами по прави­ лу: первую строку со второй, третью - с четвертой и т.д. Если количество строк в массиве нечетное, то оставить массив без изменений.

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

столбцов в массиве нечетное, то оставить массив без изменений. 11.Вычислить А”, где п - натуральное число.

89

12. Подсчитать норму матрицы по формуле ||Л| = ] £ т а х а ; .

15.Выяснить, является ли матрица симметричной относительно главной диагонали. 16.Заполнить матрицу числами от 1 до п (где n=mxk, a m - количесто строк, а к

количество столбцов прямоугольной матрицы) следующим образом:

П П

17.Определить, есть ли в данном массиве строка, состоящая только из положитель­ ных элементов.

18.Определить, есть ли в данном массиве столбец, состоящий только из отрицатель­ ных элементов.

19.В каждой строке найти максимум и заменить его на противоположный элемент. 20.В каждом столбце найти минимум и заменить его нулем.

IV. Дан массив размером п*п, элементы которого целые числа.

1.Найти максимальный элемент в каждой строке и записать данные в новый мас­ сив.

2.Найти минимальный элемент в каждом столбце и записать данные в новый мас­ сив.

3.Четные столбцы таблицы заменить на вектор X.

4.Нечетные строки таблицы заменить на вектор X.

5. Вычислить А*Х, где А - двумерная матрица, X - вектор.

6. Для каждой строки подсчитать количество положительных элементов и записать данные в новый массив.

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

8.Для каждого столбца подсчитать сумму четных положительных элементов и за­ писать данные в новый массив.

9.Для каждой строки подсчитать количество элементов, больших заданного числа,

и записать данные в новый массив.

10.Для каждого столбца найти первый положительный элемент и записать данные в новый массив.

11.Для каждой строки найти последний четный элемент и записать данные в новый массив.

12.Для каждого столбца найти номер последнего нечетного элемента и записать данные в новый массив.

13.Для каждой строки найти номер первого отрицательного элемента и записать данные в новый массив.

14.Для каждой строки найти сумму элементов с номерами от kl до к2 и записать данные в новый массив.

15.Для каждого столбца найти произведение элементов с номерами от kl до к2 и за­ писать данные в новый массив.

90