Программирование на языке высокого уровня. Лекция 4. Массивы

1.

Богатов Р.Н.
Программирование
на языке высокого уровня
C++ ► Лекция 4 ► Массивы
Кафедра АСОИУ ОмГТУ, 2020

2.

Массивы
• Массив – это именованное упорядоченное множество элементов
одного типа.
• Массивы в С++ бывают статические (размер заранее известен, память
заранее зарезервирована)
и динамические (размер становится известен во
время выполнения программы, тогда и выделяется память, размер можно менять).
• Имя массива – это переменная, которая хранит адрес начала
массива в памяти, а элементы адресуются как имя[индекс],
где индекс = 0, 1, 2, …. Например, x[2*i] при i = 0, 1, 2, … – это
нечётные (!!!) элементы массива x.
• Массив занимает непрерывную область памяти компьютера (поэтому,
например, чтобы склеить два массива, нужно завести третий, скопировать в него два
исходных, после чего исходные удалить)

3.

Одномерные статические массивы. Примеры
// объявление массива
int D[20];
const int N = 20, M = 100;
int A[N];
// сумма элементов массива
int sum = 0;
for (int i = 0; i < N; i++)
sum += A[i];
printf("sum = %d", sum );
double B[N], C[M];
// подсчёт нулей
// инициализация при объявлении
int count = 0;
int dx[4] = { 1, 0, -1, 0 };
for (int i = 0; i < N; i++)
int dy[4] = { 0, -1, 0, 1 };
if (A[i]==0)
double RGB2Grayscale[] = { 0.2126, 0.7152, 0.0722
};
count++;
// заполнение массива
for (int i = 0; i < 20; i++)
D[i] = 2 * i;
for (int i = 0; i < N; i++)
B[i] = 0.1*i*i + 3.5*i - 1;
for (int i = 0; i < N; i++)
A[i] = (int)abs(B[i]);
printf("%d zeros", count );
// поиск максимума
int max = A[0];
for (int i = 1; i < N; i++)
if (A[i] > max)
max = A[i];
printf("max = %d", max );

4.

Одномерные статические массивы. Примеры
// переворот
for (int i = 0; i < N/2; i++)
{
double x;
x = B[i];
B[i] = B[N-i-1];
B[N-i-1] = x;
}
double B[N], C[N];
...
// копирование отрицательных элементов массива B в массив C
int K = 0; // фактический размер массива C
// сортировка по убыванию
for (int i = 0; i < N-1; i++)
for (int j = i+1; j < N; j++)
if (B[j] > B[i])
{
double x;
x = B[i];
= B[j];
// размер массива C – N элементов, но занято из нихB[i]
только
K
B[j] = x;
}
for (int i = 0; i < N; i++)
if (B[i] < 0)
{
C[K] = B[i];
K = K + 1;
}

5.

