Разработать программу, осуществляющую поиск заданной строки в отсортированном в соответствии с латинским алфавитом массиве строк MasStr[n], n<100. Конкретное количество строк массива определять в процессе их ввода.
Ввод строк организуем в цикле-пока. В качестве условия завершения ввода будем использовать ввод пустой строки. Количество вводимых записей будем считать. Если введено меньше 99 слов, то после завершения ввода уменьшим количество введенных строк на 1, чтобы не обрабатывать пустую строку.
Поиск строк может быть реализован несколькими способами.
В а р и а н т 1. Самый простой способ поиска - последовательный. При последовательном способе запись за записью сравниваем строки в массиве с заданной строкой. Но данный вид поиска является и самым продолжительным по времени. Оценим время поиска. Если искомая строка совпадает с первой строкой массива, то в процессе поиска будет выполнено одно сравнение. Если искомая строка совпадает с последней строкой, то - n сравнений. В среднем в процессе поиска понадобится выполнить (n+1)/2 сравнений.
В а р и а н т 2. Для ускорения обработки можно реализовать двоичный поиск. Этот метод применим, т.к. массив отсортирован по возрастанию кодов символов строк. Метод двоичного поиска заключается в следующем. Определяют примерную середину массива и проверяют, совпадает ли искомый элемент с элементом в середине массива. Если совпадает, поиск завершен. Если не совпадает, то, если элемент больше среднего, то поиск продолжают в левой половине массива, иначе - в правой половине. Таким образом, диапазон элементов на каждом шаге уменьшается больше, чем вдвое. Если диапазон сократился до нуля, а элемент не найден, то такой элемент в массиве отсутствует.
Рассмотрим пример реализации двоичного поиска для массива, включающего 10 элементов. На первом шаге осуществляется проверка 5-го элемента, и массив разбивается на два подмассива: 1...4 и 6...10. На втором шаге - 2-го, если искомое значение меньше 5-го элемента, или 8-го, если искомое значение больше 5-го элемента. Затем проверяются значения третьего уровня и т.д.
Пример дерева двоичного поиска для исходного диапазона из 10 элементов
Оценим время поиска для данного метода. Будем считать, что дерево поиска строки получилось сбалансированным, т.е. количество записей n= 2j-1, где j=1, 2, 3 и т.д., тогда количество уровней дерева равно log2n. Считая, что искомое значение может с равной вероятностью находиться налюбом уровне, получаем, что среднее количество сравнений равно(log2n +1)/2, что при больших значениях n существенно лучше, чем при последовательном поиске.
Реализуем двоичный поиск.
Программа:
Состав задания.
Задание 1 (Среда Delphi). Обработка строк
Условие задачи. Дан текст: Наступила зима (температура -5 градусов). Выпал снег(10 см). Исключить из текста группы символов, расположенных между скобками ” (” и ”)”. Сами скобки должны быть исключены. Предполагается, что внутри каждой пары скобок нет других скобок.
1. Конструирование формы:
При выполнении задания на форме были размещены следующие компоненты:
Button1 – кнопка, имеющая заголовок Выполнить, при нажатии которой первоначальный текст из программы заносится в компонент Edit1, а преобразованный текст заносится в компонент Edit2.
Button2 – кнопка, имеющая заголовок Закрыть, при нажатии которой форма закрывается.
Edit1 – компонент предназначенный для отображения первоначального текста до изменения его.
Edit2 – компонент предназначенный для отображения текста после изменения его.
Программа
Результат
Задание 2 (Среда Delphi). Обработка записей
Пример программы обработки записей:
1.Конструирование формы:
При выполнении задания на форме были размещены следующие компоненты:
- TLabel – используется для создания комментариев. Для этого использовалось свойство компонента Caption, которое имеет строковый тип.
- TEdit – данный компонент был использован для ввода исходных данных о студентах.
- TButton – кнопка, при нажатии которой производятся действия по запоминанию данных о студентах. Код прописан в методе OnClick, который срабатывает при нажатии кнопки во время исполнения программы. Комментарий на кнопке прописывается в свойстве кнопки Caption.
- TGroupBox – компонент, предназначенный для группировки внутри себя других компонентов. Заголовок компонента прописывается в его свойстве Caption.
- TMemo – компонент, позволяющий отображать текстовую информацию. Для внесения дополнительной информации используется метод Append() свойства Lines.
2. Условие:
Ввести информацию о 10 студентах группы. Информация содержит фамилию, имя, отчество студента, год рождения, четыре оценки за экзамены последней сессии. Распечатать анкетные данные студентов, получивших в последнюю сессию оценку 2.
3. Форма:
4. Программа:
5.Результат:
Индивидуальные задания
1. Дана строка текста длиной не более 80 символов, состоящая из слов, разделенных пробелом, в конце точка. Составить программу, определяющую номера слов, в которых содержится более трех символов «А». Вывести исходную строку и номера слов. Если слов с таким числом букв не окажется, вывести соответствующее сообщение.
2. Дана строка текста длиной не более 40 символов, состоящая из слов, разделенных пробелом, в конце точка. Составить программу, удаляющую из текста слово, содержащее максимальное количество букв «В». Вывести исходную и преобразованную строки. Если в тексте нет слов с буквой «В» - вывести соответствующее сообщение.
3. Дан массив символьных строк, длиной не более 40 символов. Строки состоят из слов, разделенных пробелом, в конце точка. Составить программу, формирующую одномерный массив В, содержащий в качестве элементов количество слов каждой строки, начинающихся на гласную букву. Если таких слов нет, в соответствующий элемент массива В занести 0. Вывести исходный и сформированный массивы.
4. Дана строка, состоящая из слов, разделенных одним пробелом. Составить программу, разбивающую исходную строку на подстроки, размер которых не превышает заданного значения n. Перенос слов считать запрещенным.
5. Составить программу, осуществляющую «выравнивание по ширине» подстрок, полученных в результате работы программы задания 4. Выравнивание должно выполняться таким образом, чтобы дополнительные пробелы между словами распределялись по подстроке равномерно.
