ע. ברנדס וצוותה. עיצוב  תכנה. ספר  לתלמיד, 1997

А. Брандес и др. Программный дизайн(оформление  программы). Книга  ученика.

Шалом  учителям  и  ученикам.

Этот  учебник  посвящен  среди  прочего  теме  разработки  и  оформления  систем, часть  принципов  которых : планирование  от  общего  к  частному, деление  на  модули  и  коллективная  работа  согласно  внятным  интерфейсам. Эти  же  принципы  лежали  в  основе  работы  коллектива  авторов  настоящей  книги.  Длительный  процесс  планирования  и  оформления  предшествовал  написанию ... ; все  учебные  материалы  были  проверены  нами  согласно  критериев  правильности, устойчивости  и  дружественного  отношения  к  читателю  и  учителю ; работа  авторов  осуществлялась согласованно  и  со  взаимопониманием таким  образом, что  разделы, написанные  одним  автором, обрабатывались  и  изменялись  другими  на  более  поздних  этапах ;  документация  и  разъяснения  позволили  объединить  различные  части  согласно  общим  правилам. Наши  благодарности  ......    

 

Глава  1.  Введение

1.1. Проектирование  от  общего  к  частному

Попробуйте  поразмыслить,  что  в  первую  очередь  вы  сделаете, если  на  вас  возложат  какое-либо  задание  вроде  планирования  школьного  выпускного  вечера. Логично  предположить, что  вы  не  примитесь  немедленно  за  составление  приглашений  или  покупку  угощения. В  такого  рода  заданиях  чаще  всего  не  начинают  с  планирования небольших  частностей, но  принимают  более  важные  решения, вроде  того,  какой  будет  программа  вечера, где  и  когда  он  состоится.  Часто  подобные  решения  зависят  одно  от  другого :  если  решено, что  основным  событием  вечера  будет  сатирическое  представление  про  учителей  школы, вечер  почти  наверняка  состоится  в  школьном  зале. А  если   это  будет  танцевальный  вечер, следует  найти  для  него  более  подходящее  место. Может  быть  решили    провести  вечер  в  школе  в  определенный  день, но  именно  в  этот  день  там  проводится  учительское  совещание.

Только  после  установления  общих  рамок  вечера, станет  возможным  детальное  планирование.  Планирование  деталей  возлагается  почти  наверняка  на  несколько  групп, но  не  на  одного  человека.  Каждая  группа  получит  какое-то  поручение  для  планирования  и  осуществления. Задание  на  планирование  каждой  из  групп  принципиально  не  отличается  от  общего  плана.  Группа, ответственная, к  примеру,  за  танцы, решит  согласно  предпочтений  учащихся, какого  рода  будет  музыка,  и  в  соответствии  с  этим  выберет  проигрыватель, согласует  дату  и , возможно,  даже  пошлет  представителей  заранее  извиниться  за  ожидаемый  шум  перед  соседями , живущими  около  школы.  И  группу  угощения  ожидают  нелегкие  решения : какие  подать  вафли - со  вкусом  лимона  или  шоколада ?  Возможно,  эта  группа  решит  провести  опрос  среди  учащихся, чтобы  выяснить  какой  вкус  предпочтительней. Осуществление  опроса  будет  возложено, конечно, на  дополнительную  группу, которая  подготовит  опросные  листы, раздаст  их  ученикам  и  обработает  результаты. 

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

Когда  нам  поручено  задание, его  необходимо  определить  в  ясной  форме.  На  следующем  этапе  можно  попытаться  разложить  его  на  подзадания  и  подойти  к  их  осуществлению  одно  за  другим.  Процесс  осуществления  подзаданий  очень  похож  на  изложенное  выше: если  они  еще  слишком  сложны, можно  продолжить их разбиение  на  дополнительные  подзадания (подподзадания) . Согласно  тому, что   мы  уже  видели, существует  временами  зависимость  между  выполняемыми 

подзаданиями, а  иногда  границы  между  ними  не  ясны.  К  примеру, на  кого  возложено  подготовить  декорации  вечера - на  группу  танцев  или  следует  назначить  новую  команду ?  Ведущий  принцип  при  разделении  работы  состоит  в  максимальном  уменьшении   зависимости  между  подзаданиями. Такое  деление  оставляет  большую  свободу  действий  группам, решения  планирования  в  каждой  из  них  принимаются  самостоятельно, вне  зависимости  от  решений  в  других  группах.   Во  многих  случаях  мы  вынуждены  вернуться  на  несколько  шагов  назад  в  нашей  программе  вседствие  непредвиденных  обстоятельств  или  того  факта, что  мы  столкнулись  с  деталями, влияющими  на  общий  характер  задания.  Но    характерным  для  этого  процесса  является  то, что  сначала  мы  осуществляем  планирование  общих  направлений, а  после  этого  - приступаем  к  все  более  детальному  планированию.Из-за  характера  описанного  процесса  планирования  принято  называть  его  планированием  от  общего  к  частному (top-down  design).

Подобный  процесс  знаком  вам, конечно, из  области  планирования  алгоритмов. Когда  мы  получаем  задачу  для  решения, иногда  ее  можно  разделить  на  подзадачи  и  решать  каждую  из  них  отдельно.  Не  всегда  можно  найти  ясное  и  удобное  разделение, но  это  хороший  подход  к  решению  многих  задач, и  особенно  большое  преимущество  получается  в  сложных  заданиях.

 

1.2. Системы  программного  обеспечения

Принцип  проектирования  от  общего  к  частному  особенно  соответствует  той  области  компьютерных  наук, которая  назывется  проектированием  систем  программного  обеспечения (software  systems). Эти  системы  есть  очень  большие  программы, построенные  иногда  из  сотен  тысяч  команд  на  машинном  языке, осуществляющие  разнообразные  и  сложные  функции  и  обсуживающие  широкий набор  средств  ввода  данных. Для  создания  систем  программного  обеспечения  прилагаются  огромные  усилия, которые  не  зря  измеряют  числом  человеческих  лет, необходимых  для  разработки (произведение числа  разработчиков  на  число  лет  их  работы). Системы  программного  обеспечения  охватывают  разнообразные  темы  вроде  текстовых  редакторов, системы  баз  данных, позволяющие  обслуживать  огромные  собрания  данных, системы  связи, обеспечивающие  соединение  сетей  связи  или  действие  модема, и  даже  компьютерные  игры.

Иногда  системы  программного  обеспечения  подразделяются  на  другие  системы : полетная  система  боевого  самолета, система  отпаравки  багажа  в  аэропорту, система  для  задействования  банковского  автомата, система  задействования  тормозов  в  транспортном  средстве  и  т. д.  И  даже  как-будто  бы  простые  устройства  вроде  мобильного  телефона  включают  в  себя  системы  программного  обеспечения , ответственные  за  их  работу. 

 

1.2.1. Требования  качества

Разнообразие  функций, осуществляемых  системами  программного  обеспечения, и  их  объем  не  являются  единственными  причинами  того, что    построение систем есть  сложный  проект. Вследствие  их  сложности  к  системам  программного  обеспечения  предъявляются  более  высокие  требования  высокого  качества, чем  к  простым  компьютерным  программам.  Конкретизируем  несколько  таких  требований :

Точная  спецификация. К  системам  программного  обеспечения  прилагается  обычно  напечатанная  литература  сопровождения.  Эта  литература  включает  описание  функций  системы  и  детальные  объяснения, как  привести  ее  в  действие. Спецификация  содержит  также  объяснение  требований  установки  и  запуска  с  позиций  оборудования  и  программного  обеспечения  и  описание  ограничений  системы.  Спецификация  это  как-бы  “договор”  о  действии  системы : если  она  запущена  в  соответствии  со  спецификацией, она  будет  исполнять  свою  роль  в  соответствии  с  тем, что    определено  там. 

Устойчивость(robustness). Когда  мы  задействуем  систему  программного  обеспечения, не  исключены  неположенные  ситуации, с  ними  система  обязана  также  справляться.  Обслуживание  таких  (нештатных) ситуаций, не  включенных  в  спецификацию, и называется  устойчивостью. Например, предполагается, что  системе  нужен  экран  определенного  типа. Что  произойдет, если  к  компьютеру  будет  подключен  экран  не  того  типа ? Система  рухнет, или  напечатает  соответствующее 

сообщение  пользователю, или  выполнит  работу  частично ?  Как должен  вести  себя  обработчик  текстов, способный  обрабатывать  документы  до  определенного  размера, когда  пользователь  упорствует  и  пытается  обработать  с  его  помощью  книгу  “Война  и  мир”? Как  поведет  себя  телефонная  станция, предназначенная  обслуживать  до  1000  разговоров  одновременно, если  в  определенный  момент  времени  решат  побеседовать  по  телефону  как  раз  1001  абонент?

Дружественное  отношение  к  пользователю. Многие  системы  программного  обеспечения  предназначены  для  работы  с  человеком. Мы  хотим , чтобы  система  была  простой  и  легкой  в  эксплуатации, и  когда  она  является  такой, мы  называем  ее  “дружественной  к  пользователю”. Часть  системы, которая  обслуживает  связь  с  пользователем, называют  “интерфейсом  пользователя” (user  interface), и  чем  он  легче  и  удобнее  в  работе, тем  больший  кредит  доверия  накапливает  система  среди  пользователей.  Повидимому  вы  сталкивались  в  прошлом  с  недружественной  компьютерной  программой, вроде  той, что  ожидает  ввода  без  объяснения,  каков  он. Если  вы  еще  не  сталкивались  с  подобной  программой,  то  избежали  без  сомнения  разочаровывающего  впечатления.

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

Правильность, корректность(correctness). Последнее  требование  имеет  центральное  значение.  От  системы  программ, так  же  как  и  от  простой  программы,  мы  ждем , чтобы  она  делала  то, что  от  нее  требуется. Этим  требованием  нельзя  пренебрегать: вопрос  корректности  программы  не  простой , всеобщий  и  основной,  и  вы  конечно  сталкивались  с  ним  в  прошлом.  Вес  этого  требования  возрастает  с  обсуждением  систем, выполняющих  сложные  функции  и  обслуживающих  разнообразный  ввод. Не  слишком  успокаивает  знание  того, что  система, ответственная  за  полет  боевого  самолета, действует  верно  почти  всегда. Такая  система  обязана  правильно  действовать  в  любой  возможной  ситуации.

Один  из  путей  усилить  корректность  системы  состоит  в  осуществлении  ее  всеобъемлющей  проверки. Программистские  компании  выделяют  большие  группы  работников  на  проверку  частей  написанных  ими  систем  до  их  распространения  на  рынке.  Иногда  можно  проверить  систему  с  помощью  ее  прогона  на  большом  наборе  данных  ввода.  Следует, однако, обратить  внимание: подобная  проверка , включающая  все,  что  только  можно, - не  гарантирует  от  того ,  что  система  свободна  от  неисправностей. К  очень  немногим  системам  не  приходилось  возвращаться  в  связи  с  обнаруженными  неисправностями, и  даже - после  значительного  времени  их  эксплуатации.  Самый  простой  способ  для  создания  “верного”  кода  фрагмента  программы - воспользоваться  кодом, который  уже  написан  и  испытан  в  прошлом. Поскольку  система  программ  строится  часто  из  сотен  тычяч  машинных  команд,  включение  фрагментов  готовых  программ  сильно  экономит  время  разработки.  Существуют  программистские  компании, которые  поощряют  программистов, использующих  существующий  код, а  также  программистов, которые  написали  код  для  других.  Создание  кода    для  системы  программного  обеспечения, который  можно  будет  использовать  при  коструировании  новой  системы  в  будущем , т.е. для повторного  использования (code  reuse)   подобного  кода,  требует  глубокого  осмысления  и   всеобъемлющего  планирования.

 

1.2.2. Техническое  обслуживание (сопровождение)

Система  программного  обеспечения, подобно  любому   другому  сложному  изделию,

нуждается  в  техническом  обслуживании. Это  сопровождение  включает  исправление  ошибок  и  периодическое  обслуживаение,  ответственность  за  это  несет  компания - разработчик.  В  систему  программ  включают  обеспечение  локализации  неисправностей и  их  исправление, а  во  многих  случаях  также  изменения  и  улучшения  на  основе  требований  пользователей. Для  этого  осуществляется  время  от времени  операция  повышения (upgrade)  , включающая  требуемые  изменения.

Техническое  сопровождение  системы  программ  связано  с  изменениями  ее  машинного  кода. Изменения, которые  должны  перейти  в  код, не  выполняются  в  обязательном  порядке  исходными  разработчиками.  Построение  системы  программного  обеспечения  проходит  лучше  в  ходе  правильного  использования (indentation)  со  смысловыми  именами  переменных , что  облегчает  работу  во  время   программироания, но  принимает  особое  значение  во  время  технического  обслуживания(сопровождения). Система  программ, построенная  в  ясной  и  читаемой  форме, по  всем  правилам, позволит  сотруднику  сопровождения  следить  за  кодом  и  локализовать  фрагменты, нуждающиеся  в  изменениях.

Когда  пишем  код  системы  программ, мы  заинтересованы, чтобы  будущие  изменения  и  уточнения  были  бы  по  возможности  строго  локализованы, т.е.  изменение  определенного  фрагмента  кода  не  должно  привести  к  необходимости  изменений  во  множестве  других  мест. Это  требование  выглядит  немного  странно : ведь  трудно  прогнозировать  изменения, которые  потребуются  в  будущем !   Но   мы  еще  увидим, что  когда  готовится  система  программ, можно  работать  в  соответствие  с  рядом  основных  принципов, которые  увеличивают  надежду  на  то, что  написанный  код  можно  будет  легко  изменять  и  уточнять.

 

1.2.3. Проектирование  систем  программного  обеспечения

В  соответствии  со  сказанным выше,  требования  систем  программного  обеспечения  несомненно  предполагают  продолжительный  процесс  проектирования, предшествующий  написанию  кода  в  действительности. Раздел  компьютерных  наук, занимающийся  проектированием  систем  программного  обеспечения,  называется  инженерией  программного  обеспечения (software  engineering).

Этот  раздел  науки  возвращает  нас  к  проектированию  от  общего  к  частному.  Когда  выстраивают  систему  программ, такое  проектирование  дает  немалые  преимущества. На  первом  этапе  проектирования  любой  системы  необходима  детальная  характеристика  функций, которые  она  должна  выполнять.  На  следующем  этапе  пытаются    облегчить    задание    с    помощью   его  деления  на  ряд  подзаданий.  Делят  определение  системы  на  несколько  функций, выполняемых  подзаданиями, и  решают  вопросы  связи  между  этими  подразделениями. Примерами  подобных  подразделений  могут  быть  блок, ответственный  за  интерфейс  с  пользователем, или  блок, отвечающий  за  хранение  данных  на  диске. Общее  проектное  задание  превращается  в  набор  подзаданий , каждое  из  которых  занимается  проектированием  блока, отвественного  за  ограниченную  часть  функций  в  системе.

Как  реализуются  преимущества  проектирования  от  общего  к  частному  в  системе  программного  обеспечения ? После  того, как  решено,  какие  блоки  составляют  систему  и  как  они  связаны, можно  поделить  работу  проектирования  между  группами, каждая  из  которых  занимается  определенным  блоком. Работа  группы  в  большой  системе  программ  очень  важна, т.к.  нельзя  ожидать, что  единственный  программист будет  знать  код  всей  системы.  Распределение  на  группы  также  способствует  быстрому  и  эффективному  выполнению  задач  сопровождения, вроде  локализации  ошибок  и  функциональных  изменений, поскольку  группа  лучше  ориентируется  в  разделе, за  который  она  отвечает. А  также  вероятно, что  изменения  и  исправления  в  блоке  будут  локальными.

 

1.3. Разделение  интерфейса  и  реализации - принцип  сокрытия  информации

Сказано  вам : “Позвоните  тете  Блюме  и  передайте  ей  горячий  привет”. И  вы  сразу  поняли, что  от  вас  требуется. Подобное  указание  в  более  детальной  форме  может  прозвучать  так : “Найдите  номер  телефона  тети  Блюмы  в  телефонной  книжке, поднимите  телефонную  трубку, подождите  сигнала, разрешающего  набор, наберите   цифры  телефона  тети  Блюмы  из  телефонной  книжки, подождите  ответа,  скажите  ей “Мама  передает  горячий  привет”  и  разъединитесь”.

Когда  вас  попросили  позвонить  тете  Блюме,  то  подразумевалось, что  вы  способны  перевести  указание  “позвонить  Х”  на  последовательность  действий : “Найдите  номер  телефона  Х  в  телефонной  книге, поднимите  телефонную  трубку ...”.  Логично  предположить, что  действие   “позвонить  Х”  переводится  вами  на  более  сложную  последовательность  действий. Предположим, что  телефона  Х  нет  в  семейной  телефонной  книжке, тогда  надо  искать  его  в  общей  телефонной  книге; возможно, что  после  набора  номера  Х, будет  получен  сигнал, что  телефон  занят, тогда  надо  будет  повторить  набор. Вам  надлежит  знать, что  делать  в  каждом  возможном  случае.  Наша  жизнь  очень  упрощается  от  того, что  всякий  раз, когда  мы  звоним  тете  Блюме, нет  нужды  детализировать  последовательность  действий.

Почему  все  это  похоже ? В компьютерных  науках  мы  управляем  подобными  сокращениями  с  помощью  функций  и  процедур.  Определяя  функцию  или  процедуру, мы  объединяем  ряд  действий  и  даем  им  общее  краткое  имя.   Для  удобства  будем  теперь  называть  функции  и  процедуры  общим  именем  подпрограмма(routine).

Попытаемся  понять  глубже  процесс  определения  новой  подпрограммы. Сперва  нам  надлежит  решить, что  подпрограмма  должна  делать.  Например, можно  определить  подпрограмму, которая  будет  печатать  на  экране  элементы  массива  согласно  их  порядку   в  массиве.  Можно  также  определить  ее  так, чтобы  печать  была  согласно  порядку  значений  элементов  от  наибольшего  к  наименьшему  или  от  наименьшего  к  наибольшему. Внятное  определение  действия, которое  осуществляет  подпрограмма, очень  важно  для  ее  функционирования.  В  действительности, это  определение  похоже  на  спецификацию  системы  программного  обеспечения, которая  в  точности  описывает  назначение  системы. Следующий  этап  определения  подпрограммы  состоит  в  установлении  способа  обращения  к  ней.  Чтобы  осуществить  действие  “Позвоните  Х” , мы  оцениваем  название  действия  “Позвоните к...”  и  каковы  параметры, которые  передаются  этому  действию, в  этом  случае - Х. Подобно  этому  обращение  к  подпрограме(запуск  подпрограммы)  состоит  из  ее  имени, параметров, которые  ей  передаются, типа  и  способа  передачи - по  значению  или  имени  переменной.Способ  задействования  подпрограммы(заголовок  подпрограммы)  и  определение  ее  назначения  (документация   подпрограммы)  принято  называть  интерфейсом(interface). Интерфейс  подпрограммы, печатающей  на  экране  элементы  массива, может  выглядеть  так :

Печать_массива (А, n)

{ Подпрограмма  печати  n  первых  элементов  массива  А  согласно  их  порядку  в  массиве. Предположение : n  меньше  числа  элементов  массива  или  равно  ему. }

Документация (documentation)  это  неотделимая  часть  интерфейса  подпрограммы. Ее  назначение  состоит  в  описании  подпрограммы, передаваемых  ей  параметров  и  ограничений  на  их  значения.

После  того, как  мы  определили  интерфейс, следует  написать  реализацию (implementation) подпрограммы, т.е.  алгоритм, который  подпрограмма  осуществляет. В  простом  случае  подпрограммы  Печать_массива  реализация  выглядит  так :

(1) Для  i  от  1  до  n :

(1.1) печатай  А[i].

