Основы программирования (на языке Си). Массивы

Содержание

Слайд 2

Массивы

Массив – тип данных, состоящий из группы однотипных элементов, имеющих общее

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

Слайд 3

Массивы

A

массив

2

15

НОМЕР элемента массива
(ИНДЕКС)

A[0]

A[1]

A[2]

A[3]

A[4]

ЗНАЧЕНИЕ элемента массива

A[2]

НОМЕР (ИНДЕКС) элемента массива: 2

ЗНАЧЕНИЕ элемента массива: 15

Массивы A массив 2 15 НОМЕР элемента массива (ИНДЕКС) A[0] A[1] A[2]

Слайд 4

Объявление массивов

Зачем объявлять?
определить имя массива
определить тип массива
определить число элементов
выделить место в

Объявление массивов Зачем объявлять? определить имя массива определить тип массива определить число
памяти
Пример:
Размер через константу:

имя

размер массива (количество элементов)

тип
элементов
int A [ ];

const int N = 5;

N

int A [ 5 ];

Слайд 5

Объявление массивов

Еще примеры:

int X[10], Y[10];
float zz, A[20];
char s[80];

С присвоением начальных

Объявление массивов Еще примеры: int X[10], Y[10]; float zz, A[20]; char s[80];
значений:

int A[4] = { 8, -3, 4, 6 };
float B[2] = { 1. };
char C[3] = { 'A', '1', 'Ю' };

остальные нулевые!

Слайд 6

Что неправильно?

int X[4.5];

int A[10];
A[10] = 0;

float X[5];
int

Что неправильно? int X[4.5]; int A[10]; A[10] = 0; float X[5]; int
n = 1;
X[n-2] = 4.5;
X[n+8] = 12.;

выход за границы массива
(стираются данные в памяти)

int X[4];
X[2] = 4.5;

дробная часть отбрасывается
(ошибки нет)

float B[2] = { 1., 3.8, 5.5 };

int A[2] = { 1, 3.8 };

float

Слайд 7

Массивы

Объявление:
Ввод с клавиатуры:
Поэлементные операции:
Вывод на экран:

const int N = 5;
int A[N],

Массивы Объявление: Ввод с клавиатуры: Поэлементные операции: Вывод на экран: const int
i;

printf("Введите 5 элементов массива:\n");
for( i=0; i < N; i++ ) {
printf ("A[%d] = ", i );
scanf ("%d", & A[i] );
}

A[0] =
A[1] =
A[2] =
A[3] =
A[4] =

5
12
34
56
13

for( i=0; i < N; i++ ) A[i] = A[i]*2;

printf("Результат:\n");
for( i=0; i < N; i++ ) printf("%4d", A[i]);

Результат:
10 24 68 112 26

Слайд 8

Программа

#include
#include
main()
{
const int N = 5;
int A[N], i;
// ввод элементов

Программа #include #include main() { const int N = 5; int A[N],
массива
// обработка массива
// вывод результата
getch();
}

Задача: ввести с клавиатуры массив из 5 элементов, умножить все элементы на 2 и вывести полученный массив на экран.

на предыдущих слайдах

Слайд 9

Задания

«A»: Ввести c клавиатуры массив из 5 элементов, найти среднее арифметическое всех

Задания «A»: Ввести c клавиатуры массив из 5 элементов, найти среднее арифметическое
элементов массива.
Пример:
Введите пять чисел:
4 15 3 10 14
среднее арифметическое 9.200
«B»: Ввести c клавиатуры массив из 5 элементов, найти минимальный из них.
Пример:
Введите пять чисел:
4 15 3 10 14
минимальный элемент 3

Слайд 10

Тема 11. Поиск максимального элемента массива

Основы программирования (на языке Си)

Тема 11. Поиск максимального элемента массива Основы программирования (на языке Си)

Слайд 11

Максимальный элемент

Задача: найти в массиве максимальный элемент.
Алгоритм:

Псевдокод:

// считаем, что элемент A[0]

Максимальный элемент Задача: найти в массиве максимальный элемент. Алгоритм: Псевдокод: // считаем,
– максимальный
for ( i=1; i < N; i++ )
if ( A[i] > максимального )
// запомнить новый максимальный элемент A[i]

