1 Программирование на языке Си § 62. Массивы § 63. Алгоритмы обработки массивов § 64. Сортировка § 65. Двоичный поиск § 66. Символьные строки § 67. Матрицы § 68. Работа с файлами
§ 62. Массивы 2
3 Массив – это группа переменных одного типа, расположенных в памяти рядом (в соседних ячейках) и имеющих общее имя. Каждая ячейка в массиве имеет уникальный номер ( индекс). Надо : Как ввести 10000 переменных? ? выделять память записывать данные в нужную ячейку читать данные из ячейки
4 int A[ 5 ]; double V[ 8 ]; bool L[ 10 ]; char S[ 80 ]; Массив = таблица ! ! число элементов const int N = 10 ; int A[ N ] ; размер через константу Зачем? ? Элементы нумеруются с нуля! ! A[0], A[1], A[2], A[3], A[4]
5 5 10 15 20 25 0 1 2 3 4 A массив 2 15 НОМЕР элемента массива (ИНДЕКС) A[ 0 ] A[ 1 ] A[ 2 ] A[ 3 ] A[ 4 ] ЗНАЧЕНИЕ элемента массива A[2] НОМЕР (ИНДЕКС) элемента массива : 2 ЗНАЧЕНИЕ элемента массива : 1 5
6 Объявление : Обработка : const int N = 5 ; int A[N]; // обработать A[0] // обработать A[1] // обработать A[2] // обработать A[3] // обработать A[4] 1) если N велико (1000, 1000000)? 2) при изменении N программа не должна меняться! ?
7 Обработка с переменной: i = 0 ; // обработать A[ i ] i ++; // обработать A[ i ] i ++; // обработать A[ i ] i ++; // обработать A[ i ] i ++; // обработать A[ i ] i ++; Обработка в цикле: i = 0 ; while ( i < N ) { // обработать A[ i ] i ++; } Цикл с переменной: for( i = 0; i < N; i ++ ) { // обработать A[ i ] }
8 main() { const int N = 10 ; int A[N]; int i ; for ( i = 0 ; i < N; i ++ ) A[ i ] = i * i ; } Чему равен A[9] ? ?
9 Объявление: Ввод с клавиатуры: Вывод на экран: const int N = 10 ; int A[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 printf ( " Массив A:\n" ); for ( i = 0 ; i < N; i ++ ) printf ( "%d ", A[ i ] ); Зачем пробел? ?
10 for ( i = 0 ; i < N; i ++ ) { A[ i ] = irand ( 20, 100 ); printf ( "%d ", A[ i ] ); } Задача. Заполнить массив (псевдо)случайными целыми числами в диапазоне от 20 до 100. int irand ( int a, int b ) { return a + rand()% (b - a + 1 ); }
11 Общая схема: for ( i = 0 ; i < N; i ++ ) { ... // сделать что-то с A[ i ] } Подсчёт нужных элементов: Задача. В массиве записаны данные о росте баскетболистов. Сколько из них имеет рост больше 180 см, но меньше 190 см? count = 0 ; for ( i = 0 ; i < N; i ++ ) if ( 180 < A[ i ] && A[ i ] < 190 ) count ++;
12 Среднее арифметическое: int count, sum; count = 0 ; sum = 0 ; for ( i = 0 ; i < N; i ++ ) if ( 180 < A[ i ] && A[ i ] < 190 ) { count ++; sum += A[ i ]; } printf ( "%f", ( float )sum / count ); среднее арифметическое Зачем float ? ?
13 « A »: Заполните массив случайными числами в интервале [0,100] и найдите среднее арифметическое его значений. Пример : Массив: 1 2 3 4 5 Среднее арифметическое 3.000 « B »: Заполните массив случайными числами в интервале [0,100] и подсчитайте отдельно среднее значение всех элементов, которые <50, и среднее значение всех элементов, которые ≥50. Пример : Массив: 3 2 52 4 60 Ср. арифм. элементов [0,50): 3.000 Ср. арифм. элементов [50,100 ] : 56.000
14 « C »: Заполните массив из N элементов случайными числами в интервале [1,N] так, чтобы в массив обязательно вошли все числа от 1 до N (постройте случайную перестановку). Пример : Массив: 3 2 1 4 5
§ 63. Алгоритмы обработки массивов 15
16 Найти элемент, равный X : i = 0 ; while ( A[ i ] != X ) i ++; printf ( "A[%d]=%d", i, X ); Что плохо? ? i = 0 ; while ( i < N && A[i] != X ) i ++; if ( i < N ) printf ( "A[%d]=%d", i, X ); else printf ( " Не нашли! " ); Что если такого нет? ? i < N
17 nX = -1 ; for ( i = 0 ; i < N; i++ ) if ( A[i] == X ) { nX = i; break ; } if ( nX >= 0 ) printf ( "A[%d]=%d", nX, X ); else printf ( "Не нашли!" ); Вариант с досрочным выходом: break ; досрочный выход из цикла
18 « A »: Заполните массив случайными числами в интервале [0,5]. Введите число X и найдите все значения, равные X. Пример : Массив: 1 2 3 1 2 Что ищем: 2 Нашли: A[2]=2, A[5]=2 Пример : Массив: 1 2 3 1 2 Что ищем: 6 Ничего не нашли.
19 « B »: Заполните массив случайными числами в интервале [0,5]. Определить, есть ли в нем элементы с одинаковыми значениями, стоящие рядом. Пример : Массив: 1 2 3 3 2 1 Есть: 3 Пример : Массив: 1 2 3 4 2 1 Нет
20 « C »: Заполните массив случайными числами. Определить, есть ли в нем элементы с одинаковыми значениями, не обязательно стоящие рядом. Пример : Массив: 3 2 1 3 2 5 Есть: 3, 2 Пример : Массив: 3 2 1 4 0 5 Нет
21 M = A[ 0 ]; for ( i = 1 ; i < N; i ++ ) if ( A[ i ]> M ) M = A[ i ]; printf ( "%d", M ); M = A[ 0 ]; nMax = 0 ; for ( i = 1 ; i < N; i ++ ) if ( A[ i ] > M ) { M = A[ i ]; nMax = i ; } printf ( "A[%d]=%d", nMax, M ); nMax = 0 ; nMax = i ; Что можно улучшить? ? Как найти его номер? ?
22 По номеру элемента можно найти значение! ! nMax = 0 ; for ( i = 1 ; i < N; i ++ ) if ( A[ i ] > A[ nMax ] ) nMax = i ; printf ( "A[%d]=%d", nMax, A[ nMax ] ); A[nMax] A[nMax]
23 « A »: Заполнить массив случайными числами и найти минимальный и максимальный элементы массива и их номера. Пример : Массив: 1 2 3 4 5 Минимальный элемент: A[1]=1 Максимальный элемент: A[5]=5 « B »: Заполнить массив случайными числами и найти два максимальных элемента массива и их номера. Пример : Массив: 5 5 3 4 1 Максимальный элемент: A[1]=5 Второй максимум: A[2]=5
24 « C »: Введите массив с клавиатуры и найдите (за один проход) количество элементов, имеющих максимальное значение. Пример : Массив: 3 4 5 5 3 4 5 Максимальное значение 5 Количество элементов 3
25 0 1 2 3 N-4 N-3 N - 2 N-1 7 12 5 8 18 34 40 23 0 1 2 3 N-4 N-3 N - 2 N-1 23 40 34 18 8 5 12 7 « Простое » решение: for( i = 0; i < N ; i ++ ) { // поменять местами A[ i ] и A[N - 1-i] } N/ 2 Что плохо? ? остановиться на середине!
26 for ( i = 0 ; i < (N/ 2 ); i ++ ) { c = A[ i ]; A[ i ] = A[N- 1 -i]; A[N- 1 -i] = c; } * Как обойтись без переменной c ? ?
0 1 2 3 N-4 N-3 N - 2 N-1 12 5 8 15 34 40 23 7 Циклический сдвиг элементов 27 0 1 2 3 N-4 N-3 N - 2 N-1 7 12 5 8 18 34 40 23 « Простое » решение: c = A[ 0 ]; for ( i = 0 ; i < N- 1 ; i ++ ) A[ i ] = A[i+ 1 ]; A[N- 1 ] = c; Что плохо? ? Почему не до N-1 ? ?
28 « A »: Заполнить массив случайными числами и выполнить циклический сдвиг элементов массива вправо на 1 элемент. Пример : Массив: 1 2 3 4 5 6 Результат: 6 1 2 3 4 5 « B »: Массив имеет четное число элементов. Заполнить массив случайными числами и выполнить реверс отдельно в первой половине и второй половине. Пример : Массив: 1 2 3 4 5 6 Результат: 3 2 1 6 5 4
29 « C »: Заполнить массив случайными числами в интервале [-100,100] и переставить элементы так, чтобы все положительные элементы стояли в начала массива, а все отрицательные и нули – в конце. Вычислите количество положительных элементов. Пример : Массив: 20 -90 15 -34 10 0 Результат: 20 15 10 -90 -34 0 Количество положительных элементов: 3
30 « Простое » решение: Задача. Отобрать элементы массива A, удовлетворяющие некоторому условию, в массив B. сделать для i от 0 до N- 1 если условие выполняется для A[ i ] то B[ i ]:= A[ i ] Что плохо? ? 0 1 2 3 4 5 12 3 34 11 23 46 A 12 ? 34 ? ? 46 B выбрать чётные элементы
31 0 1 2 3 4 5 12 3 34 11 23 46 A 12 34 46 ? ? ? B выбрать чётные элементы count = 0 ; for ( i = 0 ; i < N; i ++ ) if ( A[ i ] % 2 == 0 ) { B[count] = A[ i ]; count ++; } for ( i = 0 ; i < count ; i ++ ) printf ( "%d ", B[ i ] ); count Как вывести на экран? ? Если A и B – один и тот же массив? ? B[count] = A[ i ];
32 « A »: Заполнить массив случайными числами в интервале [-10,10] и отобрать в другой массив все чётные отрицательные числа. Пример : Массив А: -5 6 7 -4 -6 8 -8 Массив B: -4 -6 -8 « B »: Заполнить массив случайными числами в интервале [0,100] и отобрать в другой массив все простые числа. Используйте логическую функцию, которая определяет, является ли переданное ей число простым. Пример : Массив А: 12 13 85 96 47 Массив B: 13 47
33 « C »: Заполнить массив случайными числами и отобрать в другой массив все числа Фибоначчи. Используйте логическую функцию, которая определяет, является ли переданное ей число числом Фибоначчи. Пример : Массив А: 12 13 85 34 47 Массив B: 13 34
§ 64. Сортировка 34
35 Сортировка – это расстановка элементов массива в заданном порядке. …по возрастанию, убыванию, последней цифре, сумме делителей, по алфавиту, … Алгоритмы: простые и понятные, но неэффективные для больших массивов метод пузырька метод выбора сложные, но эффективные «быстрая сортировка» ( QuickSort ) сортировка «кучей» ( HeapSort ) сортировка слиянием ( MergeSort ) пирамидальная сортировка время работы N
36 Идея: пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов – самый маленький («легкий» элемент перемещается вверх ( «всплывает» ). 4 5 2 1 3 4 5 2 1 3 4 5 1 2 3 1 4 5 2 3 сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами за 1 проход по массиву один элемент (самый маленький) становится на свое место 1-й проход : 4 1 5 2 3
37 1 4 5 2 3 1 4 5 2 3 1 4 2 5 3 2-й проход : 3-й проход : 1 2 4 5 3 1 2 3 4 5 1 2 4 5 3 4 -й проход : 1 2 3 4 5 1 2 3 4 5 1 2 4 3 5 Для сортировки массива из N элементов нужен N -1 проход (достаточно поставить на свои места N-1 элементов). !
38 1-й проход : сделать для j от N - 2 до 0 шаг -1 если A [ j + 1 ]< A [ j ] то // поменять местами A[ j ] и A[j+1] 2 -й проход : сделать для j от N - 2 до 1 шаг -1 если A [ j + 1 ]< A [ j ] то // поменять местами A[ j ] и A[j+1] 1 единственное отличие!
39 for ( i = 0 ; i < N- 1 ; i++ ) for ( j = N- 2 ; j >= i ; j-- ) if ( A [ j ] > A [ j + 1 ] ) { // поменять местами A[ j ] и A[j+1] } i Как написать метод «камня»? ? Как сделать рекурсивный вариант? ?
40 « A »: Напишите программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в конец массива. « B »: Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок. «С»: Напишите программу, которая сортирует массив по убыванию суммы цифр числа. Используйте функцию, которая определяет сумму цифр числа.
41 Идея : найти минимальный элемент и поставить его на первое место. сделать для i от 0 до N- 2 // найти номер nMin минимального // элемента из A[ i ]..A[N] если i != nMin то // поменять местами A[ i ] и A[ nMin ]
42 for ( i = 0 ; i < N- 1 ; i++ ) { nMin = i; for ( j = i+1; j < N; j++ ) if ( A[j] < A[nMin] ) nMin = j; if ( i != nMin ) { // поменять местами A[ i ] и A[ nMin ] } } nMin = i; for ( j = i+ 1 ; j < N; j++ ) if ( A[j] < A[nMin] ) nMin = j; Как поменять местами два значения? ?
43 « A »: Массив содержит четное количество элементов. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. Каждый элемент должен остаться в «своей» половине. Пример : Массив: 5 3 4 2 1 6 3 2 После сортировки: 2 3 4 5 6 3 2 1
44 « B »: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Пример : Массив: 5 3 4 2 1 6 3 2 4 После сортировки: 1 2 2 3 3 4 4 5 6 Различных чисел: 5 « C »: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком» и методом выбора. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.
45 Ч.Э.Хоар Идея : выгоднее переставлять элементы, который находятся дальше друг от друга. 6 5 4 3 2 1 1 5 4 3 2 6 1 2 4 3 5 6 1 2 3 4 5 6 Для массива из N элементов нужно всего N/2 обменов! !
46 Шаг 2 : переставить элементы так: при сортировке элементы не покидают « свою область»! Шаг 1 : выбрать некоторый элемент массива X A[ i ] <= X A[ i ] >= X Шаг 3 : так же отсортировать две получившиеся области Разделяй и властвуй (англ. divide and conquer ) Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов ( для этого надо отсортировать массив… ). 78 6 82 67 55 44 34 Как лучше выбрать X ? ?
47 Разделение : выбрать средний элемент массива ( X =67 ) установить L = 1, R = N увеличивая L, найти первый элемент A[L], который >= X ( должен стоять справа ) уменьшая R, найти первый элемент A[R], который <= X ( должен стоять слева ) если L<=R то поменять местами A[L] и A[R] и перейти к п. 3 иначе стоп. 78 6 82 67 55 44 34
48 78 6 82 67 55 44 34 L R 34 6 82 67 55 44 78 L R 34 6 44 67 55 82 78 L R 34 6 44 55 67 82 78 R L L > R : разделение закончено! !
49 const int N = 7 ; int A[N]; ... main() { // заполнить массив qSort ( 0, N- 1 ); // сортировка // вывести результат } Основная программа : глобальные данные процедура сортировки
50 void qSort( int nStart, int nEnd ) { int L, R, c, X; if ( nStart >= nEnd ) return ; // готово L = nStart; R = nEnd; X = A[(L+R)/ 2 ]; // или X = A[irand(L,R)]; while ( L <= R ) { // разделение while ( A[L] < X ) L ++; while ( A[R] > X ) R --; if ( L <= R ) { c = A[L]; A[L] = A[R]; A[R] = c; L ++; R --; } } qSort ( nStart, R ); // рекурсивные вызовы qSort ( L, nEnd ); } Что плохо? ?
51 void qSort ( int A[], int nStart, int nEnd ) { ... qSort ( A, nStart, R ); qSort ( A, L, nEnd ); } Передача массива через параметр : A, A, int A[], main() { // заполнить массив qSort ( A, 0, N- 1 ); // сортировка // вывести результат } A,
52 N метод пузырька метод выбора быстрая сортировка 1000 0, 2 4 с 0, 12 с 0, 004 с 5000 5,3 с 2, 9 с 0, 024 с 15000 4 5 с 3 4 с 0, 068 с Сортировка массива случайных значений :
53 « A »: Массив содержит четное количество элементов. Напишите программу, которая сортирует по возрастанию отдельно элементы первой и второй половин массива. Каждый элемент должен остаться в «своей» половине. Используйте алгоритм быстрой сортировки. Пример : Массив: 5 3 4 2 1 6 3 2 После сортировки: 2 3 4 5 6 3 2 1
54 « B »: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Используйте алгоритм быстрой сортировки. Пример : Массив: 5 3 4 2 1 6 3 2 4 После сортировки: 1 2 2 3 3 4 4 5 6 Различных чисел: 5
55 « C »: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком», методом выбора и алгоритма быстрой сортировки. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода. « D »: Попробуйте построить массив из 10 элементов, на котором алгоритм быстрой сортировки показывает худшую эффективность (наибольшее число перестановок). Сравните это количество перестановок с эффективностью метода пузырька (для того же массива).
§ 65. Двоичный поиск 56
57 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 X = 7 X < 8 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 4 X > 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 6 X > 6 Выбрать средний элемент A[c] и сравнить с X. Если X = A[c], то нашли ( стоп ). Если X < A[c], искать дальше в первой половине. Если X > A[c], искать дальше во второй половине.
58 A[ 0 ] A[N -1 ] A[N] 6 34 44 55 67 78 82 L R с 6 34 44 55 67 78 82 L с R X = 44 6 34 44 55 67 78 82 L с R 6 34 44 55 67 78 82 L R L = R-1 : поиск завершен! !
59 int X, L, R, c; L = 0 ; R = N; // н ачальный отрезок while ( L < R-1 ) { c = (L+R) / 2 ; // н ашли середину if ( X < A[c] ) // сжатие отрезка R = c; else L = c; } if ( A[L] == X ) printf ( "A[%d]=%d", L, X ); else printf ( "Не нашли!" );
60 N линейный поиск двоичный поиск 2 2 2 16 16 5 1024 1024 11 1048576 1048576 21 скорость выше, чем при линейном поиске нужна предварительная сортировка Когда нужно применять? ? Число сравнений :
61 « A »: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Подсчитать количество сравнений. Пример : Массив: 1 4 7 3 9 2 4 5 2 После сортировки: 1 2 2 3 4 4 5 7 9 Введите число X: 2 Число 2 найдено. Количество сравнений: 2
62 « B »: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, сколько чисел, равных X, находится в массиве. Пример : Массив: 1 4 7 3 9 2 4 5 2 После сортировки: 1 2 2 3 4 4 5 7 9 Введите число X: 4 Число 4 встречается 2 раз(а). Пример : Массив: 1 4 7 3 9 2 4 5 2 После сортировки: 1 2 2 3 4 4 5 7 9 Введите число X: 14 Число 14 не встречается.
63 « C »: Заполнить массив случайными числами и ввести число и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Если такого числа нет, вывести число, ближайшее к X. Пример : Массив: 1 4 7 3 9 2 4 5 2 После сортировки: 1 2 2 3 4 4 5 12 19 Введите число X: 12 Число 12 найдено. Пример : Массив: 1 4 7 3 9 2 4 5 2 После сортировки: 1 2 2 3 4 4 5 12 19 Введите число X: 11 Число 11 не найдено. Ближайшее число 12.
§ 66. Символьные строки 64
65 char s[ 10 ]; // массив символов элементы массива – отдельные объекты сложно работать со строками переменной длины Хочется : строка – единый объект длина строки может меняться во время работы программы
66 П р и в е т ! \ 0 ? ? 0 9 рабочая часть s[0] s[1] s[2] s[3] char s[ 1 0 ]; признак окончания строки: символ с кодом 0 Символ '\0' имеет код 0 символ '0' имеет код 48 ! Символьная строка – это последовательность символов, которая заканчивается символом '\0'.
67 Начальное значение : char s[10] = " Привет!" ; Вывод на экран : printf ( "%s", s ); А если массив? ? char s[] = " Привет!" ; размер вычисляется автоматически puts ( s ); с переходом на новую строку
68 Ввод с клавиатуры : scanf ( "% s ", s ); Отдельный символ : s[ 4 ] = 'a' ; Длина строки : #include < string.h > только до пробела! gets ( s ); до перевода строки ( Enter ) int n; ... n = strlen ( s ) ; библиотека для работы со строками string length – длина строки
69 # include <stdio.h> #include <string.h> main() { char s[ 80 ]; int i; printf ( " Введите строку " ); gets ( s ); for ( i = 0 ; i < strlen(s); i++ ) if ( s[i] == ' а ' ) s[i] = ' б ' ; puts ( s ); } Задача : заменить в строке все буквы ' а ' на буквы ' б '.
70 « A »: Ввести с клавиатуры символьную строку и заменить в ней все буквы «а» на «б» и все буквы «б» на «а» (заглавные на заглавные, строчные на строчные). Пример : Введите строку: ааббААББссСС Результат: ббааББААссСС
71 « B »: Ввести с клавиатуры символьную строку и определить, сколько в ней слов. Словом считается последовательности непробельных символов, отделенная с двух сторон пробелами (или стоящая с краю строки). Слова могут быть разделены несколькими пробелами, в начале и в конце строки тоже могут быть пробелы. Пример : Введите строку: Вася пошел гулять Найдено слов: 3
72 « C »: Ввести с клавиатуры символьную строку и найдите самое длинное слово и его длину. Словом считается последовательности непробельных символов, отделенная с двух сторон пробелами (или стоящая с краю строки). Слова могут быть разделены несколькими пробелами, в начале и в конце строки тоже могут быть пробелы. Пример : Введите строку: Вася пошел гулять Самое длинное слово: гулять, длина 6
73 Объединение ( конкатенация ) : char s[ 80 ]= " Привет ", s1[]= " Вася !" ; strcat ( s, ", " ); // s = " Привет, " strcat ( s, s1 ); // s = " Привет, Вася!" string concatenation – «сцепление» строк Вторая строка прицепляется в конец первой! !
74 Копирование строки : char s[ 80 ], s1[]= " Привет " ; strcpy ( s, " Вася !" ); // s1 = " Вася!" strcpy ( s, s1 ); // s = s1 = " Вася!" string copy – копировать строку Вторая строка копируется на место первой! ! Какие могут быть проблемы? ? откуда куда
75 Копирование строки со смещением : char s[ 80 ] = "Прошёл поезд." ; strcpy ( & s [ 7 ], "пароход." ); Хватит ли места? ? адрес символа s[5] : & s[5] или s +5 Прошел пароход. s совпадает с &s[0] char s [ 80 ] = "Прошёл поезд.", s1[] = " Привет, Вася." ; strcpy ( s+ 7, s1+ 8 ); Что получим? ? Прошел Вася.
76 Удаление : char s[] = "0123456789" ; strcpy ( s+ 2, s+ 6 ); Как удалить часть строки? ? 0 9 0 1 2 3 4 5 6 7 8 9 \ 0 2 6 6 7 8 9 \ 0 Можно ли так «раздвинуть» строку? ? откуда куда
77 Копирование n символов : char s [] = "Мухтар, ко мне!", s 1[] = "Цезарь живет у нас дома." ; str n cpy ( s, s1, 6 ); сколько символов Не добавляет символ конца строки! ! char s [] = "Вчера Мурзик вернулся.", s1[]= " Кота зовут Васька." ; str n cpy ( s+ 6, s1+ 11, 6 ); Васька Цезарь
78 Выделение подстроки : char s[] = "0123456789", s1[ 20 ]; strncpy ( s1, s+ 2, 4 ); s1[ 4 ] = '\0' ; с какого символа сколько символов Задача : выделить 4 символа строки s, начиная с s[2], в новую строку s1. символ конца строки добавляем вручную» s1 = "2345"
79 Вставка фрагмента в середину строки : char s [ 80 ]= "Иван меняет профессию.", s 1[ 30 ]; // буфер strcpy ( s 1, s + 4 ); strcpy ( s + 4, " Васильевич" ); strcat ( s, s 1 ); "Иван меняет профессию." Васильевич Сдвиг вправо в строке не работает! ! s+4 "Иван меняет профессию." s 1: s : " меняет профессию." Васильевич " меняет профессию."
80 Функции поиска возвращают адрес памяти! ! Указатель – это переменная. в которую можно записать адрес памяти. char * p; // указатель на символ // может хранить адрес // любого символа char s [] = "Здесь был Вася." ; char * p; p = & s[2]; printf( "%c", * p ); // е * p = ' э '; // s[2] = ' э ' содержимое ячейки
81 char s [] = "Здесь был Вася." ; char *p; p = strchr ( s, ' с ' ); где что искать в строке ( string ) символ ( character ) if ( p != NULL ) printf ( "Номер символа ' c' :% d \ n ", p - s ); else printf ( "Символ не найден.\ n " ); нулевой указатель str r chr – поиск с конца строки! ! 3
82 char s [] = "Здесь был Вася." ; char *p; p = strstr ( s, "Вася" ); где что искать в строке ( string ) строку ( string ) if ( p != NULL ) printf ( "Слово начинаетя с s[ % d] \ n ", p - s ); else printf ( "Слово не найдено.\ n " ); нулевой указатель 10
83 Задача: Ввести имя, отчество и фамилию. Преобразовать их к формату «фамилия-инициалы». Пример: Введите имя, отчество и фамилию: Василий Алибабаевич Хрюндиков Результат: Хрюндиков В.А. Алгоритм: найти первый пробел и выделить имя удалить имя с пробелом из основной строки найти первый пробел и выделить отчество удалить отчество с пробелом из основной строки «сцепить» фамилию, первые буквы имени и фамилии, точки, пробелы… Алибабаевич Хрюндиков Хрюндиков Хрюндиков В.А.
84 main() { char s[ 80 ], name[] = ".", name2[] = "." ; char *p; printf( "Введите имя, отчество и фамилию: " ); gets ( s ); name[ 0 ] = s[ 0 ]; // первая буква имени p = strchr ( s, ' ' ); // найти пробел strcpy ( s, p+ 1 ); // стереть имя name2[ 0 ] = s[ 0 ]; // первая буква отчества p = strchr ( s, ' ' ); // найти пробел strcpy ( s, p+ 1 ); // осталась фамилия strcat ( s, " " ); // добавить пробел strcat ( s, name ); // прицепить имя strcat ( s, name2 ); // прицепить отчество puts ( s ); } заготовки для инициалов
85 « A »: Ввести с клавиатуры в одну строку фамилию, имя и отчество, разделив их пробелом. Вывести фамилию и инициалы. Пример : Введите фамилию, имя и отчество: Иванов Петр Семёнович П.С. Иванов
86 « B »: Ввести адрес файла и «разобрать» его на части, разделенные знаком '/'. Каждую часть вывести в отдельной строке. Пример : Введите адрес файла: C:/Фото/2013/Поход/vasya.jpg C: Фото 2013 Поход vasya.jpg
87 « C »: Напишите программу, которая заменяет во всей строке одну последовательность символов на другую. Пример : Введите строку: (X > 0) and (Y < X) and (Z > Y) and (Z <> 5) Что меняем: and Чем заменить: & Результат (X > 0) & (Y < X) & (Z > Y) & (Z <> 5)
88 Из строки в число: # include < stdlib. h > char s[] = "123" ; int N; N = atoi ( s ); // N = 123 char s[] = "123.456" ; float X; X = atof ( s ); // X = 123.456 « 12 x 3 » 12
89 Из числа в строку: char s[ 80 ]; int N = 123 ; float X = 123.456 ; s printf (s, "%d", N); // s = "123" s printf (s, "%e", X); // s = "1.234560E+002" s printf (s, "%10.3f", X); // s = " 123.456" sprintf – вывод в строку, а не на экран! !
90 « A »: Напишите программу, которая вычисляет сумму трех чисел, введенную в форме символьной строки. Все числа целые. Пример : Введите выражение: 12+3+45 Ответ: 60 « B »: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются только знаки «+» или «–»). Выражение вводится как символьная строка, все числа целые. Пример : Введите выражение: 12-3+45 Ответ: 54
91 « C »: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки « + », « – », « * » и « / »). Выражение вводится как символьная строка, все числа целые. Операция « / » выполняется как целочисленное деление. Пример : Введите выражение: 12*3+45 Ответ: 81
92 « D »: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки « + », « – », « * » и « / ») и круглых скобок. Выражение вводится как символьная строка, все числа целые. Операция « / » выполняется как целочисленное деление ( div ). Пример : Введите выражение: 2*(3+45)+4 Ответ: 100
93 Задача : построить процедуру, которая заменяет в строке s все вхождения слова-образца wOld на слово-замену wNew. пока // слово wOld есть в строке s // удалить слово wOld из строки // вставить на это место слово wNew Что плохо? ? wOld : '12' wNew: 'A 12 B' зацикливание
94 s res б ) wNew s res в ) s res г ) wOld res s а ) wNew
95 рабочая строка s результат res " 12.12.12 " "" ".12.12 " "A 12 B" ".12" "A12B.A12B" "" "A12B.A12B.A12B" main() { char s[ 80 ] = "12.12.12" ; replaceAll ( s, "12", "A12B" ); puts ( s ); }
96 s res б ) wNew s res в ) s res г ) wOld res s а ) wNew pRes pS p pRes pS pRes pS pRes pS
97 void replaceAll ( char s[], char wOld [], char wNew []) { int lenOld, lenNew ; char *p, * pS, * pRes ; char res[ 200 ]; // строка-результат lenOld = strlen ( wOld ); lenNew = strlen ( wNew ); res[ 0 ] = '\0' ; pS = s; pRes = res; while ( strlen ( pS ) > 0 ) { // пока строка не пуста p = strstr ( pS, wOld ); if ( p == NULL ) { // прицепить хвост и выйти } if ( p > pS ) { // скопировать часть до образца } strcpy ( pRes, wNew ); pRes += lenNew ; pS += lenOld ; } strcpy ( s, res ); // записать результат в s } длины строк начальные установки добавить слово-замену указатели передвинуть указатели
98 p = strstr ( pS, wOld ); if ( p == NULL ) { strcat ( res, s ); break ; } if ( p > pS ) { strncpy ( pRes, pS, p- pS ); pRes += p- pS ; pS = p; } Если образец не найден: Если перед образцом что-то есть: длина блока перед образцом прицепить «хвост» выйти из цикла p-pS передвинуть указатели
99 « A »: Напишите процедуру, которая отсекает всю часть строки после первого слова. Пример : Введите строку: Однажды в студёную зимнюю пору... Первое слово: Однажды
100 « B »: Напишите процедуру, которая заменяет расширение файла на заданное новое расширение. Пример : Введите имя файла: qq Введите новое расширение: tmp Результат: qq.tmp Пример : Введите имя файла: qq.exe Введите новое расширение: tmp Результат: qq.tmp Пример : Введите имя файла: qq.work.xml Введите новое расширение: tmp Результат: qq.work.tmp
101 « C »: Напишите процедуру, которая заменяет во всей строке все римские числа на соответствующие десятичные числа. Пример : Введите строку: В MMXIII году в школе CXXIII состоялся очередной выпуск XI классов. Результат: В 2013 году в школе 123 состоялся очередной выпуск 11 классов.
102 Задача. В алфавите языка племени «тумба-юмба» четыре буквы: « Ы », « Ш », « Ч » и « О ». Нужно вывести на экран все слова, состоящие из L букв, которые можно построить из букв этого алфавита. Ы ? ? ? перебор L -1 символов Ш ? ? ? Ч ? ? ? 0 ? ? ? задача для слов длины К сведена к задаче для слов длины L -1!
103 перебор L символов w [ 0 ]= 'Ы' ; // перебор последних L -1 символов w [ 0 ]= 'Ш' ; // перебор последних L -1 символов w [ 0 ]= 'Ч' ; // перебор последних L -1 символов w [ 0 ]= 'О' ; // перебор последних L -1 символов
104 main() { char word[] = "..." ; TumbaWords ( " ЫШЧО ", word, 0 ); } void TumbaWords ( char A[], char w[], int N ) { int i ; if ( N == strlen (w) ) { puts ( w ); return ; } for ( i = 1 ; i < strlen (A); i ++ ) { w[N] = A[ i ]; TumbaWords ( A, w, N+1 ); } } уже установлено когда все символы уже установлены по всем символам алфавита алфавит слово любая строка длины L
105 « A »: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых вторая буква «Ы». Подсчитайте количество таких слов. « B »: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов. Программа не должна строить другие слова, не соответствующие условию.
106 « C »: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, не обязательно стоящие рядом. Программа не должна строить другие слова, не соответствующие условию.
107 пар парк Пар ? ? Сравнение по кодам символов: A B ... Y Z CP-1251 65 66 ... 89 90 UNCODE 65 66 ... 89 90 a b ... y z CP-1251 97 98 ... 121 122 UNCODE 97 98 ... 121 122 0 1 ... 8 9 CP-1251 48 49 ... 56 57 UNCODE 48 49 ... 56 57
108 А Б ... Ё ... Ю Я CP-1251 192 193 ... 168 ... 222 223 UNCODE 1040 1041 ... 1025 ... 1070 1071 а б ... ё ... ю я CP-1251 224 225 ... 184 ... 254 255 UNCODE 1072 1073 ... 1105 ... 1102 1103 5STEAM < S TEAM < S t eam < s team steam < П АР < П а р < п Ар < п а р < пар к
109 main() { const int N = 10 ; char s1[ 80 ], S[N][ 80 ]; int i, j; printf ( "Введите строки: \n" ); for ( i = 0 ; i < N; i ++ ) gets ( S[i] ); ... printf ( "После сортировки: \n" ); for ( i = 0 ; i < N; i ++ ) puts ( S[i] ); } for ( i = 0 ; i < N- 1 ; i ++ ) for ( j = N- 2 ; j >= i ; j -- ) if ( strcmp (S[j],S[j+1])> 0 ) { strcpy (s1, S[j]); strcpy (S[j], S[j+1]); strcpy (S[j+1], s1); } массив строк
110 « A »: Вводится 5 строк, в которых сначала записан порядковый номер строки с точкой, а затем – слово. Вывести слова в алфавитном порядке. Пример : Введите 5 строк: 1. тепловоз 2. арбуз 3. бурундук 4. кефир 5. урядник Список слов в алфавитном порядке: арбуз, бурундук, кефир, тепловоз, урядник
111 « B »: Вводится несколько строк (не более 20), в которых сначала записан порядковый номер строки с точкой, а затем – слово. Ввод заканчивается пустой строкой. Вывести введённые слова в алфавитном порядке. Пример : Введите слова: 1. тепловоз 2. арбуз Список слов в алфавитном порядке: арбуз, тепловоз
112 « C »: Вводится несколько строк (не более 20), в которых сначала записаны инициалы и фамилии работников фирмы. Ввод заканчивается пустой строкой. Отсортировать строки в алфавитном порядке по фамилии. Пример : Введите ФИО: А.Г. Урядников Б.В. Тепловозов В.Д. Арбузов Список в алфавитном порядке: В.Д. Арбузов Б.В. Тепловозов А.Г. Урядников
§ 67. Матрицы 113
114 0 1 2 0 -1 0 1 1 -1 0 1 2 0 1 -1 Как закодировать? ? Матрица — это прямоугольная таблица, составленная из элементов одного типа (чисел, строк и т.д.). Каждый элемент матрицы имеет два индекса – номера строки и столбца. нет знака нолик крестик строка 1, столбец 2
115 const int N = 3, M = 4 ; int A[N][M]; double X[ 10 ][ 12 ]; bool L[N][ 2 ]; строки столбцы строки столбцы Если удобна нумерация с 1? ? Нумерация строк и столбцов с нуля! !
116 Заполнение случайными числами: for ( i = 0 ; i < N; i ++ ) { for ( j = 0 ; j < M; j++ ) { A[ i ][j] = irand ( 20, 80 ); printf ( "%3d", A[ i ][j] ); } printf ( "\ n " ); } Суммирование: sum = 0 ; for ( i = 0 ; i < N; i ++ ) for ( j = 0 ; j < M; j++ ) sum += A[ i ][j]; Вложенный цикл! !
117 « A »: Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], и находит максимальный и минимальный элементы в матрице и их индексы. Пример : Матрица А: 12 14 67 45 32 87 45 63 69 45 14 11 40 12 35 15 Максимальный элемент A[2,2]=87 Минимальный элемент A[3,4]=11
118 « B »: Яркости пикселей рисунка закодированы числами от 0 до 255 в виде матрицы. Преобразовать рисунок в черно-белый по следующему алгоритму: вычислить среднюю яркость пикселей по всему рисунку все пиксели, яркость которых меньше средней, сделать черными (записать код 0), а остальные – белыми (код 255) Пример : Матрица А: 12 14 67 45 32 87 45 63 69 45 14 11 40 12 35 15 Средняя яркость 37.88 Результат: 0 0 255 255 0 255 255 255 255 255 0 0 255 0 0 0
119 «С»: Заполните матрицу, содержащую N строк и M столбцов, натуральными числами по спирали и змейкой, как на рисунках:
120 Главная диагональ: for ( i = 0 ; i < N; i++ ) { // работаем с A[i][i] } Побочная диагональ: for ( i = 0 ; i < N; i++ ){ // работаем с A[i][N-1-i] } Главная диагональ и под ней: for ( i = 0 ; i < N; i++ ) for ( j = 0 ; j <= i ; j++ ) { // работаем с A [ i ][ j ] }
121 2-я и 4-я строки: for ( j = 0 ; j < M; j++ ) { c = A[ 2 ][j]; A[ 2 ][j]= A[ 4 ][j]; A[ 4 ][j]= c; } 0 1 2 3 4 5 0 1 2 3 4 5
122 « A »: Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], а затем записывает нули во все элементы выше главной диагонали. Алгоритм не должен изменяться при изменении размеров матрицы. Пример : Матрица А: 12 14 67 45 32 87 45 63 69 45 14 30 40 12 35 65 Результат: 12 0 0 0 32 87 0 0 69 45 14 0 40 12 35 65
123 « B »: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните отражение рисунка сверху вниз: 1 2 3 4 5 6 7 8 9 7 8 9 4 5 6 1 2 3 «С»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните поворот рисунка вправо на 90 градусов: 1 2 3 4 5 6 7 8 9 7 4 1 8 5 2 9 6 3
§ 68. Работа с файлами 124
125 файлы текстовые двоичные « plain text » : текст, разбитый на строки; из специальных символов только символы перехода на новую строку любые символы рисунки, звуки, видео, …
126 открыть файл работа с файлом закрыть файл хлеб хлеб начинка FILE *Fin, *Fout; Fin = fopen ( "input.txt", "r" ); Fout = fopen ( "output.txt", "w" ); // здесь работаем с файлами fclose (Fi n ); fclose (F out ); файловые переменные- указатели "r" - чтение "w" – запись "a" – добавление
127 FILE *F; F = fopen ( "input.txt", "r" ); if ( F ) { // здесь работаем с файлом } else printf ( "Открыть файл не удалось." ); if ( F != NULL ) В случае неудачи fopen возвращает NULL ! ! Когда такое может быть? ?
128 int a, b; FILE *Fin; Fin = fopen ( "input. txt", "r" ) ; fclose ( Fi n ) ; fclose ( Fi n ) ; Fin = fopen ( "input. txt", "r" ) ; f scanf ( Fin, "%d%d", &a, &b ); Переход к началу открытого файла : if ( feof ( Fin ) ) printf ( "Данные кончились " ); Определение конца файла : eof = end of file, конец файла
129 int a = 1, b = 2 ; FILE * Fout ; Fout = fopen ( "output. txt", "w" ) ; fclose (F out ) ; f printf ( Fout, "%d+%d=%d", a, b, a+b );
130 пока не конец файла // прочитать число из файла // добавить его к сумме Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму. int n, S, x; S = 0; while ( 1 ) { n = fscanf ( Fin, "%d", &x ); if ( n < 1 ) break ; S = S + x; } fscanf возвращает количество прочитанных данных! ! при неудачном чтении выход из цикла
131 « A »: Напишите программу, которая находит среднее арифметическое всех чисел, записанных в файле в столбик, и выводит результат в другой файл. « B »: Напишите программу, которая находит минимальное и максимальное среди чётных положительных чисел, записанных в файле, и выводит результат в другой файл. Учтите, что таких чисел может вообще не быть. « C »: В файле в столбик записаны целые числа, сколько их – неизвестно. Напишите программу, которая определяет длину самой длинной цепочки идущих подряд одинаковых чисел и выводит результат в другой файл.
132 Задача. В файле записано не более 100 целых чисел. Вывести в другой текстовый файл те же числа, отсортированные в порядке возрастания. В чем отличие от предыдущей задачи? ? const int MAX = 100 ; int A[MAX]; Для сортировки нужно удерживать все элементы в памяти одновременно. !
133 Ввод массива : N = 0 ; while ( N < MAX ) { r = fscanf ( Fin, "%d", &A[N] ); if ( r < 1 ) break ; N ++; } Зачем? ?
134 Вывод результата : Fout = fopen ( "output.txt", "w" ); for ( i = 0 ; i < N ; i ++ ) fprintf ( Fout, "%d\n", A[ i ] ); fclose ( Fout ); N
135 « A »: В файле записано не более 100 чисел. Отсортировать их по возрастанию последней цифры и записать в другой файл. « B »: В файле записано не более 100 чисел. Отсортировать их по возрастанию суммы цифр и записать в другой файл. Используйте функцию, которая вычисляет сумму цифр числа. « C »: В двух файлах записаны отсортированные по возрастанию массивы неизвестной длины. Объединить их и записать результат в третий файл. Полученный массив также должен быть отсортирован по возрастанию.
136 Задача. В файле записано данные о собаках: в каждой строчке кличка собаки, ее возраст и порода: Мухтар 4 немецкая овчарка Вывести в другой файл сведения о собаках, которым меньше 5 лет. пока не конец файла ( Fin ) // прочитать строку из файла Fin // разобрать строку – выделить возраст если возраст < 5 то // записать строку в файл Fout
137 while ( fgets(s, 80, Fin) ) { // обработать строку s } Чтение одной строки : char s[ 80 ]; char *p; p = f gets ( s, 80, Fin ); строка размер файл При неудаче fgets вернет NULL ! ! Чтение всех строк :
138 // найти в строке пробел // удалить из строки кличку с первым пробелом // найти в строке пробел // выделить возраст перед пробелом // преобразовать возраст в числовой вид Разбор строки: char s[ 80 ], *p; int age; ... p = strchr ( s, ' ' ); s scanf ( p+1, "%d", &age ); чтение из строки строка (адрес) Мухтар 4 немецкая овчарка p+1 не влияет!
139 « A »: В файле записаны данные о результатах сдачи экзамена. Каждая строка содержит фамилию, имя и количество баллов, разделенные пробелами: <Фамилия> <Имя> <Количество баллов> Вывести в другой файл фамилии и имена тех учеников, которые получили больше 80 баллов. « B »: В предыдущей задаче добавить к полученному списку нумерацию, сократить имя до одной буквы и поставить перед фамилией: П. Иванов И. Петров ...
140 « C »: В файле записаны данные о результатах сдачи экзамена. Каждая строка содержит фамилию, имя и количество баллов, разделенные пробелами: <Фамилия> <Имя> <Количество баллов> Вывести в другой файл данные учеников, которые получили больше 80 баллов. Список должен быть отсортирован по убыванию балла. Формат выходных данных: П. Иванов 98 И. Петров 96 ...
141 Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru ЕРЕМИН Евгений Александрович к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь eremin@pspu.ac.ru
142 www.mcdonalds.com иллюстрации художников издательства «Бином» авторские материалы