Обрати  внимание, что  есть  ясная  линия, разделяющая  интерфейс  подпрограммы  и  ее  реализацию. Реализация  программы  очень  важна, но  чтобы  воспользоваться  подпрограммой, нам  надо  знать  только , что  она  делает  и  как  к  ней  обращаются, т.е.  каков  интерфейс  подпрограммы. Очень  похоже  на  способ  запуска  простого  электрического  прибора, вроде  вентилятора.  Чтобы  запустить  вентилятор  с  определенной  скоростью, нам  нужно  знать  на  каких  различных  скоростях  можно  запускать  вентилятор, и  на  какую  кнопку  или  кнопки  нужно  нажать, чтобы  выбрать  необходимую  скорость. Обычно  у  нас  нет  интереса  или  нужды  знать  все  разнообразие  возможностей  запуска  вентилятора  с  различной  скоростью(особенно, если  температура  снаружи  38  градусов  в  тени).

Понятия  спецификация, интерфейс  и  реализация  не  принадлежат  исключительно 

компьютерным  наукам  -  они  естественно  используются  нами  в  различных  областях. Интерфейс  между  двумя  частями  системы  есть  набор  информации, которую  одна  часть  должна  знать, чтобы  задействовать  вторую  нормальным  образом.

Рассмотрим  дополнительный  пример  использования  этих  понятий - теперь  в  стерео-системе.  Стерео-система  собрана  из  ряда  блоков, знакомых  всем : приемник, усилитель, громкоговорители, магнитофон, проигрыватель  компакт-дисков  и  иногда  также  проигрыватель(патефон). Для  каждого  блока  определена  спецификация - ее  общее  функциональное  описание  и  набор  действий, которые  можно  осуществлять  с  его  помощью.  У  каждого  блока  есть  внятный  интерфейс - способ  задействования  каждой  операции  и  пути  подключения  к  другим  блокам. Например, часть  интерфейса  приемника  может  выглядеть  так :

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

 

1.4. Модульное  программирование

Вернемся  к  стерео-системе, которую  мы  обсуждали  в  предыдущем  параграфе. Если  мы  захотим  приобрести  такую  систему, то  можем  пожелать  сочетания  блоков, созданных     разными     производителями.    Можно    купить    усилитель  одной  фирмы, подключить  его  к  приемнику , произведенному  на  другой  фабрике, и  к  громкоговорителям, сделанным  в  третьем  месте.  Какой  аппарат  позволяет  нам  собирать   стерео-систему  из  блоков  разных  фирм ?  Основная  идея  заключается  в  том, что  интерфейс  между  блоками, т.е.  способы  соединения  блоков, согласованы  производителями  элементов  стерео-систем. Звуковой  выход  магнитофона  идентичен  для  любого  из  них, даже  если  они  устроены  по-разному.  Итак  мы  знаем, что  если  вдруг  сломается  купленный  нами  магнитофон, или  мы  захотим  поменять  его  на  лучший  магнитофон, мы  можем  просто  отсоединить  провода , соединяющие  его  с  остальными  блоками  системы  и  заменить  на  новое  устройство.

В  построении  систем  программного  обеспечения  пользуются  подобным  принципом. Напомним, что  процесс  построения  систем  включает  идентификацию  ее  подразделений, выполняющих  определенные  функции, и  определение  связей  между  ними. Такие  блоки  принято  называть  модулями (modules).  Модуль  это  самостоятельный  блок, выполняющий   определенную  функцию. Примеры  модулей  весьма  многочисленны : модуль  для  обслуживания  текстовых  окон  позволяет  создавать  новые  окна, открывать  их, сдвигать,  изменять  размеры, закрывать  и   т.д.; модуль, включающий  функции, позволяющие  выполнять  математические  и  статистические  операции; модуль , ответственный  за  рисование  графических  элементов  на  экране  компьютера  и  т.п.

Как  решается  вопрос  о  том, какие  модули  должны  быть  включены  в  новую  систему? Это  не  простой  вопрос.  Не  существует  ясного  “рецепта”, который  позволит  нам  однозначно  установить, что  какая-то  определенная  часть  системы  удостаивается  статуса  отдельного  модуля,  но  в  ходе  проектирования  (программирования) нами  руководит  один  важный  принцип  -  принцип  модульности(modularity  principle). Единицы(блоки)  построения  систем  программного  обеспечения, модули, должны  быть  удобными  для  подсоединения  и  замены, подобно  тому  как  в  стерео-системе  подключение  нового  блока  или  его  замена   осуществляются  относительно  легко. Как  правило, когда  делят  систему  на  модули, стремятся  к  тому, чтобы  зависимость  между  различными  модулями,

составляющими  систему, была  бы  минимальной.  Обратите  внимание , что  модульное  построение  системы  увеличивает  вероятность  повторного  использования  созданного  кода, если  блоки  ее, удобные  для  подключения  и  замены, позволяют  присоединять  их  к  другим  системам.  Эта  вероятность  возрастает, если    изменения  кода  будут  локальными,  и  в  ходе  программирования  системы   мы  были  озабочены  уменьшением  зависимости  блоков  друг  от  друга.

И  в  программных  модулях  принято  выделять  спецификацию, интерфейс  и  реализацию. Общее  назначение  модуля  определяется  в  его  спецификации.  А  что  должно  появиться  в  интерфейсе  модуля ?  Мы  видели  в  примерах  стерео-системы  и  вентилятора, что  есть  смысл  в  сокрытии  информации, которая  не  нужна  для  их  запуска. И  если  интерфейс  определенного  блока  содержит  излишнюю  информацию, то  его  использование  становится  более  громоздким.  В  соответствие  с  этим  интерфейс  модуля  содержит  только  ту  информацию, которая  нужна  для  его  задействования.   А  информация , которая  не  требуется  для  этого,  сокрыта  от  глаз  пользователя  в  разделе  реализации  модуля.   Сокрытие  раздела  реализации  может  повлиять  также  на  легкость  внесения  изменений  в  код. Когда  мы  захотим  сменить  реализацию  или  изменить  ее, система  программного  обеспечения, пользующаяся   модулем, может  продолжать  пользоваться  им  без  каких-либо  дополнительных  изменений  до  тех  пор, пока  не  изменится  интерфейс  модуля.  С  раскрытием  многих  деталей  реализации  растет  вероятность  того, что  изменения  в  коде  не  будут  локальными.  Предположим, что  некоторой  системе  программного  обеспечения  требуется  модуль,  ответственный  за  накопление  и  хранение  номеров  удостоверений  личности  на  диске.  Спецификация  модуля  включает  определение  его  назначения : помещение  в  базу(на  диск)  новых  номеров  удостоверений  личности  и  проверка - не  занесен  ли  уже  в  базу  определенный  номер  удостоверения .  Какие  подпрограммы  должны  быть  включены  в  интерфейс ?  Возможно, например, определить  подпрограмму, которая  проверяет  - существует  ли  уже  на  диске  определенный  номер, и  подпрограмму, которая  помещает  новый  номер  на  диск, если  он  еще  не  занесен  в  базу.  Две  эти  подпрограммы   дают  возможность  исполнения  всех  функций  модуля  согласно  определения  в  спецификации. Но  единственные  ли  это  подпрограммы,  включаемые  в  модуль?   

Логично  предположить, что  в  нем  будут  и  другие  подпрограммы, вроде  той, что  ищет  свободное  место  на  диске,  или  той, которая  проверяет, а  вдруг  диск  заполнен. Эти  подпрограммы  не  нужны  для  задействования  модуля; они  подсказывают  путь, которым  требуемые  данные  запоминаются  действиями  модуля;  и  поэтому  логично  будет  спрятать  их  от  пользователя. В  действительности  такое  сокрытие  осуществляется  путем  непомещения  дополнительных  подпрограмм  в  интерфейс. Если  в  будущем  мы  захотим  изменить  реализацию  модуля  вследствие  приобретения  нового  диска, то , очевидно, будет  изменена  подпрограмма  поиска  места  на  диске, возможно  также, что  новая  реализация  включит  вызов  дополнительных  подпрограмм. Изменение  реализации  не  повлечет  за  собой  изменения  в  системах, использующих  этот  модуль, если  интерфейс  его  не  изменился.  Сокрытие  реализации  должно  осуществляться  осторожно : когда  мы  прячем  информацию  о  способе  действия  блока, следует  обратить  внимание  на  то, чтобы    это  не  привело  к  появлению  ошибок  в  его  функционировании.  Так  например, в  период  войны  в  Заливе  ошибочное  сокрытие  информации  привело  к  скверным  результатам.  Проблема  была  в  системе  программ, приводящей  в  действие  ракетные  батареи “Пэтриот”, которые  предназначались  для  поражения  ракет  “Скад”.   Один  из  модулей  программы  делал  возможным  измерять  времена, и  с  помощью  этой  информации  осуществлять  разные  вычисления, которые  нужны  для  запуска  ракеты.  Когда  приведенной  в  состояние  готовности  батарее  оставляли  слишком  много  времени, расчеты  ракетной  стрельбы  становились  ошибочными. А  цена  этому -   человеческие  жизни. Выяснилось, что  представление  времени  в  этом  модуле   осуществлялось  с  помощью  переменной, точность  которой  уменьшалась  с  ростом  отрезка  времени. Так  случилось,   что  эта  переменная  не  была  достаточно  точной  для  выполнения  вычислений, связанных  со  временем  полета  ракеты. Операторы  не  были  знакомы  с   деталями  реализации  модуля, и  потому  не  знали   этого  ограничения. Этот  пример  разъясняет  нам, что  в  спецификации  модуля, как  и  спецификации  системы,

должно  находиться  исчерпывающее  описание  всех  его  ограничений. Без  такого  описания  простодушный   пользователь  может  предположить , что  модуль  в  состоянии  выполнить  определенное  действие, хотя  в  действительности  существуют  какие-то    ограничения  в  его  функционированиии.    Понятно, что  в  определенных  случаях  мы  бываем  вынуждены  изменять  интерфейс  модуля  и  даже  его  спецификацию    вследствие  обновления  его  назначения. В  таких  случаях  изменяется  и  реализация.  К  обдумыванию  заранее  сводится  связка  принципов, которые  мы  сформулировали  до  сих  пор.  Размышления  в  каком-то  объеме  до  написания  программы , конечно, не  ухудшат  качество  результатов, верно  обратное : качество  результатов  улучшается  с  увеличением  времени, посвященного  проектированию  системы.

1.5. Резюме

·Принцип  проектирования  от  общего  к  частному  соответствует  по  своей  природе  сложным  задачам.  Когда  приступают  к  решению  сложной  задачи, необходимо  сперва  спроектировать  решение  в  общих  чертах  с  разделением  на  подзадачи, независимые  друг  от  друга  как  только  это  возможно, и  после  этого  принимаются  за  детальное  решение  каждой   из  подзадач .

·Системы  программного  обеспечения  слагаются  из  очень  больших  программ, осуществляющих  многочисленные  и  сложные  функции  и  обслуживающих  разнообразные  данные  на  вводе.

·Существует  много  требований  к  качеству  систем  программного  обеспечения, они  сосредоточены   в  таких  областях :  точная  спецификация ;       корректность ;    устойчивость ;     скорость  реакции ;     дружеское  отношение  к  пользователю .

·Система  программного  обеспечения есть  продукт, который  нуждается  в  обслуживании (сопровождении) :  локализации  неисправностей  и  их  исправлении, а  во  многих  случаях  также  в  функциональных  изменениях. 

·Удобочитаемость  и  ясность  кода  программы, стремление  к  локализации  будущих  уточнений  и  стремление  к  повторному  использованию  кода  есть  руководящие  принципы  написания  системы  программ.

·Использование  принципа  проектирования  от  общего  к  частному  в  системе  программ  позволяет  разделить  работу  между  группами, которые  действуют  одновременно,  и  каждая  команда  специализируется  в  своей  области.

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

·Модуль  в  системе  программного  обеспечения  есть  самостоятельная  единица, осуществляющая  определенную  роль.  Когда  система  разрабатывается, то  используют  принцип  модульности :  единицы  построения  системы - модули -  должны  быть  удобны  для  подключения  и  замены.

Понятия  и  ключевые  слова (согласно  еврейского  алфавита)

 

Глава  2. Библиотечный  модуль  в  Турбо  Паскале

Турбо  Паскаль  обеспечивает  удобное  средство  построения  библиотечных  модулей (library  unit).  Имя - библиотечный  модуль - подсказывает  нам  и  способ  его  использования : можно  построить  целую  “библиотеку”  модулей, каждый  из  которых  исполняет  определенную  роль, и  пользоваться  ими  в  разных  программах.

Использование  библиотек  Паскаля  не  является  для  вас  новым. Разумеется  вы  пользовались  в  прошлом  командой    uses  crt; , которая  помещалась  в  начале  программы. Команда  разрешала  использование  модуля  crt , подключенного  к  пакету  программ  Турбо  Паскаля. Среди  прочего  этот  модуль  содержит  несколько  действий, связанных  с  экраном, вроде  его  очистки (clrscr), переход  к  определенному  месту  на  экране (gotoxy)  и  т.д.  Пользователь  не  знает, как  реализованы  эти  подпрограммы, но  интерфейс  модуля  включает  точные  указания  для  обращения  к  ним. Интерфейс  можно  найти  в  документации  Турбо  Паскаля  или  посредством  команды  help  в  меню  среды  программирования. 

? Попытайтесь  проверить, какие  дополнительные  программы определены  в  интерфейсе  библиотечного  модуля  crt .  Знаете  ли  вы  другие  библиотечные  модули ?  Какова  их  функция ?

2.1. Структура  библиотечного  модуля

Файл  библиотечного  модуля  выглядит  как  обычный  файл, содержащий  программу  Паскаля (и  расширение  его  имени  также  .pas), но  две  важные  вещи  отличают  его  от  обычной  программы : первое - у  файла  модуля  специальная  структура, и  второе - после  компиляции  модуля  получается  не  программа, готовая  к  прогону, а  файл  с  расширением  имени  .tpu (начальные  буквы  Turbo  Pascal  Unit).   Этим  файлом  могут  пользоваться  другие  программы  Паскаля.

   Рис. 2.1. Структура  библиотечного  модуля  в  Турбо Паскале

На  рис. 2.1  в  схематической  форме  представлена  структура  файла  библиотечного  модуля.  Файл  начинается  с  зарезервированного  слова  unit , за  которым  следует 

имя  модуля (имя  это  должно  быть  тождественно  основной  части имени  файла). Файл  содержит  три  основных  части : интерфейс, который  начинается  с  зарезервированного  слова  interface;  реализацию, которая  начинается  с  зарезервированного  слова  implementation; инициализацию, которая  появляется  в  конце  файла  между  словами    begin  и  end.  Программа , обращающаяся  к   библиотечному  модулю,  может  пользоваться  функциями, процедурами, переменными, постоянными  или  типами, которые  декларированы  в  его  интерфейсной  части.  В  разделе  реализации  находится  вся  информация, спрятанная  от  пользователя. Реализация  функций  и  процедур, провозглашенных  в  интерфейсе, должна  находится  в  этой  части, и  можно  добавить  в  нее  дополнительные  функции  и  процедуры, которыми  мы  можем  пользоваться, не  раскрывая  их  пользователю. И  переменными, постоянными, типами, провозглашенными  в  реализации, нельзя  пользоваться  за  пределами  библиотечного  модуля.

(Программа 2.1 - библиотечный  модуль  grade)

Рассмотрим  программу  2.1, представляющую  библиотечный  модуль  grade. Этот  модуль  делает  возможным  вычисление  средней  взвешенной(согласно  числу  единиц  обучения  по  каждой  дисциплине)  оценки  экзаменов  на  аттестат  зрелости(багрут). По  дисциплинам, которые  изучались  на  повышенном  уровне 

четырех  и  пяти  единиц  обучения, можно  добавлять  бонус  10%  и  20%  соответственно.  В  добавление  к  функции, которая  вычисляет  собственно  среднюю,  модуль  включает  определение  ряда  типов  и  вспомогательных  подпрограмм, используемых  в  ходе  вычислений.  В  интерфейсе  модуля  определены :

· Постоянная :  grade_subject_num - число  дисцилин  в  экзаменах  на  багрут.

· Типы :  grade_type - запись, включающая  отметку  и  число  единиц  обучения  по отдельной   дисцилине.   

grade_array - массив, содержащий  багрутные  оценки  определенного  ученика. Оценка  на  багрут  номер  х  помещается  в  ячейке  х   массива.

· Подпрограммы :    grade_init - процедура, обнуляющая  все  поля  массива  оценок.

grade_enter - процедура, заносящая  отметку(согласно  ее  номера) в  массив  оценок.

grade_average - функция, вычисляющая  взвешенную  оценку  с  бонусом  и  без  него.

Раздел  реализации  модуля  включает  тексты  трех  подпрограмм, объявленных  в  интерфейсе, и  также  подпрограмму grade_add_bonus, вычисляющую  бонус, добавляемый  к  оценке.  Строение  файла  библиотечного  модуля  дает  возможность  применять  в  Турбо  Паскале  принципы, которые  мы  изучали  в  предыдущей  главе : размежевание  между  интерфейсом  и  реализацией  и  сокрытие  информации, которая  не  требуется  для  обращения  к  модулю.  Подпрограммы, находящиеся  только  в  разделе  реализации  и  не  требующиеся  напрямую    пользователю, не  упоминаются  в  интерфейсе, они  похожи  на  локальные(внутренние) переменные, и  поэтому  их  принято  называть  внутренними  подпрограммами  библиотечного  модуля.

2.2. Документация  библиотечного  модуля

    Рис. 2.2. Документация библиотечного модуля grade

 

Когда  пользователь  получает  библиотечный  модуль, написанный  заранее  другим  программистом, он  не  обязательно  заинтересован  в  расмотрении  библиотечного файла  на  языке  Паскаль . А  когда  модуль  поступает  к  нему  после  компиляции  в  виде  файла  .tpu, он  просто  не  может  сделать  это. Поэтому  следует  сопровождать  файл  .tpu   документацией  модуля.  Документация  позволит  пользователю  узнать  в  точности , что  это  за  библиотека  и  из  чего  она  состоит, чтобы  он  смог  подключить  этот  модуль  к  коду  своей  программы. Рис. 2.2  представляет  документацию  библиотечного  модуля  grade .

 

2.3. Подключение  библиотечного  модуля  к  программе  на  Паскале

Рассмотрим (Программа 2.2. Использование  библиотечного  модуля grade), использующую  модуль  grade. Когда  мы  желаем  в  своей  программе  прибегнуть  к  услугам  какого-либо  библиотечного  модуля, мы  пишем  в  ее  начале  команду  uses  и  затем  имя  необходимого  модуля. И  действительно, в  программе  test_grade  появляются  постоянные, типы  и  подпрограммы, определенные  в  интерфейсе  модуля grade . Но  если  бы  мы  захотели  , к  примеру, обратиться  к  функции grade_add_bonus из  нашей  программы, компилятор  объявил  бы  об  ошибке  компиляции, поскольку  эта  подпрограмма  не  объявлена  в  интерфейсной  части  модуля.  Важно  подчеркнуть, что  и  в  библиотечные  модули  можно  включать  декларацию uses.  Например, если  в  интерфейсе  модуля  А  появляется  декларация   uses  В;, то  внутри  А  можно  использовать  определения  из  интерфейса  В.

 

2.4. Внутренние  переменные  в  библиотечном  модуле

Если  внимательно  посмотреть  на  программу  2, то  увидим, что  массив  the_grade  используется  исключительно  подпрограммами , определенными  в  модуле grade . Этот  факт  подсказывает, что  можно  определить  этот  массив  как  внутреннюю  составляющую  модуля.  Подобно  определению  внутренних  переменных  в  подрограмме, используемых  только  ею, можно  определять  внутренние  переменные  в  разделе  реализации  библиотечного  модуля, и  эти  переменные  не  открыты  пользователям  модуля. Рассмотрим  программу  3, которая  представляет  собой  немного  измененную  версию  модуля grade .

(Программа 3. Вторая  версия  модуля grade)

