Document

Report
1
Программирование
на языке Си
§ 66. Символьные строки
 К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
2
Зачем нужны символьные строки?
char s[10];
// массив символов
 элементы массива – отдельные объекты
 сложно работать со строками переменной длины
Хочется:
• строка – единый объект
• длина строки может меняться во время работы
программы
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
3
Как хранится символьная строка?
char s[10];
s[2]
s[3]
признак окончания
строки: символ с
кодом 0
9
0
П р и в е т ! \0 ? ?
рабочая часть
s[0]
s[1]
!
Символ '\0' имеет код 0
символ '0' имеет код 48
Символьная строка – это последовательность
символов, которая заканчивается символом '\0'.
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
4
Символьные строки
Начальное значение:
char s[10] = "Привет!";
char s[] = "Привет!";
Вывод на экран:
размер
вычисляется
автоматически
printf ( "%s", s );
с переходом на
новую строку
puts ( s );
?
 К.Ю. Поляков, Е.А. Ерёмин, 2014
А если массив?
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
5
Символьные строки
Ввод с клавиатуры:
только до
пробела!
scanf ( "%s", s );
gets ( s );
до перевода
строки (Enter)
Отдельный символ:
s[4] = 'a';
Длина строки:
#include <string.h>
int n;
...
n = strlen(s);
 К.Ю. Поляков, Е.А. Ерёмин, 2014
библиотека
для работы со
строками
string length –
длина строки
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
6
Символьные строки
Задача: заменить в строке все буквы 'а' на буквы 'б'.
#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 );
}
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
7
Задачи
«A»: Ввести с клавиатуры символьную строку и заменить в
ней все буквы «а» на «б» и все буквы «б» на «а»
(заглавные на заглавные, строчные на строчные).
Пример:
Введите строку:
ааббААББссСС
Результат:
ббааББААссСС
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
8
Задачи
«B»: Ввести с клавиатуры символьную строку и определить,
сколько в ней слов. Словом считается
последовательности непробельных символов,
отделенная с двух сторон пробелами (или стоящая с
краю строки). Слова могут быть разделены несколькими
пробелами, в начале и в конце строки тоже могут быть
пробелы.
Пример:
Введите строку:
Вася пошел
гулять
Найдено слов: 3
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
9
Задачи
«C»: Ввести с клавиатуры символьную строку и найдите
самое длинное слово и его длину. Словом считается
последовательности непробельных символов,
отделенная с двух сторон пробелами (или стоящая с
краю строки). Слова могут быть разделены несколькими
пробелами, в начале и в конце строки тоже могут быть
пробелы.
Пример:
Введите строку:
Вася
пошел гулять
Самое длинное слово: гулять, длина 6
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
10
Операции со строками
Объединение (конкатенация):
char s[80]= "Привет",
s1[]="Вася!";
strcat( s, ", "); // s = "Привет, "
strcat( s, s1 ); // s = "Привет, Вася!"
string concatenation –
«сцепление» строк
!
Вторая строка прицепляется в конец первой!
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
11
Операции со строками
Копирование строки:
char s[80], s1[]="Привет";
strcpy( s, "Вася!"); // s1 = "Вася!"
strcpy( s, s1 );
// s = s1 = "Вася!"
куда
откуда
string copy –
копировать строку
!
Вторая строка копируется на место первой!
?
Какие могут быть проблемы?
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
12
Операции со строками
Копирование строки со смещением:
адрес символа s[5]: &s[5] или s+5
s совпадает с &s[0]
? Хватит ли места?
char s[80] = "Прошёл поезд.";
strcpy ( &s[7] , "пароход." );
Прошел пароход.
char s[80] = "Прошёл поезд.",
s1[] = "Привет, Вася.";
strcpy ( s+7, s1+8 );
?
Что получим?
 К.Ю. Поляков, Е.А. Ерёмин, 2014
