А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
. Как отсортиро- вать их, сделав порядка 𝑛 действий? 4.5. Родственные сортировке задачи 4.5.1. Какова минимально возможная сложность (число сравнений в наихудшем случае) алгоритма отыскания самого тяжёлого из 𝑛 кам- ней? Решение. Очевидный алгоритм с инвариантом «найден самый тя- жёлый камень среди первых 𝑖» требует 𝑛 − 1 сравнений. Алгоритма меньшей сложности нет. Это вытекает из следующего более сильного утверждения. 4.5.2. Эксперт хочет убедить суд, что данный камень | самый тя- жёлый среди 𝑛 камней, сделав менее 𝑛 − 1 взвешиваний. Докажите, что это невозможно. (Веса камней неизвестны суду, но известны эксперту.) Решение. Изобразим камни точками, а взвешивания | линиями между ними. Получим граф с 𝑛 вершинами и менее чем 𝑛 − 1 рёбрами. Такой граф несвязен (добавление каждого следующего ребра уменьша- ет число связных компонент не более чем на 1). Поэтому суд ничего не знает относительно соотношения весов камней в различных связ- ных компонентах и может допустить, что самый тяжёлый камень | в любой из них. Более простое объяснение: будем следить за тем, сколько камней к данному моменту не «проиграли» (то есть не оказались легче других). Вначале их 𝑛; при каждом взвешивании проигрывает только один ка- мень, а если есть двое не проигравших никому, любой из них может (с точки зрения суда) оказаться самым тяжёлым. Разница между этой задачей и предыдущей: в этой задаче мы дока- зываем, что 𝑛 − 2 взвешиваний не достаточно не только для нахожде- ния самого тяжёлого, но даже для того, чтобы убедиться, что данный камень является таковым | если предположительный ответ известен. (В случае сортировки, зная предположительный ответ, мы можем убе- диться в его правильности, сделав всего 𝑛 − 1 сравнений | каждый сравниваем со следующим по весу. Напомним, что сортировка требует в худшем случае значительно больше сравнений.) 4.5. Родственные сортировке задачи 85 4.5.3. Докажите, что можно найти самый лёгкий и самый тяжёлый из 2𝑛 камней (одновременно), сделав 3𝑛 − 2 взвешиваний. Решение. Разобьём камни произвольным образом на 𝑛 пар и срав- ним камни в каждой паре (𝑛 взвешиваний). Отложим отдельно «побе- дителей» (более тяжёлых в своей паре) и «проигравших» (более лёгких). Ясно, что самый лёгкий камень надо искать среди проигравших (𝑛 − 1 сравнений), а самый тяжёлый | среди победителей (ещё 𝑛 − 1 сравне- ний). 4.5.4. Докажите, что не существует алгоритма, позволяющего га- рантированно найти самый лёгкий и самый тяжёлый среди 2𝑛 камней (одновременно), сделав менее 3𝑛 − 2 взвешиваний. Решение. Пусть такой алгоритм существует. Наблюдая за его при- менением к какой-то группе из 2𝑛 камней, мы будем следить за четырь- мя параметрами. А именно, мы будем смотреть, сколько камней (a) кому-то уже проиграли, а у кого-то уже выиграли; (b) кому-то уже проиграли, но ещё ни у кого не выиграли; (c) у кого-то уже выиграли, но ещё никому не проиграли; (d) ни у кого не выиграли и никому не проиграли (то есть ни с кем не сравнивались). (Напомним, что выигравшим в сравнении мы считаем более тяжёлый камень.) Камни типа (a), очевидно, не могут уже оказаться ни самыми лёгкими, ни самыми тяжёлыми, каковы бы ни были результаты даль- нейших сравнений. Любой камень типа (b) имеет шанс оказаться са- мым лёгким (в самом деле, его можно произвольно облегчить, не меняя результатов уже выполненных сравнений), но уже не может быть са- мым тяжёлым; для камней типа (c) наоборот. Наконец, любой камень типа (d) может быть и самым лёгким, и самым тяжёлым. Обозначим через 𝑎, 𝑏, 𝑐, 𝑑 количества камней в соответствующих ка- тегориях и проследим, как меняются эти параметры при очередном сравнении в зависимости от того, камни какого типа сравниваются и с каким результатом (см. таблицу на следующей странице). Последний столбец таблицы показывает, как меняется величина 𝑠 = 𝑏 + 𝑐 + (3/2)𝑑 (которую можно рассматривать в качестве меры «оставшейся работы»: камень, про который не известно ничего, с точки зрения этой меры в полтора раза сложнее камня, для которого есть односторонняя оцен- ка). Изначально 𝑠 = 3𝑛, а в конце 𝑠 = 2 (про все камни, кроме двух, известно, что они относятся к категории (a)). Из таблицы видно, что при любом взвешивании есть «неудачный исход», при котором 𝑠 умень- шается не более чем на единицу. Такие исходы действительно возможны 86 4. Сортировка сравнение 𝑎 𝑏 𝑐 𝑑 𝑏 + 𝑐 + (3/2)𝑑 𝑎 { 𝑎 0 0 0 0 0 𝑎 > 𝑏 0 0 0 0 0 𝑎 < 𝑏 +1 −1 0 0 − 1 𝑎 < 𝑐 0 0 0 0 0 𝑎 > 𝑐 +1 0 − 1 0 − 1 𝑎 > 𝑑 0 +1 0 − 1 − 1/2 𝑎 < 𝑑 0 0 +1 −1 − 1/2 𝑏 { 𝑏 +1 −1 0 0 − 1 𝑏 < 𝑐 0 0 0 0 0 𝑏 > 𝑐 +2 −1 −1 0 − 2 𝑏 < 𝑑 0 0 +1 −1 − 1/2 𝑏 > 𝑑 +1 0 0 − 1 − 3/2 𝑐 { 𝑐 +1 0 − 1 0 − 1 𝑐 < 𝑑 +1 0 0 − 1 − 3/2 𝑐 > 𝑑 0 +1 0 − 1 − 1/2 𝑑 { 𝑑 0 +1 +1 −2 − 1 (не противоречат результатам предыдущих взвешиваний): при сравне- нии 𝑏-камня и 𝑐-камня может оказаться, что 𝑐-камень тяжелее (его вес не ограничен сверху предыдущими взвешиваниями), а при сравнении c участием 𝑑-камня результат может быть любым, поскольку про 𝑑-ка- мень ничего не известно. (Кроме того, можно заметить, что если один из исходов взвешивания невозможен, то это взвешивание вообще излиш- не и его можно не делать.) А если исходы всех взвешиваний неудачны, то уменьшение 𝑠 с 3𝑛 до 2 потребует как минимум 3𝑛 − 2 взвешиваний, что и требовалось доказать. 4.5.5. Дано 𝑛 различных по весу камней. Найдите самый тяжёлый и второй по весу камни, сделав не более 𝑛 + ⌈log 2 𝑛⌉ − 2 взвешиваний (⌈log 2 𝑛⌉ | наименьшее целое 𝑘, при котором 2 𝑘 > 𝑛). Решение. Сначала найдём победителя (самый тяжёлый камень), а потом будем искать второй по весу. Ясно, что второго можно искать лишь среди тех, кто проиграл лично победителю (проигравшие кому-то ещё легче сразу двух камней). Если определять победителя в турнире по олимпийской системе (все делятся на пары, проигравшие выбыва- ют, потом снова делятся на пары и так далее), то для 2 𝑘 участников понадобится 𝑘 раундов, а для 𝑛 участников | ⌈log 2 𝑛⌉ раундов. В ка- ждой игре турнира выбывает один участник, поэтому всего будет 𝑛 − 1 4.5. Родственные сортировке задачи 87 игр для определения победителя и ещё ⌈log 2 𝑛⌉ − 1 в турнире за второе место среди проигравших победителю. 4.5.6. Докажите, что никакой алгоритм нахождения самого тяжёло- го и второго по весу среди 𝑛 камней не может гарантированно сделать это менее чем за 𝑛 + ⌈log 2 𝑛⌉ − 2 взвешиваний. Решение. Пусть дан такой алгоритм. В каждый момент его испол- нения рассмотрим число 𝑘 𝑖 камней-участников, проигравших не менее 𝑖 игр-сравнений. (Косвенные проигрыши | если 𝑎 проиграл 𝑏, а 𝑏 про- играл 𝑐, | не учитываются.) Легко понять, что сумма 𝑘 𝑖 по всем 𝑖 равна числу игр, так как после каждой игры одно из 𝑘 𝑖 увеличивается на единицу. Поэтому достаточно показать, что каков бы ни был алгоритм, при неудачных для него результатах игр будет выполнено неравенство 𝑘 1 + 𝑘 2 > 𝑛 + ⌈log 2 𝑛⌉ − 2. Будем называть «лидерами» тех участников, которые ещё никому не проиграли. В начале их 𝑛, а в конце остаётся только один лидер (поскольку любой из лидеров может быть победите- лем). Поэтому 𝑘 1 > 𝑛 − 1 (все игроки, кроме одного, кому-то проигра- ли). Объясним, как надо выбирать результаты матчей, чтобы добиться неравенства 𝑘 2 > ⌈log 2 𝑛⌉ − 1. Результат встречи двух не-лидеров мо- жет быть выбран любым. Если лидер встречается с не-лидером, то вы- игрывает лидер. При встрече двух лидеров выигрывает более опытный, то есть тот, кто выиграл к этому моменту больше игр (при равенстве | любой). Чтобы доказать, что в этом случае выполнено искомое неравенство на 𝑘 2 , введём отношения подчинения, считая при этом, что каждый игрок в любой момент игры подчинён ровно одному лидеру. В нача- ле каждый сам себе лидер и подчинён только себе. При встрече лидера с не-лидером (или двух не-лидеров) подчинение не меняется; при встре- че двух лидеров проигравший и все его подчинённые переподчиняются выигравшему. Легко доказать по индукции, что если лидер выиграл 𝑘 игр, то груп- па его подчинённых (включая его самого) содержит не более 2 𝑘 человек. Вначале 𝑘 = 0 и в его группе только он сам. Если лидер выиграл 𝑘 игр и побеждает лидера, выигравшего не более 𝑘 игр, то в каждой из групп не более 2 𝑘 игроков, а в объединении не более 2 𝑘+1 игроков. Следовательно, по окончании турнира лидер выиграл не менее ⌈ log 2 𝑛⌉ игр, поскольку в его группе все 𝑛 игроков. Все побеждённые им, кроме второго по силе игрока, проиграли ещё кому-то (иначе по- чему мы уверены, что они не вторые по силе?). Отсюда и получается требуемая оценка на 𝑘 2 88 4. Сортировка 4.5.7. Докажите, что оценка предыдущей задачи остаётся в силе, если требуется найти лишь второй по весу камень, а самый тяжёлый искать не обязательно. [Указание. Если по окончанию турнира определился второй по си- ле игрок, то он кому-то проиграл (откуда мы знаем иначе, что он не первый?), и тем самым известен и победитель.] 4.5.8. Дано 𝑛 различных по весу камней и число 𝑘 (от 1 до 𝑛). Требу- ется найти 𝑘-й по весу камень, сделав не более 𝐶𝑛 взвешиваний, где 𝐶 | некоторая константа, не зависящая от 𝑘 и 𝑛. Замечание. Сортировка позволяет сделать это за 𝐶𝑛 log 𝑛 взвеши- ваний. Указание к этой (трудной) задаче приведено в главе про рекур- сию. Следующая задача имеет неожиданно простое решение. 4.5.9. Имеется 𝑛 одинаковых на вид камней, некоторые из которых на самом деле различны по весу. Имеется прибор, позволяющий по двум камням определить, одинаковы они или различны (но не говорящий, какой тяжелее). Известно, что среди этих камней большинство (более 𝑛/2) одинаковых. Сделав не более 𝑛 взвешиваний, найдите хотя бы один камень из этого большинства. (Предостережение. Если два камня оди- наковые, это не гарантирует их принадлежности к большинству.) [Указание. Если найдены два различных камня, то их оба можно выбросить | хотя бы один из них плохой и большинство останется большинством.] Решение. Программа просматривает камни по очереди, храня в пе- ременной i число просмотренных камней. (Считаем камни пронумеро- ванными от 1 до n.) Помимо этого программа хранит номер «текущего кандидата» c и его «кратность» k. Смысл этих названий объясняется инвариантом (И): если к непросмотренным камням (с номерами i+1 . . . n) до- бавили бы k копий c-го камня, то наиболее частым среди них был бы такой же камень, что и для исходного массива. Получаем такую программу: k:=0; i:=0; {(И)} while i<>n do begin if k=0 then begin 4.5. Родственные сортировке задачи 89 k:=1; c:=i+1; i:=i+1; end else if (i+1-ый камень одинаков с c-ым) then begin i:=i+1; k:=k+1; {заменяем материальный камень идеальным} end else begin i:=i+1; k:=k-1; {выкидываем один материальный и один идеальный камень} end; end; искомым является c-ый камень Замечание. Поскольку во всех трёх вариантах выбора стоит команда i:=i+1, её можно вынести наружу. Заметим также, что эта программа гарантирует отыскание наибо- лее частого камня, лишь если он составляет большинство. Следующая задача не имеет на первый взгляд никакого отношения к сортировке. 4.5.10. Имеется квадратная таблица a[1..n,1..n]. Известно, что для некоторого i строка с номером i заполнена одними нулями, а стол- бец с номером i | одними единицами (за исключением их пересечения на диагонали, где стоит неизвестно что). Найдите такое i (оно, оче- видно, единственно). Число действий порядка n. (Заметим, что это су- щественно меньше числа элементов в таблице.) [Указание. Рассмотрите a[i][j] как результат «сравнения» i с j и вспомните, что самый тяжёлый из n камней может быть найден за n сравнений. (Заметим, что таблица может не быть «транзитив- ной», но всё равно при «сравнении» двух элементов один из них от- падает.)] 5. КОНЕЧНЫЕ АВТОМАТЫ И ОБРАБОТКА ТЕКСТОВ 5.1. Составные символы, комментарии и т. п. 5.1.1. В тексте возведение в степень обозначалось двумя идущими подряд звёздочками. Решено заменить это обозначение на ^ (так что, к примеру, x**y заменится на x^y). Как это проще всего сделать? Ис- ходный текст читается символ за символом, получающийся текст тре- буется печатать символ за символом. Решение. В каждый момент программа находится в одном из двух состояний: «основное» и «после» (звёздочки): Состояние Очередной Новое Действие входной символ состояние основное * после нет основное 𝑥 ̸= * основное печатать 𝑥 после * основное печатать ^ после 𝑥 ̸= * основное печатать *, 𝑥 Если в конце текста программа оказывается в состоянии «после», то следует напечатать звёздочку (и кончить работу). Замечание. Наша программа заменяет *** на ^* (но не на *^). В ус- ловии задачи мы не оговаривали деталей, как это часто делается | предполагается, что программа «должна действовать разумно». В дан- ном случае, пожалуй, самый простой способ объяснить, как программа действует | это описать её состояния и действия в них. 5.1.2. Напишите программу, удаляющую из текста все подслова ви- да abc. 5.1. Составные символы, комментарии и т. п. 91 5.1.3. В паскале комментарии заключаются в фигурные скобки: begin {начало цикла} i:=i+1; {увеличиваем i на 1} Напишите программу, которая удаляла бы комментарии и вставляла бы вместо исключённого комментария пробел (чтобы 1{один}2 преврати- лось не в 12, а в 1 2). Решение. Программа имеет два состояния: «основное» и «внутри» (комментария). Состояние Очередной Новое Действие входной символ состояние основное { внутри нет основное 𝑥 ̸= { основное печатать 𝑥 внутри } основное печатать пробел внутри 𝑥 ̸= } внутри нет Замечание. Эта программа не воспринимает вложенные коммента- рии: строка вроде {{комментарий внутри} комментария} превратится в комментария} (в начале стоят два пробела). Обработка вложенных комментариев конечным автоматом невозможна (нужно «помнить число скобок» | а произвольное натуральное число не помещается в конечную память). 5.1.4. В паскалевских программах бывают также строки, заключён- ные в кавычки. Если фигурная скобка встречается внутри строки, то она не означает начала или конца комментария. В свою очередь, кавыч- ка в комментарии не означает начала или конца строки. Как изменить программу, чтобы это учесть? [Указание. Состояний будет три: основное, внутри комментария, внутри строки.] 5.1.5. Ещё одна возможность многих реализаций паскаля | это комментарии вида i:=i+1; (* here i is increased by 1 *) при этом закрывающая скобка должна соответствовать открывающей (то есть {. . . *) не разрешается). Как удалять такие комментарии? 92 5. Конечные автоматы и обработка текстов 5.2. Ввод чисел Пусть десятичная запись числа подаётся на вход программы символ за символом. Мы хотим «прочесть» это число (поместить в переменную типа real его значение). Кроме того, надо сообщить об ошибке, если число записано неверно. Более конкретно, представим себе такую ситуацию. Последователь- ность символов на входе делится на прочитанную и оставшуюся части. Мы можем пользоваться функцией Next:char, которая даёт первый символ оставшейся части, а также процедурой Move, которая забирает первый символ из оставшейся части, переводя его в категорию прочи- танных. прочитанная часть Next ? ? Будем называть десятичной записью такую последовательность символов: ⟨ 0 или более пробелов⟩ ⟨1 или более цифр⟩, а также такую: ⟨ 0 или более пробелов⟩ ⟨1 или более цифр⟩.⟨1 или более цифр⟩. Заметим, что согласно этому определению 1. .1 1.␣1 -1.1 не являются десятичными записями. Сформулируем теперь задачу точно: 5.2.1. Прочтите из входной строки максимальную часть, которая может быть началом десятичной записи. Определите, является ли эта часть десятичной записью или нет. Решение. Запишем программу на паскале (используя «перечислимый тип» для наглядности записи: переменная state может принимать одно из значений, указанных в скобках). var state: (Accept, Error, Initial, IntPart, DecPoint, FracPart); state := Initial; 5.2. Ввод чисел 93 while (state <> Accept) or (state <> Error) do begin if state = Initial then begin if Next = ’ ’ then begin state := Initial; Move; end else if Digit(Next) then begin state := IntPart; {после начала целой части} Move; end else begin state := Error; end; end else if state = IntPart then begin if Digit (Next) then begin state := IntPart; Move; end else if Next = ’.’ then begin state := DecPoint; {после десятичной точки} Move; end else begin state := Accept; end; end else if state = DecPoint then begin if Digit (Next) then begin state := FracPart; Move; end else begin state := Error; {должна быть хоть одна цифра} end; end else if state = FracPart then begin if Digit (Next) then begin state := FracPart; Move; end else begin state := Accept; end; end else if {такого быть не может} end; end; Заметьте, что присваивания state:=Accept и state:=Error не сопро- вождаются сдвигом (символ, который не может быть частью числа, не забирается). Приведённая программа не запоминает значение прочитанного числа. 5.2.2. Решите предыдущую задачу с дополнительным требованием: если прочитанный кусок является десятичной записью, то в перемен- ную val:real следует поместить её значение. 94 5. Конечные автоматы и обработка текстов Решение. При чтении дробной части переменная step хранит мно- житель при следующей десятичной цифре. state := Initial; val:= 0; while (state <> Accept) or (state <> Error) do begin if state = Initial then begin if Next = ’ ’ then begin state := Initial; Move; end else if Digit(Next) then begin state := IntPart; {после начала целой части} val := DigitValue (Next); Move; end else begin state := Error; end; end else if state = IntPart then begin if Digit (Next) then begin state := IntPart; val := 10*val + DigitVal(Next); Move; end else if Next = ’.’ then begin state := DecPoint; {после десятичной точки} step := 0.1; Move; end else begin state := Accept; end; end else if state = DecPoint then begin if Digit (Next) then begin state := FracPart; val := val + DigitVal(Next)*step; step := step/10; Move; end else begin state := Error; {должна быть хоть одна цифра} end; end else if state = FracPart then begin if Digit (Next) then begin state := FracPart; val := val + DigitVal(Next)*step; step := step/10; Move; end else begin state := Accept; end; end else if {такого быть не может} end; end; 5.2. Ввод чисел 95 5.2.3. Та же задача, если перед числом может стоять знак - или знак + (а может ничего не стоять). Формат чисел в этой задаче обычно иллюстрируют такой картин- кой: + - ⟨ цифра⟩ ⟨ цифра⟩ - - - 5.2.4. Та же задача, если к тому же после числа может стоять показатель степени десяти, как в 254E-4 (= 0.0254) или в 0.123E+9 (= 123 000 000). Нарисуйте соответствующую картинку. 5.2.5. Что надо изменить в приведённой выше программе, чтобы разрешить пустые целую и дробную части (как в «1.», «.1» или да- же «.» | последнее число считаем равным нулю)? Мы вернёмся к конечным автоматам в главе 10 (Сравнение с образ- цом). 6. ТИПЫ ДАННЫХ 6.1. Стеки Пусть T | некоторый тип. Рассмотрим (отсутствующий в паскале) тип «стек элементов типа T». Его значениями являются последователь- ности значений типа T. Операции: ∙ Сделать пустым (var s: стек элементов типа T) ∙ Добавить (t:T; var s: стек элементов типа T) ∙ Взять (var t:T; var s: стек элементов типа T) ∙ Пуст (s: стек элементов типа T): boolean ∙ Вершина (s: стек элементов типа T): T (Мы пользуемся обозначениями, напоминающими паскаль, хотя в паскале типа «стек» нет.) Процедура «Сделать пустым» делает стек s пустым. Процедура «Добавить» добавляет t в конец последовательно- сти s. Процедура «Взять» применима, если последовательность s непу- ста; она забирает из неё последний элемент, который становится зна- чением переменной t. Выражение «Пуст(s)» истинно, если последова- тельность s пуста. Выражение «Вершина(s)» определено, если последо- вательность s непуста, и равно последнему элементу последовательно- сти s. Мы покажем, как моделировать стек в паскале и для чего он может быть нужен. Моделирование ограниченного стека в массиве Будем считать, что количество элементов в стеке не превосходит некоторого числа n. Тогда стек можно моделировать с помощью двух 6.1. Стеки 97 переменных: Содержание: array [1..n] of T; Длина: integer; считая, что в стеке находятся элементы Содержание [1],...,Содержание [Длина]. ∙ Чтобы сделать стек пустым, достаточно положить Длина := 0 ∙ Добавить элемент t: {Длина < n} Длина := Длина+1; Содержание [Длина] :=t; ∙ Взять элемент в переменную t: {Длина > 0} t := Содержание [Длина]; Длина := Длина - 1; ∙ Стек пуст, если Длина = 0. ∙ Вершина стека равна Содержание [Длина]. Таким образом, вместо переменной типа стек в программе на па- скале можно использовать две переменные Содержание и Длина. Можно также определить тип stack, записав const N = ... type stack = record Содержание: array [1..N] of T; Длина: integer; end; (Мы позволяем себе использовать имена переменных из русских букв, хотя обычно паскаль этого не любит.) После этого могут быть | в со- ответствии с правилами паскаля | описаны процедуры работы со сте- ком. Например, можно написать procedure Добавить (t: T; var s: stack); begin {s.Длина < N} s.Длина := s.Длина + 1; s.Содержание [s.Длина] := t; end; 98 6. Типы данных Использование стека Будем рассматривать последовательности открывающихся и закры- вающихся круглых и квадратных скобок ( ) [ ]. Среди всех таких последовательностей выделим правильные | те, которые могут быть получены по таким правилам: ∙ пустая последовательность правильна. ∙ если 𝐴 и 𝐵 правильны, то и 𝐴𝐵 правильна. ∙ если 𝐴 правильна, то [𝐴] и (𝐴) правильны. Пример. Последовательности (), [[ ]], [()[ ]()][ ] правильны, а последовательности ], )(, (], ([)] | нет. 6.1.1. Проверьте правильность последовательности за время, не превосходящее константы, умноженной на её длину. Предполагается, что члены последовательности закодированы числами: ( 1 [ 2 ) −1 ] −2 Решение. Пусть a[1]. . . a[n] | проверяемая последовательность. Разрешим хранить в стеке открывающиеся круглые и квадратные скоб- ки (т. е. 1 и 2). Вначале стек делаем пустым. Далее просматриваем члены последо- вательности слева направо. Встретив открывающуюся скобку (круглую или квадратную), помещаем её в стек. Встретив закрывающуюся, про- веряем, что вершина стека | парная ей скобка; если это не так, то можно утверждать, что последовательность неправильна, если скобка парная, то заберём её (вершину) из стека. Последовательность правиль- на, если в конце стек оказывается пуст. Сделать_пустым (s); i := 0; Обнаружена_ошибка := false; {прочитано i символов последовательности} while (i < n) and not Обнаружена_ошибка do begin i := i + 1; if (a[i] = 1) or (a[i] = 2) then begin Добавить (a[i], s); end else begin {a[i] равно -1 или -2} 6.1. Стеки 99 if Пуст (s) then begin Обнаружена_ошибка := true; end else begin Взять (t, s); Обнаружена_ошибка := (t <> - a[i]); end; end; end; Правильно := (not Обнаружена_ошибка) and Пуст (s); Убедимся в правильности программы. (1) Если последовательность построена по правилам, то программа даст ответ «да». Это легко доказать индукцией по построению пра- вильной последовательности. Надо проверить для пустой, для после- довательности 𝐴𝐵 в предположении, что для 𝐴 и 𝐵 уже проверено, и, наконец, для последовательностей [𝐴] и (𝐴) | в предположении, что для 𝐴 уже проверено. Для пустой очевидно. Для 𝐴𝐵 действия про- граммы происходят как для 𝐴 и кончаются с пустым стеком; затем всё происходит как для 𝐵. Для [𝐴] сначала помещается в стек открываю- щая квадратная скобка и затем всё идёт как для 𝐴 | с той разницей, что в глубине стека лежит лишняя скобка. По окончании 𝐴 стек ста- новится пустым | если не считать этой скобки | а затем и совсем пустым. Аналогично для (𝐴). (2) Покажем, что если программа завершает работу с ответом «да», то последовательность правильна. Рассуждаем индукцией по длине по- следовательности. Проследим за состоянием стека в процессе работы программы. Если он в некоторый промежуточный момент пуст, то по- следовательность разбивается на две части, для каждой из которых программа даёт ответ «да»; остаётся воспользоваться предположением индукции и определением правильности. Пусть стек всё время непуст. Это значит, что положенная в него на первом шаге скобка будет выну- та лишь на последнем шаге. Тем самым, первый и последний символы последовательности | это парные скобки, и последовательность имеет вид (𝐴) или [𝐴], а работа программы (кроме первого и последнего шагов) отличается от её работы на 𝐴 лишь наличием лишней скобки на дне стека (раз её не вынимают, она никак не влияет на работу про- граммы). Снова ссылаемся на предположение индукции и определение правильности. |