Обратите  внимание  на  то, что  определение  типа grade_tape  переведено  в  раздел  реализации  библиотечного  модуля. Поэтому  внешний  пользователь  не  может  определять  переменные  этого  типа. Но  в  самом  разделе  реализации  переменная grades  определена  как  массив  элементов  типа  grade_tape .  Такая  переменная  называется  внутренней  переменной  библиотечного  модуля , используемой  исключительно  внутри  него. С  начала  работы  программы, включающей  модуль, создаются  внутренние  переменные, принадлежащие  ему, и  модуль  использует  их  в  течение  всего  времени  прогона  программы.

И  теперь  мы  можем  понять, в  чем  назначение  раздела  инициализации  модуля. Все  команды, содержащиеся  в  разделе  инициализации  между  словами  begin и  end,  выполняются  немедленно  после  создания  внутренних  переменных.  Назначение  этого  раздела состоит  в  инициализации(придании  начальных  значений)  этим  переменным. В  нашем  случае  раздел  инициализации  обращается  к  функции  grade_init , которая  обнуляет  массив  оценок.

А  если  и  нет  нужды  инициализировать  что-нибудь  перед  использованием  модуля, включим  в  раздел  инициализации  слова  begin и  end,  но  теперь  между  ними  нет  команд   и  не  выполняется  инициализация.

? Приведет  ли к  ошибке  компиляции  определение  переменной  с  именем  grades в  программе, использующей  модуль  grade ? Чтобы  ответить  на  этот  вопрос, подумайте, что  случится  в  аналогичном  случае  с  процедурой (т.е. при  определении  переменной  х  в  программе  Р, использующей  процедуру  f  , в  которой  также  определена  переменная  х).

Мы  рассмотрели  две  версии  модуля  grade ;  одна  принимает  внешний  массив  как  параметр  в  каждой  из  ее  подпрограмм, упомянутых  в  интерфейсе, а  вторая  содержит  этот  массив  как   часть  модуля.  У  каждой  из  версий  есть  преимущества  и  недостатки. Первая  версия  предпочтительней, если  мы  захотим  обслуживать  больше  чем  один  массив  оценок, например, когда   надо  будет  воспользоваться 

 

модулем  в  рамках   программы  для  всей  школы, создающей  единый  массив    оценок  всех  учеников.  С  другой  стороны  использование  второй  версии  модуля  проще :  нет  нужды  определять  переменную  типа  массива  оценок  и  передавать  его  в  качестве  параметра  для  каждого  действия  с  интерфейсом. Обратите  внимание,   такой  подход  близок  духу  принципа  сокрытия  информации, по  которому  пользователь  модуля  не  нуждается  в  знании, как  хранятся  элементы  оценок  ученика. 

 

2.5. Резюме

·Библиотечная  единица  есть  средство  использования  модулей  в  Турбо  Паскале.  Она  “пакует”  вместе  набор  подпрограмм, переменных, типов  и  постоянных, объединенных  каким-либо  общим  назначением.

·Библиотечная  единица  делает  возможным  разделение  между  своими  открытыми - “публичными” - разделами  и  разделами  скрытыми - “личными”. Иными  словами  имеет  место  разделение  между  интерфейсом, который  нужен  пользователю, чтобы  он  мог  задействовать  модуль, и  реализацией, информация  которой  не  требуется  прямо  для  приведения  в  действие  библиотечной  единицы. 

·Документация  библиотечного  модуля  есть  его  неотъемлемая  часть . Документация  должна  включать  всю  информацию, которая  позволит  использовать  постоянные, типы  и  подпрограммы, определенные  в  интерфейсе  модуля.

·Назначение  раздела  инициализации  заключается  в  действиях, которые  осуществляются  в  момент  подключения  модуля.

·В  разделе  реализации  можно  определять  внутренние  переменные.

Рис. 2.3  резюмирует  процесс  построения  модуля  и  способ  его  использования  в  Турбо  Паскале. (Рис. 2.3.  Библиотечный  модуль  в  Турбо Паскале)

Понятия  и  ключевые  слова (согласно  еврейского  алфавита)

 

Задачи

1. Перед  тобой  библиотечный  модуль  по  имени  mystery1 :

unit  mystery1;

interface

uses  crt ;

var  a,b : real ;

procedure one(x , y : real);

procedure three(x , y : real);

procedure two(g : real) : boolean;

implementation

var  i , j : integer ;

procedure one(x , y : real);

begin

 .......

end ; (* one *)

procedure four(var  c , d : real);

var  k : integer ;

begin

 .......

end ; (* four *)

procedure three(z , t : real);

begin

 .......

end ; (* tree *)

procedure two(g : real) : boolean;

 

begin

 .......

end ; (* two *)

begin

end.

a). Мы  хотим  написать  программу, которая  будет  использовать  модуль  mystery1. Что  требуется  для  связи  библиотеки  и  программы ?

b). Отметь подпрограммы  и  главную программу, которые  могут  обращаться  к  подпрограммам  и  переменным  из  следующей  таблицы :

2. Даны  модули  alpha , beta , gamma . Ниже  приведены  их  интерфейсы :

В  некоей  главной  программе  написано :   uses  beta , gamma;

Отметь подпрограммы  и  главную программу, которые  могут  обращаться  к  подпрограммам  из  следующей  таблицы :

3. Во  время  написания  программы  возникает  иногда  необходимость  в  использовании  секундомера, который  делает  возможным  установления  продолжительности  времени, в  пределах  которого  действуют  фрагменты  программы, и  печати  ее  на  экран.   (В    окончательной     версии     программы    можно,   понятно,    снять    обращение     к   секундомеру). Интерфейс  модуля, определяющего  такой  секундомер, будет  включать  следующие  команды :

В  разделе  реализации  модуля  необходимо  определить  внутреннюю  переменную, которая  будет  содержать  время, прошедшее  с  момента  последней  инициализации  часов. Создавая  модуль, надо  воспользоваться  командой  gettime, которая  определена  в  модуле  dos , поставляемом  системой  программирования  Турбо Паскаля. (Данные  о  данной  команде  и  о  других  вспомогательных  командах , связанных  с  часами, можно  получить  с  помощью  меню  среды  программирования  Турбо Паскаля).

a). Напишите  интерфейс  соответствующего  библиотечного  модуля.

 

b). Реализуйте  библиотечный  модуль.

с). Задокументируйте  модуль.

d). Напишите  программу,  которая  проверяет  работу  модуля.

4. Мы  хотим  построить  библиотечный  модуль  по  имени  math_utl , обслуживающий  различные  математические  функции. Модуль  должен  включать  следующие  опреции :

·power - вычисляет  х  в  степени  у.

·factorial - вычисляет  х! .

·is_prime - проверяет, является  ли  х  простым  числом.

·mul - вычисляет  произведение  х  и  у  с  использованием  только  операций  сложения  и  вычитания.

Положим, что  все  параметры  подпрограмм  есть  целые  числа.

a). Напишите  интерфейс  соответствующего  библиотечного  модуля.

b). Реализуйте  библиотечный  модуль.

с). Напишите  полную  документацию  модуля. (Обязательно  документируйте  все  ограничения  на  параметры  в  различных  подпрограммах).

d). Напишите  программу,  которая  проверяет  работу  модуля.

5. Постройте  библиотечный  модуль  по  имени  converts , осуществляющий  обслуживание  переходов  между  различными  системами  измерения. Перед  вами 

список  действий , которые  должны  войти  в  этот  модуль :

·Операция  принимает  измерение  температуры  в  градусах  Цельсия  и  переводит  его  в  градусы  Фаренгейта,  и  операция, обратная  описанной.

·Операция  принимает  измерение  расстояния  в  метрах  и  возвращает  его  в  футах(feet),   и  операция, обратная  описанной.

·Операция  принимает  измерение  объема  в  литрах  и  возвращает  его  в  пинтах(pint), и  операция, обратная  описанной.

·Операция  принимает  измерение  веса в  граммах  и  возвращает  его  в  унциях(ounce),  и  операция, обратная  описанной.

Действуйте  согласно  следующих  правил  перевода .

Из  градусов  Цельсия  в  градусы  Фаренгейта : 9с.5 + 32.

1 метр = 3.281 футов.       1 литр = 2.11 пинт.      1 грамм = 0.0353 унций.

a). Напишите  интерфейс  соответствующего  библиотечного  модуля.

b). Реализуйте  библиотечный  модуль.

с). Напишите  полную  документацию  модуля.

d). Напишите  программу,  которая  проверит  исправность  модуля. Конечно, проверке  подвергнутся  все  возможные  случаи.

 

Глава  3. Типы  данных

Многие  алгоритмы  в  той  или  иной  форме  занимаются  числами, словами, текстами  и  даже  странными  предметами  вроде  мест  в  кинотеатре. Принято  называть  разнообразные  предметы, которые  обрабатывают  алгоритмы, данными (data). Множество  целых  чисел (..., -2, -1, 0, 1, 2, ...)  есть  определенный  вид  данных, которые  могут  обрабатываться  алгоритмами. Над  целыми  числами  определены  арифметические  действия  умножения, деления, сложения  и  вычитания, а  также  действия  сравнения - равно, не  равно, больше, меньше, больше  или  равно, меньше  или  равно, образованные  из  отношений  целых  чисел(помним, что  между  двумя  целыми  числами  а  и  b  могут  существовать  только  три  вида  отношений : а  больше  b, а  меньше  b, а  равно  b ). Алгоритмы, работающие  с  целыми  числами, пользуются  набором  действий, определенных  над  этими  числами.

3.1. Абстрактные  типы  данных

Абстрактный  тип  данных (abstract  data  type  или  сокращенно  ADT)  есть  множество  значений  некоторого  типа  и  набор  действий, определенных  над  этими  значениями.  В  соответствие  с  тем, что  мы  уже  видели,  тип  абстрактных  данных - целые  числа - включает  множество  значений  ..., -2, -1, 0, 1, 2, ...  , а  действия, которые  определены  над  ними,  есть  арифметические  действия  и  действия  сравнения. Важно  обратить  внимание  на  то, что  существуют  действия, которые  не  определены, когда  их  пытаются  задействовать  над  частью  значений  этого  типа.  У  каждого  действия  есть область  определения (domain  of  definition), которая  представляет  из  себя  набор  значений, над  которыми  его  можно  осуществлять. Например, область  определения  действия  деления  над    типом  данных  целых  чисел  не  может  включать  делитель, равный  0.  Когда  описывают  абстрактный  тип  данных, следует  оценивать  для  каждого  действия  область  его  определения.

Еще  один  пример  типа  абстрактных  данных  это  слова. Определим  слово  как  последовательность  из  нуля  или  большего  числа  исключительно   букв ‘a’ - ‘z’ (без  пробелов  и  заглавных  букв). Например, abcdefgh  есть  слово  длиной  8  букв,  qwertyuio  есть  слово  из  9  букв, и  даже  w  есть  слово  длиной  в  одну  букву.  Существует  также  особое  слово - пустое  , которое  не  содержит  букв, и  его  длина    равна  0. Обратите  внимание  на  то, что  согласно  нашему  определению , слово  не  обязано  иметь  смысл  на  английском  языке. Часть  возможных  действий   над  типом  данных - словами - есть :  изменение  буквы  в  определенном  месте  слова (изменение  третьей  буквы  в  слове abcdefgh  на u  производит  слово abudefgh), добавление  буквы  следом  за    последней  буквой  в  слове( добавление f  к  слову  we  порождает  слово  wef ), представление  слова  в  обратном  порядке ( обращение  слова   waef  порождает  слово  feaw)  и  склеивание  двух  слов (склеивание  слов  riz  и  raz  порождает  слово  rizraz) . Можно  также  определить  действие, которое  возвращает  длину  слова (длина  слова  rytrewqfdertyp  равняется  14). Что  еще  можно  сказать  об  определении  этих  действий? Нет  смысла  в  изменении  пятой  буквы  слова  длиной  в  3  буквы, поэтому  область  определения  действия  изменения  буквы  , находящейся  на  позиции  n, ограничено  словами, длина  которых  не  меньше  n .     

? Каковы  области  существования  других  действий, определенных  над  типом  слов?  Если  мы  хотим  определить  действие, возвращающее  букву, находящуюся  на  позиции  n  в  слове, то  какой  будет  область  определения  этого  действия ?

3.2. Представление  в  компьютере  типов  данных

Когда  мы  хотим  воспользоваться  некоторым  абстрактным  типом  данных, чтобы  реализовать  некий  алгоритм  или  решить  задание  с  помощью  компьютерной  программы, мы  должны  “перевести”  этот  тип, т.е.  поместить  в  компьютер  данные, необходимые  для  решения  и  обслуживать  их.  Этот  процесс  именуется  представлением (representation).  Оно  включает  двойное  решение : как   представить  значения  типа  данных  в  компьютере  и  как  осуществить  действия, определенные  над  этими  значениями.

3.2.1. Определенные  заранее(предопределенные)  типы  данных

Язык  Паскаль  включает  в  себя  определенные  заранее(предопределенные)  типы  данных (built-in  data  types), которые  делают  возможным  представление  в  компьютере    распространеннных  типов  данных.  Один  из  них  тип  данных  integer ,  который  позволяет  помещать  в  компьютер  целые  числа  и  выполнять  над  ними  определенные  действия.  Чтобы  мы  могли  пользоваться  предопределенным  типом  данных, нам  необходимо  знать  пути  обозначения  этого  типа  в  компьютере  и  способы  осуществления  действий  над  ним.  Чтобы  обозначить  число  482  в  компьютере, набери  на  клавиатуре  482. Иногда  можно  представлять  значения  не  единственным  способом. В  вещественном  типе  данных  real   можно  обозначить  число  ¼    так :  0.25  или  25Е-2  или  0.00025Е3.  Тип  данных  обретает  смысловую  полноту  только  в  сочетании  с  действиями, определенными  над  ним. Арифметические  действия, определенные  над  типом  данных  integer,  выполняются  в  компьютере  с  помощью  символов  +, -, *  и  команд  mod  и  div , а  действия  сравнения  осуществляются  с  помощью  символов        =, <>, >, <, >=, <= .  Хранение  значений  в  компьютере  осуществляется  с  помощью  переменных.  Переменная  есть  имя  ячейки  памяти, в  которой  можно  хранить  значения  определенного  типа. Объявление  в  Паскале  переменной  х  типа integer  приводит  к  выделению  ячейки  памяти, способной  содержать  произвольное  значение  этого  типа, и  связывает  с  ячейкой  имя  х. Занесение  значений  в  переменную  осуществляется  с  помощью  действия  присвоения, которое  обзначается  в  Паскале  символом  := .

Способ  использования  данных, т.е.  форма  оценки  значений, через  совершение  действий  и  их  смысл  есть  интерфейс  обслуживания  данных. Он  напоминает  программный  модуль, который  включает  минимальную  информацию  требуемого  интерфейса  для  использования  модуля  и  скрывает  информацию, в  которой  нет  необходимости  для  его  задействования. Так  и  интерфейс  типа  данных  скрывает  информацию  о  способе  хранения  значений  и  пути  реализации  действий .  Знаем  ли  мы  как   хранится  целое  число  в  компьютере ?  Известно  ли  нам , как  осуществляется  действие  сложения  двух  целых  чисел ? Логично  предположить, что  мы  не  знаем  в  точности  на  уровне  битов , как  все  это  выглядит  в  компьютере. Но  чтобы  пользоваться  этим  типом  данных  у  нас  и  нет  нужды  в  этой  информации. В  стандартном  Паскале  существуют  и  другие  предопределенные  типы  данных : real - тип  вещественных  чисел, boolean - тип  логических(булевых) значений  и char - символьный  тип. 

? Тип  данных boolean  есть  представление  значений  истинности. Каковы  значения  этого  типа  данных?  Какие  действия  можно  осуществлять  над  ними?

3.2.2. Ограничения  в  представлении  значений

Представление  типа  данных  в  компьютере  связано  с  ограничениями, незнание  которых  может  привести  к  ошибкам.  Пользователь  типа  данных  integer   обязан  быть  осведомлен  о  важной  проблеме , связанной  с  реализацией  типа  в  компьютере, это  ограничения  представления (representation  limitations). Множество  целых  чисел  состоит  из  бесконечного  их  числа, но  у  компьютера  есть  возможность  представления  только  конечного  числа  элементов  этого  множества.  В  Паскале  существует  определенная  заранее  постоянная, которая  содержит  самое  большое  значение, которое  можно  выразить  с  помощью  типа  integer,  это  MAXINT.  Когда  мы  осуществляем  действия  над  целыми  числами, правильный  результат  нам  гарантирован  только  в  том  случае, если  мы  не  выходим  за  разрешенные  пределы.

? Как  с  помощью  программы  можно  выяснить, чему  равняется  значение  MAXINT ? Есть  ли  гарантия, что  это  значение  будет  тем  же  для  любого  компилятора ?  

Наибольшее  значение,  которое  можно  представить  с  помощью  типа integer, недостаточно  велико  для  определенных  применений. Если  мы  захотим  написать  программу, включающую  счетчик, значением  которого  будет  численность  населения  земного  шара  и  даже, меньше  того,   население  Государства  Израиль, нам  нужно  будет  найти  другой  способ  представления  целого  числа.  Один  из  возможных  способов  состоит  в  представлении  целого  числа  с  помощью  массива, в  котором  хранятся  его(числа)  цифры  .  Реализация  действий, определенных  над  целыми  числами  в  таком  способе  представления,  будет  совершенно  другой  по  сравнению  с  их  реализацией  над  типом  integer .

 

3.3. Пути  построения  новых  типов  данных  в  Паскале

Предопределенных  в  Паскале  типов  данных  недостаточно  для  предствления  всех  абстрактных  типов, необходимость  в  которых  возникает  по  нашему  мнению. Язык  Паскаль  обеспечивает  нас  рядом  средств, с  помощью  которых  можно  определять  новые  типы  данных.  Средства  эти  есть  тип  порядковых  данных, массив  и  запись. 

3.3.1. Порядковый  тип  данных

Значения  типа  данных  не  обязательно  являются  числовыми. Мы  уже  видели, что  в  типе  данных  слово  его  значения  есть последовательности   букв ‘a’ - ‘z’ .  Во  многих  случаях  мы  склонны  представлять  в  компьютере  наборы  нечисловых  данных  с  помощью  чисел.  Так , например, дни  недели - воскресенье, понедельник, .... , суббота(по  еврейскому  календарю) принято  обозначать  числами  1, 2, ... , 7  соответственно. Но  известно, что  во  многих  странах  понедельник  является  первым  днем  недели, поэтому  логично  выглядит  представление  дней  недели  с  помощью  их  наименований. Язык  Паскаль  дает  нам  возможность  построить  порядковый  тип (enumerated  type). Значения  этого  типа  есть  имена, устанавливаемые  программистом.  Во  время  определения  такого  типа  указываются  все  его  значения  по  порядку.  Этот  порядок  определяет  для  каждого  значения, кроме  последнего, следующее  значение  и  для  каждого  значения, кроме  первого, предыдущее  значение. Для  каждого  элемента  определяется    место, равное  его  номеру  в  списке  элементов(при  том, что  место  первого  элемента  равно  0).

Список  месяцев  еврейского  года  можно  определить  с  помощью  порядкового  типа  данных  следующим  образом :

type

  HebrewMonths = (Tishrey,Heshvan,Kislev,Tevet,Shvat,Adar,Nissan,Iyar,Sivan,Tamuz,Av,Elul);

Программа  1. Пример  использования  порядкового  типа  данных

Опишем  интерфейс  к  порядковому  типу  данных  в  Паскале. Действия  определения  предыдущего  и  последующего  значений  выполняются  с  помощью  функций  pred  и  succ.  Функция  pred(х)  возвращает  значение, предшествующее  значению  х  в  списке, а  функция  succ(x)  возвращает  следующее  за  ним  значение. Действие  определения  места  значения  выполняется  функцией   ord , которая  возвращает  число, обозначающее  место  заданного  элемента.  Например, ord(Av)  вернет  значение  10.

? Каковы  области  определения  функций   pred  и  succ ?

Программа  1  есть  простой  пример  определения  порядкового  типа  данных   и  его 