Инициализация массива
//#include <stdio.h> ...<conio.h> ...<locale.h> ...<stdlib.h> ...<time.h>
...
if (mode==0) // случайное заполнение массива
int main()
{
{
srand( (unsigned)time(NULL) );
setlocale(LC_ALL, "Russian");
for(int i=0; i<N; i++)
const int N=10;
a[i] = rand();
int a[N];
}
else // ручной ввод массива
int mode;
{
do {
printf("Введите все %d элементов массива\n", N);
printf("Заполнить массив случ. числами (0) или вручную (1)? ");
for(int i=0; i<N; i++) {
scanf("%d", &mode);
printf("a[%2d] = ", i+1);
fflush(stdin);
Сброс остатков ввода (на случай, если будет введён
scanf("%d", &a[i]);
"мусор", который не может быть считан в переменную
} while(mode!=0 && mode!=1);
fflush(stdin);
целочисленного типа)
}
if (mode==0) // случайное заполнение массива
}
{
...
// вывод массива
}
printf("Ваш массив: ");
else // ручной ввод массива
for(int i=0; i<N; i++)
{
printf("%d ", a[i]);
...
...
}

6.

Задача про пятаки и трёшки
// прямое решение на основе остатка от деления
Задача
банкомата:
заданную
int
A, для
B; ////
искомое
число
пятаков
исумму
трёшекденег (натуральное число
int A,
B;
искомое
число
пятаков
и трёшек
больше
int x = семи)
n % 5; выдать с помощью максимального числа пятаков и,
int A, B; // искомое число пятаков и трёшек
for
(int
i = 0; i < 5; i++)
if (x
== 0)
если
придётся,
некоторого
числа
трёшек.
int x = n % 5;
{
if ((n - i * 3) % 5 == 0)
switch (x)
A = nB / =5;i;
{
B = 0;
// решение
через подбор количества пятёрок
case 0:
}
...
Aelse
= (n - B * 3) / 5;
A = n / 5;
B = 0;
if (x == 1)
int n;
A, scanf("%d",
B; // искомое
число
пятаков ицелое
трёшек
int
&n);
//
исходное
>7
break;
{
case
1:
A = (n - 6) / 5;
A = (n - 6) / 5;
for A,
(B BB;
= =0;
B++)
2; ;искомое
int
//
число пятаков и трёшек
B =0;2;(n - B * 3) % 5 != 0; B++) ;
for (B =
} if ((n - B * 3) % 5 == 0)
break;
else break;
case 2:
for (A if
= n/5;
A--)
(x == A>=0;
2)
A = (n - 12) / 5;
{
A = if
(n ((n
- B -* A3)* /5)5;% 3 == 0)
B = 4;
A = (n - 12) / 5;
break;
break;
B = 4;
int }A, B; // искомое число пятаков и трёшек
case 3:
A = (n - 3) / 5;
B = (n else
- A * 5) / 3;
B = 1;
int G[5]
if =(x{==0,3)2, 4, 1, 3 };
break;
B = G[n{ % 5];
default:
printf("%d
+ /-3*%d",
A*= 3)
(n
3)
A = (n -= B5*%d
5; / 5;n, A, B);
A = (n - 9) / 5;
B = 1;
...
B = 3;
}
break;
else
}
{
A = (n - 9) / 5;
B = 3;
}

7.

Среднеквадратическое отклонение и дисперсия
// объявление массива
const int N=10;
double h[N];
// заполнение массива
...
// вывод массива
...
// вычисление среднего значения
double avg = 0;
for(int i=0; i<N; i++)
avg += h[i];
avg /= N;
printf("\nСредний рост: %.1lf\n", avg);
// вычисление дисперсии
// и среднеквадратического отклонения
double D = 0;
for(int i=0; i<N; i++)
D += (h[i]-avg)*(h[i]-avg);
D /= N;
double S = sqrt(D);
printf("Дисперсия: %.1lf\n", D);
printf("Среднеквадратическое отклонение (сигма): %.1lf\n", S);
...

8.

Поиск подпоследовательности
// найти длину максимально длинной подпоследовательности нулей
// решение с вложенным циклом
// оптимальное решение
...
...
sequences:");
// puts("Zero
наиболее компактное
решение
int max = 0, length = 0;
...int max = 0;
for (int i = 0; i < N; i++)
for (int i = 0; i < N; i++)
int max = 0;
if (a[i] == 0)
if (a[i]==0)
for (int i = 0, length = 0; i < N; i++, max = max(max, length) )
{
length++;
if (a[i] == 0)
int length = 1;
else
length++;
for (int j = i+1; j < N; j++, length++)
{
else
if (a[j] != 0)
if (length > max)
length = 0;
break;
max = length;
...
printf("length: %d\n", length);
length = 0;
// нет, вот наиболее компактное решение!
if (length > max)
}
...
max = length;
int max = 0;
i += length-1;
if (length > max)
for (int i = 0, length = 0; i < N; i++)
}
= length;
length
= (a[i]
==max);
0) ? length + 1 : 0, max max
= max(max,
length);
printf("\nmax
length
= %d",
...
...

9.

Перебор всех расстановок
// общий случай: получение всех расстановок
// единиц в массиве произвольной длины
Математическая постановка задачи: получить
все варианты
#include <stdio.h>
#include <conio.h>
расстановок единиц в множестве из N элементов.
const int N=10;
Постановка задачи для программиста: перебрать
все способы
int a[N];
заполнения массива длины N нулями и единицами.
void main()
// частный случай: получение всех расстановок единиц
{
// в массиве длиной N<31
for(long n=0; n<(1<<N); n++)
{
...
// вывод массива
for(int n=0; n<(1<<N); n++)
printf("\n%d: ", n);
{
for(int i=0; i<N; i++)
for(int i=0; i<N; i++)
printf("%d", a[i]);
a[i] = (n & (1<<i))>0 ? 1 : 0;
for(int i=0; i<N; i++)
if (a[i]==1) // переполнение
a[i] = 0;
else // прибавление единицы
{
a[i] = 1;
break;
}
// вывод массива
printf("\r%d: ", n);
for(int i=0; i<N; i++)
printf("%d", a[i]);
Вопросы:
}
1) Почему
... алгоритм для общего случая работает быстрее?
2) Почему во втором алгоритме массив нужно выводить
до обработки массива?
3) Какой из алгоритмов удобнее взять за основу для
решения задачи расстановки трёхзначных чисел?
}
_getch();
}