Прошел Вася.
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
13
Операции со строками
?
Удаление:
Как удалить часть строки?
char s[] = "0123456789";
strcpy ( s+2, s+6 );
куда
0
2
откуда
6
9
0 1 2
4 9
5 \0
6 7 8 9 \0
6 3
7 8
?
Можно ли так «раздвинуть» строку?
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
14
Операции со строками
Копирование n символов:
char s[] = "Мухтар, ко мне!",
s1[] = "Цезарь
Цезарь живет у нас дома.";
strncpy ( s, s1, 6 );
сколько символов
!
Не добавляет символ конца строки!
char s[] = "Вчера Мурзик вернулся.",
s1[]= "Кота зовут Васька
Васька.";
strncpy ( s+6, s1+11, 6 );
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
15
Операции со строками
Выделение подстроки:
Задача: выделить 4 символа строки s, начиная с s[2], в
новую строку s1.
char s[] = "0123456789", s1[20];
strncpy ( s1, s+2, 4 );
s1[4] = '\0';
с какого
символа
символ конца строки
добавляем вручную»
 К.Ю. Поляков, Е.А. Ерёмин, 2014
сколько
символов
s1 = "2345"
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
16
Операции со строками
Вставка фрагмента в середину строки:
"Иван Васильевич
меняет профессию."
!
Сдвиг вправо в строке не работает!
s+4
char s[80]="Иван меняет профессию.",
s1[30]; // буфер
strcpy ( s1, s+4 );
strcpy ( s+4, " Васильевич" );
strcat ( s, s1 );
меняет профессию."
s: "Иван Васильевич
"меняет профессию."
s1: " меняет профессию."
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
17
Поиск в строках
!
Функции поиска возвращают адрес памяти!
Указатель – это переменная. в которую можно записать
адрес памяти.
char *p; // указатель на символ
// может хранить адрес
// любого символа
char s[] = "Здесь был Вася.";
char *p;
содержимое
ячейки
p = &s[2];
printf( "%c", *p ); // е
*p = 'э'; // s[2] = 'э'
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
18
Поиск символа в строке
char s[] = "Здесь был Вася.";
где что
char *p;
p = strchr ( s, 'с' );
искать в строке (string)
символ (character)
нулевой указатель
!
strrchr – поиск
с конца строки!
if ( p != NULL )
printf("Номер символа 'c':%d\n",
p-s );
3
else
printf("Символ не найден.\n" );
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
19
Поиск подстроки
char s[] = "Здесь был Вася.";
где что
char *p;
p = strstr ( s, "Вася" );
искать в строке (string)
строку (string)
нулевой указатель
if ( p != NULL )
printf("Слово начинаетя с s[%d]\n",
p-s );
10
else
printf("Слово не найдено.\n" );
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
20
Пример обработки строк
Задача: Ввести имя, отчество и фамилию. Преобразовать их к
формату «фамилия-инициалы».
Пример:
Введите имя, отчество и фамилию:
Василий Алибабаевич Хрюндиков
Результат:
Хрюндиков В.А.
Алибабаевич Хрюндиков
Алгоритм:
• найти первый пробел и выделить имя
Хрюндиков
• удалить имя с пробелом из основной строки
• найти первый пробел и выделить отчество
• удалить отчество с пробелом из основной строки
• «сцепить» фамилию, первые буквы имени и фамилии,
точки, пробелы…
Хрюндиков В.А.
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
21
Пример обработки строк
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 );
}
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
22
Задачи
«A»: Ввести с клавиатуры в одну строку фамилию, имя и
отчество, разделив их пробелом. Вывести фамилию и
инициалы.
Пример:
Введите фамилию, имя и отчество:
Иванов Петр Семёнович
П.С. Иванов
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
23
Задачи
«B»: Ввести адрес файла и «разобрать» его на части,
разделенные знаком '/'. Каждую часть вывести в
отдельной строке.
Пример:
Введите адрес файла:
C:/Фото/2013/Поход/vasya.jpg
C:
Фото
2013
Поход
vasya.jpg
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
24
Задачи
«C»: Напишите программу, которая заменяет во всей строке
одну последовательность символов на другую.
Пример:
Введите строку:
(X > 0) and (Y < X) and (Z > Y) and (Z <> 5)
Что меняем: and
Чем заменить: &
Результат
(X > 0) & (Y < X) & (Z > Y) & (Z <> 5)
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
25
Преобразования «строка» – «число»
Из строки в число:
#include <stdlib.h>
char s[] = "123";
int N;
N = atoi ( s );
// N = 123
«12x3»  12
char s[] = "123.456";
float X;
X = atof ( s );
// X = 123.456
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
26
Преобразования «строка» – «число»
Из числа в строку:
char s[80];
int N = 123;
float X = 123.456;
sprintf(s, "%d", N); // s = "123"
sprintf(s, "%e", X); // s = "1.234560E+002"
sprintf(s, "%10.3f", X);// s = "
123.456"
!
sprintf – вывод в строку, а не на экран!
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
27
Задачи
«A»: Напишите программу, которая вычисляет сумму трех
чисел, введенную в форме символьной строки. Все числа
целые.
Пример:
Введите выражение:
12+3+45
Ответ: 60
«B»: Напишите программу, которая вычисляет выражение,
состоящее из трех чисел и двух знаков (допускаются
только знаки «+» или «–»). Выражение вводится как
символьная строка, все числа целые.
Пример:
Введите выражение:
12-3+45
Ответ: 54
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
28
Задачи
«C»: Напишите программу, которая вычисляет выражение,
состоящее из трех чисел и двух знаков (допускаются
знаки «+», «–», «*» и «/»). Выражение вводится как
символьная строка, все числа целые. Операция «/»
выполняется как целочисленное деление.
Пример:
Введите выражение:
12*3+45
Ответ: 81
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
29
Задачи
«D»: Напишите программу, которая вычисляет выражение,
состоящее из трех чисел и двух знаков (допускаются
знаки «+», «–», «*» и «/») и круглых скобок. Выражение
вводится как символьная строка, все числа целые.
Операция «/» выполняется как целочисленное деление
(div).
Пример:
Введите выражение:
2*(3+45)+4
Ответ: 100
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
30
Строки в процедурах и функциях
Задача: построить процедуру, которая заменяет в строке
s все вхождения слова-образца wOld на слово-замену
wNew.
пока // слово wOld есть в строке s
// удалить слово wOld из строки
// вставить на это место слово wNew
?
wOld: '12'
wNew: 'A12B'
 К.Ю. Поляков, Е.А. Ерёмин, 2014