использования. Обратите  внимание  на  то, что  команда  вроде  writeln(Tishrey);  послужит  причиной  ошибки  компиляции. Для  того, чтобы  напечатать значения  этого  типа, надо  воспользоваться  процедурой  mont_display.

 

3.3.2. Типы  данных - массив  и  запись

Тип  массив  объединяет  постоянное  число  ячеек  для  запоминания  значений  определенного  типа. В  массиве  можно  осуществлять  действия  доступа  к  ячейке  для  запоминания  в  ней  значения  и  извлечения  значения  из  нее. Язык  Паскаль  обеспечивает  удобный  способ  осуществления  таких  действий : когда  мы  определяем  переменную  типа  массив, действие  доступа  к  ячейкам  выполняется  посредством  указания  имени  переменной  и  следом  за  ним  в  квадратных  скобках  номера  ячейки. К  примеру, пусть  arr  есть  переменная  типа  массив  целых  чисел  с  индексами  1..100 ; доступ  к  ячейке  24  осуществляется  так : arr[24] .  Это  обращение  к  ячейке  возможно  как  для  запоминания  в  ней  некоторого  значения (arr[24] := 5;) , так  и  для  извлечения  значения  из  ячейки (writeln(arr[24];).

? Какова  область  определения  действия  доступа  к  элементу  массива ?

Запись  позволяет  объединять  вместе  некоторое  число  ячеек  для  запоминания  значений, которые  не  обязательно  принадлежат  одному  типу, и  обращаться  к  каждой  из  них  по  имени  записи. Ячейки  запоминания  в  записи  называются  полями.  Над  записью  определено  действие  доступа  к  полю,   осуществляемое  с  помощью  имени  записи, имени  поля  и  точки  между  ними.  К  примеру, если  р  есть  запись, составленная  из  двух  полей - num  типа  real  и   let  типа  char , - то  доступ  к  полю   let   выполняется  так: p.let. И  в  записи  доступ  к  полю  может  выполняться  для  запоминания  значения  в  поле  и   извлечения  значения  из  него.

3.4. Этапы  определения  и  представления  абстрактного  типа  данных

Проследим  детально  за  способом  построения    абстрактного  типа  данных  по  имени  прямые_прямоугольники  и  его  представлением  в  компьютере и  попытаемся  понять  различные  этапы  процесса.

3.4.1. Прямые  прямоугольники

У  прямых  прямоугольников  стороны  параллельны  осям  координат.  В  противоположность  прямоугольникам  “испорченым”, у  которых   стороны  не  параллельны  осям  координат, прямые  прямоугольники  есть  консервативное  и  упорядоченное  подмножество  множества  прямоугольников.

(Рис. 3.1. Прямые  и  “испорченные”  прямоугольники)

Над  прямыми  прямоугольниками  можно  выполнять  широкое  разнообразие  операций, например,  операцию  ширины, возвращающую  ширину  прямоугольника. Подобным  же  образом  определим  операцию  длины, операции  центра, периметра, площади  и  еще  четыре  операции, возвращающие  четыре  угла  прямоугольника. Операция “разбухания”  в  с  раз  увеличивает  длину  и  ширину  прямоугольника  в  с  раз.  Опрерация  смещения  на  (dx, dy) перемещает  прямоугольник  на  dx  единиц  в  направлениии  оси  х  и  на dy единиц  в  направлениии  оси  у, а  действие  объединения  двух  прямоугольников  возвращает  наименьший  прямоугольник , включающий  два  заданных (см. рис. 3.2).

(Рис. 3.2. Действия  разбухания  и  объединения)

Прямые  прямоугольники отвечают  определению  абстрактного  типа  данных  согласно  описанию  в  начале  главы.  Совокупность  значений  этого  типа  составляют  все  существующие  прямые  прямоугольники, и  над  ними  выполняются  описанные  выше  действия. Обратите  внимание : в  определении  прямого  прямоугольника  отсутствует  какое-либо  отношение  к  его  представлению  в  компьютере,  величина  прямых  прямоугольников  может  устанавливаться  по  нашему  желанию.  Ясно , что  экран  компьютера  ограничен  по  своей величине  и  может  показывать  прямые  прямоугольники  до  определенного  размера , но  пока   мы  не  принимаем  во  внимание  эти  ограничения. К  примеру, действие  разбухания  может  раздуть  прямоугольник  в  миллион  раз  и  не  выйти  за  область  определения.  Когда  нам  понадобится  представить  в  компьютере  тип  данных  прямых  прямоугольников ? Использование  их  может  возникнуть  по  разным  поводам; например, для  представления  с  их  помощью  графического  окна  на  экране  или  некоей  фигуры  в  графической  программе.  

3.4.2. Проектирование  интерфейса  к  абстрактному  типу  данных

После  определения  абстрактного  типа  данных  необходимо  спроектировать  интерфейс. Хорошо  спроектированный  интерфейс  делает  возможным  легкое  и  удобное  пользование  типом  данных  и  увеличивает  вероятность  того, что  он  будет 

в  будущем  подключен  к  большому  числу  программ.  Мы  избрали  написание  имен  действий  в  интерфейсе  на  русском;  это  промежуточный  этап  между  описанием  операций  и  их  представлением   в  компьютере.  В  русском  интерфейсе  мы  уточняем  в  ходе  описания  назначение  каждой  операции  и  параметры, передаваемые  ей.  Этот  этап  допускает  определенную  гибкость, он  не  зависит  от  программной  среды  . В  таблице  3.1  представлен  черновик  интерфейса  типа  данных - прямых  прямоугольников.

Таблица 3.1.Черновик интерфейса типа данных - прямые прямоугольники

Каждая  операция  в  интерфейсе  принимает  в  качестве  параметра  одну  или  более  переменных  типа  прямой  прямоугольник  и  иногда  некоторые  дополнительные  параметры. Смысл  каждой  операции  раскрывается  во  второй  колонке  таблицы. 

Обратите  внимание  на  то, что  действия  периметр_прямоугольник  и  площадь_прямоугольник  можно  реализовать  с  помощью  других  операций  в  интерфейсе.  Значение, возвращаемое  действием  площадь_прямоугольник,  есть  результат  умножения  значения, возвращаемого  операцией  длина_прямоугольник, на  значение, возвращаемое  операцией  ширина_прямоугольник ; значение, возвращаемое  действием  периметр_прямоугольник,  есть  удвоенная  сумма  значений  операции  длина_прямоугольник  и  ширина_прямоугольник. Благодаря  этому  можно  было  бы  пользоваться  интерфейсом, не  содержащим  операции  периметра  и  площади, но  поскольку  они  очень  распространены, удобнее  расширить  интерфейс  и  включить в  него эти  операции.  

3.4.3. Выбор  способа  представления  значений  типа  данных

До  сих  пор  мы  совсем  не  занимались  вопросом  представления  прямоугольника  в  компьютере.  Согласно  тому , что  мы  сейчас  увидим, имеет  место  не  один  способ  представления.  Нетрудно  заметить, что  представление  с  помощью  четырех  вершин  содержит  излишнюю  информацию.  Чтобы  представить  прямой  прямоугольник  достаточно  двух  вершин:  левой  верхней  и  нижней  правой  или  правой  верхней  и  левой  нижней.  Можно  также  представлять  прямой  прямоугольник  с  помощью  его  центра, длины  и  ширины.   Последнее  представление  приводит  еще  к  четырем  способам :  одна  из  четырех  вершин, длина  и  ширина  прямоугольника.  

? Достаточны  ли  верхний  левый  угол  и  левый  нижний  угол  для  представления  прямого  прямоугольника?

Какой  из  указанных  способов  представления  предпочтительней? На  первый  взгляд

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

· Способ  представления  с  помощью  центра, длины  и  ширины (далее центр_длина_ширина) будет  представлять  прямоугольник  посредством  четырех  величин :  (center_x, center_y), length, width .   Здесь  length  есть  длина  прямоугольника  по  оси  у   и  width  его  ширина  по  оси  х. 

· Метод  представления  с  помощью  левого  верхнего  и  правого  нижнего  углов (далее способ  представления  углами) будут  представлять  прямоугольник  посредством  четырех  величин: (left_top_x, left_top_y), (right_bottom_x, right_bottom_y) .

В  способе  представления  центр_длина_ширина  операции  центр_прямоугольник,  длина_прямоугольник  и  ширина_прямоугольник  можно  осуществить  сразу, поскольку  представление  осуществляется  этими  величинами. И  эти  операции  должны  только  возвращать  нужное  значение.

Операции  левый_верхний_прямоугольник  и  правый_нижний_прямоугольник  реализуются немедленно  в  способе  представления   углами, но  не  сразу  в  способе  центр_длина_ширина.Например, операция  левый_верхний_прямоугольник  требует  достаточно  простого  вычисления  значений  х  и  у  левой  верхней  вершины :

             (left_top_x, left_top_y) = (center_x - width/2, center_y + length/2).

? Определи  значения  х  и  у  точек  левый_нижий_прямоугольник  , правый_верхний_прямоугольник и правый_нижний_прямоугольник, когда  прямоугольник  представлен  методом  центр_длина_ширина.

Если  мы  изберем  представление  углами, нам  придется  осуществлять  несколько  вычислений  для  нахождения  центра, длины  и  ширины  прямоугольника, также  достаточно  простых.

? Как  вычисляются  значения, возвращаемые  операциями  центр_прямоугольник, левый_нижний_прямоугольник, длина_прямоугольник и ширина_прямоугольник, когда  прямоугольник  представлен  методом  углов.

Обрати внимание  на  то, что  благодаря  реализации  операций  центр_прямоугольник,  длина_прямоугольник и ширина_прямоугольник  в  методе  представления  углами  можно  перейти  к  представлению  методом  центр_длина_ширина.  Реализацией операций  правый_нижний_прямоугольник  , левый_верхний_прямоугольник   в  методе  представления  центр_длина_ширина  можно  перейти  к  представлению  с  помощью  углов. И  поскольку  реализация  указанных  действий  простая, то  и  переход  между  двумя  представлениями  также  несложен.

Рассмотрим  еще три операции  и  выясним, как  они  реализуются  в  этих  двух   представлениях. сдвиг_прямоугольник(rect,dx,dy)  перемещает  прямоугольник rect  на dx  единиц  по  оси  х  и  на  dy  единиц  по  оси  у. В  представлении  посредством  углов  все , что  нам  надлежит  сделать,  это  сдвинуть  left_top_x  на  dx  единиц  и left_top_y  на  dy  единиц. Таким  же  образом  надо  изменить  значения  нижней  правой  точки - и  новый  прямоугольник  нами  установлен. А  что  происходит, если  наше  представление  есть  центр_длина_ширина?  Значения  center  изменяются  точно  также, но  length и  width  не  изменяются.

раздувание_прямоугольник(rect, c)  раздувает  прямоугольник  rect  в  с > 0  раз.  Т.е. нужно  умножить  на  с  длину  и  ширину   прямоугольника. (Обратите  внимание, что  действие  раздувания  обращается  в  сжатие, если  0 < c < 1).

? Что  происходит  в  операции  раздувания  с  точкой  центра  прямоугольника ?

Реализация действия  раздувание_прямоугольник  очень  простая, когда   прямоугольник  представляется  посредством  центр_длина_ширина. А  в  методе  представления  углами  раздувание  реализуется  не  так  уж  просто.  Ширина  исходного  прямоугольника  согласно  этого  представления

                          width = right_bottom_x - left_top_x . 

Ширина  нового  прямоугодльника  равна  с×width. Чтобы  сохранить  местоположение  центра  прямоугольника, надо  уменьшить  left_top_x   на  половину  разницы  между  новой  шириной  прямоугольника  и  его  исходной  шириной, т.е.

           left_top_x_new = left_top_x_old - (с×width - width)/2 = left_top_x_old  - (с - 1)×width/2

? Как  определяются  остальные  значения  прямоугольника  left_top_y, right_bottom_x  и  right_bottom_у ?

объединение_прямоугольники(rect1, rect2)  возвращает  наименьший  из  прямоугольников, содержащих  в  себе  два  заданных (см. рис. 3.2). Это  действие  очень  простое  для  реализации  в  методе  представления  углами. Для , к  примеру , левой  верхней  точки, формулы  выглядят  так :

left_top_x_объед = minimum(left_top_x_rect1, left_top_x_rect2)

left_top_y_объед = maximum(left_top_y_rect1, left_top_y_rect2)

Тем  же  способом  можно  найти  и  правый  нижний  угол  объединенного 

прямоугольника.  Вычисление  значений  объединенного  прямоугольника  в  методе 

представления  центр_длина_ширина  является  более  сложным.

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

3.4.4. Инициализация  абстрактного  типа  данных

В  определенном  нами  интерфейсе пока  отсутствует  важная  операция , создающая  прямоугольники. Без  нее   в  нашем  распоряжении не  будет  прямоугольников  для  других  действий  интерфейса.  Операция  эта  называется  инициализацией и  ее  необходимо  включать  в  интерфейс  любого  абстрактного  типа  данных. Обращение  к  операции  инициализации  создает  элемент   абстрактного  типа  данных.  Можно  установить, что  инициализация  типа  данных - прямых  прямоугольников  будет  возвращать  некий  прямоугольник, определенный  заранее, например, прямоугольник, правая  верхняя  вершина  которого  находится  в  точке (1, 1), а  левая  нижняя - в  точке  (0, 0). Можно  также  установить, что  действие  инициализации  будет  получать  параметры, определяющие  какой-то  прямой  прямоугольник.  Например, операция  принимает  значения  х  и  у  левого  верхнего  и  правого  нижнего  углов  инициилизируемого  прямоугольника. В  последнем  случае  действие  инициализации  ближе  к  характеру  операции  присвоения(подстановки), которая  нам  знакома, поскольку  она  способна  возвратить  инициализируемый  прямоугольник  для  любого  возможного  значения. Мы  избрали  действие  инициализации  в  таком  виде :  

инициализация_прямоугольник(left_top_x, left_top_y, right_bottom_x, right_bottom_y) .

Например,   инициализация_прямоугольник(0, 1, 2, 0) ®  rect     возвращает  прямоугольник  rect, левый  верхний  угол  которого  (0, 1), а  правый  нижний (2, 0).

? Будет  ли  необходимость  изменить  передаваемые  этой  инициализации  параметры, если  избран  способ  представления  центр_длина_ширина?

Все  операции  интерфейса, определенные  в  черновике (таблица  3.1)  получают  в  качестве  параметра  прямоугольник. Ясно, что  передаваемый  прямоугольник  должен  быть  инициализирован, чтобы  сами  действия  были  бы  определены. Это  положение  важно  добавить  к  описанию  операций  в  интерфейсе  на  русском.

3.4.5. Контроль  исправности  данных

Рассмотрим  операцию  инициализация_прямоугольник(1,0,0,1) ® rect . В этой  операции  сделана  ошибка: значения  верхнего  левого  угла  поменялись  местами  со  значениями  правого  нижнего  угла. И rect  не  есть  законное  значенние  типа данных.

Каким  условиям  должны  удовлетворять  избранные  нами  значения, чтобы  прямоугольник  получился  законным ? На  рис. 3.3  показан  прямой  прямоугольник. Из  рисунка  следует, что  должны  выполняться  два  условия :   left_top_x <  right_bottom_x  ,   right_bottom_y < left_top_y .  (Рис. 3.3. Представление  с  помощью  левой  верхней  вершины  и  правой  нижней  вершины  и  отношения  между  ними).

Чтобы  быть  уверенным  в  том, что  некий  прямоугольник  содержит  законные  данные, надо  добавить  в  интерфейс  операцию  прямоугольник_законный  , которая  получает  в  качестве  параметра  прямоугольник  и  возвращает  “истина”,

если  он  законный, а  иначе - “ложь”.  В  описание  действия  инициализации  можно 

включить  ограничение, что  сразу  за  инициализацией  нового  прямоугольника  пользователь  обязан  проверить, является  ли  созданный  прямоугольник - законным. 

Когда  принято  решение  о  представлении  значений  нового  типа  данных  и  существует  опасение  получать  неисправные  значения, следует  позаботиться  о  добавлении  операции, проверяющей   законность  определенного  значения.  В  дополнение  к  этому  следует  сопроводить  операции  в  интерфейсе  типа  данных  соответствующей  документацией; надо  оценить, когда  существует  опасение , что  операции  могут  породить  незаконное  значение, и  с  помощью  каких  средств  пользователь  может  проверить  законность  операций.  

3.4.6. Полный  интерфейс  на  русском  для  абстрактного  типа  данных

После  того, что  мы  поняли  важность  действий  инициализации  и  проверки  исправности  в  определении  типа  данных, мы  можем  написать   полный  интерфейс  на  русском  для   типа  данных - прямых  прямоугольников. В  интерфейсе  помещены  различные  операции  над  параметрами, передаваемыми  им, описания    и  допущения  по  их  поводу.  Таблица  3.2  содержит  описание  полного  интерфейса.

     Таблица 3.2.Интерфейс типа данных - прямые прямоугольники

3.4.7. Использование  вспомогательных  типов

Иногда  в  ходе  построения  одного  типа  данных  появляется  необходимость  использовать  другой  тип  данных. Если  этот  вспомогательный  тип  не  был  определен  прежде, нам  предстоит  задействовать  его  в  процессе  определения  и  реализации, чтобы  затем  мы  могли  продолжить  построение  основного  типа. Поскольку  мы  решили  представлять  прямоугольник  с  помощью  углов(вершин), воспользуемся  типом  данных  точка.  Таблица  3.3  содержит  основной  интерфейс  к  типу  данных  точка  на  русском.

          Таблица 3.3.Интерфейс типа данных - точка

Точка  представляется  с  помощью  записи, состоящей  из  двух  вещественных  полей  х  и  у, которые  есть  координаты  точки  в   декартовой  системе. 

(Программа  3.2. Библиотечный  модуль point ) Программа  3.2  представляет  из  себя  модуль point, который  реализует  абстрактный  тип  данных  точка  в  Паскале.  В  интерфейсной  части  модуля  находится  определение  типа  данных  point_type .  Также  в  этой  части  находятся   интерфейсы  подпрограмм  point_init, point_getx, point_gety, реализующие  действия, определенные  в  интерфейсе  на  русском. В  интерфейсе  также  определена  подпрограмма  point_copy , реализующая  операцию  присвоения, поскольку  в  Паскале  не  выполняется  прямо  подстановка  списков   в  форме  target := source.

Обратите  внимание, что  в   реализации  действия  инициализации  типа  данных  точка  в  качестве  параметра  передается  переменная  р  типа  point_type .  В  этой  переменной  будет  возвращено  значение  инициализируемой  точки (см. примечание 

к  следующему  параграфу).

? В  компьтерном  представлении  целых  чисел  мы  сталкиваемся  с  ограничением  - возможностью  использования  только  конечного  числа  целых  чисел. А  существует  ли  ограничение, если  мы  представляем  точку  в  компьютере  посредством  двух  вещественных  чисел ?

3.4.8. Реализация  типа  данных  в  окрестностях  среды  программирования

Напишем  библиотечный  модуль, реализующий  тип  данных  прямых  прямоугольников  с  использованием  библиотечного  модуля  point .  В  программе  3.3  находится  интерфейсная  часть  этой  библиотеки, включающая  определение  типа  rect_type  и  операций  над  ним.  Обратите  внимание  на  следующее :

· Определение    типа   rect_type    находится    в     интерфейсной     части    модуля, чтобы   пользователи  библиотеки  могли  определять  свои  переменные  этого  типа.

· Процедура rect_init , осуществляющая  абстрактную  инициализацию, получает  в  качестве  параметра  в  дополнение  к  начальным  значениям  прямоугольника  также  переменную  типа   rect_type.   Эта  переменная  будет  содержать  вновь  созданный  прямоугольник. Операция  выполнена  как  процедура, а  не  функция, поскольку  возвращаемое  значение  функции  в  Паскале  не  может  быть  списком. Подобная  проблема  возникает  во  время  реализации  еще  ряда  операций  интерфейса, возвращающих  прямоугольники  и  точки. Все  они  выполняются  в  виде  процедур , к  которым  в  качестве  параметра  передается  переменная  соответствующего  типа.

· Интерфейс  включает  процедуру  rect_display  , которая  принимает  в  качестве  параметра  прямоугольник  и  печатает  на  экране  значения(координат)  его  вершин - левой  верхней  и  правой  нижней. Понятно, что  способ  представления  значений  типа  данных  находится  в  нашем  распоряжении  и  можно , к  примеру, определить  процедуру  rect_display , которая будет  представлять  прямоугольник  на  каком-то  графическом  экране.

· Библиотечный  модуль rect  включает  функцию rect_are_equal, которую  до  сих  пор  не  обсуждали.  Эта  функция  выполняет  операцию  тождества. Проверяется, тождественны  ли  два  значения  типа  данных  один  другому, как  в  условии, которое  обозначается    знаком    ‘ = ’ .  В  типе  данных  прямые  прямоугольники  нельзя  пользоваться  знаком  равенства, поскольку  тип  этот  представляется  с  помощью  списка, а  в  Турбо  Паскале  нельзя  сравнивать  два  списка, поэтому  есть  нужда  в  определении  специальной  операции. (Программа  3.3. Интерфейс  библиотечного  модуля  rect)

3.4.9. Реализация  операций  в  среде  программирования

Приступим  к  реализации  операций, объявленных  в  интерфейсе. Программа  3.4  есть  раздел  реализации  библиотечного  модуля  rect. Реализация  включает  все  функции, описанные  в  интерфейсе,  плюс  две  дополнительные  функции  max  и  min.

(Программа  3.4. Реализация  библиотечного  модуля  rect)

3.5. Резюме

· Абстрактный  тип  данных  это  совокупность  значений  и  операций, определенных  над  ними.

· Язык  Паскаль  определяет  заранее  несколько  типов  данных , вроде  integer, real, перечисляемый  тип  данных, запись, массив. Определение  включает  способы  представления  типов  данных  и  действия  над  ними.

· Во     время     определения  и     реализации     типа     данных  необходимо  осуществить  следующие  шаги :

     · Проектирование  интерфейса  к  операциям , определяемым  над  абстрактным

        типом     данных. Хорошо  спроектированный  интерфейс  делает  возможным

        легкое  и  удобное   использование  типа  данных.

     · Написание    на  русском(иврите, английском)     интерфейса  к  типу  данных,

        который   включает  операции  и  параметры, передаваемые  им,   описание

        операций  и   допущения  по  их  поводу.

     · Выбор     способа     представления   в    определенной  среде   программирования

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

       влияют   на     характер      реализации  операций.  После  выбора  способа 

       представления   приступают     к          написанию         точного       интерфейса  к 

       типу  данных  в  среде   программирования.

     · Реализация  различных  действий  в  разделе  реализации  библиотечного 

        модуля.

· Во  время  определения  абстрактного  типа  данных  и  его  представления  необходимо  соотноситься  с  областями  определения  различных  операций.

Понятия  и  ключевые  слова

Задачи

1. В  добавление  к  знакомым  вам  предопределенным  типам  данных  в  Турбо Паскале    также  определены  следующие  типы  данных :  ·shortint           ·longint           ·byte         ·word              ·single         ·double        ·extended .  Проверьте, что  представляет  каждый  из  этих  типов , какова  область его  значений  и  какие  действия  определены  над  ним. 

2. Абстрактный  тип  данных  вещественные  числа  включает  в  качестве  значений  все  существующие  вещественные  числа.  Над  этим  типом  определены  арифметические  действия, подобные  тем, что  определены  над  целыми  числами. Представление  этого  типа  данных  в  Паскале  именуется  real.   a). Проверьте  как  задействуют  в  Паскале арифметические  действия  над  вещественными  числами  - сложение, вычитание, умножение  и  деление.        b). Каковы  способы  обозначения  значений  этого  типа  в  компьютере?       с). Можно  ли , по  твоему  мнению, представить  любое  значение  этого  типа  в  компьютере? Почему?      d). Дополнительными  действиями, определенными  над   вещественными  числами, являются  урезание  и  округление(trunc, round). Задокументируйте  эти  действия.     e). Что  произойдет, если  попытаться  скомпилировать  следующую  программу? Объясните - в  чем  основная  проблема.

