Рекурсивные функции для массивов

1.

Рекурсивные функции для
массивов
1

2.

• тестирование на двух массивах
int a1[]={1,2,3,4,5,6};
Текст слайда
int a2[] = {1, 9, 2, 8, 3, 7, 4, 6, 0};
//a1[6]
//a2[9]
2

3.

Сумма элементов массива
int summa (const int* a, int n)
{
if (n==0) return 0;
return summa(a, n-1)+ a[n-1];
}
cout<<summa(a1,6)<<endl;
cout<<summa(a2,9)<<endl;
cout<<summa(a1,3)<<endl;
cout<<sums(a1+3,3)<<endl;
3

4.

Для диапазона
int summa( const int*bg, const int*end)
{
if ( bg == end) return 0;
return summa(bg+1,end) + *bg;
}
cout<<summa(a1,a1+6)<<endl;
cout<<summa(a1,&a1[6])<<endl;
cout<<summa(a2+3,a2+9)<<endl;
cout<<summa(a1+2,a1+2)<<endl;
4

5.

Условие на элемент
inline bool IsEven(int x) { return x % 2 == 0; }
inline bool IsOdd(int x) { return x% 2 != 0; }
inline bool IsNul(int x) { return x == 0; }
inline bool IsPositive(int x) { return x > 0; }

6.

Условие на элемент
int kol (const int *a, int n, bool (*cond)(int))
{
if ( n==0 ) return 0;
return cond(a[n-1]) + kol(a,n-1, cond);
}
Примеры вызовов:
cout<<"count of Positive = "<<kol(a1,6,IsPositive)<<endl;
cout <<"count of Odd="<<kol(a2,9,IsOdd)<<endl;
6

7.

Для диапазона
int kol (const int *bg, const int* end, bool (*cond)(int))
{
if (bg==end) return 0;
return cond(*bg) + kol(bg+1,end, cond);
}
cout << kol (a1, a1+6)<<endl;
cout << kol (a2,a2+9)<<endl;
7

8.

Максимум/минимум
int max(const int* a, int n)
{
if ( n==1 ) return a[0];
int m = max(a,n-1);
return a[n-1]>m ? a[n-1] : m;
}
// return a[n-1]> max(a,n-1) ? a[n-1] : max(a,n-1); ПЛОХО!!!
cout<<max(a1,6)<<endl;
cout<<max(a2,9)<<endl;
8

9.

Для диапазона
int max (const int* bg, const int * end)
{
if (bg+1 == end) return *bg;
int m = max(bg+1,end);
return *bg > mТекст
? *bg
: m;
слайда
}
cout << max(a1, a1+6)<<endl;
cout << max (a2, a2+9)<<endl;
cout << max (a2+4, a2+9)<<endl;
cout << max (a2+8, a2+9)<<endl;
9

10.

Матрицы

11.

67
Лекция #4. Двумерные статические массивы
Двумерные статические массивы
Двумерный массив — это одномерный массив одномерных массивов
<тип> <имя> [<размерность1>][<размерность2>];
// объявление двумерного массива:
int a[3][4];
// объявление и инициализация двумерного массива:
int b[2][3] = { { 1, 2, 3 },{ 4, 5, 6 } };
//возможно
int m[][4]={{1,2,3,4},{5,6,7,8},{9,0,1,2}};
a[0][0]
a[0][1]
a[0][2]
a[0][3]
a[1][0]
a[1][1]
a[1][2]
a[1][3]
a[2][0]
a[2][1]
a[2][2]
a[1][2]
11

12.

68
Лекция #4. Двумерные статические массивы
Двумерные статические массивы
#include <iostream>
#include <iomanip>
using namespace std;
void main() {
// объявление и инициализация двумерного массива:
int a[2][3] = { { 1, 2, 3 },{ 11, 22, 33 } };
// строки
for (int i = 0; i < 2; i++)
{
// столбцы
for (int j = 0; j < 3; j++)// переключение по столбцам
cout << setw(4)<<right<<a[i][j];
cout << endl;
}
}
12