Слайд 12

Максимальный элемент

max = A[0]; // пока A[0]– максимальный
iMax = 0;
for (

Максимальный элемент max = A[0]; // пока A[0]– максимальный iMax = 0;
i=1; i < N; i++ ) // проверяем остальные
if ( A[i] > max ) { // нашли новый
max = A[i]; // запомнить A[i]
iMax = i; // запомнить i
}

Дополнение: как найти номер максимального элемента?

По номеру элемента iMax всегда можно найти его значение A[iMax]. Поэтому везде меняем max на A[iMax] и убираем переменную max.

A[iMax]

Слайд 13

Заполнение случайными числами

RAND_MAX – максимальное случайное целое число (обычно RAND_MAX = 32767)
Случайное

Заполнение случайными числами RAND_MAX – максимальное случайное целое число (обычно RAND_MAX =
целое число в интервале [0,RAND_MAX]
x = rand(); // первое число
x = rand(); // уже другое число
Установить начальное значение последовательности:
srand ( 345 ); // установка зерна генератора
srand ( time (NULL) ); // зерно равно
// количеству секунд, прошедших с 01.01.1970

#include // случайные числа

необходимо подключить
#include

Слайд 14

Заполнение случайными числами

#include
#include
main()
{
const int N = 10;
int A[N], i;
srand (

Заполнение случайными числами #include #include main() { const int N = 10;
100 );
printf("Исходный массив:\n");
for (i = 0; i < N; i++ ) {
A[i] = rand()%101 - 50;
printf("%4d", A[i]);
}
...
}

Слайд 15

Программа

#include
#include
main()
{
const int N = 5;
int A[N], i, iMax;
// заполнить

Программа #include #include main() { const int N = 5; int A[N],
случайными числами [100,150]
// найти максимальный элемент и его номер
printf("\nМаксимальный элемент A[%d] = %d", iMax, A[iMax]);
getch();
}

на предыдущих слайдах

Слайд 16

Задания

«A»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и

Задания «A»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10]
найти в нем максимальный и минимальный элементы и их номера.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0
максимальный a[4]=10
минимальный a[8]=-10
«B»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и найти в нем два максимальных элемента и их номера.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0
максимальные a[4]=10, a[7]=8

Слайд 17

Тема 12. Обработка массивов

Основы программирования (на языке Си)

Тема 12. Обработка массивов Основы программирования (на языке Си)

Слайд 18

Реверс массива

Задача: переставить элементы массива в обратном порядке (выполнить инверсию).
Алгоритм:
поменять местами A[0]

Реверс массива Задача: переставить элементы массива в обратном порядке (выполнить инверсию). Алгоритм:
и A[N-1], A[1] и A[N-2], …
Псевдокод:

for ( i = 0; i < N; i++ )
// поменять местами A[i] и A[N-1-i]

сумма индексов N-1

Слайд 19

Программа

main()
{
const int N = 10;
int A[N], i, c;
// заполнить

Программа main() { const int N = 10; int A[N], i, c;
массив
// вывести исходный массив
for ( i = 0; i < N/2; i++ ) {
c = A[i];
A[i] = A[N-1-i];
A[N-1-i] = c;
}
// вывести полученный массив
}

Слайд 20

Задания

«A»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и

Задания «A»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10]
выполнить инверсию отдельно для 1-ой и 2-ой половин массива.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0
Результат:
-4 10 3 -5 4 0 1 -10 8 -6
«B»: Заполнить массив из 12 элементов случайными числами в интервале [-12..12] и выполнить инверсию для каждой трети массива.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0 5 7
Результат:
10 3 -5 4 -10 8 -6 -4 7 5 0 1

Слайд 21

Циклический сдвиг

Задача: сдвинуть элементы массива влево на 1 ячейку, первый элемент становится

Циклический сдвиг Задача: сдвинуть элементы массива влево на 1 ячейку, первый элемент
на место последнего.
Алгоритм:
A[0]=A[1]; A[1]=A[2];… A[N-2]=A[N-1];
Цикл:

for ( i = 0; i < N-1; i ++) A[i] = A[i+1];