program    test7;

var  a, b : real;

begin

  a := 5.5;

  b := 3.2;

  writeln(a div b);

end.

3.Тип  данных  символы  включает  в  качестве  значений  все  символы, которые  можно  представить  в  компьютере. a). Какой  тип  данных  существует  в  Паскале  для  представления  символов?     b). Как  обозначают  символы  в  компьютере?

Например, если  мы  захотим  поместить  в  переменную  с  символ  *(звездочка), то  как  это  сделать?   с). Какие  действия  определены  над  символьным  типом  данных? Определены  ли  в  нем  порядковые  отношения?      d). В  каждом  ли  компьютере  будет  вывод   yes ?  Объсни, на  каком  допущении  базируется  твой  ответ.

If  succ(‘A’) = ‘B’  then  writeln(‘yes’)

                            else  writeln(‘no’);

4.Рассмотрите  программу, в  которой  используется  тип  данных  real :

program  real_check;

var  x, y, z : real;

begin

  y := 10;

  x := 9.9;

  z := y/x*x;

  if (y = z) then writeln(y, ‘  equal  ‘ , z)

                else writeln(y, ‘  not  equal  ‘, z);

end. 

а). Каким  будет  вывод  программы  по  вашей  оценке ?      b). Прогоните  эту  программу. Получился  ли  предсказанный  вывод?  Почему ?

5. В  реализации  типа  данных  rect_type  используется  тип  point_type.  Библиотечный  модуль  point, определяющий  этот  тип,  реализован  частично. Мы  намерены  добавить  в  модуль  ряд  операций : 

· Отражение  точки  относительно  оси  х - операция  принимает  точку  Р  и  возвращает  точку, которая  является  отражением  Р  относительно  оси  х.

· Отражение  точки  относительно  оси  у - операция  принимает  точку  Р  и  возвращает  точку, которая  является  отражением   Р  относительно  оси  у.

· Перемещение  точки   - операция  принимает  точку  , а  также  два  дополнительных  параметра  dx и dy   и  возвращает  точку  с  новыми  координатами.

· Расстояние  между  двумя  точками - операция  принимает  две  точки  и  возвращает  расстояние  между  ними.

· Середина - операция  принимает  две  точки  и  возвращает  точку, которая  находится  в  точности  посредине  между  заданными  точками.

а. Добавьте  эти  новые  действия  в  интерфейс  библиотечного  модуля  point . Имя  каждой  операции  должно  начинаться  с point_...  .  Не  забывайте  описать  область  определения  операции.  b. Реализуйте  эти  операции.  с. Напишите  программу, проверяющую  этот  модуль.

6. Различные  операции, определенные  над  типом  данных  прямые  прямоугольники, можно  реализовывать  посредством  того  же   представления, но  иными  способами. 

а). Напишите  иную  реализацию  операции rect_center  (в  рамках  представления  прямоугольника  в  модуле rect).     b).  Связано  ли  это  изменение  с  изменением  в  интерфейсе?  Нужно  ли  теперь  изменять  программы, выполненные  с  использованием  этого  модуля ?

7. Уже  говорилось, что  можно  представлять  в  компьютере  целое  неотрицательное  число  также  с  помощью  массива, содержащего  цифры  этого  числа. Например, число  1234315003142999  представляется  так :

a).Какое  наибольшее  число  можно  представить  с  помощью  массива  из  16  ячеек ?

Можно  ли  изменить  способ  представления  так, чтобы   работать  и  с  отрицательными  числами? Как  выглядит  число  0  в  таком  представлении ?      

b). Напишите  интерфейс  к  библиотечному  модулю, определяющему  тип  данных  неотрицательные  большие  целые  числа  и  действия  инициализации, сложения, умножения, тождества  и  печати  таких  чисел.   Указание : Действие  инициализации  большого  неотрицательного  целого  числа   может  принимать  как  параметр  строку 

символов(string).  Операция  читает   из  строки  символы  один  за  другим, переводит 

цифру, представленную  символом,  в  число  и  заносит  его  на  соответствующее  место  в  массиве.   с). Реализуйте  этот  библиотечный  модуль.    d). Напишите  программу  проверки  модуля.

8.Таблица  “крестики-нолики”  это  абстрактный  тип  данных, значения  которого  есть    все  игровые  таблицы  размером  3*3, а   каждая  ячейка  может  быть  пустой,

содержать  крестик  или  нолик.   В  заданной  таблице  можно  добавить  крестик  или  нолик  в  пустую  ячейку  или  сделать  ее  пустой. В  дополнение  к  этому  необходимо  устанавливать получилась  ли  таблица_победы_крестиков  или  таблица_победы_ноликов, если  есть  в  ней  строка  или  столбец  или  диагональ  крестиков  или  ноликов. a).Напишите  словесный  интерфейс  к  типу  данных  таблица  крестики-нолики. b).Представьте  тип  данных  таблица  крестики-нолики в  среде  программирования.   с).Определите  интерфейс  к  данным  крестики-нолики  в  среде  программирования.  d).Реализуйте  библиотечный  модуль, задокументируйте  его  и  напишите  проверочную  программу. е).Какие  потребуются  изменения  в  интерфейсе  и  реализации, чтобы  расширить  игровые  таблицы  крестиков-ноликов  до   10*10.

9. Значениями  типа  данных  рациональные  числа  являются  все  числа, которые  можно  представить  в  виде  отношения  двух  целых  чисел. К  примеру, 0.25  есть  рациональное  число, т.к.  его  можно  записать  в  виде   1/4 .  Любое  целое  число  также  является  рациональным  , поскольку , к  примеру, 45  можно  записать  в  виде  45/1. Над  рациональными  числами  определены  действия  сложения, вычитания,

умножения  и  деления. a). Предположим, что  решили  представлять  в  компьютере  рациональное  число  посредством  пары  целых  чисел - делимого  и  делителя. Сколько  есть  способов  для  записи  этим  способом  любого  рационального  числа ? (Намек : К  примеру  число  1/3  можно  записать  и  в  виде  2/6, а  число  4  можно  записать  в  виде  8/2).                  b). Определите  операцию, которая  принимает  два  различных  представления  рациональных  чисел, и  проверяет, являются  ли  эти  числа  равными.   с). Существует  ли  в  этом  методе  представление  незаконного  значения ?  d). Как  будут  реализованы  в  этом  представлении  операции  сложения, умножения, деления  и  вычитания  рациональных  чисел ?

10. Определим  полином  так: Полином  есть  функция  

 P(x) = a_nxⁿ + a_n-1x^n-1 + ...+ a₁x + a₀,   где  х  называется  аргументом(переменной)  полинома,  а  элементы a_n , a_n-1  ,  ... , a₁ , a₀   - вещественные  числа - называются  множителями  полинома.    Например,

4x⁵ - 5.5x² + 7x + 3  и   -9.23x⁷ - 3x⁴  + 10x³ + 2x² - 17.9   это  полиномы.

Умножение  на  скаляр  s : s×P(x) = s×a_nxⁿ + s×a_n-1x^n-1 + ...+ s×a₁x + s×a₀ .

Сложение.  Чтобы  сложить  два  полинома, складывают  множители  при  одинаковых  степенях  аргумента. Например,  если  Р(х) = 5х² - 6х + 5  и

Q(x) = 6.5x⁵ - 50x⁴ - 10.5x² + 6x+ 12, то  Р(х) + Q(x) = 6.5x⁵ - 50x⁴ - 5.5x² + 17.

Вычитание. Чтобы  вычесть  один  полином  из  другого, выполняют  вычитание  над  множителями  при  одинаковых  степенях  аргумента подобно  действию  сложения.

Степень. Степень  полинома  Р  определяется  как  наибольшее  целое  число n,  для  которого  а_n  отлично  от  нуля  в  Р.  Например, степень  полинома                                         Q(x) = 6.5x⁵ - 50x⁴ - 10.5x² + 6x + 12  равна  5, степень  полинома  Р(х) = 5х² - 6х + 5  есть  2, а  степень  полинома  R(х) = 4.5  есть  0 .  Результатом  операции  степень  является  неотрицательное  целое  число.

Вычисление  полинома  Р  от  переменной(аргумента)  х. Можно  подставить  вместо  х  вещественное  число  и  так  вычислить  значение  полинома  Р  в  точке  х.  К  примеру , значение  Р(х) = 5х² - 6х + 5  в  точке  2  равно   5×2² - 6×2 + 5 = 13.  Результатом  этого  действия  является  вещественное  число.

a). Напишите  словесный  интерфейс  к  типу  данных  полином).        b). Представьте  этот  тип  данных  в  среде  программирования. Каковы  ограничения  метода  представления, который  вы  избрали ?   с). Определите  интерфейс  в  среде  программирования  к  типу  данных  полином.  d). Реализуйте  библиотечный  модуль, задокументируйте  его  и  напишите  проверочную  программу.

 

Глава  4. Стек

“Твои  обязанности  очень  простые”,- объяснил  старшина  бравому

солдату  Швейку(Израиль). -“Все   что    тебе  надлежит  сделать  это 

освободить  кнопку   от   записок,  которые  на  ней”.         “Огромное

 спасибо, господин  старшина”,- ответил  Швейк .    - “Вот  я  сейчас 

освобождаю  кнопку  и   топаю  домой”.   “Остановись!!!,- заревел  старшина. -“Еще  один  шаг  и  ты  отправишься   прямо  в  карцер. Заруби  себе  на  носу  не  делать  ничего  до  тех  пор,  пока  я  не  закончу  говорить, ясно?!  А  теперь  обрати  внимание : каждая  из  записок, которые  я  подколол  к  кнопке,  содержит  задание, которое  ты  должен  выполнить. Когда  ты  снимаешь  записку, то  немедленно  приступаешь  к  исполнению  задания, изложенному  в  ней. Только  после  выполнения  задания  ты  вправе  снять  следующую  записку. Понял?  Очень  хорошо!  Теперь  за  работу!”

Возможно,  наш  рассказ  демонстрирует  систему  отношений  между  старшиной  и  Швейком, но  не  это  является  причиной  появления  рассказа  здесь. В  нем  описывается  также  система , смысл  которой  очень  близок  нашим  интересам: система, которую  старшина  спроектировал, чтобы  его  контора  функционировала  исправно. В  этой  системе  есть  несколько  составляющих: задания  к  исполнению, кнопка, записки  и  Швейк.  На  нашем  языке : кнопка  это  средство, избранное  старшиной  для  хранения  данных,  на  ней  хранятся  детали  информации - задания, которые  надо  выполнить.  Старшина  даже  обеспечил  Швейка  алгоритмом  его  работы :

Рабочий_день

(1)До  тех  пор,  пока  кнопка  не  пустая :

(1.1) Сними  задание  с  кнопки;

(1.2) Выполни  задание;

(2) Иди  домой.

Швейк  снял  первую  записку  с  кнопки . В  ней  было  написано:  Помыть пол.

Швейк  энергично  приступил  к  выполнению  задания.  Примерно  через  час  он  огляделся  и  с  удовлетворением  подумал, что  выполнил  свое  первое  задание  наилучшим  образом. Без  колебаний  снял  следующую  записку  с  кнопки. Там  было  написано :  Подмести.

Швейк  послушно  выполнил  это  задание  несмотря  на  лужи, стоявшие  на  его  пути. По  завершении  второго  задания  он  снял  последнюю  записку. Там  было  написано : Выбрось окурки и мусор из пепельниц и мусорных корзин.

Швейк  аккуратно  выполнил  и  это  задание  наиболее  эффективным  образом. “Вместо  того, чтобы  идти  с  каждой  пепельницей  или  корзиной  в  конец  двора”,- подумал  он,    -“притащу-ка  я  мусорный  ящик  со  двора  сюда, опорожню  в  него  все, что  нужно, и  верну  на  место”. И  сделал  так.

После  того, как  мусорный  ящик  был  возвращен  на  свое  место, Швейк  вернулся  в  контору. К  своему  удивлению  он  обнаружил  там  старшину  с  багровой  физиономией  и  ощетинившимися  усами. “Солдат, ты  намерен  смеяться  надо  мной?”

“Но, старшина, я  сделал  все  так, как  вы  сказали. И  по  моему  мнению, очень  прилежно, уважаемый  старшина.”

“Все  как  я  сказал? Все  как  я  сказал? Утром  была  у  меня  контора, а  сейчас - болота  Хулы, река  Аялон!”.

“Извините, старшина  , но  вы  написали - помыть, и  я  помыл. Написали 

подмести - подмел. И  вы  видите  своими  глазами:  все  пепельницы в  конторе - пустые.”

“Что  это  значит? Сперва  помыл, потом  подмел, а  затем  опорожнил  мусорные  корзины? Солдат! Твои  мозги  работают  наоборот?”

Прервем  в  этот  момент  спор  между  Швейком  и  старшиной, до  того  как  Швейк  отправится  в  карцер, и  попытаемся  понять, что  произошло. Старшина  хотел, чтобы  Швейк  опророжнил  мусорные  корзины  и  пепельницы, подмел  и  помыл  пол. Он  написал  три  задания  на  записках  и  приколол  к   кнопке  в  указанном  порядке. Та  записка , которую  старшина  подколол  последней, оказалась  первой  для  Швейка, и  потому  Швейк  выполнял  задания  в  обратном  порядке. Проблема  заключается  в  особом  характере  структуры, которую  избрал  старшина : всегда  есть  единственная  записка, к  которой  есть  доступ, та, что  находится  сверху, и  поэтому  записка, введенная  последней, выводится  первой.

За  секунду  до  того,  как  старшина  окончательно  вышел  из  себя,  Швейку  на  счастье  в  контору   вошла  офицер  Мири .  Железным  правилом  старшины  было  отдавать   беседе  с  Мири  главное  предпочтение. “Исчезни  с  глаз  моих!”, - заорал  он  на   Швейка  и  начал  рассказывать  Мири  о  своих  несчастьях  с  этим  солдатом.  “Ты  видишь, он  все  делает  наоборот! Я  оставил  ему  на  кнопке  эти  записки, а  он  вместо  того, чтобы  опорожнить  сначала  все  мусорные  корзины, начал  с  мытья  полов”. “Но  ведь  записка  “Опорожнить  мусорные  корзины”  находилась  снизу . Чтобы  добраться  до  нее, надо  было  снять  две  другие  записки”,- заметила  Мири.  “Большое  дело!”,- ответил  старшина, - “ Надо  было  только  переменить  порядок  записок!” Но  стало  заметно, что  замечание  Мири  смутило  его.

Мири  попыталась  выручить  старшину: “Ты  не  мог  полагаться  на  то, что простой  солдат  проникнется  всей  глубиной  замысла  старшины. Я  думаю, что  самое  простое  было  бы  заранее  ввести  записки  в  обратном  порядке”.

“О  чем  это  говорит, госпожа  Мири? В  армии  нет  обратного  порядка. Завтра  утром  я  возвращаю  кнопку  назад  в  интенданство”.  

Мири, лучшим  другом   которой  был  главный  интендант  Миро, забеспокоилась. Именно  завтра  Миро  намеревался  прибыть  на  базу  с  опозданием.  Она  принялась  искать  убедительные  предлоги, почему  не  надо  возвращать  кнопку  в  интенданство, как  вдруг  в  контору  вошли  три  новых  на  базе  солдата  -Оз(отвага), Он(сила), Цур(кремень). При  виде   новобранцев    на  лице  старшины  стали  обнаруживаться  признаки  нервозности. “Солдаты! Что  вы  тут  вообще  делаете?  Контора  старшины  это  ваш  салон?  Забор  управления   уже  побелен ?”

“Но, командир”, - пожаловался  Он, -“у  меня  есть  освобождение”. 

“Командир, я  пришел  только  выписать  вещевой  мешок”,- сказал  Оз.

“Мой  старшина, я  пришел  выяснить  время  работы  армейской  лавки”,- дополнил  Цур.