13.

69
Лекция #4. Двумерные статические массивы
Двумерные статические массивы. Расположение в памяти
Для двумерного массива выделяется единый блок памяти необходимого
размера:
размер_массива1 * размер_массива2 * sizeof(тип_элемента_массива))
• Значения располагаются последовательно.
• Самый левый индекс изменяется медленнее всего.
• Имя (идентификатор) двумерного массива является указателем на
первый элемент массива
13

14.

72
Лекция #4. Двумерные статические массивы
Двумерные статические массивы. Передача в функцию
const unsigned int max_ROWS = 10;
const unsigned int max_COLS = 10;
void func(int arr[max_ROWS][max_COLS],int rows,int cols) { ... } // (1)
//
//
При передаче многомерного массива в функцию можно
не указывать длину самого левого измерения.
void func(int arr[][max_COLS], int rows,int cols) { ... } // (2)
14

15.

73
Лекция #4. Двумерные статические массивы
Двумерные статические массивы. Передача в функцию
#include <iostream>
#include <iomanip>
using namespace std;
// Максимальное количество строк
const unsigned int max_ROWS = 10;
Пример 1
// Максимальное количество столбцов
const unsigned int max_COLS = 10;
void printArr(int a[max_ROWS][max_COLS], int rows, int cols) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++)
cout << setw(4) << right << a[i][j];
cout << endl;
}}
void main() {
int a[max_ROWS][max_COLS]={{1, 2, 3},{ 4, 5, 6 },{7, 8, 9} };
int rows = 3, cols = 3; // размеры самой матрицы
printArr(a,rows,cols);
}
15

16.

74
Лекция #4. Двумерные статические массивы
Двумерные статические массивы. Передача в функцию
#include <iostream>
#include <iomanip>
using namespace std;
// Максимальное количество строк
const unsigned int D1 = 2;
// Максимальное количество столбцов
const unsigned int D2 = 3;
Пример 2
// Результат
// 10 20 30
// 111 220 330
// ... код для printArr
void changeArr(int a[][D2],int rows, int cols) {
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
a[i][j]*=10;
}
void main() {
int a[][D2] = { { 1, 2, 3 },{ 11, 22, 33 } };
changeArr(a);
printArr(a);
}
16

17.

75
Лекция #4. Определение типов
Определение типов
17

18.

76
Лекция #4. Определение типов
Определение типов
Синонимы (псевдонимы)типов определяются с помощью typedef
typedef тип новое_имя[размерность];
typedef int matrixInt[D1][D2]; // matrixInt имя типа
// Использование matrixInt
// Объявление переменной matrixInt a будет заменено на int a[D1][D2]
void printArr(matrixInt a, int m, int n);
18

19.

77
Лекция #4. Определение типов
Определение типов
#include <iostream>
#include <iomanip>
using namespace std;
const unsigned int D1 = 2;
const unsigned int D2 = 3;
Пример. matrixInt
typedef int matrixInt[2][3]; // matrixInt имя типа
void printArr(matrixInt a, int D1, int D2) {
for (int i = 0; i < D1; i++) {
for (int j = 0; j < D2; j++)
cout << setw(4) << right << a[i][j];
cout << endl;}}
void main() {
matrixInt a = { { 1, 2, 3 },{ 11, 22, 33 } };
printArr(a, D1, D2);
}
19

20.

Подсчет количества строк матрицы, содержащих нули
int kol_zeros(const matrix m, const uint rows, const uint cols)
{int k=0;
for (uint i = 0; i < rows; ++i)
for (uint j = 0; j < cols; ++j){
if (m[i][j]==0) {k++; break;}
}
return k;
}

21.

Проверка, что массив содержит нули
bool is_zeros(const int *a, const uint len)
{
for (uint i = 0; i < len; ++i) {
if (a[i]==0)
return true;
}
return false;
}
Подсчет количества строк матрицы, содержащих нули
int zero_row(const matrix m, const uint rows, const uint cols)
{int k=0;
for (int i = 0; i < rows; ++i) {
// Строки матрицы располагаются в памяти линейно,
// их можно обрабатывать как отдельный массив
if (is_zeros(&m[i][0], cols))
k++;
}
return k;
}

