Методич_стат-исправлено. Методические указания по курсу Информатика
 Скачать 2.11 Mb.
|
Базовые алгоритмы обработки текстаС определенной долей условности можно выделить ряд действий, которые чаще других выполняются в программах, работающих с текстовой информацией. К таким действиям можно отнести:
Каждому действию соответствует группа алгоритмов, которая имеет определенную специфику приложения к разным задачам Определение количества символов в строке Длину текстовой переменной вычисляет функция LEN. Она возвращает числовое значение целого типа (INTEGER), которое равно общему количеству знаков в анализируемой строке. Пример 8. Определить количество символов в переменной «Москва» A$ = “Москва” x = LEN (A$) PRINT X Результат: 6 Функция LEN может быть частью выражения или аргументом оператора. В частности, данную программу можно записать и в одну строку: PRINT LEN("Москва”) В качестве аргумента функции LEN можно ввести не только одну текстовую переменную, но и выражение с несколькими переменными и специальными функциями. Выделение символов Необходимость выделения определенного символа или символов текстовой переменной диктуется условиями, большого количества задач. Под выделением понимают нахождение знака, вывод его на экран или любой другой вид обработки. Естественно, что выделяют знаки, удовлетворяющие определенному условию, Алгоритмы, решающие подобные задачи, как правило, работают в два этапа: сначала выделяют очередной знак переменной, затем анализируют его на удовлетворение условию. Поочередное выделение всех знаков переменной осуществляется в цикле с помощью функции MID$. Пример 9. Вывести на экран буквы слова «Хорошо» по одной в каждой строке A$ = "Хорошо" 'Задаем переменную x = LEN(A$) 'и определяем ее длину FOR i = 1 TO x tmp$ = MID$(A$, i, 1) 'Присваиваем очередной значение переменной tmp$ PRINT tmp$ 'Выводим знак NEXT i PRINT LEN("Москва") Результат X о р о ш о 6 Работа программы. Переменной A$ присваиваем строку символов “Хорошо”. Определяем длину слова и сохраняем это значение в переменной х. Задаем цикл, счетчик которого изменяется от 1 до х. В ходе каждой итерации цикла функция MID$ будет присваивать tmp$ очередной (i-й) символ переменной A$. При этом значение самой А$ не изменяется, то есть MID$ не вырезает знак из нее, а просто копирует и присваивает его переменной tmp$. С очередной итерацией цикла в tmp$ передается очередной знак. При i = 1 передается первый знак, при i - 2 — второй, и так далее. На то, что передастся один знак, указывает третий параметр в списке аргументов MID$. Пример 10. Определить сколько раз встречается буква «а» в слове «абракадабра» А$ ="абракадабра" FOR i = 1 TO LEN(a$) tmp$ = MID$(a$, i, 1) 'Выделяем букву IF tmp$ = "а" THEN k = k + 1 'Сравниваем букву с "а" NEXT i PRINT k 'Выводим результат Результат: 5 Работа программы. В цикле функция MID$ поочередно выделяет буквы из слова абракадабра и присваивает их переменной tmp$. В строке с оператором IF проверяется, содержит ли tnp$ букву а. Если tmp$= "a", то значение счетчика k увеличивается на 1. Функция MID$ — не единственный инструмент выделения знаков из текстовой переменной. В некоторых случаях Пример 11.Удалить первый и последний символ текстовой переменной. a$ = " В Россию можно только верить." a$ = LEFT$(a$, LEN(a$) - 1) a$ = RIGHT$(a$, LEN(a$) - 1) PRINT a$ Выделение знаков, номера которых обладают определенными свойствами, происходит с использованием операторов логической передачи управления. Пример 12. Сформировать В$, состоящую из знаков A$. порядковые номера, которых кратны N. n = 3 a$ = "cиСтеМныЙ бЛок" FOR i = 1 TO LEN(a$) tmp$ = MID$(a$, i, 1) IF i / n = i \ n THEN B$ = B$ + tmp$ NEXT i PRINT B$ Результат: СМЙЛ! Работа программы. Программа выделяет каждый третий знак строки A$ и прибавляет его к В$, в которой накапливается текстовая сумма выделенных знаков. Условие выбора описано в операторе IF. Выделение логической группы Логической группой называют совокупность знаков, которая объединена общими свойствами. К таким группам можно отнести гласные и согласные буквы русского алфавита, буквы латинского алфавита, цифры, строчные и прописные буквы и многие другие. Каждый алгоритм анализа символа содержи три основных действия :
Анализ заключается в проверке, соответствует ли знак условию принадлежности к логической группе. Как правило, анализ основан на сравнении выделенного знака с определенным ASCII-кодом или диапазоном номеров. Обработка в соответствии с решаемой задачей определяет то, что нужно делать с выделенным символом или текстом в целом, и может подразумевать большой спектр действий. Пример 13. Определить, сколько в слове «АВРОРА» русских букв А и Р. A$ = "ABPOPA" FOR i = 1 TO LEN(A$) tmp$ = MID$(A$, i, 1) IF tmp$ = "A" OR tmp$ = "P" THEN k = k + 1 NEXT i PRINT k Результат: 4 Приведенная программа имеет недостаток — она определяет наличие только заглавных А и Р. Если значение исходной переменной присваивается оператором INPUT, то есть вводится пользователем, то при вводе строчных букв результат будет неверным. Пример 14. Определить к какому языку и регистру клавиатуры относится данная буква. INPUT a$ SELECT CASE ASC(a$) CASE 65 TO 90: PRINT " Лат.ЗАГЛАВНАЯ " CASE 97 TO 122: PRINT "Лат. Строчная" CASE 12 TO 159: PRINT "Русс. ЗАГЛАВНАЯ" CASE 160 TO 175: PRINT "Русс. Строчная" CASE 224 TO 239: PRINT "Русс. Строчная" CASE ELSE: PRINT "НЕ является БУКВОЙ" END SELECT Работа программы. Алгоритм основан на использовании конструкции логической передачи управления SELECT CASE. Она анализирует ASCII-код введенного знака, который выдает функция ASC. В каждом CASE указан диапазон возможных значений, соответствующей группе букв. Большой спектр задач выделения и анализа фрагментов строк решается с помощью функции INSTR. Пример 15. Определить, входит ли строка В$="dow" в слово, A$ = "Windows". INPUT A$ INPUT B$ k = INSTR(A$, B$) IF k > 0 AND LEN(B$) > 0 THEN PRINT "Yes" ELSE PRINT "No" END Результат: Yes Работа программы. Алгоритм основан на работе функции INSTR. Результатом ее работы является целое число k равное номеру знака в А$, с которого начинается вхождение B$. Естественно, что если k больше нуля, то В$ входит в А$. Условие в операторе IF состоит из двух компонентов. В одном проверяется значение k, во втором (LEN(B$) > 0) — длина переменной В$. Второе условие введено для того, чтобы выдать отрицательный ответ в случае ввода нулевой переменной. Иначе при В$="" значение k будет равно 1, и программа определит вхождение. Пример 16. Определить, сколько раз B$ входит в A$. A$ = "промышленное производство проводов" B$="про" i = 1 k = 0 DO x = INSTR(i, A$, B$) IF x > 0 THEN i = x + LEN(B$) ' Номер начала поиска k = k + 1 ' Счетчик вхождений ELSE EXIT DO ' Выход из цикла END IF LOOP PRINT "всего вхождений="; k Результат: Всего вхождений= 3 Работа программы. Цикл DO …LOOP использован потому, что заранее неизвестно, сколько будет вхождений. В строке i = x + LEN(B$) номер начала поиска передвигается направо. Если программа найдет первое вхождение, то нужно будет продолжить поиск с позиции, номер которого равен номеру начала вхождения плюс длина искомого слова. В примере первое вхождение «про» в «промышленное производство проводов» начинается с первой позиции, следователь но, продолжать поиск нужно с 4-й позиции (1 + LEN(B$)=1+3=4). Если обнаруженное вхождение нужно заменить другой строкой, то используют оператор MID$. Пример 17. Заменить все пробелы на тире в тексте А$. A$= "Погиб поэт! невольник чести!" FOR i = 1 TO LEN(A$) IF ASC(MID$(A$, i, 1)) = 32 THEN MID$(A$, i, 1) = "-" NEXT i PRINT A$ Результат: Погиб-поэт!-невольник-чести! Работа программы. В цикле поочередно выделяются знаки переменной А$. Функция ASC определяет АSCII-код знака, но в том случае, если номер равен 32 (ASCII-код пробела), оператор MID$ заменяет текущий символ знаком «минус» (тире). Сортировка текстовых массивовПример 18. Дан массив текстовых переменных. Отсортировать по всем знакам каждого слова в соответствии с алфавитом. CLS DATA "512","101","324","712","310","520","001","721" REM Формируем исходный массив A$ n = 8 DIM a$(n) PRINT "Исходный массив" FOR i = 1 TO n READ a$(i) PRINT " "; a$(i); NEXT i REM Сортировка FOR i = 1 TO n FOR j = 1 TO n k = 1 IF ASC(MID$(a$(i), k, 1)) < ASC(MID$(a$(j), k, 1)) THEN SWAP a$(i), a$(j) ELSE IF ASC(MID$(a$(i), k, 1)) = ASC(MID$(a$(j), k, 1)) THEN k = k + 1 END IF IF MID$(a$(j), k, 1) = "" THEN SWAP a$(i), a$(j) NEXT j NEXT i REM вводим отсортированный массив на экран PRINT "Отсортированный" FOR i = 1 TO n PRINT " "; a$(i); NEXT i Результат: Исходный массив 512 101 324 712 310 520 001 721 Отсортированный 001 101 310 324 520 512 712 721 Для других исходных данных: Исходный Яковлев А. Андреев Д., Сланов Р., Ананко Р., Ваниёва Р., Антонов И.. Шейхов М, Гринберг Л., Галич Г., Сапин В. Отсортированный Ананко Р., Андреев Д., Антонов И.., Ваниева Р., Галич Г., Гринберг Л., Санин В., Сланов Р., Шейхов М., Яковлев А. Работа программы. Алгоритм, как и многие программы сортировки, основан па сравнении слов во вложенных циклах. Внешний цикл со счетчиком i задает номер слова для анализа. Внутренний цикл со счетчиком j сравнивает это слово со всеми остальными и при необходимости меняет его на другое. Логической группой может быть не только язык или тип символов, но и отдельная переменная. Пример 19. Состоит ли В$ только из символов, входящих в А$. По количеству знаков переменные не равны. a$ = "123456" b$ = "654" DO k = k + 1 tmp$ = MID$(b$, k, 1) IF INSTR(a$, tmp$) = 0 THEN rez = 1: EXIT DO LOOP WHILE k < LEN(b$) IF rez = 1 THEN PRINT "НЕ состоит" ELSE PRINT " Состоит " Результат: Состоит Работа программы. Идея алгоритма состоит в том, что каждый элемент BS проверяется на вхождение в AS. Если обнаружено хотя бы одно несовпадение, проверка закапчивается и машина выводит ответ о том, что В$ не состоит только из символов А$. На основе подобного алгоритма можно решать любые задачи, связанные со сравнением одной строки символов с группой других. Например, поиск слова или числа с неповторяющимися знаками, поиск символа, который реже или чаще; других встречается в тексте, определение слова с наибольшим содержанием заданного знака. Изменение текста путем вставки или удаления знаков В Qbasic нет операторов, которые позволяют вставить новые элементы, раздвинув слово. Поэтому вставка символов осуществляется путем составления новой переменной, которая формируется из следующих частей исходного слова: первая_частъ + вставка + вторая часть. Например, для того чтобы в переменную 0$="АС" вставить букву В. нужно создать новую переменную А$="А" I "B"+"C". Такая же логика применяется в задачах поиска и замены. В них нужно не только выделить определенную последовательность символов, по и заменить ее другой, не изменив структуры исходной переменной. Причем таких замен для одной строки может быть несколько, и реализуются они в цикле. Удаление части исходной строки проходит аналогично. Программа формирует новую переменную, в которую записываются все символы исходной строки, кроме удаляемых. Структуру новой переменной можно представить формулой: символы_до_удаляемых + символы после_удаляемых. Например, чтобы из переменной А$= "ABC" удалить В. Нужно создать новую переменную G$="А"+"С". Рассмотрим ряд примеров вставки и удаления фрагментов текста. Пример 20. Разделить цепочку литер «QuickBasic 4.5», вставив, робел между буквами «k» и «В». (Примем во внимание, что k - это 5-й по счету символ слева, а В - 9-й символ справа в А$). a$ = "QuickBASIC 4.5" b$ = LEFT$(a$, 5) + "_" + RIGHT$(a$, 9) PRINT b$ Результат: Quick_BASIC 4.5 Работа программы. В переменную В$ записывается сумма первой части A$, которая должна быть расположена слева от пробела, знак «пробел» и вторая часть исходной цепочку, которая должна стоять справа от пробела. Особого внимания заслуживают задачи, в которых переменную необходимо изменять несколько раз в зависимости от условия. Эти алгоритмы предполагают использование цикла и операторов логической передачи управления, хотя принцип действия остается неизменным — формирование новой переменной путем сложения частей Пример 21. В тексте A$ после каждого пробела вставить B$. a$= "Белеет парус одинокий" PRINT a$ B$ = "11" x = LEN(a$) FOR i = 1 TO x IF ASC(MID$(a$, i, 1)) = 32 THEN a$ = MID$(a$, 1, i) + B$ + MID$(a$, i + 1, x) END IF NEXT i PRINT a$ Результат. Белеет 11парус 11одинокий Работа программы. В цикле анализируется АSСП-код очередного выделенного символа на равенство 32 (код пробела). Если равенство выполняется в ходе 1-й итерации цикла, то переменной А$ присваивается сумма трех компонентов — левая часть исходной А$ (знаки с номерами от 1 до 1) + В$ + правая часть AS (знаки от 1 до х). Удаление символов Удаление символов проходит путем записи в новую текстовую переменную знаков исходной строки, расположенных до удаляемой части и после нее. Пример 22. Удалить пятый символ из A$. a$ = "123456789" n = 5 x = LEN(a$) a$ = MID$(a$, 1, n - 1) + MID$(a$, n + 1, x) PRINT a$ Результат: 12346789 Работа программы. Первое значение A$ образуется путем сложения знаков 1-4 (1, N - 1) и 6-9 (N+1, x) исходной строки. Если удаляется не один знак, а целый блок знаков BS, то во втором MID$ номер первого элемента правой части запишется N + LEN(B$) и команда в целом будет иметь вид MID$(A$, N+LEN(B$) Рассмотрим алгоритм многократного удаления знака по условию. Такие задачи решаются с помощью цикла. Пример 23. Удалить все запятые в строке А$. a$ = ",,,1,2,3,4,5,,,," PRINT a$ x = LEN(a$) FOR i = 1 TO x IF MID$(a$, i, 1) = "," THEN a$ = MID$(a$, 1, i - 1) + MID$(a$, i + 1, x) i = i – 1 'Уменьшаем счетчик i END IF NEXT i PRINT a$ Результат: ,,,1,2,3,4,5,,,, 12345 Работа программы. В значение A$ специально введено несколько блоков идущих друг за другом запятых. Это сделано для того, чтобы продемонстрировать частный случай задач на удаление. Если удаляются знаки, стоящие последовательно по одному, то необходимо уменьшать счетчик цикла па количество удаляемых знаков. Выделение отдельного слова из текста Текст состоит из отдельных слов. Слово – это последовательность букв, заключенных между двумя символами, не являющимися буквами. Алгоритмы выделения слов, как правило, основаны на поиске знаков – разделителей. Ими могут быть пробелы, знаки пунктуации, специальные символы. Пример 25. Определить количество слов в тексте. a$ = " Отговорила роща золотая Березовым, веселым языком " ' выделяем i-й знак и проверяем буква ли это FOR i = 1 TO LEN(a$) tmp$ = MID$(a$, i, 1): isletter = 0 IF 128 <= ASC(tmp$) AND ASC(tmp$) <= 175 THEN isletter = 1 IF 224 <= ASC(tmp$) AND ASC(tmp$) <= 239 THEN isletter = 1 IF 65 <= ASC(tmp$) AND ASC(tmp$) <= 90 THEN isletter = 1 IF 97 <= ASC(tmp$) AND ASC(tmp$) <= 122 THEN isletter = 1 ' Если это буква, то формируем слово ' Иначе переходим к формированию след слова IF isletter = 1 AND i < LEN(a$) THEN T$ = T$ + tmp$ ELSE IF LEN(T$) > 0 OR isletter = 1 THEN IF i = LEN(a$) AND isletter = 1 THEN T$ = T$ + tmp$ ' Теперь можно проводить анализ очередного слова Т$ PRINT T$ L = L + 1 T$ = "" ' Обнулять Т$ обязательно END IF END IF NEXT i PRINT " Всего слов "; L Результат: Отговорила роща золотая Березовым веселым языком Всего слов 6 Работа программы. Приведенный алгоритм выполняет следующие операции: выделяет очередной символ; если это буква, то начинает накапливать очередное слово; если это не буква — переходит к анализу полученного слова и формированию следующего. Четыре оператора IF в начале цикла предназначены для определения принадлежности выделенного знака к буквам русского или английского алфавита. Действие операторов основано на анализе ASCII-кода каждого знака. Если знак является буквой, то переменной isletter присваивается значение 1, в противном случае — 0. Пример 26. Сформировать массив слов Word$, входящих в текст A$. Определить слова с максимальным и минимальным количеством букв. CLS 'Очистка экрана DIM word$(LEN(a$)) a$ = "Еще светло перед окном, В разрывы облак солнце блещет" min = LEN(a$) FOR i = 1 TO LEN(a$) ' выделяем i-й знак и проверяем буква ли это … ' Если это буква, то формируем слово … 'Теперь можно проводить анализ очередного слова Т$ K = K + 1: word$(K) = T$ 'формируем массив слов ' находим слово с max кол-вом букв IF LEN(T$) > max THEN max = LEN(T$): wmax$ = T$ ' находим слово с min кол-вом букв IF LEN(T$) < min THEN min = LEN(T$): wmin$ = T$ T$ = "" ' Обнуляем Т$ END IF END IF NEXT i PRINT "Слово с кол букв max "; wmax$ PRINT " Слово с кол букв min "; wmin$ PRINT "Массив слов" FOR i = 1 TO K PRINT word$(i) NEXT i END Результат Слово с кол букв max разрывы Слово с кол букв min В Массив слов Еще светло перед окном, В разрывы облак солнце блещет Работа программы. Алгоритм выделения слова из предыдущего примера приведен сокращенно. В первой сроке программы происходит объявление массива Word$. Рассчитывать, сколько нем будет слов не рационально. Для этого пришлось бы анализировать исходную строку и, получив количество слов, и объявить массив, а для его заполнения выполнить алгоритм заново. Поэтому предполагаем, что в массиве Word$ Len(a$) элементов. Перестановка элемента в тексте Перестановка элементов текста осуществляется путем формирования новой переменной на основе исходной. Можно переставлять не только отдельные слова, но и логические группы, блоки. Алгоритмы перестановки текста состоят из двух основных этапов: выделение элементов формирование новой строки в соответствии с условиями. Например, для того чтобы поменять местами самое длинное и самое короткое слова, нужно сначала их найти, а затем в ходе формирования новою текста вместо первого записать второе, а вместо второго первое. Последовательность всех остальных знаков при этом не изменится. Пример 27. Поменять местами самое длинное и самое короткое слова в A$. CLS a$ = "Белеет парус одинокий" PRINT a$ min = LEN(a$) 10 : FOR i = 1 TO LEN(a$) ' выделяем i-й знак и проверяем буква ли это tmp$ = MID$(a$, i, 1): isletter = 0 IF 128 <= ASC(tmp$) AND ASC(tmp$) <= 175 THEN isletter = 1 IF 224 <= ASC(tmp$) AND ASC(tmp$) <= 239 THEN isletter = 1 IF 65 <= ASC(tmp$) AND ASC(tmp$) <= 90 THEN isletter = 1 IF 97 <= ASC(tmp$) AND ASC(tmp$) <= 122 THEN isletter = 1 ' Если это буква, то формируем слово IF isletter = 1 AND i < LEN(a$) THEN T$ = T$ + tmp$ ELSE IF LEN(T$) > 0 OR isletter = 1 THEN IF i = LEN(a$) AND isletter = 1 THEN T$ = T$ + tmp$: tmp$ = "" 'Теперь можно проводить анализ очередного слова Т$ ' max IF LEN(T$) > max THEN max = LEN(T$): wmax$ = T$ 'min IF LEN(T$) < min THEN min = LEN(T$): wmin$ = T$ ' Блок замены и прибавление слова rez$ IF switsch = 1 THEN IF T$ = long$ AND c <> i THEN T$ = short$: c = i IF T$ = short$ AND c <> i THEN T$ = long$: c = i rez$ = rez$ + T$ END IF ' закрываем switsch T$ = "" ' обнуляем T$ END IF ' закрываем Len(T$)>0 or.... IF switsch = 1 THEN rez$ = rez$ + tmp$ ' прибавляем не букву 45 END IF ' закрываем switsch END IF ' закрываем islitter NEXT i ' возвращаемся в начало программы после 1-го прохода IF short$ = "" THEN switsch = 1: short$ = wmin$ long$ = wmax$: GOTO 10 ELSE PRINT rez$ ' вывод результата END IF END Белеет парус одинокий Белеет одинокий парус Работа программы. Алгоритм работает в два прохода, В первом проходе определяет самое длинное (wmax$) и самое короткое (wmin$) слово. Затем управление оператором GOTO передается в начало программы и осуществляется второй проход да является формирование новой переменной rez$, в которой накапливается результат, — строка с переставленными максимальным и минимальным словами. На основе подобных алгоритмов решаются задачи перестановки или вставки блоков, а также некоторых видов сортировки элементов строки. Сортировка массива слов Сортировка — один из самых сложных видов обработки текстовых переменных, а необходимость перестановки элементов в рамках одной строки усложняет задачу еще и тем, что требует сохранения последовательности знаков, не участвующих в перемещении. К таким элементам относятся числа, знаки пунктуации, пробелы. Пример 28. Переставить слова в А$ согласно алфавиту. Количество и порядок следования других знаков остается неизменным. CLS A$ = "август - астры,,,,, - звезды - грозди винограда -- рябины??????" PRINT A$ DIM word$(LEN(A$)) FOR i = 1 TO LEN(A$) ' выделяем i-й знак и проверяем буква ли это … ' Если это буква, то формируем слово … ' Теперь можно проводить анализ очередного слова Т$ k = k + 1 word$(k) = T$ ' формируем массив слов T$ = "" ' обнуляем T$ END IF END IF NEXT i ' сортировка массива word$ по росту ASCII-кодов FOR i = 1 TO k FOR j = 1 TO k f = 1 10 : IF ASC(MID$(word$(i), f, 1)) < ASC(MID$(word$(j), f, 1)) THEN SWAP word$(i), word$(j) ELSE IF ASC(MID$(word$(i), f, 1)) = ASC(MID$(word$(j), f, 1)) THEN f = f + 1 IF MID$(word$(i), f, 1) <> "" AND MID$(word$(j), f, 1) <> "" THEN GOTO 10 END IF END IF END IF NEXT j NEXT i PRINT PRINT "Сортировка массива слов" FOR i = 1 TO k PRINT " "; word$(i); NEXT i END Результат: август - астры,,,,, - звезды - грозди винограда -- рябины?????? Сортировка массива слов август астры винограда грозди звезды рябины Работа программы. Программа анализирует исходную строку А$. Формирует массив word$ только слов. Переставляет слова в массиве в порядке возрастания ASCII-кодов букв. |