Что плохо?
зацикливание
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
31
Замена всех экземпляров подстроки
wNew
wOld
а) res
s
s
б) res
wNew
в) res
s
г) res
s
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
32
Замена всех экземпляров подстроки
main()
{
char s[80] = "12.12.12";
replaceAll ( s, "12", "A12B" );
puts ( s );
}
рабочая строка s
"12.12.12"
".12.12"
".12"
""
 К.Ю. Поляков, Е.А. Ерёмин, 2014
результат res
""
"A12B"
"A12B.A12B"
"A12B.A12B.A12B"
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
33
Использование указателей
wNew
pRes
pS
p
wOld
а) res
pRes
s
pS
s
б) res
pRes
wNew
pS
s
в) res
pRes
г) res
 К.Ю. Поляков, Е.А. Ерёмин, 2014
pS
s
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
34
Замена всех экземпляров подстроки
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
}
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
35
Замена всех экземпляров подстроки
Если образец не найден:
p = strstr ( pS, wOld );
if ( p == NULL )
прицепить
«хвост»
{
strcat ( res, s );
break;
выйти из
цикла
}
Если перед образцом что-то есть:
длина блока
перед образцом
if ( p > pS ) {
strncpy ( pRes, pS, p-pS );
pRes += p-pS;
передвинуть
pS = p;
указатели
}
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
36
Задачи
«A»: Напишите процедуру, которая отсекает всю часть строки
после первого слова.
Пример:
Введите строку: Однажды в студёную зимнюю пору...
Первое слово: Однажды
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
37
Задачи
«B»: Напишите процедуру, которая заменяет расширение
файла на заданное новое расширение.
Пример:
Введите имя файла: qq
Введите новое расширение: tmp
Результат: qq.tmp
Пример:
Введите имя файла: qq.exe
Введите новое расширение: tmp
Результат: qq.tmp
Пример:
Введите имя файла: qq.work.xml
Введите новое расширение: tmp
Результат: qq.work.tmp
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
38
Задачи
«C»: Напишите процедуру, которая заменяет во всей строке все
римские числа на соответствующие десятичные числа.
Пример:
Введите строку:
В MMXIII году в школе CXXIII состоялся
очередной выпуск XI классов.
Результат:
В 2013 году в школе 123 состоялся очередной
выпуск 11 классов.
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
39
Рекурсивный перебор
Задача. В алфавите языке племени «тумба-юмба»
четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести
на экран все слова, состоящие из L букв, которые
можно построить из букв этого алфавита.
перебор L-1
символов
Ы
?
?
?
Ш
?
?
?
Ч
?
?
?
0
?
?
?
 К.Ю. Поляков, Е.А. Ерёмин, 2014