22.

Матрицы в динамической памяти
int **a;
// определение n – количества строк
a=new int *[n];
// определение m – количества столбцов
for (int i=0; i<n; i++)
a[i]=new int[m];
22

23.

a
23

24.

Удаление матрицы
for ( int i=0; i<n; i++)
delete []a[i];
delete []a;
24

25.

Параметры
void print (const int **p, int n, int m)
{
for (int i=0; i<n; ++i)
{
for (int j=0; j<m; ++j)
cout<< p[i][j]<<" ";
cout<<endl;
}
}
25

26.

Функции для создания матрицы
void create(int **& a,int n, int m){
a=new int *[n];
for (int i=0; i<n; ++i)
a[i]=new int[m];
}
Использование
int **matr;
int n;
cin>>n;
create(matr,n,n);
26

27.

Функции для создания матрицы
int ** create(int n, int m){
int ** a=new int *[n];
for (int i=0; i<n; ++i)
a[i]=new int[m];
return a;
}
Использование
int **a;
int n;
cin>>n;
a=create(n,n);
27

28.

Проверка свойства матрицы
bool isSymm(const int ** a,int n){
bool fl=true;
for (int j, i=0; i<n && fl; ++i){
for (j=0; j<i && fl; ++j)
fl=a[i][j]==a[j][i];
}
return fl;
}
28

29.

• как использовать, если матрица не в
динамической памяти
int a[2][3];
int *p[2];
p[0]=&a[0][0];
p[1]=&a[1][0];
print (p,2,3);
29

30.

Нерегулярные матрицы
for (int i=0; i<n; i++)
{
// определение m – количества столбцов
a[i]=new int[m];
}
30

31.

Пример
n
n
0 n 1
0
0
0
0
... n
n
... n 1 n 1
...
2
... 2
1
... 0
31

32.

Пример
int **matr;
int n,m,i,j;
cin>>n;
matr = new int *[n];
for ( i=0; i<n; i++) {
m=n-i;
matr[i]= new int[m];
for (j=0; j<m; j++)
matr[i][j]=m;
}
32

33.

Пример
for (i=0; i<n; i++) {
for (j=0; j<i; j++)
cout<<"0 ";
m=n-i;
for (j=0; j<m; j++)
cout<<matr[i][j]<<" ";
cout<<endl;
}
33

34.

Пример
for (i=0; i<n; i++)
delete []matr[i];
delete[] matr;
34

35.

Сортировка для матриц
• Если возможно, не переставлять
строки/столбцы, а хранить информацию об
их правильном расположении
• Индексная сортировка
• Для матриц в динамической памяти можно
в качестве индекса использовать массив
указателей на строки
35

36.

Индексная сортировка
• Упорядочить строки матрицы по
возрастанию сумм элементов
36

37.

void ind_sort(int a[][10],int n,int m, int ind[]) {
int sum[10];
for (int i=0; i<n; ++i) {
ind[i]=i; sum[i]=0;
for(int j=0;j<m; ++j) sum[i]+=a[i][j];
}
37

38.

bool flag=true;
int j=n-1;
while (flag) {
flag=false;
for (int i=0; i<j; ++i) {
if (sum[ind[i]]>sum[ind[i+1]]) {
swap (ind[i], ind[i+1]);
flag=true;
}
}
j--;
}
38

39.

Сортировка массива указателей на
строки
• Упорядочить строки матрицы по
возрастанию их первых элементов.
39

40.

void sort(int **a, int n, int m) {
bool flag=true;
int j=n-1;
a
while (flag) {
flag=false;
for (int i=0; i<j; i++) {
if (a[i][0]>a[i+1][0]) {
int * k=a[i];
a[i]=a[i+1];
a[i+1]=k;
flag=true;
}}
j--;
}}
3
2
1
4
-1
9
4
40