“Ну  вы  трое, - один  другого  стоите”,- умилился  старшина., но  тотчас  изменил  интонацию,- “Я  немедленно  записываю  вас  в  наряд  охраны. Ну  и  что  вы  стоите  здесь  как  три  ханукальные  свечи?  Летите  отсюда  и  немедленно!”

Мири , которая внимательно  прислушивалась  к  беседе  старшины  и  его  новых  солдат, пришла  в  голову  блестящая  идея. “Эту  кнопку  еще  можно  использовать”,- попытала  она  счастья.- “Ее  можно  использовать  для 

управления  списком  охраны  базы. Ведь  когда  нужен  кто-нибудь  в  охрану,

всегда  ищут  самого  молодого    солдата”.

«Чего  тебе  надо?”,- испугался  старшина.- “Ты  ведь  прошла  офицерский  курс! Только  что  мы  видели, что  подобная  кнопка  извлекает  данные  наоборот. Ты  хочешь  послать  командира  базы  или  меня  в  охрану? Через  двадцать  лет  в  армии  не  ходят  пешком! ”

Мири  поняла, что  судьба  кнопки (и  ее  приятеля  Миро)  зависит  от  ее  быстрого  и  убедительного  ответа. “Ясно, что  кнопка  извлекает  данные  наоборот, но  именно  здесь    обратный  порядок  подходит. Всякий  раз,  когда  новобранец  приходит  на  базу , подкалываем  его  имя  на  кнопку. Когда  кто-нибудь  нужен  в  охрану, достаем  верхнее  имя  с  кнопки, а  что  есть  там?”,- пыталась  Мири  вовлечь  старшину  в  ход  своих  рассуждений.

“Ну, конечно”,- сказал  старшина,-“там  есть  записка  с  именем  того, кто  может  охранять”.  “Очень  верно”,- поддержала  Мири  его  слова,- “Но  не  просто  кто-то, а  самый  молодой  солдат  на  базе, который  еще  не  был  в  охране!”. Стало  заметно, что  старшина  начал  понимать  величие  кнопки. Чтобы  окончательно  убедить  его,  Мири  добавила: “И  есть  еще  одно  преимущество . Если  тебе  захочется  наказать  солдата, просто  добавь  записку  с  его  именем  на  верхушку  кнопки. Он  станет  первым  в  охране  в  следующий  раз”.

Впервые  за  длительное  время   улыбнулся  старшина . “Молодец, Мири”,- сказал  он. -“Завтра  утром  пойду  к  Миро  и  скажу  ему , чтобы  устроил  тебе  в  комнату  новый  кондиционер”.

4.1. Абстрактный  тип  данных - стек

Кнопка, которой  пользовался  старшина, есть  в  действительности  реализация  абстрактного  типа  данных  стек(stack). Этот  тип  данных  на  иврите  получил  имя  “махсанит”, из-за  его  сходства  с  оружейной  обоймой, магазином, у  которого  есть  единственный  вход, через  который  осуществляется  операция  ввода(заряжения)  пуль  и  их  извлечение.  Стек  это  тип  данных , хранящий  элементы  определенного  типа. Для  того, чтобы  стало  возможным  добавлять  элементы  в  стек  и   извлекать  их  оттуда, определим  операции  занеси_в_стек  и  извлеки_из_стека. Связь  между  этими  операциями  есть  назначение  типа: если  в  стек  занесен  элемент  и  немедленно  за  этим  осуществляется  извлечение   данного, то  выполняются  два  условия :  а). Извлеченный  элемент  будет  тем  же  элементом, что  мы  занесли.     б). Состояние   стека   после    извлечения    будет  тождественным  его    состоянию  до  занесения.

Можно  видеть  в  стеке  закрытый  ящик  с  одним  входом, через  который  выполняются  действия  занесения  и  извлечения. Обслуживание  элементов  через  единственный  вход  порождает  положение, при  котором  элемент, который  вошел  последним  выходит  первым.  Такой  доступ  к  элементам  называется  LIFO - по  первым  буквам  слов    LAST  IN  FIRST  OUT. Действие  извлечения  не  определено, когда  стек  пуст, подобно  действию  деления  целых  чисел, которое  не  определено, когда  делитель  равен  нулю. Если  так, то  нам  следует  определить  операцию  стек_пустой?, возвращающую  ‘ИСТИНА’ , если  он  пустой, иначе - ‘ЛОЖЬ’ . Этим  ействием  мы  будем  пользоваться  перед  выполнением  операции  извлечения, когда  есть  опасение, что  стек  пустой.  Важной  для  работы  со  стеком  является  операция  инициализация_стек, возвращающая  пустой  стек. 

И  какие  еще  нужны  операции?  Иногда  хочется  заглянуть  на  вершину  стека, чтобы  узнать  значение  элемента, находящегося  там, без  выполнения  извлечения, которое  изменяет  содержимое  стека. Для  этого  определим  операцию  загляни_в_стек. И  действие  заглядывания  определено  только  для  непустого  стека. Подчеркнем, что  в  противоположность  другим  операциям  действие  заглядывания  может  быть  реализовано  посредством  остальных  описанных  нами

операций.

? Как  будет  реализована  операция  загляни_в_стек  с  помощью  остальных  действий  из  интерфейса?

Таблица  4.1  представляет  интерфейс  к  типу  данных  стек.

                  Таблица 4.1. Интерфейс к типу данных стек

4.2. Применения  типа  данных  стек

4.2.1. Операция  опс!

В  программистской  компании, где  работает  Мошик, решили  разработать  графический  редактор, позволяющий  рисовать  картинки  с  помощью  компьютера. После  нескольких  месяцев  проектирования  была  готова  толстенная  книга  и  в  ней  спецификация  модуля  интерфейса  пользователя.  Спецификация  включала  определения  состояния  экрана  в  любом  положении, задействованном  программой, окна, меню  и  т.д. Построение  модуля  было  поручено  Мошику.

Мошик  взял  книгу  домой, расположился  на  балконе  и  стал  размышлять  как  реализовать  все  операции. Часть  из  них  выглядели  достаточно  простыми.  Такие, например, как  находящиеся в  спецификации  разнообразные  возможности  рисования  и  стирания  картинок.  Чтобы  реализовать  эти  операции, достаточно  задействовать  соответствующую  подпрограмму, определенную  в  интерфейсе  одного  из  других  модулей  системы  программирования. У  Мошика  зародилось  ощущение, что  ему  предстоит  нетрудная  и  скучная  работа, но  вот  он  добрался  до  параграфа, в  котором  обсуждались  команды  редактирования. Первая  операция  в  этом  параграфе  называлась  опс! :

“Операция  опс!  отменяет  последнюю  исполненную  операцию(кроме  самой  опс!). Пользователь  может  повторять  и  задействовать  эту  операцию  без  ограничения  вплоть  до  отмены  первой исполненной  операции .”

“Не  проблема  отменить  одну  операцию!”,- подумал   Мошик. -“Если  последней  операцией  было  нарисуй_многоугольник, то  всего  навсего  надо  выполнить  сотри_многоугольник. Но  как  я  буду  знать, какой  была  операция  перед  последней?  И  ту, которая  была  перед  предпоследней?”  

Через  несколько  минут  размышлений  Мошик  понял, что  операция  опс!  обязательно скрывает дополнительные  проблемы. Например, пусть  пользователь  осуществил  последовательность  операций :

 1.  нарисуй_линию

 2.  нарисуй_точку

 3.  нарисуй_линию

 4.  опс!

5. нарисуй_ многоугольник

6.опс!

7.опс!

Опс!  в  6  отменяет  рисование  многоугольника  в  5, но  опс!  в  7  имеет  ввиду  изображение  точки  в  2, поскольку  опс!  в  4  уже  отменил  изображение  линии  в  3.    Мошик  начал  отчаиваться ...

Операция  опс!  не  так  уж  сложна, чтобы  отчаяние  Мошика  было  оправданным. Что  в  конце  концов  нужно  сделать  для  реализации  этой  операции :

·Необходимо  сохранять  описание, которое  будет  включать  всю  информацию , требуемую  для  отмены  любой  осуществленной  операции.

·Описания  операций  необходимо  хранить  так, чтобы  к  ним  можно  было  обращаться  в  порядке ,обратном  порядку  их  исполнения, т.е. по  методу  вошел  последним  , выходит  первым.

Искомое  решение - в  использовании  стека. Всякий  раз, когда  исполняется  какая-либо  операция(кроме  самой  опс!), в  стек  заносится  ее  описание  и  ее  параметры.  Когда  пользователь  захочет  отменить  операцию, она  извлекается  из  вершины  стека  и  выполняется  операция  по  ее  отмене. Алгоритм  4.1   отвечает  за  выполнение  операций , вводимых  пользователем. Рис. 4.1  описывает  согласно  порядку  действий течение  алгоритма, вызвавшего затруднения  у  Мошика.

алгоритм_Мошика

{ Алгоритм , ответственный  за  ввод  операций  от  пользователя  и  их  осуществление. S  это  стек, содержащий  описания  операций, заданных  пользователем; х  и  у  это  переменные, содержащие  описание  действий 

и  их  параметры}

(1) инициализация_стек ® S .

(2) до  тех  пор, пока  пользователь  осуществляет  операции :

(2.1) прочти  операцию  х.

(2.2) если  х  не  есть  опс!, выполни :

        (2.2.1) занеси_в_стек(S,x).

              (2.2.2) выполни  операцию  х .

(2.3) иначе { действие  х  есть  опс!}  выполни :

(2.3.1) если  стек_пустой?(S),

          выдай  пользователю  сообщение, что  в  пямяти  нет  операций.

(2.3.2) иначе { S  не  пустой}  выполни:

(2.3.2.1)извлеки_из_стека(S) ® y .

     (2.3.2.2) выполни  операцию  отмены  у.

             Алгоритм 4.1. Алгоритм Мошика

Рис.4.1. Состояния  экрана  и  стека  на  каждом  этапе  работы  алгоритма  Мошика - в  порядке  действия  операций

4.2.2. Контроль  исправности  скобок  в  арифметических  выражениях

Определим  исправное  по  части  скобок  арифметическое  выражение : оно  может  включать  разного  рода   скобки, их  число  не  ограничено, но  они  должны  быть  сбалансированы. Баланс  скобок  состоит  в  том , что  число  открытых  скобок  должно  в  точности  равняться  числу   закрытых, а  кроме  того  каждой  открытой  скобке  должна  быть  найдена  соответствующая  закрытая  того  же  типа  и  в  соответствующем  месте. Например, следующие  выражения  исправные :

((a))

(b + a - 2*7)

{+32*(37*)/[5 + 1]} - 4

(Обратите  внимание, последнее  выражение  исправно  по  части  скобок, но  как  арифметическое  выражение  оно  не  исправно).  А  эти  выражения  не  исправны :

a + ((c

([3 + a) + 4]

[)(5 - 3]*[2 - 3]

Если  выражение  содержит  скобки  только  одного  типа, мы  можем  проверить  их  баланс  наиболее  просто  с  помощью  подсчета  открытий  и  закрытий.  Начинаем  со  счетчиком , равным  нулю. Когда  натыкаемся  на  открытие , добавляем  к  нему  1, а 

когда  на  закрытие, то  уменьшаем  счетчик  на  1.  

? Каким  условиям  должен  отвечать  счетчик, чтобы  мы  могли  сказать, что  выражение   исправно   по  части   скобок.

А  если   в  выражении  используются  скобки  различного  типа, можем  ли  мы  решить  проблему  подобным  образом, используя  несколько  счетчиков  по  числу  видов  скобок?  Т.е.  можем  ли  мы  сделать  верный  вывод, если  будем  всякий  раз, натыкаясь  на  открытие  или  закрытие  определенного  вида  скобок, добавлять  в  соответствующий  счетчик  1  или  вычитать  из  него  1 ?

? Правильно  ли  будет  проверена  с  помощью  трех  счетчиков  исправность,  по  части  скобок,  выражения  ({a} + b)*[a +(b + c])  ?

Когда  в  выражении  используются  разные  типы  скобок, недостаточно  их  подсчитывать, нужно  также  знать  порядок  их  появления. Следует  найти  средство, которое  позволит  сохранять  и  сами  скобки  и  порядок  их  появления.  Проблема  эта  похожа  на  задачу  опс!, которой  мы  прежде  занимались.  И  там  было  нужно  сохранять  операции  и  порядок  их  появления. Теперь  же  воспользумся  стеком, содержащим  скобки. Просканируем  выражение  слева  направо. Поскольку  мы  проверяем  исправность  выражения   только  относительно  скобок, проигнорируем  все  символы, которые  не  являются  скобками .  Во  время  прочесывания  выражения  будем  заносить  в  стек  все  открывающие  скобки  до  того  момента, когда  встретим  первую  закрывающую  скобку. Какой  элемент  находится  на  этом  этапе  на  вершине  стека?  Поскольку  мы  заносили  в  стек  только  открывающие  скобки, на  вершине  находится  теперь  последняя  открывающая  скобка, на  которую  мы  наткнулись. Проверим, соответствует  ли  она  по  по  типу  текущей  закрывающей  скобке. Если - да , то  подвыражение  между  открывающей  и  закрывающей  скобками  исправно, и  в  нем  нет  других  скобок.  Извлечем  из  стека  открывающую  скобку  и  продолжим  проверку  выражения. А  если  закрывающая  скобка  не  принадлежит  типу  открывающей, то, ясно, что  выражение  неисправное.  Продолжим  проверку  тем  же  образом; каждая  открывающая  скобка будет  заноситься  в  стек, и  каждая  закрывающая  скобка  приводит  к  попытке  извлечения  из  стека  открывающей  скобки. Открывающая  скобка, которую  мы  должны  занести  в  стек, есть  на  самом  деле  последняя  еще  не  использованная  и  не  соответствующая  никакой  закрывающей  скобке. Если  открывающая  скобка, которую  мы  извлекли  из  стека  и  закрывающая  из  ввода    соответствуют  друг  другу, то  все  подвыражение , заключенное  между  ними, исправно.  Если  же  они  не  соответствуют  друг  другу, все  выроажение  неисправно  и  сканирование  прекращается. Попытка  извлечь  открывающую  скобку  из  пустого  стека     также  указывает  на  то, что       выражение  не  исправное, поскольку  существует  больше  закрывающих  скобок, чем  открывающих.

На  каждом  этапе  подвыражение, находящееся  между  открывающей  скобкой, извлеченной  из  стека,  и  соответственной  закрывающей, по  части  скобок - исправно. Мы  начали  сканирование  с  пустым  стеком. Если  мы  пришли  к  концу  выражения без  обнаружения  несоответствия  и  с  пустым  стеком, то  все  выражение  исправно  по  части  скобок .  Рис.4.2  представляет  процесс  проверки, задействованный  нами  над  примером  ({a} + b)*[a + (b + c]),  мы  сканируем  выражение  в  поисках  различных  скобок  и  не  обращаем  внимание  на  другие  символы.  Рис.4.2. Проверка  исправности  скобок 

Алгоритм  4.2  проверяет  исправность  арифметического  выражения  по  части  скобок  по  методу, описанному  выше. Действие  алгоритма  может  завершаться  в  одном  из  трех  случаев :

· Если  на  определенном  этапе  проверяемые  закрывающая   и  открывающая  скобки  не  соответствуют  друг  другу, выражение  неисправно. 

· Если  пришли  к  закрывающей  скобке, а  стек  пуст, то  выражение  неисправно.

· Когда  пришли  к  концу  выражения  и  если  стек  не  опорожнен, это  знак  того, что  не  хватает  закрывающей  скобки  соответственной  открывающей, и  выражение  неисправно; если  же  стек  пуст, то  выражение  исправно.

проверь_исправность_скобок

{ Алгоритм  возвращает  ‘Истина’ , если  вводимое  выражение  исправно  по  части  скобок, иначе -  ‘Ложь’. S  это  стек, содержащий  символы; ch  и  old_ch  это  символы }

(1) инициализация_стек ® S .

(2) Переход  к  вводу. До  тех  пор, пока  не  достигнут  его  конец, исполняй :

(2.1) прочти  символ ch .

(2.2) если ch  есть  открывающая  скобка, то  занеси_в_стек(S,ch).

      (2.3)  если ch  - закрывающая  скобка,  выполни :

(2.3.1) если  стек_пустой?(S), верни  ‘Ложь’.

 (2.3.2) иначе { S  не  пустой}  выполни:

(2.3.2.1)извлеки_из_стека(S) ® old_ch.

     (2.3.2.2) если old_ch  не  соответствует  ch, верни  ‘Ложь’.

{ конец  выражения }

(3) Если  не  стек_пустой?(S), верни  ‘Ложь’.

(4) Иначе -  верни  ‘Истина’.

  Алгоритм 4.2.Проверка исправности скобок арифметического выражения 

4.3. Представление  типа  данных  стек

Мы  определили  интерфейс  к  типу  данных  стек  и  решали  с  его  помощью  две  задачи  на  уровне  алгоритмов.  Обратите  внимание  на  то, что  решение  этих  задач  не  требовало заранее  решения  о способе  представления  стека  в  компьютере. Чтобы  реализовать  алгоритмы, описанные  в  предыдущих  параграфах, следует  принять  решение  о  способе  его  представления.  Можно  представлять  стек  посредством  массива  элементов, в  который  будут  помещены  элементы  стека.  Переменная  top  типа  integer  будет  включать  номер  ячейки, в  которой  находится  вершинный  элемент  стека.  Когда  стек  пуст, значение  top  равняется  нулю. Во  время  занесения  элемента  в  стек  значение  top  увеличивается  на  единицу,  и  в  ячейке  с  этим  номером  помещается  новый  элемент.  Когда  мы  захотим  извлечь  элемент  из  стека, то  прочтем  элемент из  ячейки  top,  возвратим  этот  элемент  и  уменьшим  значение  top на  единицу.

Рис.4.3  демонстрирует, как   реализуются  основные  действия  в  стеке  символов  описанным  способом.  На  шаге  а  массив  инициализируется  с  помощью  обнуления  переменной top. На  шаге  b  введен  в  стек  символ  ’!’ . Он  введен  в  первую  ячейку  массива, а  значение top  изменяется , становится  равным  1.  На  шаге  с  подобным  же  образом  введен  символ  'א' . Извлечение  из  стека  на  шагах   d  и  е  (выведение  символов  'א'  и  ’!’  соответственно)  сопровождается  всякий  раз  уменьшением   top  на  1.  Проверка  на  этапе  f  возвещает, что  стек  пуст, т.е.  значение  top  равно  нулю.                                   Рис. 4.3. Реализация  стека  с  помощью  массива

? Почему  нет  нужды  обнулять  ячейки  массива  во  время  осуществления  извлечения  или  инициализации  стека?

При  выборе  определенного  способа   представления  возникают  ограничения, которых нет  в  абстрактном  типе  данных. Стек  в  принципиальном  определении  не  ограничен  каким-либо  размером  и  в  него  можно  заносить  любое  число  элементов.  А  когда  мы  представляем  стек  с  помощью  массива,  размер  стека  ограничен  размером  массива. В  связи  с  этим  ограничением  возможно  возникновение  ошибки  во  время  попытки   занести  элемент  в  заполненный  стек. Ошибка  эта  называется  переполнение(overflow).

Чтобы  предотвратить  переполнение, надо  добавить  в  интерфейс  типа  данных  операцию, возвращающую  ‘Истина’, если  стек  заполнен, а  иначе - ‘Ложь’. Когда  мы  передаем  пользователою  библиотечный  модуль, реализующий  стек, необходимо  сообщить  ему  об  этом  ограничении  и  дать  оценку  максимального  числа  элементов, которое  стек  может  содержать.

4.4. Реализация  в  среде  программирования  Турбо  Паскаля

Перейдем  в  Паскаль  и  напишем  библиотечный  модуль, реализующий  тип  данных  стек.  Для  того, чтобы  подчеркнуть  общий  характер  примера, мы  не  указали  тип  данных  элементов , сохраняемых  в  стеке, не  написали  мы  и  размер  массива, который  осуществляет  стек.  Обратите  внимание  на  то, что  операции  stack_pop  и   stack_top   сделаны  в  виде  процедур, а  не  функций, поскольку  язык  Паскаль  ограничивает  возможные  типы  , которые  функции  могут  возвращать, он  не  позволяет   возвращаемому  значений  иметь  сложный  тип(вроде  списка).

Программа  4.1. Библиотечный  модуль  stack(раздел  интерфейса)

Программа  4.2. Библиотечный  модуль  stack(раздел  реализации)

 

4.5. Резюме

· Стек  это  абстрактный  тип  данных, у  которого  действие  занесения  элементов  в  него  и  действие  извлечения  элементов  из  него  определено  так, что  извлекаемый  из  стека  элемент  является  последним  из  занесенных  в  него. Такой  доступ  к  элементам  называется  LIFO - по  первым  буквам  слов    LAST  IN  FIRST  OUT.

· Стек  естественно  применять  при  решении  задач, в  которых  необходимо  возвращать  данные   в  порядке  обратном  их  вводу.

· Возможно  представлять  стек  посредством  массива  и  указателя  на  вершину  стека, но  следует  помнить, что  такое  представление  ограничивает  размер  стека.

Понятия  и  ключевые  слова (согласно  еврейского  алфавита)

Задачи

1. Опиши  содержимое  стеков  s1 и s2   после  следующих  последовательностей операций :

                                                        а.

stack_init(s2);

stack_init(s1);

stack_push(s1, ‘א’);

stack_push(s1, ‘ב’);

stack_push(s2, ‘ג’);

stack_push(s2, ‘ד’);

сh := stack_pop(s1);

stack_push(s2, ch);

ch := stack_pop(s2);

stack_push(s1, ‘ה’);

                                                       b.

инициализация_стек ® s1.

занесение_в_стек(s1, 7).

занесение_в_стек(s1,9).

инициализация_стек ® s2.

извлечение_из_стека(s1) ® i.

занесение_в_стек(s2, i).

занесение_в_стек(s1, 6).

извлечение_из_стека(s2) ® i.

извлечение_из_стека(s1) ® i.

занесение_в_стек(s1, 8).

                                                     с.

stack_init(s1);

stack_init(s2);

stack_push(s1, ‘x’);

stack_push(s2, ‘y’);

stack_push(s1, ‘z’);

stack_push(s2, ‘a’);

stack_init(s1);

stack_push(s1, ‘x’);

stack_push(s2, ‘b’);

 

2. Следующий  алгоритм  оперирует  над  строками  символов:

(1) инициализация_стек ® stk .

(2) прочти  символ ® ch .

(3) пока  (ch = 'א' ), исполняй :

(3.1) занесение_в_стек(stk, ch).

(3.2) прочти  символ ® ch .

 

 

(4) пока  (ch = 'ב' )  и  не  стек_пустой?(stk)  и  не  конец  ввода, исполняй :

(4.1) извлечение_из_стека(stk) ® ch.

(4.2) прочти  символ ® ch .

(5) если  достигнут  конец  ввода  и  также  стек_пустой?(stk)  возврати  ‘годится’

(6) иначе -   возврати  ‘не  годится’ .

Опиши, что  характерно  для  строк, о  которых  алгоритм  извещает  ‘годится’ .

3. а. Установите  исправность  по  части  скобок  следующих  арифметических  выражений :

  i.   {(a + b)   + c}*[2*{5 - a}]         

 ii.  q - (r - (s + 2))*q)   

 c.  [a +]]*[b -{a*3}] + (a - (i)          

 iv.  {1 +(a*4)} -((2 +(3 - [5 + b]))/2)

b. Проследите  за  прогоном  алгоритма  проверь_исправность_скобок  , который  приведен  в  этой  книге , для  каждого  примера  из  а.  Покажите  состояние  стека  на  каждом  шаге. Охарактеризуйте  проблему  для  каждого  неисправного  примера.

4.  Дано  выражение  {a + (b*c - d*[e + f])/g}. Оно  вводится  в  алгоритм , контролирующий  исправность  скобок. На  каком-то  этапе  работы  алгоритма  состояние  стека  таково :

В  какой  из  следующих  проверок  может  быть  получено  это  состояние  стека? 

a). После  ввода  части  выражения  {a + (b*c   .           

b). После  ввода  части  выражения  {a + (b*c - d*[e   .   

c). Такое  состояние  стека  не  может  быть  получено.   

d). После  ввода  части  выражения  {a + (b*c - d*[e + f]  .

5. а). Напишите  алгоритм  по  имени  элемент_в_глубине_стека(st, k),  который  возвращает  элемент  находящийся  “на  глубине”   k  в  стеке  символов  st .  Операция  не  изменяет  окончательное  состояние  стека.  К  примеру, пусть  стек  выглядит  так :

Тогда  элемент_в_глубине_стека(st, 4)  возвратит  символ  ‘$’ . Если  в  стеке  меньше  k  элементов, то  дожен  быть  возвращен  пустой  символ  ‘’ . Можно  использовать  вспомогательный  стек.       

b). В  11  классе  школы  “Большие  надежды”   вспыхнул  спор  относительно  предыдущего  вопроса : Гиди  утверждал, что  операция  элемент_в_глубине_стека  самая  используемая, поэтому  стоит  добавить  ее  в  интерфейс  стека. Напротив  Шира  утверждала, что  это  действие  не  “естественно”  для  типа  данных  стек, предпочтительнее  воздерживаться  от  ее  использования. Кто, по  твоему  мнению, прав?  Аргументируй.

6. Даны  два  стека st1 и  st2, элементами  которого  являются  целые  числа.  Стек st2  пустой, а  st1  содержит  неизвестное  число  элементов. Дан  фрагмент  программы :

while  not  stack_empty(st1)  do

begin

  stack_pop(st1, x);

  if  not  stack_empty(st1)  then   

  begin 

    stack_pop(st1, y);  

    stack_push(st2,y);  

  end

  else      stack_push(st2, x);

  stack_push(st2, x);

end;

 

while  not  stack_empty(st2)  do 

begin 

  stack_pop(st2, x);  

  write(x);  

end;

а). В  предположении, что  стек st1  содержит  следующие  элементы

напишите , каким  будет  вывод   в  результате  прогона  этого  фрагмента.

b). Кратко  опишите, что  делает  этот  отрезок  программы.

7. а). Напишите  алгоритм, который  вводит  строку  символов - по  одному  символу  на  каждом  шагу - и  устанавливает , имеет  ли  строка  форму  xZyZx, где : 

· x  это  непустая  строка  неизвестной  длины, в  которую  могут  входить  символы  А,  В  и С. 

· у  это  строка, которая  включает  те  же  символы , что  и  х, но  в  обратном  порядке.  

· Z  это  символ  Z. 

Например, строками  вида  xZyZx  являются  AZAZA   и   AACBZBCAAZAACB , а  строка  AZBZA  не  обладает  этой  формой.

Воспользуйтесь  двумя  вспомогательными  стеками.

b). Реализуйте  алгоритм  в  среде  программирования. Полагайте, что  строка  ввода  всегда  завершается  на   eoln . (?)

8. а) Напишите  алгоритм  условная_инверсия  , который  вводит  от  пользователя  последовательность  символов. Алгоритм  печатает  символы  в  порядке  ввода  до  появления  символа  ’@’.  Этот  символ  не  печатается, но  приводит  к  инверсии  порядка  печати  символов  между  ним  и  следующим  ’@’. (Обратите  внимание : последовательность  символов  не  может  завешаться  внутри  отрезка, выводимого  наоборот).

К  примеру, для  двух  вводов  @ven@@im  re@nd    и   ne@m  rev@ind  получится  вывод  never mind .

А  для  se@tp@emb@re@  so@gn@   вывод  будет  sptember  song . 

b). Напишите  программу  cond_inv, реализующую   алгоритм  условная_инверсия .

 

                                  Глава  5. Эффективность

Существует  больше  одного  способа  расколоть  орех. Можно  положить  его  на  пол  и  топнуть  по  нему  ногой,  можно  расколоть  его  зубами  или  прибегнуть  к  помощи  второго  ореха  и  сильного  друга, можно, понятно, воспользоваться  щипцами  для  колки  орехов.  Каждым  из  способов  мы  достигаем  своей  цели - расколотого  ореха.  С  точки  зрения  результата  все  способы  правильные.  Способы  отличаются  друг  от  друга  по  требуемым  усилиям  для  выполнения  задания, по  продолжительности  времени, которое  требуется  способу, по  средствам, которые  должны  находится  в  нашем  распоряжении (щипцы, крепкий  товарищ ...)  и  по  цене  осуществления (лечение  зубов  или  новая  обувь - в  крайних  случаях). Мы  предпочтем  тот  способ, который  будет  для  нас  наиболее  эффективным.

И  в  компьютерных  науках  мы  хотим, чтбы  алгоритмы, которые  мы  готовим, и  программы, которые  мы  создаем, были  бы  эффективными. Когда  оценивают  эффективность  алгоритмов  и  программ, принимают  во  внимание  два  критерия : время  и  место.  Время  это  время  вычислений, т.е. продолжительность  времени , в  течение  которого  работает  программа, а  второй  критерий (место) связан  с  размером  памяти  компьютера, которое  надлежит  выделить  для  исполнения  программы. Критерий  времени  и  критерий  места  называаются  комплексными  показателями(complexity measures). Проблемы, возникающие  при  оценке  алгоритмов  по  двум  этим  критериям, очень  похожи, и  исследования  показателя  места  посвящаются  предметам  очень  похожим  на  те, что  нужны  для  показателя  времени. Мы  сосредоточимся  на  определении  показателя  времени.

Сегодня   очень  распространены  компьютеры, которые  выполняют  миллионы  операций  в  секунду, а  с  годами  мощности  компьютеров  возрастают. Каждое  новое  поколение  компьютеров  работает  значительно  быстрее  предыдущего  поколения? Зададим  вопрос, нужно  ли  в  таком  случае  считаться  со  скоростью  прогона  алгоритмов?  Почему  нужно  обсуждать  этот  вопрос  в  связи  с  программами, которым  потребуется  два  миллиона  операций  или  только  один  миллион?  Ведь  в  любом   случае  время  работы  программы  составит  доли  секунды.

Такой  подход  ошибочен  в  своей  основе. Когда  мы  хотим  найти  книжку  в  компьютеризированном  библиотечном  каталоге  или  получить  номер  телефона  некоего  абонента  в  справочном  ‘144’(‘09’), мы  не  желаем  ждать  ответа  больше  нескольких  секунд. Поскольку  речь  идет  об  огромных  наборах  данных, очень  важно  использовать  эффективные  алгоритмы  поиска. В  системе  прогноза  погоды, например, скорость  важна  еще  больше, ведь  чего  будет  стоить  прогноз  на  завтра, если  его  получат  только  послезавтра? В  таких  системах  требуются  эффективные  алгоритмы  обработки  огромных  массивов  данных  и  выполнения  сложных  и  многочисленных  вычислений.  И  в  системах  управления  полетом, наведения  ракет, управления  промышленными  предприятиями  и  даже  в  компьютерных  играх время  есть  решающий  фактор. Эти  системы  обязаны  реагировать  на внешние  сигналы, вроде  нажатия  клавиш, в  реальном  времени, т.е.  почти немедленно. Иначе  можно  прийти  к  отрицательным  и  даже  смертельным  результатам.

     5.1.“Неприемлемые”  задачи

Существуют  задачи, решение  которых  может  продолжаться  даже  на  самых  быстрых  современных  компьютерах(и  даже  на  компьютерах  обозримого  будущего)  неприемлемо  долго. Рассмотрим  в  качестве  примера  такую  задачу : 

Вследствие  беспрецендентного  уменьшения  числа  туристов, посещающих  город  Симамон, решил  его  мэр  господин  Эго  продвинуть  туристические  предприятия  города. Для  этого  он  задумал  автобусный  маршрут, который  проходил  бы  по  основным  туристическим  местам  города. Он  пригласил  в  свой  офис  руководителя  автобусной  компании, объяснил, что  нужно, и  снабдил  приготовленной  им  картой  города, на  которой  отметил  важнейшие

места, дороги, которые  их  соединяют, и  протяженность  этих  дорог. Руководитель  автобусной  компании  собрал  группу  проектирования  и  поставил  перед  ними  такую  задачу : “Найти  самый  короткий  маршрут,

отходящий  от  городских  ворот  и  там  же  завершающийся. Маршрут должен  пройти  около  каждой   достопримечательности  только  один  раз”.

Рис. 5.1. Карта  города  Симамон(числа  отмечают  расстояния  в  км; протяженность  дорог  не  представлена  в  едином  масштабе).

? Попытайся  найти  алгоритмический  метод  решения  задачи  для  любого  заданного  списка  мест  и  расстояний.

Одно  из  решений  этой  задачи  заключается  в  нахождении  всех  возможных  маршрутов, которые  начинаются  и  завершаются  у  городских  ворот  и  проходят  у  каждой  достопримечательности  только  один  раз, в  вычислении  их  протяженности  и  определении  наикратчайшего  из  маршрутов. Задача  эта  выглядит  простой, ведь  число  возможных  маршрутов  на  карте  города  Симамон  на  первый  взгляд  невелико. Если  написать  компьютерную  программу для  решения  этой  задачи, мы  увидим, что  время  ее  работы, когда на вводе данная  карта, будет   небольшим.

А  сколько  существует  подобных  маршрутов? Первая  точка  любого  маршрута  установлена, это - городские  ворота. Для  выбора  второй  точки  есть  у  нас  пять  различных  возможностей, поскольку  городские  ворота  соединены  со  всеми  объектами  города. После  того, как  мы  выбрали  вторую  точку,  у  нас  остается  только  четыре  возможности  для  выбора  третьей  точки  и  так  далее. Подчеркнем, что  у  нас  есть  максимум  x  возможностей, а  в  действительности  вариантов  может  быть  меньше, т.к.  есть  места, не  связанные  между  собой  напрямую.  Например, если  вторая  избранная  точка  есть  оперный  театр, то  нам  не  дано  избрать  статую  мэра  в  качестве  третьей  точки.

Итак, максимально  возможное  число  маршрутов  5×4×3×2×1 = 120.

А  что  произойдет, если  мы  обобщим  алгоритм  на  n  объектов?  Число  возможных  маршрутов  будет  не  более  (n - 1)! .  Предположим, что  в  нашем  распоряжении  компьютер, способный  вычислять  миллион  маршрутов  в  секунду. Для  города  с  11  объектами  нам  потребуется  примерно  4  секунды  на  все  возможные  маршруты  и  нахождение  решения. Это  приемлемое  время. Но  если  перейдем  к  карте  ненамного  большей  с  15  объектами, наш  компьютер  должен  проработать  целый  день, чтобы  найти  решение. А  для  обычного  города  туризма, в  котором  20  объектов, нашему  компьютеру  потребуется  примерно  3857  лет  для  нахождения  решения ... Такое  положение  явно  неэффективно : мы  располагаем  алгоритмом  нахождения  решения, но  продолжительность  поиска - неприемлема. 

Таблица  5.1  представляет  количество  возможных  маршрутов  для  разного  числа  объектов  и  требуемые  времена  поиска.

Таблица 5.1. Число маршрутов и время, необходимое для их вычисления

Эта  задача  именуется  “задачей  комивояжера”  по  имени  безвестного  комивояжера, который  пытался  найти  кратчайший  маршрут  посещения  клиентов. Существует  ли  другой  алгоритм  решения  задачи  комивояжера, требующий  меньше  машинного  времени? Задача  эта  является  центральной  в  компьютерных  науках, и  пока  не  найдено  алгоритма, решающего  ее  в  приемлемое  время.  Задача  комивояжера  не  единственная  в  своем  роде.  Существует  огромный  набор  подобных  задач, большинство  из  которых  используются  в  экономике  и  промышленности, например, 

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

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

Мы  видели, что  есть  зададачи, которые  можно  решать  на  компьютере  с  помощью  простых, но  неэффективных  алгоритмов. Время  работы  программ  в  таких  случаях  оказывается  неприемлемо  продолжительным   даже  для  относительно  небольших  исходных  данных.  Ясный  вывод: когда  мы  намерены  использовать  некий  алгоритм  для  решения  какой-либо  задачи, нам  необходимо  проверить  его  эффективность  и  удостовериться, что  можно  решить  задачу  с  его  помощью  в  приемлемое  время. Ес ли  это  не  так, желательно  найти  более  эффенктивный  алгоритм. Иногда  найти  такой  алгоритм  не  просто(как  в  задаче  комивояжера), но  во  многих  случаях  это  возможно.

5.2. Как  измеряют  эффективность? 

Если  бы  вам  предоставили  два  различных  алгоритма  для  решения  определенной  задачи  и  надо  было  решать, какой  из  них  более  эффективный, удовлетворились  ли  бы  вы  следующим  ответом? Алгоритмы  реализованы  на  компьютере  и  измерены  времена  их  прогона.  Результаты: алгоритм  А - решение  задачи  продолжалось  1.25 сек ; алгоритм  В - решение  задачи  продолжалось  0.34 сек . Заключение: алгоритм  В  эффективнее .  Нельзя  решить  какой  из  алгоритмов  эффективнее, поскольку  не  даны  многие  детали.  Например, измерялось  ли  время  работы  двух  программ  на  одном  компьютере  или  на  разных? Ведь  существуют  разные  компьютеры, процессоры  которых  обладают  разной  скоростью. И  вообще, разве  только  продолжительность  времени  интересует  нас? Мы  должны  оценивать  собственно  алгоритм  без  привязки  к  компьютеру, на  котором  его  прогнали.

Продолжительность  прогона  алгоритма  зависит  от  “количества  работы”, которое  ему  нужно  выполнить, а  оно  зависит  от  длины  ввода, над  которым  действует  алгоритм. Алгоритм, суммирующий  элементы  массива, работает   меньше  времени  с 

массивом  из  10  ячеек,  чем  с  массивом  из  100  ячеек. Для  каждой  задачи  надо  определить  соответствующую  ей  длину  ввода. Для  алгоритма  суммирования  элементов  массива  этот  параметр  есть  размер  массива. Если  мы  хотим  искать  слово  в  тексте, то  длина  ввода  может  быть  числом  букв  или  слов  в  нем. В  алгоритме  умножения    длина  ввода  есть  количество  цифр  в  перемножаемых  числах. После  того, как  мы  определили  длину  ввода, соответствующую  задаче, мы  можем  заняться  эффективностью  алгоритмического  решения  в  зависимости  от  ее  величины. Делается  это  путем  подсчета  операций, которые  выполняет  алгоритм  над  данными  различного  размера.

В  каждом  алгоритме  можно  найти  операцию  или  несколько  операций, используемых  вместе, основное  действие, к  которому  возвращается  алгоритм  в  ходе  исполнения. Продолжительность  исполнения  основного  действия  не  зависит  от  длины  ввода, т.е.  это  временная  постоянная. Например, алгоритм  суммирования  элементов  массива  повторяет  несколько  раз  действие  “добавь  значение  следующего  элемента  массива  к  накапливаемой  сумме”. Алгоритм, проверяющий  является  ли  число  х  простым, будет  повторять  действие “проверь, является  ли  у  делителем  х”. Алгоритм  умножения  двух  чисел  выполняет  два  вида  основных  действий: умножение  двух  цифр  и  сложение  двух  цифр. А  вот  операция  “проверь, находится  ли  элемент  х  в  массиве  А”  не  является  основным  действием, поскольку  продолжительность  ее  исполнения  зависит  от  длины  ввода - размера  массива.

Количество  повторений  алгоритмом  основного  действия  в  ходе  прогона  зависит  от  длины  ввода  и  используется  как  хорошая  мера  эффективности. Обратим  внимание  на  то, что  эта  мера  не  зависит  от  типа  компьютера, но  позволяет  легко 

оценить  сколько  времени  продлится  прогон  алгоритма  на  данном  компьютере. Для 