почему не N?

Слайд 22

Программа

main()
{
const int N = 10;
int A[N], i, c;
// заполнить

Программа main() { const int N = 10; int A[N], i, c;
массив
// вывести исходный массив
c = A[0];
for ( i = 0; i < N-1; i ++)
A[i] = A[i+1];
A[N-1] = c;
// вывести полученный массив
}

Слайд 23

Задания

«4»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и

Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10]
выполнить циклический сдвиг ВПРАВО.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0
Результат:
0 4 -5 3 10 -4 -6 8 -10 1
«5»: Заполнить массив из 12 элементов случайными числами в интервале [-12..12] и выполнить циклический сдвиг ВПРАВО на 4 элемента.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0 5 7
Результат:
1 0 5 7 4 -5 3 10 -4 -6 8 -10

Слайд 24

Тема 13. Сортировка массивов

Основы программирования (на языке Си)

Тема 13. Сортировка массивов Основы программирования (на языке Си)

Слайд 25

Сортировка

Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию,

Сортировка Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию,
последней цифре, сумме делителей, …).
Задача: переставить элементы массива в порядке возрастания.
Алгоритмы:
простые и понятные, но неэффективные для больших массивов
метод пузырька
метод выбора
сложные, но эффективные
«быстрая сортировка» (Quick Sort)
сортировка «кучей» (Heap Sort)
сортировка слиянием
пирамидальная сортировка

сложность O(N2)

сложность O(N·logN)

Слайд 26

Метод пузырька

Идея – пузырек воздуха в стакане воды поднимается со дна вверх.

Метод пузырька Идея – пузырек воздуха в стакане воды поднимается со дна

Для массивов – самый маленький («легкий») элемент перемещается вверх («всплывает»).

начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
за 1 проход по массиву один элемент (самый маленький) становится на свое место

1-ый проход

2-ой проход

3-ий проход

Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

Слайд 27

Программа (1-ый проход)

сравниваются пары
A[N-2] и A[N-1],
A[N-3] и A[N-2]

Программа (1-ый проход) сравниваются пары A[N-2] и A[N-1], A[N-3] и A[N-2] …
A[0] и A[1]

A[j] и A[j+1]

for( j = N-2; j >= 0 ; j-- )
if ( A[j] > A[j+1] ) {
c = A[j];
A[j] = A[j+1];
A[j+1] = c;
}

0

Слайд 28

Программа (следующие проходы)

2-ой проход

for ( j = N-2; j >= 1 ;

Программа (следующие проходы) 2-ой проход for ( j = N-2; j >=
j-- )
if ( A[j] > A[j+1] ) {
c = A[j];
A[j] = A[j+1];
A[j+1] = c;
}

1

(i+1)-ый проход

for ( j = N-2; j >= i ; j-- )
...

i

Слайд 29

Программа

main()
{
const int N = 10;
int A[N], i, j, c;
//

Программа main() { const int N = 10; int A[N], i, j,
заполнить массив
// вывести исходный массив
for (i = 0; i < N-1; i ++){
for (j = N-2; j >= i ; j --)
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
}
}
// вывести полученный массив
}

элементы выше A[i] уже поставлены

i

меняем A[j] и A[j+1]

Слайд 30

Метод пузырька с флажком

Идея – если при выполнении метода пузырька не было

Метод пузырька с флажком Идея – если при выполнении метода пузырька не
обменов, массив уже отсортирован и остальные проходы не нужны.
Реализация: переменная-флаг, показывающая, был ли обмен; если она равна 0, то выход.

do {
flag = 0; // сбросить флаг
for (j = N-2; j >= 0; j --)
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
flag = 1; // поднять флаг
}
}
while ( flag ); // выход при flag = 0

flag = 0;

flag = 1;

( flag );

int flag;

Слайд 31

Метод пузырька с флажком

i = 0;
do {
flag = 0; // сбросить

Метод пузырька с флажком i = 0; do { flag = 0;
флаг
for ( j = N-2; j >= i ; j -- )
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
flag = 1; // поднять флаг
}
i ++;
}
while ( flag ); // выход при flag = 0

i = 0;

i

i ++;

Слайд 32

