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

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

Сумма элементов массива
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;
}