задача для слов длины
К сведена к задаче для
слов длины L-1!
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
40
Рекурсивный перебор
перебор L символов
w[0]='Ы';
// перебор последних
w[0]='Ш';
// перебор последних
w[0]='Ч';
// перебор последних
w[0]='О';
// перебор последних
 К.Ю. Поляков, Е.А. Ерёмин, 2014
L-1 символов
L-1 символов
L-1 символов
L-1 символов
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
41
Рекурсивный перебор
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 );
}
алфавита
}
main()
любая строка
{
длины L
char word[] = "...";
TumbaWords ( "ЫШЧО", word, 0 );
}
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
42
Задачи
«A»: В алфавите языке племени «тумба-юмба» четыре буквы:
«Ы», «Ш», «Ч» и «О». Нужно вывести на экран все
возможные слова, состоящие из K букв, в которых вторая
буква «Ы». Подсчитайте количество таких слов.
«B»: В алфавите языке племени «тумба-юмба» четыре буквы:
«Ы», «Ш», «Ч» и «О». Нужно вывести на экран все
возможные слова, состоящие из K букв, в которых есть по
крайней мере две одинаковые буквы, стоящие рядом.
Подсчитайте количество таких слов.
Программа не должна строить другие слова, не
соответствующие условию.
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
43
Задачи
«C»: В алфавите языке племени «тумба-юмба» четыре буквы:
«Ы», «Ш», «Ч» и «О». Нужно вывести на экран все
возможные слова, состоящие из K букв, в которых есть по
крайней мере две одинаковые буквы, не обязательно
стоящие рядом.
Программа не должна строить другие слова, не
соответствующие условию.
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
44
Сравнение строк
Пар ? пар ? парк
Сравнение по кодам символов:
CP-1251
UNCODE
CP-1251
UNCODE
CP-1251
UNCODE
0
48
48
1
49
49
...
...
...
8
56
56
9
57
57
A
65
B
66
...
...
Y
89
Z
90
65
66
...
89
90
a
b
...
y
z
97
97
98
98
...
...
121
121
122
122
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
45
Сравнение строк
А
Б
CP-1251 192 193
UNCODE 1040 1041
...
...
...
Ё
168
1025
...
...
...
Ю
Я
222 223
1070 1071
а
б
CP-1251 224 225
UNCODE 1072 1073
...
...
...
ё
184
1105
...
...
...
ю
я
254 255
1102 1103
5STEAM < STEAM < Steam < steam
steam < ПАР < Пар < пАр < пар < парк
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
46
Сортировка строк
main()
{
массив строк
const int N = 10;
char s1[80], S[N][80];
int i, j;
printf ( "Введите строки: \n" );
for ( i = 0; i < N; i ++ )
for ( i = 0; i < N-1; i ++ )
gets ( S[i] );
for ( j = N-2; j >= i; j -- )
...
if( strcmp(S[j],S[j+1])> 0 )
printf ( "После сортировки:
{ \n" );
for ( i = 0; i < N; i ++ )
strcpy (s1, S[j]);
puts ( S[i] );
strcpy (S[j], S[j+1]);
}
strcpy (S[j+1], s1);
}
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
47
Задачи
«A»: Вводится 5 строк, в которых сначала записан порядковый
номер строки с точкой, а затем – слово. Вывести слова в
алфавитном порядке.
Пример:
Введите 5 строк:
1. тепловоз
2. арбуз
3. бурундук
4. кефир
5. урядник
Список слов в алфавитном порядке:
арбуз, бурундук, кефир, тепловоз, урядник
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
48
Задачи
«B»: Вводится несколько строк (не более 20), в которых сначала
записан порядковый номер строки с точкой, а затем –
слово. Ввод заканчивается пустой строкой. Вывести
введённые слова в алфавитном порядке.
Пример:
Введите слова:
1. тепловоз
2. арбуз
Список слов в алфавитном порядке:
арбуз, тепловоз
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
49
Задачи
«C»: Вводится несколько строк (не более 20), в которых сначала
записаны инициалы и фамилии работников фирмы. Ввод
заканчивается пустой строкой. Отсортировать строки в
алфавитном порядке по фамилии.
Пример:
Введите ФИО:
А.Г. Урядников
Б.В. Тепловозов
В.Д. Арбузов
Список в алфавитном порядке:
В.Д. Арбузов
Б.В. Тепловозов
А.Г. Урядников
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
50
Программирование
на языке Си
§ 67. Матрицы
 К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
51
Что такое матрица?
нолик
нет знака
0
1
2
0
-1 0
1
крестик
1
-1 0
1
строка 1,
столбец 2
2
?
0
1 -1
Как закодировать?
Матрица — это прямоугольная таблица, составленная
из элементов одного типа (чисел, строк и т.д.).
Каждый элемент матрицы имеет два индекса –
номера строки и столбца.
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
52
Объявление матриц
const int N = 3, M = 4;
int A[N][M];
double X[10][12];
bool L[N][2];
строки
столбцы
строки
!
столбцы
Нумерация строк и столбцов с нуля!
?
Если удобна нумерация с 1?
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
53
Простые алгоритмы
Заполнение случайными числами:
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];
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
54
Задачи
«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
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
55
Задачи
«B»: Яркости пикселей рисунка закодированы числами от 0 до 255 в
виде матрицы. Преобразовать рисунок в черно-белый по
следующему алгоритму:
1) вычислить среднюю яркость пикселей по всему рисунку
2) все пиксели, яркость которых меньше средней, сделать
черными (записать код 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
0 255
255 255
0
0
255
0
0
0
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
56
Задачи
«С»: Заполните матрицу, содержащую N строк и M столбцов,
натуральными числами по спирали и змейкой, как на рисунках:
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
57
Перебор элементов матрицы
Главная диагональ:
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]
}
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
58
Перестановка строк
2-я и 4-я строки:
for ( j = 0; j < M; j++ )
{
c = A[2][j];
A[2][j]= A[4][j];
A[4][j]= c;
}
 К.Ю. Поляков, Е.А. Ерёмин, 2014
