Презентация, доклад на тему Массивы

Содержание

Программирование на языке Си Часть IIТема 1. Массивы

Слайд 1Программирование на языке Си Часть II
Массивы
Максимальный элемент массива
Обработка массивов
Сортировка массивов
Поиск в массиве
Массивы

в процедурах и функциях

Практикум (моделирование)
Символьные строки
Рекурсивный перебор
Матрицы
Файлы

Программирование на языке Си Часть IIМассивыМаксимальный элемент массиваОбработка массивовСортировка массивовПоиск в массивеМассивы в процедурах и функцияхПрактикум

Слайд 2Программирование на языке Си Часть II
Тема 1. Массивы

Программирование на языке Си Часть IIТема 1. Массивы

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

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

Слайд 4
Массивы

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

15



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

Слайд 5

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

в памяти
Пример:


Размер через константу:

имя

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

тип
элементов


int A [ ];

const int N = 5;

N




int A [ 5 ];

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

Слайд 6Объявление массивов
Еще примеры:
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', 'Ю' };

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

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

Слайд 7
Что неправильно?
int N = 10;

float A[N];

const 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

Что неправильно? int N = 10; float A[N];const int int X[4.5];

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

A[N], 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

МассивыОбъявление:Ввод с клавиатуры:Поэлементные операции:Вывод на экран:const int N = 5; int A[N], i;printf(

Слайд 9
Программа
#include
#include
main()
{
const int N = 5;
int A[N], i;
// ввод

элементов массива
// обработка массива
// вывод результата
getch();
}

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

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

Программа#include #include main(){const int N = 5;int A[N], i; // ввод элементов массива // обработка массива //

Слайд 10
Задания
«4»: Ввести c клавиатуры массив из 5 элементов, найти среднее арифметическое

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

Слайд 11Программирование на языке Си Часть II
Тема 2. Максимальный

элемент массива

© К.Ю. Поляков, 2007-2009

Программирование на языке Си Часть IIТема 2. Максимальный

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




Псевдокод:
// считаем, что элемент

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

Слайд 13Максимальный элемент
max = A[0]; // пока A[0]– максимальный
iMax = 0;
for

( 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]

Максимальный элементmax = A[0]; // пока A[0]– максимальный iMax = 0;for ( i=1; i < N; i++

Слайд 14Заполнение случайными числами
RAND_MAX – максимальное случайное целое число

(обычно RAND_MAX = 32767)
Случайное целое число в интервале [0,RAND_MAX]
x = rand(); // первое число
x = rand(); // уже другое число
Установить начальное значение последовательности:
srand ( 345 ); // начнем с 345

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

Заполнение случайными числамиRAND_MAX – максимальное случайное целое число

Слайд 15Целые числа в заданном интервале

Целые числа в интервале [0,N-1]:




Примеры:

Целые

числа в интервале [a,b]:

int random(int N) {
return rand()% N;
}

x = random ( 100 ); // интервал [0,99]
x = random ( z ); // интервал [0,z-1]

x = random ( z ) + a; // интервал [a,z-1+a]
x = random (b – a + 1) + a; // интервал [a,b]

Целые числа в заданном интервалеЦелые числа в интервале [0,N-1]: Примеры: Целые числа в интервале [a,b]: int random(int

Слайд 16Заполнение случайными числами
#include
#include


main()
{
const int N = 10;
int A[N], i;
printf("Исходный

массив:\n");
for (i = 0; i < N; i++ ) {
A[i] = random(100) + 50;
printf("%4d", A[i]);
}
...
}

int random(int N)
{ return rand() % N; }

функция выдает случайное число от 0 до N-1

Заполнение случайными числами#include #include main(){const int N = 10;int A[N], i;printf(

Слайд 17Программа

#include
#include
main()
{
const int N = 5;
int A[N], i, iMax;
//

заполнить случайными числами [100,150]
// найти максимальный элемент и его номер
printf("\nМаксимальный элемент A[%d] = %d", iMax, A[iMax]);
getch();
}

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

Программа#include #include main(){const int N = 5;int A[N], i, iMax; // заполнить случайными числами [100,150] // найти

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

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

Слайд 19Программирование на языке Си Часть II
Тема 3. Обработка массивов

Программирование на языке Си Часть IIТема 3. Обработка массивов

Слайд 20Реверс массива
Задача: переставить элементы массива в обратном порядке (выполнить инверсию).
Алгоритм:
поменять местами

A[0] и A[N-1], A[1] и A[N-2], …
Псевдокод:




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

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



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

Слайд 21Как переставить элементы?
2
3
1
Задача: поменять местами содержимое двух чашек.
Задача: поменять местами содержимое

двух ячеек памяти.

4

6

?

4

6

4

x

y

c

c = x;
x = y;
y = c;

x = y;
y = x;


3

2

1

Как переставить элементы?231Задача: поменять местами содержимое двух чашек.Задача: поменять местами содержимое двух ячеек памяти.46?464xycc = x;x =

Слайд 22Программа


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;
}
// вывести полученный массив
}
Программаmain(){ const int N = 10; int A[N], i, c; // заполнить массив // вывести исходный

Слайд 23
Задания
«4»: Заполнить массив из 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
«5»: Заполнить массив из 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
Задания«4»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и выполнить инверсию отдельно для 1-ой

Слайд 24Циклический сдвиг
Задача: сдвинуть элементы массива влево на 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?

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

Слайд 25Программа


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;
// вывести полученный массив
}
Программаmain(){ const int N = 10; int A[N], i, c; // заполнить массив // вывести исходный массив

Слайд 26
Задания
«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
Задания«4»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и выполнить циклический сдвиг ВПРАВО.

Слайд 27Программирование на языке Си Часть II
Тема 4. Сортировка массивов

Программирование на языке Си Часть IIТема 4. Сортировка массивов

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

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

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

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

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

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

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




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



1-ый проход

2-ой проход

3-ий проход


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

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

Слайд 30Программа (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

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

Слайд 31Программа (следующие проходы)
2-ой проход

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

; 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


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

Слайд 32Программа


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

// заполнить массив
// вывести исходный массив
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]

Программаmain(){ const int N = 10; int A[N], i, j, c; // заполнить массив // вывести

Слайд 33Метод пузырька с флажком
Идея – если при выполнении метода пузырька не

было обменов, массив уже отсортирован и остальные проходы не нужны.
Реализация: переменная-флаг, показывающая, был ли обмен; если она равна 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;


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

Слайд 34Метод пузырька с флажком
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 ++;

Метод пузырька с флажкомi = 0;do { flag = 0; // сбросить флаг for ( j =

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

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







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

Слайд 36Метод выбора

N


for( i = 0; i < N-1 ; 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

Метод выбораNfor( i = 0; i < N-1 ; i ++ ) { nMin = i ;

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

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

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

условию (например, отрицательные), и скопировать их в другой массив.

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

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



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

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

Слайд 39Формирование массива по условию
Решение: ввести счетчик найденных элементов 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

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

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

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

Слайд 41Программирование на языке Си Часть II
Тема 5. Поиск в массиве

Программирование на языке Си Часть IIТема 5. Поиск в массиве

Слайд 42Поиск в массиве
Задача – найти в массиве элемент, равный X, или

установить, что его нет.
Решение: для произвольного массива: линейный поиск (перебор)
недостаток: низкая скорость
Как ускорить? – заранее подготовить массив для поиска
как именно подготовить?
как использовать «подготовленный» массив?
Поиск в массивеЗадача – найти в массиве элемент, равный X, или установить, что его нет. Решение: для

Слайд 43Линейный поиск
nX = -1;
for ( i = 0; i < N;

i ++)
if ( A[i] == X ) {
nX = i;
break; //выход из цикла
}


Улучшение: после того, как нашли X, выходим из цикла.


break;

nX = -1; // пока не нашли ...
for ( i = 0; i < N; i ++) // цикл по всем элементам
if ( A[i] == X ) // если нашли, то ...
nX = i; // ... запомнили номер
if (nX < 0) printf("Не нашли...")
else printf("A[%d]=%d", nX, X);

nX – номер нужного элемента в массиве

Линейный поискnX = -1;for ( i = 0; i < N; i ++) if ( A[i] ==

Слайд 44
Двоичный поиск


X = 7
X < 8

8
4
X > 4

6

X > 6
Выбрать средний

элемент A[c] и сравнить с X.
Если X = A[c], нашли (выход).
Если X < A[c], искать дальше в первой половине.
Если X > A[c], искать дальше во второй половине.
Двоичный поискX = 7X < 884X > 46X > 6Выбрать средний элемент A[c] и сравнить с X.Если

Слайд 45Двоичный поиск



N-1
nX = -1;
L = 0; R =

N-1; // границы: ищем от A[0] до A[N-1]
while ( R >= L ){
c = (R + L) / 2;
if (X = = A[c]) {
nX = c;
break;
}
if (X < A[c]) R = c - 1;
if (X > A[c]) L = c + 1;
}
if (nX < 0) printf("Не нашли...");
else printf("A[%d]=%d", nX, X);

номер среднего элемента

если нашли …

выйти из цикла

сдвигаем границы

>

">Двоичный поискN-1 nX = -1; L = 0; R = N-1; // границы: ищем от A[0] до

Слайд 46Сравнение методов поиска

Сравнение методов поиска

Слайд 47
Задания
«4»: Написать программу, которая сортирует массив ПО УБЫВАНИЮ и ищет в

нем элемент, равный X (это число вводится с клавиатуры). Использовать двоичный поиск.

«5»: Написать программу, которая считает среднее число шагов в двоичном поиске для массива из 32 элементов в интервале [0,100]. Для поиска использовать 1000 случайных чисел в этом же интервале.
Задания«4»: Написать программу, которая сортирует массив ПО УБЫВАНИЮ и ищет в нем элемент, равный X (это число

Слайд 48Программирование на языке Си Часть II
Тема 6. Массивы в процедурах и функциях
©

К.Ю. Поляков, 2007-2009
Программирование на языке Си Часть IIТема 6. Массивы в процедурах и функциях© К.Ю. Поляков, 2007-2009

Слайд 49Массивы в процедурах
Задача: составить процедуру, которая переставляет элементы массива в обратном

порядке.

void Reverse ( int A[] , int N )
{
int i, c;
for ( i = 0; i < N/2; i ++ ) {
c = A[i];
A[i] = A[N-1-i];
A[N-1-i] = c;
}
}

int A[]

параметр-массив

размер массива

Массивы в процедурахЗадача: составить процедуру, которая переставляет элементы массива в обратном порядке. void Reverse ( int A[]

Слайд 50Массивы как параметры процедур
Особенности:
при описании параметра-массива в заголовке функции его размер

не указывается (функция работает с массивами любого размера)


размер массива надо передавать как отдельный параметр
в процедура передается адрес исходного массива: все изменения, сделанные в процедуре влияют на массив в основной программе
Массивы как параметры процедурОсобенности:при описании параметра-массива в заголовке функции его размер не указывается (функция работает с массивами

Слайд 51Массивы в процедурах
void Reverse ( int A[], int N )
{
...
}
main()
{
int

A[10];
// здесь надо заполнить массив
Reverse ( A, 10 ); // весь массив
// Reverse ( A, 5 ); // первая половина
// Reverse ( A+5, 5 ); // вторая половина
}

A или &A[0]

это адрес начала массива в памяти

A+5 или &A[5]

Массивы в процедурахvoid Reverse ( int A[], int N ){...}main(){ int A[10]; // здесь надо заполнить

Слайд 52
Задания
«4»: Написать процедуру, которая сортирует массив по возрастанию, и показать пример

ее использования.

«5»: Написать процедуру, которая ставит в начало массива все четные элементы, а конец – все нечетные.
Задания«4»: Написать процедуру, которая сортирует массив по возрастанию, и показать пример ее использования.«5»: Написать процедуру, которая ставит

Слайд 53Массивы в функциях
Задача: составить функцию, которая находит сумму элементов массива.
int

Sum ( int A[], int N )
{
int i, sum = 0;
for ( i = 0; i < N; i ++ )
sum += A[i];
return sum;
}

результат – целое число

int A[]

параметр-массив

размер массива

Массивы в функцияхЗадача: составить функцию, которая находит сумму элементов массива. int Sum ( int A[], int N

Слайд 54Массивы в процедурах и функциях
int Sum ( int A[], int N

)
{
...
}
main()
{
int A[10], sum, sum1, sum2;
// заполнить массив
sum = Sum ( A, 10 ); // весь массив
sum1 = Sum ( A, 5 ); // первая половина
sum2 = Sum ( A+5, 5 ); // вторая половина
...
}
Массивы в процедурах и функцияхint Sum ( int A[], int N ){...}main(){ int A[10], sum, sum1, sum2;

Слайд 55
Задания
«4»: Написать функцию, которая находит максимальный элемент в массиве.

«5»: Написать логическую

функцию, которая определяет, верно ли, что среди элементов массива есть два одинаковых. Если ответ «да», функция возвращает 1; если ответ «нет», то 0.
Подсказка: для отладки удобно использовать массив из 5 элементов, задаваемых вручную:

const int N = 5;
int A[N] = { 1, 2, 3, 3, 4 };

Задания«4»: Написать функцию, которая находит максимальный элемент в массиве.«5»: Написать логическую функцию, которая определяет, верно ли, что

Слайд 56Программирование на языке Си Часть II
Тема 7. Практикум

(моделирование)
Программирование на языке Си Часть IIТема 7. Практикум

Слайд 57Моделирование кипения воды
Задача: Построить компьютерную модель кипения воды.
Хранение данных: координаты (центров)

пузырьков хранятся в массивах X и Y:
X[i], Y[i] – координаты центра пузырька с номером i.
Моделирование кипения водыЗадача: Построить компьютерную модель кипения воды.Хранение данных: координаты (центров) пузырьков хранятся в массивах X и

Слайд 58Структура программы





#include
#include
#include
const int N = 100;
int X[N], Y[N],

r = 3;
void Init (); // начальное положение
void Draw ( int color ); // рисуем, стираем
void Sdvig ( int dy ); // летят вверх
void Zamena (); // ушли, пришли
main()
{
initwindow (600, 400);
... // основная часть программы
closegraph();
}
... // здесь сами процедуры

глобальные константы и переменные

объявления процедур

Структура программы#include #include #include const int N = 100;int X[N], Y[N], r = 3;void Init ();

Слайд 59Основная программа
Init(); // начальная расстановка
while (

1 ) // зацикливание ???
{


Draw ( YELLOW ); // рисуем все пузырьки
delay ( 10 ); // ждем 10 мс
Draw ( BLACK ); // стираем все пузырьки
Sdvig ( 4 ); // вверх на 4 пикселя
Zamena(); // если за пределами экрана…
}

if ( kbhit() )
if ( getch() == 27 ) break;

выход по Esc (код 27)

Основная программа Init(); // начальная расстановка while ( 1 ) // зацикливание ???

Слайд 60Процедура Init
void Init()
{
int i;
for ( i = 0; i

< N; i ++ ) {
X[i] = random(600 - 2*r) + r;
Y[i] = random(400 - 2*r) + r;
}
}

Начальная случайная расстановка:


600


Интервал для x: [r, 600-r]

400



Интервал для y: [r, 400-r]

X[i] = random(640 - 2*r) + r;

Y[i] = random(400 - 2*r) + r;

Процедура Initvoid Init(){ int i; for ( i = 0; i < N; i ++ ) {

Слайд 61Процедуры Draw, Sdvig
Рисование и стирание:
void Draw ( int color )
{


int i;
setcolor ( color );
for ( i = 0; i < N; i ++ )
circle ( X[i], Y[i], r );
}

Сдвиг вверх:

void Sdvig ( int dy )
{
int i;
for ( i = 0; i < N; i ++ )
Y[i] -= dy;
}

Процедуры Draw, SdvigРисование и стирание: void Draw ( int color ){ int i; setcolor ( color

Слайд 62Процедура Zamena
Замена вышедших за границы экрана:

400


void Zamena ()
{
int

i;
for ( i = 0; i < N; i ++ )
if ( Y[i] < r ) {
X[i] = random(600 - 2*r) + r;
Y[i] = 400 - r;
}
}

Y[i]< r

Y[i] = 400 - r

Условие выхода:

Перебросить вниз:

if ( Y[i] < r ) { ... }

X[i] = random(600 - 2*r) + r;
Y[i] = 400 – r;

Процедура ZamenaЗамена вышедших за границы экрана: 400void Zamena (){ int i; for ( i = 0;

Слайд 63
Задания
«4»: Моделирование кипения воды в стакане (синий фон, рамка):


«5»: Моделирование двустороннего

потока: часть частиц двигаются влево, часть – вправо.










































Задания«4»: Моделирование кипения воды в стакане (синий фон, рамка):«5»: Моделирование двустороннего потока: часть частиц двигаются влево, часть

Слайд 64Программирование на языке Си Часть II
Тема 8. Символьные строки

Программирование на языке Си Часть IIТема 8. Символьные строки

Слайд 65Чем плох массив символов?
char A[4] = { 'A', '3', '[', 'Ж'};
char

B[10];

Это массивы символов:

Для массива:
каждый символ – отдельный объект;
массив имеет длину N, которая задана при объявлении

Что нужно:
обрабатывать последовательность символов как единое целое
строка должна иметь переменную длину

Чем плох массив символов?char A[4] = { 'A', '3', '[', 'Ж'};char B[10];Это массивы символов:Для массива: каждый символ

Слайд 66Символьные строки
рабочая часть
s[0]
s[1]
s[2]
s[3]
char s[80];
признак окончания строки: символ с кодом 0
Символьная строка

– это последовательность символов, которая заканчивается символом '\0'.
Символьные строкирабочая частьs[0]s[1]s[2]s[3]char s[80];признак окончания строки: символ с кодом 0Символьная строка – это последовательность символов, которая заканчивается

Слайд 67Объявление символьных строк
Объявить строку = выделить ей место в памяти и

присвоить имя.


char s[80];

char s1[80] = "abc";

char qqq[] = "Вася";

выделяется 80 байт, в строке – «мусор» (если она глобальная, то нули '\0‘)

выделяется 80 байт, занято 4 байта (с учетом '\0')

выделяется 5 байт
(с учетом '\0')

Объявление символьных строкОбъявить строку = выделить ей место в памяти и присвоить имя.char s[80]; char s1[80] =

Слайд 68

Ввод и вывод символьных строк
Задача: ввести слово с клавиатуры и заменить

все буквы «а» на буквы «б».

main()
{
char q[80];
int i;
printf("Введите строку\n");
scanf( "%s", q);
i = 0;
while ( q[i] != '\0' ) {
if ( q[i] == 'а' ) q[i] = 'б';
i ++;
}
printf ( "Результат: %s ", q );
}

%s

не надо ставить &:
q ⇔ &q[0]

%s – формат для ввода и вывода символьных строк (выводится только часть до '\0'

"%s"

пока не дошли до конца строки

переход к следующему символу

начали с q[0]

Ввод и вывод символьных строкЗадача: ввести слово с клавиатуры и заменить все буквы «а» на буквы «б».main(){

Слайд 69Ввод одного слова:



Ввод строки с пробелами:
char q[80];
printf ("Введите текст:\n");
scanf ( "%s",

q );
printf ("Введено:\n%s", q );

Ввод символьных строк

Введите текст:
Вася пошел гулять
Введено: Вася

char q[80];
printf("Введите текст:\n");
gets ( q );
printf("Введено:\n%s", q );

Введите текст:
Вася пошел гулять
Введено: Вася пошел гулять

gets ( q );

Ввод одного слова:Ввод строки с пробелами:char q[80];printf (

Слайд 70Универсальный способ:



Только для одной строки:
printf ( "Результат: %s", q );
Вывод символьных

строк

puts ( q );

можно выводить сразу и другую информацию: надписи, значения переменных, …

вывод только одной строки
после вывода – переход на новую строку

printf ( "%s\n", q );


Универсальный способ:Только для одной строки:printf (

Слайд 71
Задания
«4»: Ввести символьную строку и заменить все буквы "а" на буквы

"б" и наоборот, как заглавные, так и строчные.
Пример:
Введите строку:
ааббссААББСС
Результат:
ббаассББААСС
«5»: Ввести символьную строку и проверить, является ли она палиндромом (палиндром читается одинаково в обоих направлениях).
Пример: Пример:
Введите строку: Введите строку:
АБВГДЕ КАЗАК
Результат: Результат:
Не палиндром. Палиндром.
Задания«4»: Ввести символьную строку и заменить все буквы

Слайд 72Функции для работы со строками
Длина строки: strlen (string length)
Подключение библиотеки:
#include
char

q[80] = "qwerty";
int n;
n = strlen ( q );

n = 6

Функции для работы со строкамиДлина строки: strlen (string length)Подключение библиотеки:#include char q[80] =

Слайд 73Сравнение строк
char q1[80], q2[80];
int n;
gets ( q1 );
gets ( q2 );
n

= strcmp ( q1, q2 );

strcmp (string comparison):





Сравнение строкchar q1[80], q2[80];int n;gets ( q1 );gets ( q2 );n = strcmp ( q1, q2 );strcmp

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

Программа должна работать только при вводе правильного пароля.
Идея решения:
проверка пароля – через strcmp
количество слов = количеству первых букв слова
первая буква: пробел и за ним «не пробел»


исключение: предложение начинается со слова (а не с пробела)



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

Слайд 75Проверка пароля


#include
main()
{
char secret[] = "123", pass[20];
printf ( "Введите

пароль\n" );
gets ( pass );
if ( strcmp ( pass, secret ) != 0 )
{
printf ( "Пароль неверный" );
getch ();
return 1;
}
...
}

если пароль неверный...

сообщить об ошибке и выйти из программы

аварийное завершение, код ошибки 1

Проверка пароля#include main(){ char secret[] =

Слайд 76Основная часть программы


#include
#include
main()
{
char q[80];
int i, len,

count = 0;
... // проверка пароля
printf ("Введите предложение\n");
gets ( q );
len = strlen( q );
if ( q[0] != ' ') count++;
for ( i = 0; i < len - 1; i ++ )
if ( q[i] == ' ' && q[i+1] != ' ' )
count ++;
printf ( "Найдено %d слов", count );
}

особый случай

если нашли пробел, а за ним не пробел…

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

Основная часть программы#include #include main(){ char q[80]; int i, len, count = 0; ... // проверка пароля

Слайд 77Подсказка: для вывода одного символа используйте функцию putchar(символ). Например:

Задания (везде –

с паролем!)

«4»: Ввести предложение и определить, сколько слов заканчиваются на букву 'а'.
Пример:
Введите предложение: Введите предложение:
Мама мыла раму Декан пропил бутан Найдено слов: 2 Нет таких слов
«5»: Ввести предложение и разобрать его на отдельные слова:
Пример:
Введите предложение:
Мама мыла раму
Результат:
Мама
мыла
раму

putchar(q[i]);
putchar('\n'); // переход на новую строку

Подсказка: для вывода одного символа используйте функцию putchar(символ). Например:Задания (везде – с паролем!)«4»: Ввести предложение и определить,

Слайд 78Копирование строк
strcpy (string copy)
char q1[10] = "qwerty", q2[10] = "01234";

strcpy (

q1, q2 );

куда

откуда


копирование «хвоста» строки

char q1[10] = "qwerty", q2[10] = "01234";
strcpy ( q1, q2+2 );

q2

q1

q2 = &q2[0]

q2+2 = &q2[2]


Копирование строкstrcpy (string copy)char q1[10] =

Слайд 79Копирование строк
копирование в середину строки
char q1[10] = "qwerty", q2[10] = "01234";
strcpy

( q1+2, q2 );

q2

q1

q1+2 = &q1[2]


char q1[10] = "qwerty", q2[10] = "01234";
strcpy ( q1+2, q2+3 );

q2

q1

q2+3 = &q2[3]


q1+2 = &q1[2]

Копирование строккопирование в середину строкиchar q1[10] =

Слайд 80Копирование строк
strncpy – копирование нескольких символов
char q1[10] = "qwerty", q2[10] =

"01234";
strncpy ( q1+2, q2, 2 );

q2

q1

q1+2 = &q1[2]


Слайд 81Копирование строк
копирование строки-константы
char q1[10] = "qwerty";
strcpy ( q1+1, "ABCD");
q1

char q1[10] =

"qwerty";
strcpy ( "ABCD", q1+2 );


НЕ

Копирование строккопирование строки-константыchar q1[10] =

Слайд 82Копирование строк
копирование внутри одной строки
char q[10] = "012345";
strcpy ( q, q+2

);

q

char q[10] = "012345";
strcpy ( q+2, q );


q







Зацикливание и зависание компьютера!


Копирование строккопирование внутри одной строкиchar q[10] =

Слайд 83Объединение строк
strcat (string concatenation) = копирование второй строки в конец первой
char

q1[10] = "qwe", q2[10] = "0123";
strcat ( q1, q2 );

q2

q1


char q1[10] = "qwe", q2[10] = "0123";
strcat ( q1, q2+2 );

q2

q1


Объединение строкstrcat (string concatenation) = копирование второй строки в конец первойchar q1[10] =

Слайд 84что-то другое
Проблемы при копировании строк
char q1[] = "qwer", q2[10] = "01234";
strcpy

( q1+2, q2 );

не хватает места для строки-результата

q2

q1


зацикливание при копировании в ту же строку «слева направо»

char q[10] = "01234";
strcpy ( q+2, q );

что-то другоеПроблемы при копировании строкchar q1[] =

Слайд 85Пример решения задачи
Задача: ввести имя файла (без пути) и поменять его

расширение на ".exe".
Пример:
Введите имя файла: Введите имя файла:
vasya.html vasya
Результат: Результат:
vasya.exe vasya.exe
Алгоритм:
найти точку в имени файла
если она есть, скопировать в это место строку-константу ".exe"
если точки нет, добавить в конец строки ".exe"
Пример решения задачиЗадача: ввести имя файла (без пути) и поменять его расширение на

Слайд 86Программа



main()
{
char fName[80];
int i;
printf("Введите имя файла\n");
gets ( fName );
i = 0;
while ( fName[i]

!= '.' ) {
if ( fName[i] == '\0' ) break;
i ++;
}
if ( fName[i] == '.' )
strcpy ( fName+i, ".exe" );
else strcat ( fName, ".exe" );
puts ( "Результат:" );
puts ( fName );
}

поиск точки

дошли до конца строки

меняем или добавляем расширение

Программаmain(){char fName[80];int i;printf(

Слайд 87
Задания
«4»: Ввести полный адрес файла (возможно, без расширения) и изменить его

расширение на «.exe».
Пример:
Введите имя файла: Введите имя файла:
C:\DOC.TXT\qqq C:\DOC.TXT\qqq.com
Результат: Результат:
C:\DOC.TXT\qqq.exe C:\DOC.TXT\qqq.exe
«5»: Ввести в одной строке фамилию, имя и отчество. Вывести приветствие, где останутся имя и фамилия (см. пример).
Пример:
Введите ФИО:
Пупкин Василий Иванович
Результат:
Привет, Василий Пупкин!
Задания«4»: Ввести полный адрес файла (возможно, без расширения) и изменить его расширение на «.exe». Пример: Введите

Слайд 88Поиск в символьных строках
Задача: найти заданный символ или сочетание символов (подстроку)

в символьной строке.

Указатель – это переменная в которую можно записать адрес другой переменной заданного типа.

Поиск в символьных строкахЗадача: найти заданный символ или сочетание символов (подстроку) в символьной строке.Указатель – это переменная

Слайд 89Указатели
char *p; // адрес любого символа или строки
int *pI;

// адрес целого числа
float *pF; // адрес вещественного числа

Объявление:

Целые переменные и массивы:

int n = 6, A[5] = {0, 1, 2, 3, 4};
int *p; // указатель на целое
p = &n; // записать адрес n
*p = 20; // n = 20
p = A + 2; // записать адрес A[2] (&A[2])
*p = 99; // изменить A[2]
p ++; // перейти к A[3]
printf("Адрес: %p, число %d", p, *p);

Адрес: 6BCD:000C, значение 3

pointer – указатель

Указателиchar *p; // адрес любого символа или строкиint *pI; // адрес целого числаfloat *pF; //

Слайд 90Указатели и символьные строки
char str[10] = "0123456";
char *p;


p = str;
*p = 'A';
p ++;
*p = 'B';
p ++;
strcpy ( p, "CD" );
strcat ( p, "qqq" );
puts ( p );

// указатель на символ
// или & str[0]
// "A12345"
// перейти к str[1]
// "AB2345“
// перейти к str[2]
// "ABCD"
// "ABCDqqq"

Указатели и символьные строкиchar str[10] =

Слайд 91Поиск символа
strchr: найти первый заданный символ c начала строки
strrchr: найти последний

заданный символ в строке

char q[10] = "abcdabcd";
char *p;
int nomer;
p = strchr(q, 'b');
if ( p == NULL )
printf ( "Не нашли..." );
else {
nomer = p – q;
printf ( "Номер символа %d", nomer );
}

q

q+1

q+5

p


reverse

Поиск символаstrchr: найти первый заданный символ c начала строкиstrrchr: найти последний заданный символ в строкеchar q[10] =

Слайд 92Поиск подстроки
strstr: найти первую подстроку c начала строки
char q[10] = "abcdabcd";
char

*p;
int nomer;
p = strstr(q, "bcd");
if ( p == NULL )
printf ( "Не нашли..." );
else {
nomer = p – q;
printf ( "Номер первого символа %d", nomer );
}

q

q+1

q+5

p

Поиск подстрокиstrstr: найти первую подстроку c начала строкиchar q[10] =

Слайд 93Пример решения задачи
Задача: ввести предложение и определить, сколько раз в нем

встречается имя «Вася».
Проблема: функция strstr ищет только с начала строки.
Алгоритм:
Записать адрес начала строки в указатель start.
Искать подстроку «Вася», начиная с адреса start.

Если не нашли, выход из цикла.
Увеличить счетчик найденных слов.
Переставить start на адрес после найденного слова.
Перейти к шагу 2.

start






p






p = strstr( start, "Вася");

Пример решения задачиЗадача: ввести предложение и определить, сколько раз в нем встречается имя «Вася». Проблема: функция strstr

Слайд 94Программа


main()
{
char q[80], *start, *p;
int count = 0;
puts

( "Введите предложение" );
gets ( q );
start = q; // ищем с начала строки
while ( 1 ) {
p = strstr ( start, "Вася" );
if ( p == NULL ) break;
count ++;
start = p + 4; // отсюда ищем следующее слово
}
printf ( "Имя 'Вася' встречается %d раз", count );
}

начало поиска

адрес найденного слова

Программаmain(){ char q[80], *start, *p; int count = 0; puts (

Слайд 95
Задания
«4»: Ввести предложение и заменить все имена «Вася» на «Юра».

Пример:
Введите предложение:
Вася, Вася, Вася и Вася!!!
Результат:
Юра, Юра, Юра и Юра!!!
«5»: Ввести предложение и заменить все имена «Юра» на «Вася».
Пример:
Введите предложение:
Юра, Юра, Юра и Юра!!!
Результат:
Вася, Вася, Вася и Вася!!!
Задания«4»: Ввести предложение и заменить все имена «Вася» на «Юра». Пример: Введите предложение: Вася, Вася, Вася

Слайд 96Строки в процедурах и функциях
Задача: составить процедуру, которая переставляет символы строки

в обратном порядке.
Алгоритм:
определить длину строки len;
все символы первой половины переставить с соответствующими символами второй половины:

c = s[i];
s[i] = s[len-i-1];
s[len-1-i] = c;

s[i]

s[len-1-i]


Строки в процедурах и функцияхЗадача: составить процедуру, которая переставляет символы строки в обратном порядке. Алгоритм:определить длину строки

Слайд 97Программа
void Reverse ( char s[] )
{
int len = strlen(s);
char

c;
for ( i = 0; i < len/2; i ++ ) {
c = s[i];
s[i] = s[len-i-1];
s[len-1-i] = c;
}
}
main()
{
char s[] = "1234567890";
Reverse ( s );
puts ( s );
Reverse ( s + 5 );
puts ( s );
}

0987654321

0987612345

длину строки определяем на месте

Программаvoid Reverse ( char s[] ){ int len = strlen(s); char c; for ( i = 0;

Слайд 98
Задания
«4»: Разработать процедуру, которая переставляет пары соседних символов.
Пример:
Введите

предложение:
Вася пошел гулять!
Результат:
аВясп шолег лутя!ь
«5»: Разработать процедуру, которая удаляет все лишние пробелы (в начале предложения и сдвоенные пробелы).
Пример:
Введите предложение:
Вася пошел гулять!
Результат:
Вася пошел гулять!
Задания«4»: Разработать процедуру, которая переставляет пары соседних символов. Пример: Введите предложение: Вася пошел гулять! Результат: аВясп

Слайд 99Символьные строки в функциях
Задача: составить функцию, которая находит количество цифр в

строке.

int NumDigits ( char s[] )
{
int i, count = 0;
for ( i = 0; i < strlen(s); i ++ )
if( strchr ( "0123456789", s[i] ) )
count ++;
return count;
}

if ( strchr ( "0123456789", s[i] ) != NULL )
или
if ( '0' <= s[i] && s[i] <= '9' )

Символьные строки в функцияхЗадача: составить функцию, которая находит количество цифр в строке. int NumDigits ( char s[]

Слайд 100Символьные строки в функциях
Основная программа
int NumDigits ( char s[] )
{
...
}
main()
{
char

s[80];
int n;
printf ( "Введите строку\n" );
gets ( s );
n = NumDigits ( s );
printf ( "Нашли %d цифр.", s );
}
Символьные строки в функцияхОсновная программаint NumDigits ( char s[] ){...}main(){ char s[80]; int n; printf (

Слайд 101
Задания
«4»: Разработать функцию, которая определяет, верно ли, что слово – палиндром.

Пример:
Введите слово: Введите слово:
казак кунак
Результат: Результат:
Это палиндром. Не палиндром.
«5»: Разработать функцию, которая определяет, верно ли, что предложение (с пробелами) – палиндром.
Пример:
Введите предложение:
а роза упала на лапу азора
Результат:
Это палиндром.
Задания«4»: Разработать функцию, которая определяет, верно ли, что слово – палиндром. Пример: Введите слово: Введите слово:

Слайд 102Программирование на языке Си Часть II
Тема 9. Рекурсивный перебор

Программирование на языке Си Часть IIТема 9. Рекурсивный перебор

Слайд 103Рекурсивный перебор
Задача: Алфавит языка племени «тумба-юмба» состоит из букв Ы, Ц,

Щ и О. Вывести на экран все слова из К букв, которые можно составить в этом языке, и подсчитать их количество. Число K вводится с клавиатуры.

0

K-1

в каждой ячейке может быть любая из 4-х букв

4 варианта

4 варианта

4 варианта

4 варианта

Количество вариантов:

Рекурсивный переборЗадача: Алфавит языка племени «тумба-юмба» состоит из букв Ы, Ц, Щ и О. Вывести на экран

Слайд 104Рекурсивный перебор
0
K-1
Рекурсия: Решения задачи для слов из К букв сводится к

4-м задачам для слов из K-1 букв.

0

K-1

0

K-1

0

K-1


перебрать все варианты


перебрать все варианты


перебрать все варианты


перебрать все варианты

Рекурсивный перебор0K-1Рекурсия: Решения задачи для слов из К букв сводится к 4-м задачам для слов из K-1

Слайд 105Процедура

0
K-1
p
Глобальные переменные:
char s[80];
int count, K;
s


p+1
рекурсивные вызовы
окончание рекурсии
void Rec( int

p )
{
if ( p >= K ) {
puts ( s );
count ++;
return;
}
s[p] = 'Ы'; Rec ( p + 1 );
s[p] = 'Ц'; Rec ( p + 1 );
s[p] = 'Щ'; Rec ( p + 1 );
s[p] = 'О'; Rec ( p + 1 );
}

p символов уже на своих местах

Процедура0K-1pГлобальные переменные: char s[80]; int count, K;sp+1рекурсивные вызовыокончание рекурсииvoid Rec( int p ){ if ( p >=

Слайд 106Процедура
void Rec ( int p )
{
const char letters[] = "ЫЦЩО";

int i;
if ( p >= K ) {
puts ( s );
count ++;
return;
}
for ( i = 0; i < strlen(letters); i ++) {
s[p] = letters[i];
Rec ( p + 1 );
}
}

const char letters[] = 'ЫЦЩО';

for ( i = 0; i < strlen(letters); i ++) {
s[p] = letters[i];
Rec ( p + 1 );
}

все буквы

цикл по всем буквам

локальная переменная

= K ) { puts ( s ); count ++; return; } for ( i = 0; i < strlen(letters); i ++) { s[p] = letters[i]; Rec ( p + 1 ); }}const char letters[] = 'ЫЦЩО';for ( i = 0; i < strlen(letters); i ++) { s[p] = letters[i]; Rec ( p + 1 ); }все буквыцикл по всем буквамлокальная переменная">Процедураvoid Rec ( int p ){ const char letters[] = =">

Слайд 107Программа
char s[80];
int K, count = 0;

main()
{
printf ( "Введите длину слов:\n"

);
scanf ( "%d", &K );
Rec ( 0 );
printf ( "Всего %d слов.", count );
}

void Rec ( int p )
{
...
}

процедура

глобальные переменные
(обнуляются)

count;

Программаchar s[80];int K, count = 0;main(){ printf (

Слайд 108
Задания
Алфавит языка племени "тумба-юмба" состоит из букв Ы, Ц, Щ и

О. Число K вводится с клавиатуры.

«4»: Вывести на экран все слова из К букв, в которых буква Ы встречается более 1 раза, и подсчитать их количество.
«5»: Вывести на экран все слова из К букв, в которых есть одинаковые буквы, стоящие рядом (например, ЫЩЩО), и подсчитать их количество.

ЗаданияАлфавит языка племени

Слайд 109Программирование на языке Си Часть II
Тема 10. Матрицы

Программирование на языке Си Часть IIТема 10. Матрицы

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

c6
A[5][2]

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

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

котором каждый элемент имеет два индекса (номер строки и номер столбца).

A

строка 1

столбец 2

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

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

Слайд 112Матрицы
Объявление:
const int N = 3, M = 4;
int A[N][M];
float a[2][2] =

{{3.2, 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 ++ ) {

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

Слайд 113Матрицы
Заполнение случайными числами
for ( i = 0; i < N; i

++ )
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]);

вывод строки


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

МатрицыЗаполнение случайными числамиfor ( i = 0; i < N; i ++ ) for ( j =

Слайд 114Обработка всех элементов матрицы
Задача: заполнить матрицу из 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];

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

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

интервале [-10,10] и вывести ее на экран.

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

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

Слайд 116Операции с матрицами
Задача 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

Операции с матрицамиЗадача 1. Вывести на экран главную диагональ квадратной матрицы из N строк и N столбцов.A[0][N-1]A[1][1]A[2][2]A[N-1][N-1]for

Слайд 117Операции с матрицами
Задача 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

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

Слайд 118Операции с матрицами
Задача 4. Перестановка строк или столбцов. В матрице из

N строк и 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];

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

Слайд 119
Задания
Заполнить матрицу из 7 строк и 7 столбцов случайными числами в

интервале [-10,10] и вывести ее на экран. Обнулить элементы, отмеченные зеленым фоном, и вывести полученную матрицу на экран.

«4»: «5»:

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

Слайд 120Программирование на языке Си Часть II
Тема 11. Файлы

Программирование на языке Си Часть IIТема 11. Файлы

Слайд 121Файлы
Файл – это область на диске, имеющая имя.
Файлы
только текст без оформления, не

содержат управляющих символов (с кодами < 32), кроме перевода строки

ACSII (1 байт на символ)
UNICODE (2 байта на символ)

*.txt, *.log,
*.htm, *.html

могут содержать любые символы кодовой таблицы

*.doc, *.exe,
*.bmp, *.jpg,
*.wav, *.mp3,
*.avi, *.mpg

Текстовые

Двоичные

Папки (каталоги)

ФайлыФайл – это область на диске, имеющая имя.Файлытолько текст без оформления, не содержат управляющих символов (с кодами

Слайд 122Принцип сэндвича

I этап. открыть файл (сделать его активным, приготовить к работе)

f

= fopen("qq.dat", "r");

II этап: работа с файлом

III этап: закрыть (освободить) файл

fclose ( f );


fscanf ( f, "%d", &n ); // ввести значение n

fprintf( f, "n=%d", n ); // записать значение n

для чтения ("r", англ. read)

f = fopen("qq.dat", "w");

для записи ("w", англ. write)

f = fopen("qq.dat", "a");

для добавления ("a", англ. append)

Переменная типа «указатель на файл»: FILE *f;

Принцип сэндвичаI этап. открыть файл (сделать его активным, приготовить к работе)f = fopen(

Слайд 123Работа с файлами
Особенности:
имя файла упоминается только в команде fopen, обращение к

файлу идет через указатель f;
файл, который открывается на чтение, должен существовать
если файл, который открывается на запись, существует, старое содержимое уничтожается
данные (этим способом) записываются в файл в текстовом виде
когда программа заканчивает работу, все файлы закрываются автоматически
после закрытия файла переменную f можно использовать еще раз для работы с другим файлом
Работа с файламиОсобенности:имя файла упоминается только в команде fopen, обращение к файлу идет через указатель f;файл, который

Слайд 124Последовательный доступ
при открытии файла курсор устанавливается в начало
чтение выполняется с той

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

12 5 45 67 56●

конец файла
(end of file, EOF)


12 5 45 67 56●

f = fopen("qq.dat", "r");

fscanf ( f, "%d", &x );












Последовательный доступпри открытии файла курсор устанавливается в началочтение выполняется с той позиции, где стоит курсорпосле чтения курсор

Слайд 125Ошибки при открытии файла
FILE *f;
f = fopen("qq.dat", "r");
if ( f ==

NULL ) {
puts("Файл на найден.");
return;
}

NULL

неверное имя файла
нет файла
файл заблокирован другой программой

Если файл открыть не удалось, функция fopen возвращает NULL (нулевое значение)!

!

FILE *f;
f = fopen("qq.dat", "w");
if ( f == NULL ) {
puts("Не удалось открыть файл.");
return;
}

NULL

неверное имя файла
файл «только для чтения»
файл заблокирован другой программой

Ошибки при открытии файлаFILE *f;f = fopen(

Слайд 126
Пример
Задача: в файле input.txt записаны числа (в столбик), сколько их –

неизвестно. Записать в файл output.txt их сумму.
Алгоритм:
Открыть файл input.txt для чтения.
S = 0;
Прочитать очередное число в переменную x.
Если не удалось, перейти к шагу 7.
S += x;
Перейти к шагу 3.
Закрыть файл input.txt.
Открыть файл output.txt для записи.
Записать в файл значение S.
Закрыть файл output.txt.

цикл с условием «пока есть данные»

ПримерЗадача: в файле input.txt записаны числа (в столбик), сколько их – неизвестно. Записать в файл output.txt их

Слайд 127Как определить, что числа кончились?
FILE *f;
int n, x;
f = fopen("input.txt", "r");
...
n

= fscanf ( f, "%d", &x );
if ( n ! = 1 )
puts ( "Не удалось прочитать число" );

дошли до конца файла
встретили «не число»

Как определить, что числа кончились?FILE *f;int n, x;f = fopen(

Слайд 128Программа




main()
{
FILE *f;
int n, x, S = 0;
f = fopen ( "input.txt",

"r" );
if ( f == NULL ) {
printf("Файл не найден.");
return;
}
while ( 1 ) {
n = fscanf ( f, "%d", &x );
if ( n != 1 ) break;
S += x;
}
fclose ( f );
f = fopen ( "output.txt", "w" );
fprintf ( f, "S = %d", S );
fclose ( f );
}

ошибка при открытии файла

цикл чтения данных: выход при n ≠ 1.

запись результата

Программаmain(){FILE *f;int n, x, S = 0;f = fopen (

Слайд 129
Задания
В файле input.txt записаны числа, сколько их – неизвестно.
«4»: Найти

среднее арифметическое всех чисел и записать его в файл output.txt.
«5»: Найти минимальное и максимальное числа и записать их в файл output.txt.
ЗаданияВ файле input.txt записаны числа, сколько их – неизвестно. «4»: Найти среднее арифметическое всех чисел и записать

Слайд 130Обработка массивов
Задача: в файле input.txt записаны числа (в столбик), сколько их

– неизвестно, но не более 100. Переставить их в порядке возрастания и записать в файл output.txt.
Проблемы:
для сортировки надо удерживать в памяти все числа сразу (массив);
сколько чисел – неизвестно.
Решение:
выделяем в памяти массив из 100 элементов;
записываем прочитанные числа в массив и считаем их в переменной N;
сортируем первые N элементов массива;
записываем их в файл.
Обработка массивовЗадача: в файле input.txt записаны числа (в столбик), сколько их – неизвестно, но не более 100.

Слайд 131

Чтение данных в массив
int ReadArray ( int A[], char fName[],

int MAX )
{
int N = 0, k;
FILE *f;
f = fopen ( fName, "r" );
while ( 1 ) {
k = fscanf ( f, "%d", &A[N]);
if ( k != 1 ) break;
N ++;
if ( N >= MAX ) break;
}
fclose(f);
return N;
}

Функция, которая читает массив из файла, возвращает число прочитанных элементов (не более MAX):

массив

заканчиваем цикл если не удалось прочитать …

имя файла

предел

… или заполнили весь массив

= MAX ) break; } fclose(f); return N; }Функция, которая читает массив из файла, возвращает число прочитанных элементов (не более MAX):массивзаканчиваем цикл если не удалось прочитать …имя файлапредел… или заполнили весь массив">Чтение данных в массив int ReadArray ( int A[], char fName[], int MAX ) { int

Слайд 132Программа


main()
{
int A[100], N, i;
FILE *f;
N = ReadArray (

A, "input.txt", 100 );
... // сортировка первых N элементов
f = fopen("output.txt", "w");
for ( i = 0; i < N; i ++)
fprintf ( f, "%d\n", A[i] );
fclose ( f );
}

int ReadArray(int A[], char fName[], int MAX)
{
...
}

вывод отсортированного массива в файл

Программаmain(){ int A[100], N, i; FILE *f; N = ReadArray ( A,

Слайд 133
Задания
В файле input.txt записаны числа (в столбик), известно, что их не

более 100.

«4»: Отсортировать массив по убыванию последней цифры и записать его в файл output.txt.
«5»: Отсортировать массив по возрастанию суммы цифр и записать его в файл output.txt.

ЗаданияВ файле input.txt записаны числа (в столбик), известно, что их не более 100. «4»: Отсортировать массив по

Слайд 134Обработка текстовых данных
Задача: в файле input.txt записаны строки, в которых есть

слово-паразит "короче". Очистить текст от мусора и записать в файл output.txt.
Файл input.txt :
Мама, короче, мыла, короче, раму.
Декан, короче, пропил, короче, бутан.
А роза, короче, упала на лапу, короче, Азора.
Каждый, короче, охотник желает, короче, знать, где ...
Результат – файл output.txt :
Мама мыла раму.
Декан пропил бутан.
А роза упала на лапу Азора.
Каждый охотник желает знать, где сидит фазан.
Обработка текстовых данныхЗадача: в файле input.txt записаны строки, в которых есть слово-паразит

Слайд 135
Обработка текстовых данных
Особенность:
надо одновременно держать открытыми два файла (один в

режиме чтения, второй – в режиме записи).

Алгоритм:
Открыть оба файла.
Прочитать строку.
Удалить все сочетания ", короче,".
Записать строку во второй файл.
Перейти к шагу 2.
Закрыть оба файла.

пока не кончились данные

Обработка текстовых данныхОсобенность: надо одновременно держать открытыми два файла (один в режиме чтения, второй – в режиме

Слайд 136Работа с файлами
main()
{
char s[80], *p;
int i;
FILE *fIn,

*fOut;
fIn = fopen("input.txt", "r");
fOut = fopen("output.txt", "w");
... // обработать файл
fclose(fIn);
fclose(fOut);
}

файловые указатели

открыть файл для чтения

открыть файл для записи

указатель для поиска

закрыть файлы

Работа с файламиmain(){ char s[80], *p; int i; FILE *fIn, *fOut; fIn = fopen(

Слайд 137Обработка текстовых данных
Чтение строки s:
while ( 1 ) {

p = strstr ( s, ", короче," );
if ( p == NULL ) break;
strcpy ( p, p + 9 );
}

искать ", короче,"

удалить 9 символов

выйти из цикла, если не нашли

char s[80], *p;
FILE *fIn;
... // здесь надо открыть файл

p = fgets ( s, 80, fIn );
if ( p == NULL )
printf("Файл закончился.");
else printf("Прочитана строка:\n%s", s);

Обработка строки s:

строка

длина

файл

Обработка текстовых данныхЧтение строки s: while ( 1 ) { p = strstr ( s,

Слайд 138 #include
Полный цикл обработки файла
while ( 1 )

{
p = fgets ( s, 80, fIn );
if ( p == NULL ) break;
while ( 1 ) {
p = strstr ( s, ", короче," );
if ( p == NULL ) break;
strcpy ( p, p + 9 );
}
fputs ( s, fOut );
}

while ( 1 ) {
p = strstr ( s, ", короче," );
if ( p == NULL ) break;
strcpy ( p, p + 9 );
}

если нет больше строк, выйти из цикла

обработка строки

запись "очищенной" строки

читаем строку

#include Полный цикл обработки файла while ( 1 ) { p = fgets (

Слайд 139
Задания
В файле input.txt записаны строки, сколько их – неизвестно.
«4»: Заменить

во всем тексте «в общем» на «короче» и записать результат в файл output.txt.
«5»: Заменить во всем тексте «короче» на «в общем» и записать результат в файл output.txt.
ЗаданияВ файле input.txt записаны строки, сколько их – неизвестно. «4»: Заменить во всем тексте «в общем» на

Слайд 140Двоичные файлы
Особенности:
данные хранятся во внутреннем машинном формате (в текстовом редакторе не

прочитать)
можно читать и записывать любой кусок памяти (просто биты…)
принцип сэндвича (открыть – работать – закрыть)
обращение к файлу через указатель

Файловые указатели

FILE *fp;

Двоичные файлыОсобенности:данные хранятся во внутреннем машинном формате (в текстовом редакторе не прочитать)можно читать и записывать любой кусок

Слайд 141Открытие и закрытие двоичных файлов
Открытие файла
fp = fopen ( "input.dat",

"rb" );

"rb" = read binary (чтение)
"wb" = write binary (запись)
"ab" = append binary (добавление)

Ошибки при открытии

if ( fp == NULL ) { printf("Файл открыть не удалось.");
}

Закрытие файла

fclose ( fp );

Открытие и закрытие двоичных файловОткрытие файла fp = fopen (

Слайд 142Чтение по блокам
Чтение в начало массива
int A[100];
n = fread (

A, sizeof(int), 100, fp );

адрес области памяти («куда»):
A ⇔ &A[0]

размер одного блока

размер переменной целого типа

количество блоков

указатель на файл

прочитано фактически

Чтение в середину массива

int A[100];
n = fread ( A+5, sizeof(int), 2, fp );


читается 2 целых числа:
A[5], A[6]

Чтение по блокамЧтение в начало массива int A[100];n = fread ( A, sizeof(int), 100, fp ); адрес

Слайд 143Запись по блокам
Запись с начала массива
int A[100];
n = fwrite( A,

sizeof(int), 100, fp );

адрес области памяти («откуда»):
A ⇔ &A[0]

размер одного блока

размер переменной целого типа

количество блоков

указатель на файл

записано фактически

Запись отдельных элементов массива

int A[100];
n = fwrite( A+5, sizeof(int), 2, fp );


записывается 2 целых числа:
A[5], A[6]

Запись по блокамЗапись с начала массива int A[100];n = fwrite( A, sizeof(int), 100, fp ); адрес области

Слайд 144Работа с матрицами
Хранение в памяти: по строкам (Си, Паскаль)

Запись матрицы
int A[3][3];
FILE

*fp = fopen("output.dat", "wb");
... // здесь заполняем матрицу
n = fwrite( A, sizeof(int), 9, fp );
Работа с матрицамиХранение в памяти: по строкам (Си, Паскаль)Запись матрицыint A[3][3];FILE *fp = fopen(

Слайд 145Пример
Задача: прочитать массив из файла input.dat, умножить все элементы на 2

и вывести в файл output.dat.
Структура программы:

#include
main()
{
const int N = 10;
int i, A[N], n;
FILE *fp;
// чтение данных и файла input.dat
for ( i = 0; i < n; i ++ )
A[i] = A[i] * 2;
// запись данных в файл output.dat
}

прочитано фактически

ПримерЗадача: прочитать массив из файла input.dat, умножить все элементы на 2 и вывести в файл output.dat.Структура программы:#include

Слайд 146Работа с файлами
fp = fopen( "input.dat", "rb" );
if ( fp ==

NULL ) {
printf("Файл открыть не удалось.");
return;
}
n = fread ( A, sizeof(int), N, fp );
if ( n < N ) printf("Не хватает данных в файле");
fclose ( fp );

Чтение данных:

fp = fopen( "output.dat", "wb" );
fwrite ( A, sizeof(int), n, fp );
fclose ( fp );

Запись данных:

критическая ошибка

некритическая ошибка

сколько прочитали

Работа с файламиfp = fopen(

Слайд 147
Задания
«4»: В текстовом файле input.txt записан массив целых чисел. Отсортировать его

и записать в двоичный файл output.dat.
«5»: В текстовых файлах input1.txt и input2.txt записаны два массива. Объединить их в один массив, отсортировать и записать результат в двоичный файл output.dat.
Задания«4»: В текстовом файле input.txt записан массив целых чисел. Отсортировать его и записать в двоичный файл output.dat.«5»:

Слайд 148Конец фильма

Конец фильма
Скачать презентацию

Похожие презентации

Презентация по информатике Представление информации Презентация по информатике Представление информации 194
Презентация к уроку по информатике и икт (8 класс) на тему: Геометрия в Лого Презентация к уроку по информатике и икт (8 класс) на тему: Геометрия в Лого 204
Презентация к уроку Работа над проектом. Подготовка графических материалов (3 класс)) Презентация к уроку Работа над проектом. Подготовка графических материалов (3 класс)) 279
Презентация ВНЕДРЕНИЕ НОВЫХ ИННОВАЦИОННЫХ ТЕХНОЛОГИЙ В ОБРАЗОВАТЕЛЬНЫЙ ПРОЦЕСС Презентация ВНЕДРЕНИЕ НОВЫХ ИННОВАЦИОННЫХ ТЕХНОЛОГИЙ В ОБРАЗОВАТЕЛЬНЫЙ ПРОЦЕСС 241
Игра Занимательная информатика Игра Занимательная информатика 279
Презентация по информатике Вирусы и антивирусы, 7 класс Презентация по информатике Вирусы и антивирусы, 7 класс 376

Что такое shareslide.ru?

Это сайт презентаций, где можно хранить и обмениваться своими презентациями, докладами, проектами, шаблонами в формате PowerPoint с другими пользователями. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами.

Для правообладателей

Яндекс.Метрика

Обратная связь

Email: Нажмите что бы посмотреть