10.

Многомерные массивы
• Массивы могут быть двумерными, трёхмерными и
…сколь-угодно-мерными.
• Так как память компьютера одномерна, многомерные массивы в
памяти развёрнуты в одномерные. Например, как если бы из кинотеатра
стали выносить кресла на улицу, ряд за рядом, и выстраивать в одну линейку.
// объявление многомерных статических массивов
int D[4][10];
int A[N][M]; // N, M - константы
double B[3][2][4];
char F[3][256][256][256][2];

11.

Двумерные массивы. Примеры
// полное обнуление
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
F[i][j] = 0;
// верхняя треугольная матрица
for (int i = 0; i < N; i++)
for (int j = i; j < M; j++)
F[i][j] = 0;
// нижняя треугольная матрица
for (int i = 0; i < N; i++)
for (int j = 0; j <= i; j++)
F[i][j] = 0;
// поиск максимума
int max = A[0];
for (int i = 1; i < 100; i++)
if (A[i] > max)
max = A[i];
printf("max = %d", max );
// поиск максимума
double max = -1.7976931348623158e+308;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (F[i][j] > max)
max = F[i][j];
// под побочной диагональю
printf("max = %lg", max );
for (int i = 1; i < N; i++)
for (int j = M-i; j < M; j++)
F[i][j] = 0;

12.

Равны ли два массива поэлементно?
// одномерный случай
int a[N], b[N];
...
// двумерный случай
int a[N][M], b[N][M];
...
bool equal = true;
for (int i = 0; i < N
N;&&
i++)
equal; i++)
if (a[i] != b[i])
{
equal = false;
equal = false;
break;
}
bool equal = true;
for (int i = 0; i < N
N;&&
i++)
equal; i++)
for (int j = 0; j < M;
M &&
j++)
equal; j++)
if (a[i][j] != b[i][j])
{
equal = false;
equal = false;
break;
}
if (equal) printf("Массивы равны!");
else printf("Массивы не равны!");
if (equal) printf("Массивы равны!");
else printf("Массивы не равны!");
Как проверить на равенство два пятимерных массива?

13.

Циклический сдвиг элементов матрицы
// сначала разберём циклический сдвиг одномерного массива влево
int x = a[0];
for (int i = 0; i < N - 1; i++)
a[i] = a[i + 1];
a[N - 1] = x;
// теперь возьмём двумерный массив, но применим алгоритм только к первой строке
// (циклический сдвиг первой строки матрицы влево)
int x = a[0][0];
for (int j = 0; j < M - 1; j++)
a[0][j] = a[0][j + 1];
a[0][M - 1] = x;
// применив это ко всем строкам, получаем общий циклический сдвиг матрицы
for (int i = 0; i < N; i++)
{
int x = a[i][0];
for (int j = 0; j < M - 1; j++)
a[i][j] = a[i][j + 1];
a[i][M - 1] = x;
}

