Методическое пособие для подготовки к государственному экзамену по информатике для студентов специальности «Прикладная математика»



бет5/5
Дата28.06.2016
өлшемі418 Kb.
#162858
түріМетодическое пособие
1   2   3   4   5
§ 14. Алгоритмы текстовой обработки.
См. преамбулу "Алгоритмы символьной обработки"
Итак, формальная обработка текстов связана с взглядом на последовательности f как текст в некотором алфавите tChar, f  tWord=NtChar или слова - подпоследовательности (интервалы) текста. Примеры - операции вставки, исключения и замены слов, обычные при редактировании текстов.
В реальности, мы в этом пункте нигде далее не используем даже какие-либо специфические особенности типа tChar как множества символов. На деле, здесь tChar - произвольный тип.
type

tChar=?;


tPosition=?;

tWord=?;


p
rocedure

Вставка(var ОсновнойТекст:tWord;ВставляемоеСлово: tWord; Позиция:tPosition);


Варианты - слово вставляется после, начиная с и до заданной позиции.
procedure Исключение

(
var ОсновнойТекст:tWord; var Новое: tWord; НачалоИсключения,КонецИсключения :tPosition);


В
арианты - те же, а также удаление подслова - процедура не порождает нового слова.
Все остальные операции формальной обработки текстов можно свести к операциям вставки и исключения. Так, например, операцию замены можно свести к исключению из текста одного слова и вставки другого, операцию порождения текста можно трактовать как вставку в пустой текст, а операцию уничтожения текста - как исключение (удаление) содержимого текста "из себя".
Другое дело - нужно ли это делать при заданной реализации текста. См. далее - при реализации текста списком мы в действительности выражаем вставку через порождение, удаление и копирование символов текста.
В свою очередь, операции вставки и исключения слов сводятся к кратной вставке и исключения символов.
Вставка и замена при представлении слов (псевдодинамическими) массивами.
type

tIndex=1..nMax; {максимальная длина текста+1}

tPosition=tIndex;

tWord=record Content: array[tPosition] of tChar; {содержимое слова/текста}

Len: tPosition {фактическая длина текста}

end;
procedure Insert {ВставкаПосле}

(var T {ОсновнойТекст} :tWord; W {ВставляемоеСлово}: tWord; P {Позиция}: tPosition);

var


i, {текущая позиция в W}

k: tPosition ; {=p+i, текущая позиция в T }

begin

i:=1;k:=p+1;



while (i<=W.Len) and (k<=nMax) do

begin {вставка i-го символа W}

{сдвиг текста вправо на 1, начиная с позиции k}

for j:= T.Len+1 downto k do T.Content[j+1]:= T.Content[j];

T.Content[k]:=V.Content[i];

inc(i);inc(k)

end; end;
procedure Exclude {Исключение}

(var T {ОсновнойТекст}:tWord; var V { Новое}: tWord; Start, Finish {НачалоИсключения,КонецИсключения} : tPosition);

begin

var


k: tPosition; {текущая позиция в T, k  [Start,Finish] }

begin


V.Len:=0;k:=Start;

while k<=Finish do

begin {исключение i-го символа W}

inc(V.Len); V.Content[V.Len]:=T.Content[k];

{ удаление T.Content[k] - сдвиг текста влево на 1, начиная с позиции k+1}

for j:= k to T.Len do T.Content[j]:= T.Content[j+1];

inc(k)

end; end;


Вставка и замена при представлении слов списочными структурами.
type

pComponent=^tComponent;

tComponent=record Content: tChar; {содержимое слова/текста}

next:pComponent; {ссылка на следующую компоненту}

end;

pPosition=pComponent;



pWord=pComponent; {ссылка на начало списка}
{область определения( предусловие): тест не пуст  pT<>nil, p<>nil}

procedure Insert {ВставкаПосле}

(var pT {ОсновнойТекст} :pWord; pW {ВставляемоеСлово}: pWord; P {Позиция}:pPosition);

var


pn, {ссылка на новую компоненту}

pi, {ссылка на текущую позицию в W}

pk: pPosition; {ссылка на текущую позиция в T }

begin


pi:=pW;pk:=P;

while pi<>nil do

begin {вставка i-го символа W}

new(pn); {порождаем новую компоненту}

pn^.Content:=pw.Content; {с содержимым равным символу w[k]}

pn^.next:=pk^.next; {вставляем его перед T[i+1]}

pk^.next:= pn; {и после T[i]}

pw:=pw^.next; {переходим к следующим символам}

pk:=pk^.next;

end; end;


procedure Exclude {Исключение}

