Разработка и программная реализация алгоритмов

6. Разработка и программная реализация алгоритмов

обработки строк

Задание

1. Разработать алгоритмы решения задачи. Алгоритм основной программы должен представлять собой последовательность действий:

1) вывод сведений об авторе и программе;

2) ввод исходных данных;

3) обращение к подпрограмме, решающей задачу;

4) вывод результата.

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

Спецификация.

Название: GetWord.

Заголовок:

Function GetWord(S:string; var Index:byte):string;

Назначение: Возвращает слово, расположенное в строке S. Первый символ слова находится в позиции Index или за ней. Index устанавливается на позицию, следующую за словом. Слова в строке S разделяются пробелами.

Входные параметры:

S – строка;

Index – номер позиции, начиная с которой определяется слово.

Выходные параметры:

Index – номер позиции в строке S, следующей за словом.

Возвращаемое значение: слово, которое может быть пустым, если начиная с позиции Index в строке S нет слов.

2. Подобрать тестовые данные.

3. Программно реализовать алгоритмы.

Пример

Сократить количество пробелов между словами до одного.

Решение.

1. Алгоритм первого шага детализации представлен блок-схемой на рис.6.1.

Рис.6.1

Процедура DeleteSpase.

Спецификация.

Название: DeleteSpase.

Заголовок:

Procedure DeleteSpase(var S: string);

Назначение: сокращает количество пробелов между словами до одного.

Входные параметры:

S - строка.

Выходные параметры:

S - строка.

Алгоритм 1.

1. С помощью стандартной функции Pos найдём позицию первых двух пробелов и удалим первый стандартной процедурой Delete.

2. Пункт 1 повторяем, пока в строке есть хотя бы одна пара следую-щих друг за другом пробелов.

Алгоритм 1 представлен блок-схемой на рис.6.2.

Алгоритм 2.

Результат будем формировать в новой строке S1, “выбирая “ слова из строки S с помощью функции GetWord. Слова в строке S1 будем разделять только одним пробелом. Результат присвоим строке S.

Алгоритм 2 представлен блок-схемой на рис.6.3.

нет

да

Рис.6.2

нет

да

S1:=S1+w+’ ’

Рис.6.3

Алгоритм 3.

Пусть анализируемый символ строки S находится в позиции i2. Он может быть переписан в позицию i1 если он не пробел или первый пробел из последовательности пробелов, после чего i1 увели-чивается на единицу. Второе условие будем определять с помощью переменной f, которая принимает истинное значение, если обработан не пробел и ложное – если пробел. Инициализируется f истинным значением. После обработки всех символов необходимо подкорректировать длину строки S , т.к. она может уменьшиться и станет равной i1.

Алгоритм 3 представлен блок-схемой на рис.6.4.

нет

да

нет да

нет да

S[i1]:=S[i2]

S[i1]:=’ ’

i2:=i2+1

f:=true

Рис.6.4

2. Наборы тестовых данных представлены в табл.6.1.

Таблица 6.1

Номер набора	Исходные данные	Результат
Номер набора	S	S
	‘‘	‘‘
	‘ ‘	‘‘
	‘ abc defg h ‘	‘abc defg h‘
	‘abc defg h‘	‘abc defg h‘
	‘abc defg h‘	‘abc defg h‘

3. Программная реализация алгоритмов решения задачи на языке Паскаль приведена ниже.

PROGRAM Аlgorithm1;

Procedure DeleteSpase(var S: string);

Var i: byte;

Begin

i:=Pos(‘ ‘,S);

while i>0 do begin

Delete(S,i,1);

i:=Pos(‘ ‘,S)

end

End;

VAR S: string;

BEGIN

Writeln(‘Программа Иванова И.И.’);

Writeln;

Writeln(‘Сокращает количество пробелов между словами до одного.’);

writeln(‘Введите строку’);

readln(S);

DeleteSpase(S);

writeln(‘Результат:’);

writeln(S)

END.

PROGRAM Аlgorithm2;

Function GetWord(S:string; var Index:byte):string;

{ разработать самостоятельно }

Procedure DeleteSpase(var S: string);

Var S1, w: string;

i: byte;

Begin

S1:=’’; i:=1;

w:=GetWord(S,i);

while w<>’’ do begin

S1:=S1+w+’ ’;

w:=GetWord(S,i);

end;

S:=S1

End;

VAR S: string;

BEGIN

Writeln(‘Программа Иванова И.И.’);

Writeln;

Writeln(‘Сокращает количество пробелов между словами до одного.’);

writeln(‘Введите строку’); readln(S);

DeleteSpase(S);

writeln(‘Результат:’);

writeln(S)

END.

PROGRAM Аlgorithm3;

Procedure DeleteSpase(var S: string);

Var i1, i2: byte;

f: boolean;

Begin

i1:=1;

i2:=1;

f:=TRUE;

while i2<ord(S[0]) do begin

if S[i2]<>’ ’ then begin

S[i1]:=S[i2];

i1:=i1+1;

f:=TRUE

end else begin

if f then begin

S[i1]:=’ ’;

i1:=i1+1;

f:=FALSE

end

end;

i2:=i2+1

end;

S[0]:=chr(i1)

End;

VAR S: string;

BEGIN

Writeln(‘Программа Иванова И.И.’);Writeln;

Writeln(‘Сокращает количество пробелов между словами до одного.’);

writeln(‘Введите строку’); readln(S);

DeleteSpase(S);

writeln(‘Результат:’);

writeln(S)

END.

При тестировании программ будут обнаружены ошибки в алгоритмах. Исправьте их.

Варианты заданий

1. Даны две строки. Получить строку, в которой чередуются слова первой и второй строки. Если в одной из строк число слов больше, чем в другой, то оставшиеся слова должны быть дописаны в строку-результат.

2. Дана строка. Определить количество слов-палиндромов, которые начинаются с буквы “а”.

3. Даны две строки. Определить последнее из слов первой строки, которое есть во второй строке.

4. Преобразовать строку, изменив порядок следования слов в строке на обратный.

5. Преобразовать строку, обратив каждое слово этой строки.