Разделы презентаций


Динамические структуры данных (язык Си) 2 презентация, доклад

Содержание

Программирование на языке Си Часть IIТема 1. Массивы© К.Ю. Поляков, 2007-2009

Слайды и текст этой презентации

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

массиве
Массивы в процедурах и функциях
© К.Ю. Поляков, 2007-2009
Практикум (моделирование)
Символьные строки
Рекурсивный

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

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

Программирование  на языке Си Часть IIТема 1. Массивы© К.Ю. Поляков, 2007-2009

Слайд 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. Обработка массивов
© К.Ю.

Поляков, 2007-2009

Программирование  на языке Си  Часть IIТема 3. Обработка массивов© К.Ю. Поляков, 2007-2009

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

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

Поляков, 2007-2009

Программирование  на языке Си  Часть IIТема 4. Сортировка массивов© К.Ю. Поляков, 2007-2009

Слайд 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. Поиск в массиве
©

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

Программирование  на языке Си  Часть IIТема 5. Поиск в массиве© К.Ю. Поляков, 2007-2009

Слайд 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. Практикум

(моделирование)

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

Программирование  на языке Си  Часть 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. Символьные строки
© К.Ю.

Поляков, 2007-2009

Программирование  на языке Си  Часть IIТема 8. Символьные строки© К.Ю. Поляков, 2007-2009

Слайд 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. Рекурсивный перебор
© К.Ю.

Поляков, 2007-2009

Программирование  на языке Си  Часть IIТема 9. Рекурсивный перебор© К.Ю. Поляков, 2007-2009

Слайд 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 );
}

все буквы

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

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


Слайд 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. Матрицы
© К.Ю. Поляков,

2007-2009

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

Слайд 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. Файлы
© К.Ю. Поляков,

2007-2009

Программирование  на языке Си  Часть IIТема 11. Файлы© К.Ю. Поляков, 2007-2009

Слайд 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):

массив

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

имя файла

предел

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


Слайд 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Конец фильма

Конец фильма

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

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

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

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

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


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

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