(var pT {ОсновнойТекст}:pWord; var pV { Новое}: pWord; pStart, pFinish {НачалоИсключения,КонецИсключения} : pPosition);

begin

var


pD, {ссылка на уничтожаемый символ}

pN, {ссылка на новый символ V}

pK: pPosition; {ссылка на текущую позицию в T}

begin


new(pV);pV^.next:=nil; {вводим фиктивный/нулевой символ }

pLast:=pV; {причина - определить ссылку на последний символ}

pK:=pStart;

while pK<>pFinish do

begin {исключение i-го символа W}

{порождаем новый символ = T[k]}

new(pN); pN^.Content:=pK^.Content; pN^.next:=nil;

{делаем его последним в V}

pLast^.Next:=pN; pLast:=pN;

{удаляем текущий, переходим к следующему символу в T}

pD:=pK; pK:=pK^.next; destroy(pD);

end;


{удаляем фиктивный/нулевой символ }

pD:=pV; pV:=pV^.next; destroy(pD)

end;
§ 15. Формальные вычисления.
См. преамбулу «Алгоритмы символьной обработки». В частности, там определено понятие формального вычисления как нахождение текста (обозначения) результата операции по тексту (обозначениям) аргументов, в некоторой фиксированной системе обозначений.
Очевидно, деление «обозначение(имя)/значение, синтаксис/семантика» является фундаментальным не только в программировании, но и в целом, для нашего мышления (см. § 1 «Основные понятия…»). Но программист обязан понимать и условность этого деления – в реальности, все компьютерные вычисления формальны, реализуясь в конечном счете в алгоритмах символьной обработки последовательностей битов (см. § 8 «Машинно-ориентированное программирование»). Отсюда – очевидная важность рассматриваемой темы.
Рассмотрим ее на простом примере операции сложения натуральных чисел.
Задача. Найти запись (обозначение) суммы двух натуральных чисел по записям аргументов, не прибегая к преобразованиям типов. Обозначения чисел (в традиционной 10-ной системе счисления) представлены массивами.

type


tIndex=1..Len;

tCifer='0'..'9';

tNotation=array[tIndex] of tCifer;

tPair=record First,Second:tCifer end; {пара цифр}

{глобальный параметр - таблица сложения}

{PifagorTable: array[tCifer,tCifer] of tPair;}

procedure СложениеСтолбиком(Arg1,Arg2:tNotation; var Sum:tNotation; Error:boolean);

{Error - ошибка переполнения}

var

Um: '0'..'1'; {цифра "в уме"}



Pair:tPair;

i:tIndex;

begin

Um:='0';


for i:=1 to Len do

begin


Pair:= PifagorTable[Arg1[i],Arg2[i]]; {пара цифр от '00' до '18'}

if Um='0'

then begin Sum[i]:=Pair.Second;Um:=Pair.First end

else {Um=1}

if Pair.Second='9' {особый случай}

then { Pair.First='0' } Sum[i]:='0'

else begin Sum[i]:=succ(Pair.Second);Um:=Pair.First end;

end;


Error:=Um='1'

end;




  1. Пример вычисления функции значения и обратной функции.

Задача. Найти запись (обозначение) суммы двух натуральных чисел по записям аргументов, прибегая к преобразованиям типов. Обозначения чисел (в традиционной 10-ной системе счисления) представлены массивами (также, как в предыдущей задаче).

procedure ToValue(cArg:tNotation; var iResult:integer);

var a:0..9; {значение очередной цифры}

begin


iResult:=0;

{вычисление многочлена  {ai 10 Len-i: i  [1..Len]} по схеме Горнера}

for i:=1 to Len do begin a:= ord(cArg[i]))-ord('0'); iResult:=iResult*10+a; end;

end;


procedure ToName(iArg:integer; var cResult:tNotation; Error:boolean);

var


c:tCifer; {очередная цифра десятичной записи}

a:0..9; {значение очередной цифры}

OrdZero:integer; {номер символа '0' в таблице символов}

begin


OrdZero:=Ord('0'); k:=1;

while (iArg<>0) and (k<=Len) do

begin

a:= iArg mod 10; iArg:=iArg div 10;



cResult[k]:=chr(OrdZero+a);k:=k+1

end;


Error:=k>Len;

while k<=Len do begin cResult[k]:='0';k:=k+1 end;

end;

procedure Sum(cArg1,cArg2:tNotation;var cResult:tNotation;Error:boolean);



var iArg1,iArg2:integer;

begin


toValue(cArg1,iArg1); toValue(cArg2,iArg2); ToName(iArg1+iArg2,cResult,Error);

end;

Достарыңызбен бөлісу:
1   2   3   4   5




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет