Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 12
Текст из файла (страница 12)
323; Чае сб: сйаг'„у: геа1„аде: йиекег; з,зз: Ьоо)еагг; (знаки) 1аас11оа геп(е; рояпг): геа1; ( =- 10ч*е, 0<е<322 ), чвг 1: гпГе8ег; Г: геа1; Ье81а 1:= 0; Г:= 1.0; хереае 11 оаа(е) ЬЬеа саяе 1 о1' 0: г:=- г ч 1.ОЕ1; 1: 1;= г ч 1.0Е2; 2: г:= г ч 1.0Е4; 3: г:= г ч 1.ОЕ8; 4: г;= е ч 1.ОЕ16; 5: г:= г' ч 1.0Е32; б: г:= 1 е 1.0Е64; 7: Г:= 1 ч 1,ОЕ128; 8: г:= 1 е 1,0Е256 еай; е:= е й(т 2; г .'= 1+1 ааб! е = 0; ген;= с еаб; Ье81а (пропуск начальных пробелов) зчЬ11е Д'(=' ' йо ае1Я; сЬ:= Д'; 11 сЬ = '-' 1Ьеа Ье81а г:= 1гие; 8е1Я; сЬ:=- г"1 еай е)зе Ье8(а в .'= уа)зе; 11 сд = '+' 1Ьеа Ье81а беф'),' сЬ;= у'1.
еаа еаа; И -" ~(сЬ 1а ~'О' „ '9')) 1Ьеа Ъеп(а теххаие ( и!а!т ехистиь); Ьа[с! епй; а:= 0; е:= 0; реуса! И а < Бти йеп а:= 10еа + оггс(сЬ)-х еЬе в;= в+11 йвС(~); сЬ:= С'[ па!!1 -т(сЬ за ['О', '9'))1 И сЬ =- '' йеп Ъеи!в [чтение дробной части) асс(~); сЬ: = Д; вЬИе сЬ !п ['0'..'9') йо Ьее!а И а < бтИйеа Ъерп а:= 10еа + огй(сЬ) -х; в:= в — 1 епй; бес((); сЬ:= Д) епй епй; И сЬ = — 'Е' йев Ъев[п (чтение порядка) йес(С); сЬ:= Я[; г':= О; И' сЬ '-' йеа ЬейЬт хх;= сгис; бес(Я; сЬ;= Д еай е!ее Ьей[а хг:= Са1хе; И сЬ = '+' йеп Ьей(в ВеСЯ; сЬ ."=- С'[ епй епй; вЬО!е сЬ вт ['0' .. '9') йо Ъерп И 1<бтО йеа Ьера 1:= 1Ое! + огс((сЬ) — х епй; йес(~); сЬ:= Д епй; И хх !Ьеа е:=- е — ! е1ве е:= е+1 епй; И е < 11т2 !Ьеп Ьепш а:=- 0; е:= 0 епй е[ее Ие > 1(т1йеа Ъей!в твххакс(' ниеееяя тоо ыпок '); Ьа!с евй; ( 0 < а < 2* 49 ) И а > с43 Отса у:= — ((а+1) йт 2) в 2.0 е[хе у:= а; И х йеа у:=- — у; И в < 0 йеп х:= у~сев( — е) е[ее И е че 0 йеп х: = уесеи(в) е!ие х:= у; чеИйе (С'[ =' ')Л( — тво1(С)) йо ЮеС(Д; епй [геай еа!) Программа !ум Чтение венгеетвенного числа, ргаеейаге ни<етеа1 (таг у«ех<; х: геа); и: <и<ееег); [ печать вещесп<венного числа х с и символами в десяпщ чном виде с плавающей запятой) [ следующие, константы зависят от используемого представления вещественных чисел с плавающей запятой) гаазе <48 = 281474976710656; [ 2**48; 48-размермантиссь<1 к = 27; ( оМ('0') ) гурерогт< .= О,.
323; [диапазон для десятичного порядка) чаг с,а,е,еО,е1,е2,4< [и<е8ег," 0<пег[оп <еи(е: рог<т): геа1; ( 10ече, 0(е(322 ) айаг <: <п<е8ег; <', геа1; Ьейш <:=- 0; г:=- 1.0; гереаг И ой 1(е) <Ъеп сазе < оГ 0: <:=- < е 1.0Е1; 1: <:=-. < е 1,0Е2; 2: «:= * 1.0Е4; 3: <:= < е 1.0Е8; 4: <:== < е 1.ОЕ16; 5: «:== а 1,0Е32; 6: г:=: < е 1.0Е64; 7: «:== е 1.0Е128; 8: «::= е 1.0Е256 д; е:= е й[г 2; <:=- <+1 апгйе =0; <еи:= < епй [ <еи ); Ьей[п [требуются ио крайней мере 10 символов<Ь+9.9Е+999 1 И х .= О йеп Ьей[п гереаг иг<<е(~, ' '); 'и: =-. и — 1 ап01 и 1; <гг<<е(7', '0') епд е[зе Ъей<п И и ( 10 йеп и:= 3 е[зе и:= п — 7; гереаг ие«е(1; ' '); и:= и — 1 ап<И п ( 15; [ 1 ( и ( 15, число печатаемых йиФо) Ъе81п [проверка знака, определение порядка) Их(Ойеп Ьей[п ит(<еЦ; ' — '); х;= — х епд е1зе ать К ' '); е:== езсро (х); (е = серег(/о82(абл(х)))) ФГс '.
Ойеп Ье8)п е:= еа77 йт 256 +1; х:=* х/~ел(е); !1х) 1,0йеп Ье8!и х;=- х/!О.О; с:=- с+1 епп ев$ е!яе Ье8!и е:= (с+1)е77 йт 256; х:= Сел( — е)ек; 11 х < 0.1 йеп Ье8!п х:=- 10.0ех; с:= е-1 епй еп6 ! (0.1 ~х < 1.0) саке л о1 (округление) 2.' х:= х+05Е-2; 3: х:= х+0.5Е-З; 4: х:= х+0.5Š— 4; 5: х:= х+0.5Š— 5; б: х.:= х+0.5Š— 6; 7; х:= х+0.5Š— 7; 8: х:= х+0.5Š— 8; 9: х:= х+0.5Š— 9; 10: х:= х+0.5Š— 1О; 11: х:= х+0.5Š— !1; 12: х: х+0.5Š— 12; 13: х: х+0.5Š— 13; 14: х:= х+0.5Š— 14; 15: х: х+0,5Š— 15 епд; !! х '.) 1.0 йеп Ьее!и х:= х * 0.1; е ."=- с+1; епб; с:= !гиле(х,48); (= Лиле(ха(2ее48))) с;= 10*с; /:= с а» !48; ьн!е~Х, сЬг(Ы+г), '.'); !ог !:= 2 ео л Оо Ье8 п:= (с — И*!48) * 10; /;= с 6!.
!481 юп(е(/, сЬг(с/+г)) еЫ; палс(/', 'Е'); е:==- е — 1! Ые < Ойеп ип, Послеооеотсл ч ве81в ит!!г(у; ' — '); е:=- -е евй е!ае тгг!ге(у; '+'); е1:= е а 205 41т 2048; е2:= е — 10*е1; еО:= е1 * 205 41т 2048; е1:= е1 — 10«еО; кт!ге(г, сйг(еО+х), сйг(с1+х), сЩе2+х)) евй евй (ио!гегеа!) Программа Ь4, Печать вешествеииого числа. щественные числа из десятичного в произвольное «внутреннее» представление и наоборот.
(Константы в заголовках связаны с особенностями формата чисел с плавающей запятой в вычислительной машине СРС 6000: 11-разрядный двоичный порядок и 48-разрядная мантисса. Функция ехро(х) означает порядок х). 1.11.4. Программа редактирования файноя В качестве примера применения последовательной структуры мы приведем следующую задачу, которая одновременно продемонстрирует методику разработки и пояснения программ. Этот метод называется методом поэтапного уточнения [1А, 1.6), мы будем использовать его в этой книге при разборе многих алгоритмов. Задача состоит в том, чтобы разработать программу, которая редактирует текст х, превращая его в текст у, Редактирование означает исключение или замену определенных строк илн включение новых строк.
Редактированием унрааляет последовательность команд редактирования, представленных стандартным текстом !при!. Зти команды имеют такой вид: 1, т. Вставка в текст после т-й строки. В, т, и. Исключение строк от т до и. й, т, п. Замена строк от т до п. Е. Окончание редактирования. Каждая команда занимает одну строку в стандартном файле !при!, который мы называем файлом команд, т и и — десятичные номера строк, а вставляемые тексты должны непосредственно следовать за командами 1 и 11. Они заканчиваются пустой строкой. Мы требуем, чтобы номера строк в командах редактирования шли в строго возрастающем порядке.
Зто правило обеспечивает строго последовательную обработку входного текста х. Очевидно, что состояние работы определяется теку- (. Фундаменга*ьные структура данных шей позицией х, т. е. номером строки, которая рассматривается в данный момент, Предположим, что программа редактирования работает в интерактивном режиме и что, следовательно, файл команд представляет собой, например, данные, вводимые с терминала. В таком режиме работы весьма желательно, чтобы пользователь имел некоторую обратную связь.
Подходящая и полезная форма обратной связи — это распечатка той строки, на которую продвинулся процесс редактирования после выполнения последней команды. Мы назовем эту строку теку- и(ей строкой. Вследствие нового требования, чтобы после выполнения каждой команды текущая строка выводилась на печать, нужно иметь явную переменную, в которой эта строка будет храниться после чтения из к и перед записью в у. Этот прием называется «заглядыванием вперед». Теперь можно представить программу редактирования следующим образом: рту(ага еййог (к, у, три(, ои(ри(); тат 1ло: !л(сует; (номер текущей строки) с!: 1(ле; [текущая с(ловка) к,у: (ек(; Ьея)в геаа (лх(гис(1ол; (1.57) гереас 1л(егрге( (лз(гис(!оп; («г((е 1те; геай!лх(гис(1оп вв61 тс(гисйоп =* 'Е' евй. Попробуем теперь более подробно определить некоторые операторы.
Уточняя «читать команду» и «выполнить команду», мы обращаем внимание, что команда обычно состоит из трех частей: кода команды и двух параметров. Поэтому мы вводим трн переменные: соде, т и и — для обмена между этими двумя операторами. тат сове,сЬ: сйаг; т,п: !л(екег Читать команду: геа4соае,сЬ); Ы сЬ = ',' (йев гела(т,сЬ) е1зе т:= !по; (1.58) Н' сЬ °" ,йеи геа(1(л) е1зе и:= т) Эта формулировка допускает команды с О, 1 или 2 парамет.
рами, так как для «пропущенных» спецификаций подставляются значения по умолчанию. ПП. Послеооаательамй фоал Выполнить команду: «ору; И'соИ« = '!' йеп Ъей!и риИйе; 1пз«г1; епй е1ее ИсоИ« = '0'йевзИр е1ее И соИ« = 'й' йеп Ьей(в 1иеег!у еИр евй е(ее Ы соус =. 'Е' йеи соругеет е(ее Еггог (!.59) Фар: лпгегт ттЫ!е!по < и шоу«ИЕпе геоИ11пе; чгЬ1!е поепИ йо Ьейш ри111ие; геоИ11пе еий; у«11(ие; Соругезт: иЬИе -~сои'(к) йо Ьейй ри111ие; уе111пе евд; риИ(пе (!.60) На третьем, последнем этапе уточьення мы выражаем операции уеШпе, ри!Ипе, геаИ11пе и гог11«11пе с помощью операций с отдельными символами.
Мы видим, что до сих пор все действия касались исключительно целых строк и не делалось никаких специальных предположений о детальной структуре строки. Мы знаем, что строки являются последовательностями символов. Было бы заманчиво описать переменную На следующем этапе уточнения мы выразим операторы сору (копировать), (пзег1 (вставить) н зЫр (пропустить), использованные в (1.59), с помощью операций с отдельными строками уе111пе и ри111пе.
Их общим свойством является цикличность структуры. Сору служит для переписи строк из х в у, начиная с текущей и кончая гп-й строкой. ЯЬ(р читает строки нз х до и-й строки, не переписывая нх в у, Сару: чгЬ!!е 1по < т йе Ьей(п рагуне; уеИйе евй то !. Фундаментальные струнтурь! данные с1 (содержащую текущую строку) как последовательность наг сй 1!!е о! сйаг Однако вспомним совет никогда не использовать структуру с бесконечным кардинальным числом, если имеется эквивалентная фундаментальная структура (такая, как массив). Действительно, в этом случае рекомендуется нспользовагь массив.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
