Обработка символьных строк. Рекурсивный перебор. Сравнение и сортировка строк.

53-54 урок, 10 класс – практика

Учитель: Брух Т.В.

Дата: ____________

Тема урока: Обработка символьных строк. Рекурсивный перебор. Сравнение и сортировка строк.

Цели: Обучать работе с символьными строками.

Развивать логическое мышление.

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

Ход урока:

1. Организационный момент

2. Проверка домашнего задания.

3. Изучение нового материала

Строкой называется последовательность заданной длины, состоящая из символов.

Строки (переменные типа String) могут быть объявлены, например, таким образом:

При объявлении строковой переменной в квадратных скобках может указываться длина строки. Если длина строки не указывается, то она принимается равной 255. Надо заметить, что строка похожа на одномерный массив символов: она имеет определенную длину (не больше некоторого числа), к каждому символу можно обратиться по его номеру (как в массиве) - Str[i] - это обращение к i-му элементу строки Str.

Переменные типа String выводятся на экран посредством стандартных процедур Write и Writeln и вводятся с помощью стандартных процедур Redad и Redln. То есть вводятся и выводятся не поэлементно, а целиком.

Примечание. Если при вводе задать символов больше, чем максимально допустимо, то лишние символы будут проигнорированы.

В Паскале имеется два основных способа обработки строковых переменных. Первый способ предполагает обработку всей строки как одного целого. Второй способ предполагает рассмотрение строки как составного элемента, т.е. объекта, состоящего из отдельных символов, то есть элементов типа Char, которые при обработке доступны каждый в отдельности.

СКЛЕИВАНИЕ

Под склеиванием понимается последовательное объединение нескольких строк:

СРАВНЕНИЕ

Паскаль позволяет выполнить сравнение двух строк. Сравнение производится посимвольно слева направо: сравниваются коды соответствующих символов до тех пор, пока не нарушится равенство или не кончится одна из строк (или обе сразу), при этом сразу делается вывод о знаке неравенства. Две строки называются равными, если они равны по длине и совпадают посимвольно:

Можно использовать любые операции отношения (, =, =True или False.

Для доступа к отдельному символу в строке необходимо указать имя строки и в квадратных скобках номер позиции символа в строке. При этом по отношению к отдельному символу строки возможны все те же операции, что и к переменной типа Char.

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

УДАЛЕНИЕ

Для удаления из строки фрагмента используется процедура Delete (Str, n, m), которая вырезает из строки Str m символов, начиная с n-го, таким образом, сама строка изменяется.

После выполнения этих операторов из строки будут удалены четыре символа начиная с третьего, то есть строка будет такой: Str1='ABGH'.

ВСТАВКА

Для вставки в строку используется процедура Insert (Strl, Str2, п), которая вставляет строку Strl в строку Str2 начиная с n-го символа, при этом первая строка остается такой же, как и была, а вторая получает новое значение.

После выполнения этих операторов строка будет такой - Str2=' abABCDEFGHcdefgh';

Этот же результат будет и при выполнении такой последовательности операторов:

КОПИРОВАНИЕ

Функция Copy (Str, n, m) копирует m символов строки Str начиная с n-го символа, при этом исходная строка не меняется.

ДЛИНА СТРОКИ

Под длиной строки понимается фактическое, (а не максимально возможное) количество символов в строке. Это значение можно найти при помощи процедуры Length (Str), результат которой - целое число, равное количеству символов.

ПОИСК ПОДСТРОКИ

В Паскале имеется функция, определяющая позицию подстроки в строке, - Pos (Strl, Str2) . Результатом этой функции - целое число, и оно определяет номер элемента, с которого начинается первое вхождение подстроки strl в строку Str2. Если Strl не входит в Str2, то значение функции равно 0.

ЧИСЛА И СТРОКИ

Часто возникает необходимость получить строковое представление числа и наоборот (например, получить строку '15' из числа 15). Для работы с числами и строками применяются две процедуры.

str (N, strl) - переводит числовое значение N в строковое и присваивает результат строке Strl, причем можно переводить как целые числа, так и вещественные.

Вторая процедура выполняет обратное действие. Val (Str, N, К) - переводит строковое значение в числовое. Если данная строка действительно является записью числа (вещественного или целого), то значение К=0, а N - это искомое число, иначе К будет равно номеру первого символа, с которым процедура Val «не справилась».

Пример: Сколько раз в данной строке встречается символ «а»?

Решение: Опишем функцию, которой будем передавать строку. Результат выполнения - целое число.

Пример: Если в строке нечетное количество символов, то удалить средний.

Решение:

Пример: Заменить все вхождения подстроки 'del' на 'insert'.

Решение: Пока такая подстрока встречается, необходимо находить номер первого символа очередного вхождения подстроки 'del', удалять 'del' и вставлять 'insert'.

Пример: Подсчитать сумму цифр; входящих в данную строку.

Решение:

Пример: Сколько раз в данной строке встречается гласные буквы русского алфавита?

Решение:

Пример: Введённую с клавиатуры строку А записать в обратном порядке в строку Б. Строку Б вывести на экран.

Решение:

Сущность рекурсии

Процедура или функция может содержать вызов других процедур или функций. В том числе процедура может вызвать саму себя. Никакого парадокса здесь нет – компьютер лишь последовательно выполняет встретившиеся ему в программе команды и, если встречается вызов процедуры, просто начинает выполнять эту процедуру. Без разницы, какая процедура дала команду это делать.

Пример рекурсивной процедуры:

Сложная рекурсия

Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией. При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать опережающее описание.

Пример:

4. Практическая работа:

Смотри приложение

5. Домашнее задание: конспект.