Основы программирования (947332), страница 21
Текст из файла (страница 21)
Запретить ввод номеров, которые превышают количество слов в строке или равны между собой.121Часть 1. Основы алгоритмизации и процедурное программированиеВ а р и а н т 1. При решении данной задачи строку приходится просматривать посимвольно, так как необходимо фиксировать начало и длину каждого из слов с указанными номерами.
Если очередной символ равен пробелу,то количество слов необходимо увеличить на единицу, проверить, не совпадает ли номер с одним из заданных и если совпадает, то запомнить номерпервого символа и длину слова. После чего обнуляем счетчик длины слова ификсируем начало следующего слова. Если символ не пробел, то увеличиваем длину текущего слова.В конце строки пробела может не быть. Следовательно, завершение последнего слова необходимо проверять отдельно, к тому же учитывая, что если после последнего слова нет пробела, то его длина получается на единицуменьше, что тоже необходимо скорректировать.После того, как местоположение слов определено, необходимо осуществить их перемещение.
При этом необходимо учесть, что как только мы удалим первое слово, начало второго слова сместится. Следовательно, вначаленеобходимо удалить второе слово и вставить первое, а затем уже удалитьпервое слово и вставить второе. Чтобы не анализировать, какое из слов первое, а какое второе, лучше всего сортировать введенные номера слов по возрастанию.Program Stroka2;Var nsl, ns2, ks, nl, п2, dll, dl2,ns ,dls, i, w:byte;s, si, s2:string;BeginWriteLn(*Введите исходную строку'); Readln(s);ks:=0; {обнуляем счетчик слов}for /.•= 1 to Length (s) doif(s[i]=' ') or (i=length(s)) then {если конец очередного слова }ks:=ks-\-l: { увеличиваем счетчик слов}WriteLn('Beedume номера слов для обмена');ReadLn(nl,n2); {вводим номера}while (nl>ks) or(n2>ks) ог(п1=п2) do {пока номера не допустимы}beginWriteLnCКоличество слов в строке \ks:5,\ Одинаковые номера не допустимы.Повторите ввод номеров.
*);ReadLn(nl,n2); {вводим номера}end;ifnl>n2 then{сортируем номера по возрастанию}begin w:-nl; п1:=п2; n2:=w; end;ns:=l;{начало первого слова равно 1}dls:=0; {длина первого слова равна 0}ks:=0; {номер слова пока равен 0}1224. Структурные типы данныхfor i:^l to Length(s) do {no всей строке}beginif(sfij=' ') or (i=Length(s)) then {если слово завершено}beginif (i=Lengt/t(s)) and (sfij <>' ') then {если в концестроки нет пробела}dls:=dls+l; {корректируем длину слова}b:=ks+l;ifks=nl then {если это первое слово}begin {то запоминаем начало и длину}ns 1: =ns; dll: =dls;end;ifks=n2 then {если это второе слово}begin {то запоминаем начало и длину}ns2:=ns; dl2:=dls;end;dls:=0; {обнуляем длину текущего слова}ns:=i+l; {запоминаем начало текущего слова}endelsedls:=dls+l; {считаем длину очередного слова}end;sl:=Copy(s, nsJ, dll); {копируем значение первого слова}s2:=Copy(s, ns2, dl2); {копируем значение второго слова}Delete(s, ns2, dl2);{удаляем дальнее слово}Insert(sl, S, ns2);{вместо него вставляем ближнее}Delete(s, nsl, dll);{удаляем ближнее слово}Insert(s2,s,nsl);{вставляем дальнее}WriteLnf'Результат : \ s);End.В а р и а н т 2.
Вначале разобьем текст на слова и поместим каждое слово в элемент вспомогательного массива строк. Затем выполним перестановку элементов. И, наконец, вновь объединим слова в строку.Это решение имеет два существенных недостатка. Во-первых, оно требует дополнительной памяти для размещения вспомогательного массива.
Вовторых - выполняться такая программа будет несколько дольше, так как исходная строка будет просматриваться несколько раз. Однако этот вариант решения несколько проще, и в тех случаях, когда отсутствуют строгие ограничения на объем используемой памяти и время выполнения, он может оказаться предпочтительным.Program StrokaS;Var ks, nl, п2, i, kbyte; 5, si .string;MasStr:array[L. 100] ofstring[20];{рабочий массив}123Часть L Основы алгоритмизации и процедурное программированиеBeginWriteLnCВведите исходную строку'); Readln(s);ks:^0; {обнуляем счетчик слов}ifs[length(s)]<>' ' then 5;=л'+' V {если в конце строки нет пробела,то дописываем его}{разбор строки}while s<> *' do{пока в строке остались слова}beginb:=ks+l;{увеличиваем счетчик слов}k:=Pos(' \s); {определяем конец слова}masStr[ks]:=Copy(sJ,k); {копируем слово в массив}Delete(sJ,k);{удаляем слово из строки}end;{обмен слов}WriteLn('Beedume номера слов для обмена');ReadLn(nl,n2); {вводим номера}while (nl>ks) ог(п2>Ь) ог(п]=п2) do {пока номера не допустимы}beginWriteLn('Количество слов в строке \ks:5,\ Одинаковые номера не допустимыЛовторите ввод номеров.
');ReadLn(nl,n2); {вводим номера}end;sl:=MasStrfn]J;{меняем слова местами}MasStrfnlJ: =MasStrfn2J;MasStr[n2]:=sl;{объединение слов в строку}for /;=7 to ks do s:=s-^MasStr[iJ; {объединяем слова в строку}Delete(s,Length(s),l);{удаляем пробел после последнего слова}WriteLnCРезультат : \ s); {выводим результат}EndПример 4.19. Разработать программу, которая осуш.ествляет поиск заданной строки в отсортированном в соответствии с латинским алфавитоммассиве строк MasStr[n], п<100.
Конкретное количество строк массива определять в процессе их ввода.Ввод строк организуем в цикле-пока. В качестве условия завершенияввода будем использовать ввод пустой строки. Количество вводимых записейбудем считать. Если введено меньше 99 слов, то после завершения вводауменьшим количество введенных строк на единицу, чтобы не обрабатыватьпустую строку.Поиск строк может быть реализован несколькими способами.В а р и а н т 1. Самый простой способ поиска - последовательный. Припоследовательном способе мы запись за записью сравниваем строки в мас1244, Структурные типы данныхсиве с заданной строкой.
Однако данный вид поиска является и самым продолжительным по времени. Оценим время поиска.Если искомая строка совпадает с первой строкой массива, то в процессепоиска будет выполнено одно сравнение. Если искомая строка совпадает споследней строкой, то - п сравнений. В среднем в процессе поиска понадобится выполнить (n-fl)/2 сравнений, т.е. вычислительная сложность последовательного поиска Оср(п).В а р и а н т 2.
Для ускорения обработки можно реализовать двоичныйпоиск. Э^от метод применим, так как массив отсортирован по возрастаниюкодов символов строк. Метод двоичного поиска заключается в следующем.Определяют примерную середину массива и проверяют, совпадает ли искомый элемент с элементом в середине массива. Если совпадает, поиск завершен. Если не совпадает, то, если элемент больше среднего, то поиск продолжают в левой половине массива, иначе - в правой половине. Таким образом,диапазон элементов на каждом шаге уменьшается больше, чем вдвое. Еслидиапазон сократился до нуля, а элемент не найден, то такой элемент в массиве отсутствует.На рис.
4.30 показан пример реализации двоичного поиска для массива,включающего 10 элементов. На первом шаге осуществляется проверка 5-гоэлемента, и массив разбивается на два подмассива: 1 ...4 и 6... 10. На второмшаге - 2-го, если искомое значение меньше 5-го элемента, или 8-го, еслиискомое значение больше 5-го элемента. Затем проверяются значениятретьего уровня и т.
д.Исходный массив1232 .3441-й шаг12-й шаг3-й шаг11•5м678611/I7[109 1019 ^10ШШ~1• П•81 I \—Ш6^74-й шаг9\7п\10I — элемент, анализируемый на данном шагеРис. 4.30. Пример дерева двоичного поиска для исходногодиапазона из 10 элементов125Часть 1. Основы алгоритмизации и процедурное программированиеОценим время поиска для данного метода.
Будем считать, что дерево поиска строки получилось сбалансированным, т.е. количество записейп = 2J-1, где j=l, 2, 3 и т.д., тогда количество уровней дерева равно log2 п.Считая, что искомое значение может с равной вероятностью находиться налюбом уровне, получаем, что среднее количество сравнений равно(log2 п +1)/2, т.е. вычислительная сложность двоичного поиска 0^,p(log2 п),что при больших значениях п существенно лучше, чем при последовательном поиске.Примечание. Если бы изначально массив не был отсортирован, а поиск требовалось быпроизводить многократно, то массив целесообразно было бы сортировать.Реализуем двоичный поиск.Program ex;Var MasStr:array[L. 100] ofstring[22];n, k, I: integer; st:strmg[22];key:boolean;Beginn:=l;WriteLnCВведите до 100 строкЗавершение ввода - пустая строка');ReadLn(MasStr[n]);while (MasStr[n]<> 7 and (n<100) dobeginn:=n+l;ReadLn(MasStr[n]);end;ifn<100 then п:=П'1; {слов в массиве на одно меньше}WriteLnCВведите строку для поиска.');ReadLn(st);к:=1; key:=false;while (П'к>=0) and not key do {пока диапазон положителен изапись не найдена}begin1:-(П'к) div 2+к;{определяем среднее значение индекса}ifst=MasStr[l] then key:-true{запись найдена}else{уменьшаем диапазон индексов}if s(>MasStr[l] then k:-lH{смещаем левую границу}else n:-l'l;{смещаем правую границу}end;if key thenWriteLn('Строка найдена.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
