Уроки 27 - 28
Символьные строки. Функции для работы с символьными строками
§66. Символьные строки

Содержание урока

Что такое символьная строка?

Операции со строками

Поиск в строках

Пример обработки строк

Преобразования число ↔ строка

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

Рекурсивный перебор

Сравнение и сортировка строк

Вопросы и задания

Задачи

Рекурсивный перебор

В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все слова, состоящие из К букв, которые можно построить из букв этого алфавита.

Это типичная задача на перебор вариантов, которую удобно свести к задаче меньшего размера. Будем определять буквы слова последовательно, одну за другой. Первая буква может быть любой из четырёх букв алфавита. Предположим, что сначала первой мы поставили букву 'Ы'. Тогда для того, чтобы получить все варианты с первой буквой 'Ы', нужно перебрать все возможные комбинации букв на оставшихся К - 1 позициях:

Далее поочерёдно ставим на первое место все остальные буквы, повторяя процедуру:

Здесь через w обозначена символьная строка, в которой хранится рабочее слово. Таким образом, задача для слов длины К свелась к 4 задачам для слов длины К - 1. Как вы знаете, такой прием называется рекурсией, а процедура — рекурсивной.

Когда рекурсия должна закончиться? Тогда, когда все символы будут расставлены. При этом нужно вывести получившееся слово на экран и выйти из процедуры.

Подсчитаем количество всех возможных слов длины К. Очевидно, что слов длины 1 всего 4. Добавляя ещё одну букву, получаем 4 • 4 = 16 комбинаций, для трёх букв — 4 • 4 • 4 = 64 слова и т. д. Таким образом, из 4 букв можно составить 4^K слов длины К.

В основной программе построим слово (символьную строку) word нужной длины (что в ней будет записано, не имеет значения). Процедуре TumbaWords передаётся алфавит в виде символьной константы, слово word и число уже установленных символов (в начале — 0):

В процедуре используется описанный выше рекурсивный алгоритм:

Если условие в начале процедуры ложно (не все символы расставлены), в цикле перебираем все символы алфавита и поочерёдно ставим их на первое свободное место, а затем вызываем рекурсивно эту же процедуру, увеличивая третий параметр на 1. Поскольку школьный алгоритмический язык не позволяет менять переменную-аргумент, мы вынуждены ввести дополнительную локальную переменную w.

Приведём аналогичную программу на Паскале:

Следующая страница Сравнение и сортировка строк

Cкачать материалы урока