Метод выбора

Идея:
найти минимальный элемент и поставить на первое место (поменять местами с

Метод выбора Идея: найти минимальный элемент и поставить на первое место (поменять
A[0])
из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[1]), и т.д.

Слайд 33

Метод выбора

N

for( i = 0; i < N-1 ; i ++ )

Метод выбора N for( i = 0; i nMin = i ;
{
nMin = i ;
for ( j = i+1; j < N; j ++)
if( A[j] < A[nMin] ) nMin = j;
if( nMin != i ) {
c = A[i];
A[i] = A[nMin];
A[nMin] = c;
}
}

N-1

нужно N-1 проходов

поиск минимального от A[i] до A[N-1]

если нужно, переставляем

i+1

i

Слайд 34

Задания

«A»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и

Задания «A»: Заполнить массив из 10 элементов случайными числами в интервале [0..100]
отсортировать его по последней цифре.
Пример:
Исходный массив:
14 25 13 30 76 58 32 11 41 97
Результат:
30 11 41 32 13 14 25 76 97 58
«B»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать первую половину по возрастанию, а вторую – по убыванию.
Пример:
Исходный массив:
14 25 13 30 76 58 32 11 41 97
Результат:
13 14 25 30 76 97 58 41 32 11

Слайд 35

Формирование массива по условию

Задача – найти в массиве элементы, удовлетворяющие некоторому условию

Формирование массива по условию Задача – найти в массиве элементы, удовлетворяющие некоторому
(например, отрицательные), и скопировать их в другой массив.

Примитивное решение:

const int N = 5;
int A[N], B[N];
// здесь заполнить массив A
for( i = 0; i < N; i ++ )
if( A[i] < 0 ) B[i] = A[i];

A

B

выбранные элементы не рядом, не в начале массива
непонятно, как с ними работать

Слайд 36

Формирование массива по условию

Решение: ввести счетчик найденных элементов count, очередной элемент ставится

Формирование массива по условию Решение: ввести счетчик найденных элементов count, очередной элемент
на место B[count].

int A[N], B[N], count = 0;
// здесь заполнить массив A
for( i = 0; i < N; i ++ )
if( A[i] < 0 ) {
B[count] = A[i];
count ++;
}
// вывод массива B
for( i = 0; i < count; i ++ )
printf("%d\n", B[i]);

A

B

count

Слайд 37

Задания

«A»: Заполнить массив случайными числами и отобрать в другой массив все числа,

Задания «A»: Заполнить массив случайными числами и отобрать в другой массив все
у которых вторая с конца цифра (число десятков) – ноль.
Пример:
Исходный массив:
40 105 203 1 14
Результат:
105 203 1
«B»: Заполнить массив случайными числами и выделить в другой массив все числа, которые встречаются более одного раза.
Пример:
Исходный массив:
4 1 2 1 11 2 34
Результат:
1 2

Слайд 38

Тема 14. Матрицы

Основы программирования (на языке Си)

Тема 14. Матрицы Основы программирования (на языке Си)

Слайд 39

Матрицы

Задача: запомнить положение фигур на шахматной доске.

1

2

3

4

5

6

c6

A[5][2]

Матрицы Задача: запомнить положение фигур на шахматной доске. 1 2 3 4 5 6 c6 A[5][2]

Слайд 40

Матрицы

Матрица – это прямоугольная таблица однотипных элементов.
Матрица – это массив, в котором

Матрицы Матрица – это прямоугольная таблица однотипных элементов. Матрица – это массив,
каждый элемент имеет два индекса (номер строки и номер столбца).

A

строка 1

столбец 2

ячейка A[2][3]

Слайд 41

Матрицы

Объявление:

const int N = 3, M = 4;
int A[N][M];
float a[2][2] = {{3.2,

Матрицы Объявление: const int N = 3, M = 4; int A[N][M];
4.3}, {1.1, 2.2}};
char sym[2][2] = { 'a', 'b', 'c', 'd' };

Ввод с клавиатуры:

for ( i = 0; i < N; i ++ )
for ( j = 0; j < M; j ++ ) {
printf ( "A[%d][%d]=", i, j);
scanf ( "%d", &A[i][j] );
}

A[0][0]=

25

A[0][1]=

14

A[0][2]=

14

...

A[2][3]=

54

i

j

for ( j = 0; j < M; j ++ )
for ( i = 0; i < N; i ++ ) {

Слайд 42

Матрицы

Заполнение случайными числами

for ( i = 0; i < N; i ++

Матрицы Заполнение случайными числами for ( i = 0; i for (
)
for ( j = 0; j < M; j ++ )
A[i][j] = random(25)- 10;

цикл по строкам

цикл по столбцам

Вывод на экран

for ( i = 0; i < N; i ++ ) {
for ( j = 0; j < M; j ++ )
printf("%5d", A[i,j]);
printf("\n");
}

перейти на новую строку

for ( j = 0; j < M; j ++ )
printf("%5d", A[i][j]);

вывод строки

в той же строке

Слайд 43

Обработка всех элементов матрицы

Задача: заполнить матрицу из 3 строк и 4 столбцов

Обработка всех элементов матрицы Задача: заполнить матрицу из 3 строк и 4
случайными числами и вывести ее на экран. Найти сумму элементов матрицы.

main()
{
const int N = 3, M = 4;
int A[N][M], i, j, S = 0;
... // заполнение матрицы и вывод на экран
for ( i = 0; i < N; i ++ )
for ( j = 0; j < M; j ++ )
S += A[i][j];
printf("Сумма элементов матрицы S=%d", S);
}

for ( i = 0; i < N; i ++ )
for ( j = 0; j < M; j ++ )
S += A[i][j];

Слайд 44

Задания

Заполнить матрицу из 8 строк и 5 столбцов случайными числами в интервале

Задания Заполнить матрицу из 8 строк и 5 столбцов случайными числами в
[-10,10] и вывести ее на экран.

«4»: Найти минимальный и максимальный элементы в матрице их номера. Формат вывода:
Минимальный элемент A[3][4]=-6
Максимальный элемент A[2][2]=10
«5»: Вывести на экран строку, сумма элементов которой максимальна. Формат вывода:
Строка 2: 3 5 8 9 8

Слайд 45

Операции с матрицами

Задача 1. Вывести на экран главную диагональ квадратной матрицы из

Операции с матрицами Задача 1. Вывести на экран главную диагональ квадратной матрицы
N строк и N столбцов.

A[0][N-1]

A[1][1]

A[2][2]

A[N-1][N-1]

for ( i = 0; i < N; i ++ )
printf ( "%5d", A[i][i] );

Задача 2. Вывести на экран вторую диагональ.

A[N-1][0]

A[N-2][1]

A[1][N-2]

сумма номеров строки и столбца N-1

A[0][0]

for ( i = 0; i < N; i ++)
printf ( "%5d", A[i][ N-1-i ]);

N-1-i

Слайд 46

Операции с матрицами

Задача 3. Найти сумму элементов, стоящих на главной диагонали и

Операции с матрицами Задача 3. Найти сумму элементов, стоящих на главной диагонали
ниже ее.

строка 0: A[0][0]
строка 1: A[1][0]+A[1][1]
...
строка i: A[i][0]+A[i][2]+...+A[i][i]

S = 0;
for ( i = 0; i < N; i ++ )
for ( j = 0; j <= i; j ++ )
S += A[i][j];

цикл по всем строкам

for ( j = 0; j <= i; j ++ )
S += A[i][j];

складываем нужные элементы строки i

Слайд 47

Операции с матрицами

Задача 4. Перестановка строк или столбцов. В матрице из N

Операции с матрицами Задача 4. Перестановка строк или столбцов. В матрице из
строк и M столбцов переставить 1-ую и 3-ю строки.

1

3

j

A[1][j]

A[3][j]

for ( j = 0; j <= M; j ++ ) {
c = A[1][j];
A[1][j] = A[3][j];
A[3][j] = c;
}

Задача 5. К третьему столбцу добавить шестой.

for ( i = 0; i < N; i ++ )
A[i][3] += A[i][6];

Имя файла: Основы-программирования-(на-языке-Си).-Массивы.pptx
Количество просмотров: 37
Количество скачиваний: 0