того оценим  продолжительность  исполнения  основного  действия  на  нашем  компьютере  и  помножим  ее  на  число  основных  действий, которое  выполняется  для  соответствующей  длины  ввода.

5.3. Улучшение  эффективности  алгоритма  на  постоянный  множитель

Исследуем, например, такую  задачу: дан  на  вводе  ивритский  текст и  нам  надлежит проверить, находится  ли  в  нем (хотя  бы  одна) буква   'ד'. Предположим, что  текст  находится  в  компьютерной  памяти  и  что  возможен  прямой  доступ  к  каждой  из  букв  текста. Задачу  можно  решить  с  помощью  алгоритма  5.1.

Найти_'ד'

{ Алгоритм  извещает, найдена  ли  в  тексте  буква     'ד'. }

(1) Прочти  первую  букву  текста.

(2) Пока  не  пришли  к  концу  текста  и  также  текущая  буква  не   'ד', выпоняй :

(2.1) Прочти  следующую  букву  текста.

 

(3)Если  пришли  к    концу  текста, то  сообщи  “нет  в  тексте   'ד'”, иначе   

     сообщи   “есть  в  тексте   'ד'” .

             Алгоритм 5.1. Нахождение в тексте буквы   'ד'

Алгоритм  по  порядку  в  цикле  просматривает  буквы  текста  и  всякий  раз  делает  две  проверки: а)дошли ли  до  конца  текста; b)является  ли  текущая  буква  буквой 'ד'. Положительный  ответ  на  одно  из  двух  условий - а)  или  b) - приведет  алгоритм  к  прекращению  исполнения  цикла. Если  цикл  прекращен  из-за  выполнения  условия b) , надо  сообщить , что  буква  'ד'  найдена; если  же  цикл  завершен  по  условию  а) , то  надо  сообщить , что  буква  'ד'  не  найдена.   Основное  действие, которое  повторяется  алгоритмом, включает  три  операции : чтение  следующей  буквы  текста  и  выполнение  проверок  а)  и  b). Длина  ввода  в  нашей  задаче  есть  количество  символов  в  тексте. Если  так, то  каково  число  основных  действий, которое  должен  выполнить  алгоритм  для  ввода  длиной  n  символов? Ясно, что  ответ  зависит  от  конкретного  текста. В  самом  плохом  случае, когда  'ד'  оказзалась  последней  буквой  текста  или  вовсе  не  найдена, число  основных  действий  будет  n. Подведем  итог : для  ввода  длиной  n  алгоритм  выплнит  основное  действие  не  более  n  раз.  Если  предположить, что  продолжительность  основного  действия  равна  c₁, то  время  исполнения  главного  цикла  будет c₁×n. Операции  (1)  и  (3), выполняемые  алгоритмом  до  и  после  главного  цикла, длятся  некоторое  постоянное  время, которое  мы  обозначим d₁. Поэтому  время  исполнения  всего  алгоритма  c₁×n + d₁.

Можно  ли  улучшить(сократить)  достигнутое  выше  время исполнения  программы? При  внимательном  рассмотрении  алгоритма  5.1  видим, что  в  каждом  повторении  тела  цикла  проверяется  достижение  конца  текста. Можно  сэкономить  на  этой  проверке. Добавим  букву  'ד'  в  конец  текста. Теперь  ясно,  что  выполнение  цикла  всегда  будет  прекращено  по  условию b), поскольку  существует  хотя  бы  одна  буква  'ד'  перед  концом  текста. Поэтому  можно  отменить  проверку  достижения  конца  текста  внутри  цикла. Улучшенный  алгоритм  сперва  будет  вводить  'ד'  в  конец  текста  и  не  будет  содержать  проверку  первого  условия. А  когда  выполнение  цикла  нового  алгоритма  завершится, мы  проверим  достижение  конца  текста. Положительный  ответ  означает, что  мы  нашли  добавленную  букву  'ד'  и  ее  нет  в  исходном  тексте.  Иначе - мы  нашли  'ד'  в  тексте. Алгоритм  5.2  представляет  улучшенную  версию.

Найти_'ד'_усовершенствовано

{ Алгоритм  извещает, найдена  ли  в  тексте  буква     'ד'. }

(1) Добавь   'ד' в  конец  текста.

(2) Прочти  первую  букву  текста.

(3) Пока  текущая  буква  не   'ד', выпоняй :

(3.1) Прочти  следующую  букву  текста.

(4) Если  пришли  к  концу  текста, то  сообщи  “нет  в  тексте   'ד'”, иначе   

     сообщи   “есть  в  тексте   'ד'” .

(5) Убери   'ד' в  конце  текста.

      Алгоритм 5.2. Нахождение в тексте буквы   'ד', улучшенная версия

Основное  действие  усовершенствованного  алгоритма  включает  теперь  только  две  операции: чтение  следующей  буквы  текста  и  проверку  b). Число  основных  действий  в  нем  над  текстом  длиной  n  остается  прежним - не  более n. И  подобно  алгоритму  5.1  время  прогона  алгоритма  5.2  равно c₂×n + d₂, где  c₂ есть  время  исполнения  основного(улучшенного)  действия, а  d₂  есть  постоянная, описывающая  суммарную  продолжительность  исполнения  операций  (1), (2), (4) и (5).

Улучшение   нашего  алгоритма  связано  с  экономией  на  одной  проверке  во  время  выполнения  каждого  основного  действия, т.е.  постоянная c₂  меньше  постоянной c₁.  Предположим, что  каждая  операция, выполняемая  в  цикле, требует  одинаковое  время, тогда  величина  c₁ равняется  3  единицам  времени, поскольку  основное  действие  первого  алгоритма  включает  три  операции. А величина  c₂  равна  двум 

единицам  времени(мы  сэкономили  одну  операцию  внутри  цикла). Если  так, то  можно  предположить, что  с  помощью  усовершенствования  на  треть  уменьшается  время  работы  программы.   Но  немного  и  прибавится: мы  уменьшили  коэффициент  при  n , но  d₂  больше d₁. Предположим, что  d₁  равняется  двум  единицам  времени (выполняются  две  операции: одна - перед  циклом, друая - после  него), а  d₂  равна 

четырем  единицам  времени(добавлены  две  операции: запись  'ד'  в  конец  текста  и  удаление  ее). Величина  этих  двух  коэффициентов  не  зависит  от  длины  ввода. И  действительно  для  коротких  текстов  эффективность  улучшенного  алгоритма  не  так  значительна  по  сравнению  с  простым  алгоритмом  из-за  роста  d₂; но  с  увеличением  длины  текста  вклад d₁  и  d₂  уменьшается,  и  отношение  времен  прогона  приближается  к  ожидаемому  значению  1.5 . Таблица  5.2  содержит  времена  прогона  двух  алгоритмов, она  показывает, что  для  любой  длины  ввода  больше  2  символов  улучшенный  алгоритм  быстрее. Когда  ясно, что  ввод, которым  мы  занимаемся, достаточно  велик, нет  нужды  считаться  с  постоянными  типа  d  при  оценке  времени  прогона.

          Таблица 5.2. Сравнение времен прогона алгоритмов 5.1 и 5.2

Подобное  улучшение  эффективности  алгоритма  именуется  усовершенствованием  на  постоянный  множитель (improvement  by  factor), т.к. отношение  времен  прогона  двух  алгоритмов  при  большой  длине  ввода  близко  к  постоянной. (Таблица  5.2  показывает, что  с  увеличением  ввода  отношение  между  временами  прогона  приближаетсяя  к  1.5).

Итак  мы  рассмотрели  пример, в  котором при  помощи  детального  анализа  основного  действия  и  уменьшения  числа  составляющих  его  операций было  достигнуто  улучшение эффективности  алгоритма   на  постоянный  множитель.

5.4. Случаи  хорошие, плохие  и  средние

Обратите  внимание  на  то, что  при  подсчете  числа  основных  действий  алгоритма  мы  принимали  в  расчет  самый  плохой  вариант, при  котором  буква  'ד' или  вовсе  отсутствовала  в  тексте  или  была  самой  последней, и  мы  должны  были  просмотреть  весь  текст, чтобы  найти  ее. А  что  произойдет, если   'ד'  окажется  первой?  Тогда  мы  выполним  только  одно  основное  действие. А  во  всех  остальных  случаях  выполняется  от  одного  до   n  основных  действий.

Мы    избрали    для    подсчета    времени    прогона    такие    данные   ввода, которые 

соответствуют  определению  наихудший  случай (worst  case). А  почему  не  подсчитать  время  прогона  алгоритма  согласно  среднему  случаю (average  case)? Ведь  алгоритм  отработает  для  большинства  вводов  длиной  n  меньше  наихудшего  времени!  Для  этого  есть  две  причины.

Во-первых, если  мы  будем  знать  время  прогона  для  среднего  случая, возможно  ли  оценить  время  прогона  для  случая  конкретного? Т.е. можно  ли  сказать  будет  ли  оно  больше  или  меньше  среднего  времени. Нечто  подобное  имеем  с  измерениями  роста  учеников  некоего  класса. Если  нам  известно, что  средний  рост  равен  1.65 м, разве  мы  сможем  что-нибудь  сказать  о  росте  Дани  из  этого  класса. А  вот  если  мы  знаем, что  самый  высокий  ученик  класса  возвышается  на  1.80 м, то  можем  уверенно  сказать, что  рост  Дани  не  больше  1.80 м.  Аналогично - при  вычислении  времени  прогона. Когда  число  операций  определено  для  наихудшего  случая, а  работать  будет  алгоритм  с  произвольным  вводом  длиной  n  , то  число  операций, которое  он  исполнит, никогда  не  превысит  вычисленного  значения.

Во-вторых, чтобы  узнать  время  прогона  алгоритма  в  среднем  случае, надо  найти  среднее  время  для  всех  возможных  текстов  длиной  n. Такое  вычисление  времени  куда  труднее, чем  определение  времени  для  самого  плохого  случая.

Есть  смысл  в  вычислении  времени  и  для  наихудшего  случая  и  для  среднего  случая, но  по  изложенным  выше  причинам  мы  ограничимся  в  анализе  эффективности, в  основном, наихудшим  случаем.

? Можно  определить  время  прогона  и  для  наилучшего  случая. Будет  ли  оно  хорошей  мерой  эффективности  алгоритма?

Количество  исполнений  алгоритмом  основного  действия  в  ходе  прогона  для  наихудшего  случая  есть  функция  длины  ввода. Оно  называется  функцией  времени  прогона  алгоритма  и  является  мерой  его  эффективности.

     5.5.Улучшение  на  порядок  величины

Вернемся  к  примеру  алгоритма  поиска   'ד'. Два  алгоритма(простой  и  улучшенный) реализуют, в  сущности, одну  алгоритмическую  идею. Основная  идея  заключается  в  просмотре  всего  текста  и  в  сравнении  символов  текста  с  искомой  буквой; этот  подход  именуется  линейным(последовательным) поиском (linear  search). И  улучшенный  алгоритм  действует  точно  так  же, просто  в  нем  снято  одно  сравнение  при  каждом  повторении  цикла(благодаря  добавлению   'ד'  в  конец  текста). Так  достигнуто  повышение  эффективности  алгоритма  на  постоянный  множитель. Такое  усовершенствование  действительно  важно, но - мы  скоро  это увидим - иногда  иной  подход, иная  алгоритмическая  идея  могут  привести  к  более  значительному  усовершенствованию. Нам  предстоит  проанализировать  задачу  поиска  в  телефонной  книжке - массиве, каждая  ячейка  которой  включает  список, состоящий  из  двух  полей - имени  и  номера  телефона. Чтобы  найти  номер  телефона  некоего  абонента, надо  проверить,  находится  ли  его  имя  в  массиве, и  если  находится, то  где. Для  простоты  положим, что  все  имена  в  массиве  отличаются  одно  от  другого. Задача  эта  по  сути  своей  подобна  задаче  поиска   'ד'  и  решать  ее  можно  подобным  образом.

Предположим, что  массив  упорядочен   по  полю  имени    в   лексографическом (словарном) порядке, т.е. по  именам  по  алфавиту. В  этом  случае  нет  нужды  продолжать  поиск  до  конца  массива. Можно  прекращать  поиск  при  достижении  имени, которое  с  точки  зрения  словарного  порядка  больше  искомого  имени.

? А  почему  можно  прекращать  поиск  в  описанной  ситуации?

? чем  буде  отличаться  алгоритм  линейного  поиска  в  упорядоченном  массиве  от  алгоритма  поиска  'ד', изложенного  в  этой  главе?

? Есть  ли  изменения  в  анализе  времени  прогона  для  наихудшего  случая  в  связи  с  тем, что  массив  упорядочен?

Тот  факт, что  массив  упорядочен, можно  использовать  эффективнее  посредством  новой  алгоритмической  идеи. Если  размер  массива  равен  тысяче  ячеек, начнем  поиск  в  ячейке  номер  500, и  тогда  перед  нами  три  возможности: а).имя  находится 

в  этой  ячейке - поиск  завершен;  б).имя, которое  находится  в  этой  ячейке, лексографически  больше  имени, которое  мы  ищем, и  теперь  мы  знаем, что  нет  смысла  искать  во  второй  половине  массива, а  нужно  искать  требуемое  имя  только  в  области  ячеек  от  1  до  499;   в). имя, которое  находится  в  этой  ячейке, лексографически  меньше  имени, которое  мы  ищем, и  теперь  мы  продолжим  поиск   в  ячейках  от  501  до  1000. 

Предположим, что  выполняется  условие  б. Теперь, когда   нам  нужно  искать  только  в  первой  части  массива, перейдем  подобным  образом  к  ячейке  250  и  снова  окажемся  перед  тремя  описанными  возможностями. Алгоритм  будет  прерван, когда  найдется  искомая  ячейка  или  когда  нельзя  будет  разделить  очередную  область  поиска. Ясно, что  в  последнем  случае  искомое  имя  отсутствует  в  массиве.

Новая  алгоритмическая  идея  позволяет  нам  “отрезать”  половину  области  поиска  на  каждом  его  этапе. Этот  алгоритм  называется  бинарным  поиском(binary  search). Рисунок  5.2 описывает  бинарный  поиск  числа  29  в  упорядоченном  массиве  из  16  элементов. Рамочки  отмечают  область  поиска  на  каждом  этапе, а  стрелки  указывают  на  “срединную”  ячейку  в  этой  области.

Рис. 5.2. Бинарный  поиск  числа  29  в  упорядоченном  массиве

Проанализируем  эффективность  двух  алгоритмов  поиска. В  обоих  случаях  основное  действие  включает  решение  о  продолжении  поиска  и  определении  номера  следующей  проверяемой  ячейки. Основное  действие  последовательного (линейного)  поиска  включает  такие  операции :   а).проверка - не  включает  ли  текущая  ячейка  искомое  имя  или  лексографическое  значение  имени  больше  искомого  имени;     б).проверка- не  находится  ли  текущая  ячейка  в  конце  массива;  в).если  ответ  на  проверки  а)  и  б)  отрицательный, следует  перейти  к  следующей 

ячейке  массива.

Основное  действие  бинарного  поиска  включает  такие  операции : а).проверка - не  включает  ли  текущая  ячейка  искомое  имя ;     б).проверка- не  сократился  ли  размер  области  поиска  до  1(невозможно  продолжить  деление  области);  в).если  ответ  на  проверки  а)  и  б)  отрицательный, следует  вычислить  номер  срединной  ячейки  области  и  перейти  к  ней. Вычислим  число  основных  действий, осуществляемых  в  ходе  бинарного  поиска  элемента  в  массиве  из  1000  элементов. Как  было  сказано, на  каждом  этапе  мы  делим  массив  всякий  раз  пополам, поэтому  размеры  фрагментов  массива, в  которых  осуществляется  поиск, могут  быть  такими : 1000, 500, 250, 125, 63, 32, 16, 8, 4, 2, 1.  В  самом  плохом  случае  мы  завершим  поиск  через  10  шагов(такой  будет  область  поиска  отдельной  ячейки  по  величине), и  мы  сможем  сообщить, находится  или  нет  нужное  имя  в  массиве. Такое  положение, конечно, предпочтительнее  1000  шагов, выполняемых  в  наихудшем  случае  линейным  поиском.

Таблица  5.3  суммирует  рассмотренное  усовершенствование. Она  дает  зависимость  числа  основных  шагов  от  различных  по  длине  вводов. Как  можно  убедиться, теперь  улучшение  куда  более  значительное: отношение  между  числом  шагов, осуществляемых  двумя  алгоритмами, увеличивается  с  ростом  размера  ввода.

    Таблица 5.3. Количество шагов поиска линейным и бинарным методами

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

больше  по  сравнению  с  продолжительностью  шага  в  линейном  поиске, все  равно  преимущество (линейного  поиска), начиная  с  определенной  длины  ввода, пренебрежимо. Рассмотрим  таблицу  5.4, в  ней  мы  предположили, что  шаг  в  линейном  поиске  продолжается  одну  единицу  времени, а  шаг  бинарного  поиска  требует  значительно  больше  времени - 100  единиц. (Эти  предположения  о  продолжительности  основного  действия  в  каждом  из  случаев  являются  произвольными, они  предназначены  для  демонстрации  того, насколько  существенны  изменения  “на  порядок  величины”.  В  действительности  продолжительность  основного  действия  в  бинарном  поиске  превышает  время  шага  в  линейном  поиске  в  5-10  раз  не  более).  Из  рассмотрения  таблицы  выясняется, что  действительно  до  длины  ввода  1000  линейный  поиск  предпочтительнее  из-за  указанного  соотношения  между  временами 

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

Таблица 5.4. Сравнение времен прогона бинарного и линейного  поиска

Усовершенствование  такого  рода  именуется  улучшением  на  порядок  величины (improvement  in order  of  magnitude): отношение  между  временами  прогона  алгоритмов  улучшается  с  увеличением  длины  ввода. (Сравните  это  с  улучшением  на  постоянную  в  таблице  5.2, там  отношение  времен  прогона - постоянно).

5.5.1. Порядок  величины

До  сих  пор  мы  рассматривали  два  вида  усовершенствования  функций  времени  прогона : улучшение  на  постоянный  множитель  и  улучшение  на  порядок  величины.  Мы  также  видели, что  последнее  улучшение  значительнее  весьма. По  этой  причине  для  первоначальной  классификации  времен  прогона  алгоритмов  мы  вправе  “игнорировать”  мелкие  различия  двух  функций  времени  прогона  и  объединять  их  вместе  в  одну  группу. Так, например, простой  и  улучшенный  алгоритма  поска  'ד'  и  алгоритм  линейного  поиска  - все  требуют  в  плохом  случае  выполнения  n  шагов  поиска. И  чем  больше  мы  пытаемся  уточнить  время  прогона  в  конце  концов  получаем  функцию  вида  f(n) =  a^.n + b,  известную  под  именем  линейной, в  которой  a  и  b  есть  некоторые  постоянные. Для  достаточно  большого  n  отношение  двух  функций  этого  типа  будет  постоянным. Отсюда  можно  сказать, что  функция  времен  прогона  таких  алгоритмов  порядка  линейной  величины, или  что  сложность  времени  прогона - линейная. Поскольку  самая  простая  линейная  функция  это f(n) =  n,  принято  обозначать  линейную  сложность  в  виде   O(n),  читается  “О  большое  от  n” .

Обобщим  и  скажем, что  две  функции  времени  прогона  принадлежат  одному  порядку  величины, если  отношение  их  значений  приближается  к  постоянной  величине  для  достаточно  большого  n. Существует  несколько употребительных  семейств  порядка  величины, на  них  мы  остановимся  в  дальнейшем.

? Относится  ли  функция  f(n) =  n²  к  линейному  порядку  величины?

? Функции  f(n) =  n²/100  и f(n) =  n²/10  одного  порядка  величины?

Подобно  линейному  порядку  величины  можно  определить  квадратичный  порядок  величины,  обозначаемый  O(n²). Это  семейство  всех  функций, отношение  которых  к  наиболее  прростой  квадратичной  функции  f(n) = n²  есть  величина