0 1 2 3 4 5
0
1
2
3
4
5
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
59
Задачи
«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
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
60
Задачи
«B»: Пиксели рисунка закодированы числами (обозначающими
цвет) в виде матрицы, содержащей N строк и M столбцов.
Выполните отражение рисунка сверху вниз:
1
2
3
7
8
9
4
5
6
4
5
6
7
8
9
1
2
3
«С»: Пиксели рисунка закодированы числами (обозначающими
цвет) в виде матрицы, содержащей N строк и M столбцов.
Выполните поворот рисунка вправо на 90 градусов:
1
2
3
7
4
1
4
5
6
8
5
2
7
8
9
9
6
3
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
61
Программирование
на языке Си
§ 68. Работа с файлами
 К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
62
Как работать с файлами?
файлы
текстовые
«plain text»:
• текст, разбитый на строки;
• из специальных символов
только символы перехода
на новую строку
 К.Ю. Поляков, Е.А. Ерёмин, 2014
двоичные
• любые символы
• рисунки, звуки, видео, …
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
63
Принцип сэндвича
хлеб
начинка
хлеб
открыть файл
работа с файлом
закрыть файл
файловые переменныеуказатели
FILE *Fin, *Fout;
Fin = fopen ( "input.txt", "r" );
Fout = fopen ( "output.txt", "w" );
// здесь работаем с файлами
fclose (Fin);
"r" - чтение
fclose (Fout);
"w" – запись
"a" – добавление
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
64
Обработка ошибок
!
В случае неудачи fopen возвращает NULL!
FILE *F;
F = fopen ( "input.txt", "r" );
if ( F ) if ( F != NULL )
{
// здесь работаем с файлом
}
else
printf("Открыть файл не удалось.");
?
Когда такое может быть?
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
65
Ввод данных
int a, b;
FILE *Fin;
Fin = fopen("input.txt", "r");
fscanf( Fin, "%d%d", &a, &b );
fclose(Fin);
Переход к началу открытого файла:
fclose(Fin);
Fin = fopen("input.txt", "r");
Определение конца файла:
eof = end of file, конец файла
if ( feof(Fin) )
printf("Данные кончились");
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
66
Вывод данных в файл
int a = 1, b = 2;
FILE *Fout;
Fout = fopen("output.txt", "w");
fprintf ( Fout, "%d+%d=%d", a, b, a+b );
fclose(Fout);
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
67
Чтение неизвестного количества данных
Задача. В файле записано в столбик неизвестное
количество чисел. Найти их сумму.
пока не конец файла
// прочитать число из файла
// добавить его к сумме
int n, S, x;
S = 0;
fscanf возвращает количество
while( 1 )
прочитанных данных!
{
n = fscanf ( Fin, "%d", &x );
if ( n < 1 ) break;
S = S + x;
при неудачном чтении
}
выход из цикла
!
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
68
Задачи
«A»: Напишите программу, которая находит среднее
арифметическое всех чисел, записанных в файле в
столбик, и выводит результат в другой файл.
«B»: Напишите программу, которая находит минимальное и
максимальное среди чётных положительных чисел,
записанных в файле, и выводит результат в другой файл.
Учтите, что таких чисел может вообще не быть.
«C»: В файле в столбик записаны целые числа, сколько их –
неизвестно. Напишите программу, которая определяет
длину самой длинной цепочки идущих подряд одинаковых
чисел и выводит результат в другой файл.
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
69
Обработка массивов
Задача. В файле записано не более 100 целых чисел.
Вывести в другой текстовый файл те же числа,
отсортированные в порядке возрастания.
?
!
В чем отличие от предыдущей задачи?
Для сортировки нужно удерживать все элементы в
памяти одновременно.
const int MAX = 100;
int A[MAX];
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
70
Обработка массивов
Ввод массива:
N = 0;
while ( N < MAX )
Зачем?
{
r = fscanf ( Fin, "%d", &A[N] );
if ( r < 1 ) break;
N ++;
}
?
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
71
Обработка массивов
Вывод результата:
Fout = fopen ( "output.txt", "w" );
for ( i = 0; i < N ; i++ )
fprintf ( Fout, "%d\n", A[i] );
fclose ( Fout );
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
72
Задачи
«A»: В файле записано не более 100 чисел. Отсортировать их
по возрастанию последней цифры и записать в другой
файл.
«B»: В файле записано не более 100 чисел. Отсортировать их
по возрастанию суммы цифр и записать в другой файл.
Используйте функцию, которая вычисляет сумму цифр
числа.
«C»: В двух файлах записаны отсортированные по возрастанию
массивы неизвестной длины. Объединить их и записать
результат в третий файл. Полученный массив также
должен быть отсортирован по возрастанию.
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
73
Обработка строк
Задача. В файле записано данные о собаках: в каждой
строчке кличка собаки, ее возраст и порода:
Мухтар 4 немецкая овчарка
Вывести в другой файл сведения о собаках, которым
меньше 5 лет.
пока не конец файла(Fin)
// прочитать строку из файла Fin
// разобрать строку – выделить возраст
если возраст < 5 то
// записать строку в файл Fout
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
74
Чтение строк из файла
Чтение одной строки:
char s[80];
строка
файл
char *p;
p = fgets( s, 80, Fin );
размер
!
При неудаче fgets вернет NULL!
Чтение всех строк:
while ( fgets(s, 80, Fin)
{
// обработать строку s
}
 К.Ю. Поляков, Е.А. Ерёмин, 2014
)
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
75
Обработка строк
Разбор строки:
//
//
//
//
//
найти в строке пробел
удалить из строки кличку с первым пробелом
найти в строке пробел
выделить возраст перед пробелом
преобразовать возраст в числовой вид
char s[80], *p;
p+1
int age;
Мухтар 4 немецкая овчарка
...
p = strchr ( s, ' ' );
sscanf ( p+1, "%d", &age );
не влияет!
чтение из
строки
строка
(адрес)
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
76
Задачи
«A»: В файле записаны данные о результатах сдачи экзамена.
Каждая строка содержит фамилию, имя и количество
баллов, разделенные пробелами:
<Фамилия> <Имя> <Количество баллов>
Вывести в другой файл фамилии и имена тех учеников,
которые получили больше 80 баллов.
«B»: В предыдущей задаче добавить к полученному списку
нумерацию, сократить имя до одной буквы и поставить
перед фамилией:
П. Иванов
И. Петров
...
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
77
Задачи
«C»: В файле записаны данные о результатах сдачи экзамена.
Каждая строка содержит фамилию, имя и количество
баллов, разделенные пробелами:
<Фамилия> <Имя> <Количество баллов>
Вывести в другой файл данные учеников, которые
получили больше 80 баллов. Список должен быть
отсортирован по убыванию балла. Формат выходных
данных:
П. Иванов 98
И. Петров 96
...
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
78
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной
дидактики и ИТО ПГГПУ, г. Пермь
[email protected]
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru
Алгоритмизация и программирование, язык Си, 10 класс
79
Источники иллюстраций
1.
2.
3.
www.mcdonalds.com
иллюстрации художников издательства «Бином»
авторские материалы
 К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

similar documents