14.

Произведение матриц
// произведение прямоугольных матриц константного размера
const int N=7, M=4, L=5;
int a[N][M], b[M][L], c[N][L];
// инициализация
...
// вывод массива
...
// инициализация
...
// вывод массива
...
массива a
a на экран
массива b
b на экран
// произведение матриц
for(int i=0; i<N; i++)
for(int j=0; j<L; j++)
{
int s = 0;
for(int k=0; k<M; k++)
s += a[i][k]*b[k][j];
c[i][j] = s;
}
// вывод результата на экран
...

15.

Игра «Пятнашки»
char a[N][N];
...
int x = 3, y = 3; // позиция пустой ячейки
int xm = 3, ym = 3; // ячейка для сдвига
for (;; ) {
// отрисовка поля
system("cls");
for (int i = 0; i < N; i++, printf("\n"))
for (int j = 0; j < N; j++)
if (i == y && j == x)
printf(" []");
else
printf("%3d", a[i][j]);
// выбор (xm, ym) для сдвига на (x, y)
switch (_getch()) {
case 'a': if (x > 0) ym = y, xm = x-1;
case 'd': if (x<N-1) ym = y, xm = x+1;
case 'w': if (y > 0) ym = y-1, xm = x;
case 's': if (y<N-1) ym = y+1, xm = x;
}
// сдвиг
a[y][x] = a[ym][xm];
a[ym][xm] = 0;
x = xm; y = ym;
}
break;
break;
break;
break;

16.

Одномерные динамические массивы
int n;
printf("Введите N: ");
scanf("%d", &n);
int *a; // массив объявлен, но им пользоваться нельзя
// выделение памяти для n элементов типа int
a = new int[n];
// после этого с массивом a можно работать как с обычным массивом, т.е. через a[i]
// заполнение случайными числами
srand( (unsigned)time(NULL) );
for(int i=0; i<n; i++)
a[i] = rand()%100;
// вывод на экран
for(int i=0; i<n; i++)
printf("%2d ", a[i]);
// высвобождение выделенной памяти (операция, обратная new)
delete a;
// после этого массивом a опять пользоваться нельзя

17.

Многомерные динамические массивы
int n, m;
printf("Введите N, M: ");
scanf("%d%d", &n, &m);
int **a;
a = new int*[n];
for(int i=0; i<n; i++)
a[i] = new int[m];
srand( (unsigned)time(NULL) );
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
a[i][j] = rand()%10;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++)
printf("%2d ", a[i][j]);
printf("\n");
}
for(int i=0; i<n; i++)
delete a[i];
delete a;

18.

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

19.

Упражнения на одномерные массивы
Заполнить массив натуральными числами в обратном порядке;
значениями sin x; случайными числами
Подсчитать в массиве количество отрицательных чисел
Найти сумму элементов массива, максимум, минимум, среднее...
Каких элементов больше: отрицательных или неотрицательных?
Найти произведение элементов массива (с прерыванием цикла,
если встретится ноль)
Найти элемент, наиболее близкий к заданному числу
Заполнить массив по образцу: 1, 3, 5, ..., N, ..., 6, 4, 2
Проверить, является ли массив упорядоченным по возрастанию
Повышенной сложности: найти медиану массива – элемент,
разделяющий массив на две наиболее близких по сумме части

20.

Упражнения на двумерные массивы
Заполнить массив натуральными числами, функцией двух
переменных (например, –2x4+x3+8x2–2y4+y3+8y2), случайными
числами
Подсчитать в массиве количество чисел, близких к нулю (с
заданной точностью)
Найти максимум, минимум, среднее, суммы главной и побочной
диагоналей. Вычесть из матрицы значение минимума
Транспонировать квадратную матрицу
Получить заданный минор (удалить заданные строку и столбец)
Переставить четверти по часовой стрелке
Повышенной сложности: заполнить массив натуральными
числами а) по спирали, б) змейкой, в) массив 8х8 – прыжками
шахматного коня