Учебник_Информатика. Стандарт третьего поколениян. В. Макарова, В. Б. Волков
 Скачать 14.49 Mb.
|
{ Комментарий Символическое обозначение используется для добавления комментариев. Пунктирные линии в символе комментария связаны с соответству ющим блоком. Текст комментариев должен быть помещен около скобки 9 м -------- 1 Линия Символ отображает поток данных или управле ние 10 m i j Граница цикла Символ, состоящий из двух частей, отображает начало и конец цикла. Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т. д. помещаются внутри символа в начале или в конце в зависимости от расположения операции, проверяющей условие 402 Глава 14. Основы теории алгоритмов На рис. 14.6 в виде блок-схемы представлен алгоритм нахождения минималь ного числа М в последовательности из п чисел аи а2> а п (п * 0). Рис. 14.6. Блок-схема алгоритма нахождения минимума в последовательности чисел 14.2.3. Представление алгоритма с помощью диаграммы Нэсси—Шнейдермана Диаграмма Нэсси—Шнейдермана была предложена в сочетании со структур ным программированием как средство борьбы с присущей схемам алгоритмов проблемой большого количества стрелок, отображающих передачу управления на другую часть программы (так называемого «спагетти-кода») . Эта диаграмма заменяет одномерное представление вложенных операторов двухмерным. Тем не менее и в этом случае по мере роста сложности программного кода проявляются проблемы отображения, поскольку элементы диаграммы быстро становятся все меньше и меньше. 14.2. Способы записи алгоритмов 403 На рис. 14.7 приведены составные элементы диаграммы Нэсси—Шнейдермана. На рис. 14.8 представлен алгоритм нахождения действительных корней ква дратного уравнения ах2 + Ьх + с = 0, представленный при помощи диаграммы Нэсси—Шнейдермана. Программа Заголовок программы Тело программы Простая конструкция Оператор Условный оператор Циклическая конструкция т Условие F True-блок False-блок Условие Тело цикла Рис. 14.7. Элементы диаграммы Нэсси— Шнейдермана Рис. 14.8. Алгоритм, представленный при помощи диаграммы Нэсси— Шнейдермана 404 Глава 14. Основы теории алгоритмов 14.2.4. Представление алгоритма с помощью псевдокодов Широкое распространение получил способ записи алгоритма при помощи псев докода. Этот способ записи является промежуточным — к нему прибегают перед записью алгоритма в терминах выбранного языка программирования. Псевдокод представляет собой удобный для практического применения промежуточный язык. Это симбиоз естественного языка и языка программирования. Псевдокод похож на язык программирования тем, что в нем, с одной стороны, присутствуют некоторые инструкции и конструкции языка программирования, а с другой — допускается словесная или формульная запись там, где сложно использовать средства языка программирования. Примером псевдокода является алгоритмический язы к (АЯ), содержащий систему обозначений для единообразной и точной записи алгоритмов и задания правил их использования. Важной особенностью алгоритмических языков типа псевдокодов является их близость к языкам программирования. Как и любой язык, АЯ строится на основе алфавита, включающего в себя набор символов, разрешенных к применению при написании алгоритмов. Алфавит АЯ включает в себя строчные и прописные буквы русского и латинского алфавитов; цифры десятичной системы счисления; специальные символы, имеющиеся на клавиатуре устройства ввода данных ПК и в наборах устройств печати; символы математических операций, используемые при написании выражений. Для дополнения символов алфавита в АЯ вводятся так называемые ключевые (служебные) слова, которые позволяют сделать запись алгоритма более понятной и выразительной, формализованной. Они используются для формирования типо вых синтаксических конструкций. Перечислим основные ключевые слова алгоритмического языка: алг (алгоритм), рез (результат), нач (начало), кон (конец), арг (аргумент), знач (значение), тип, вещ (вещественный), цел (целый), лит (литерный), таб (табличный), сим (символьный), не, то, если, и, все, или, выбор, иначе, нц (начало цикла), кц (конец цикла), от, до, шаг, для, пока, := (оператор присваивания), при, да, нет. Дополнительные ключевые слова: запись, истина, лог (логический), ложь, массив, множество, функция, дано, надо, ввод, вывод, утв (утверждение). Пример программы, записанной на алгоритмическом языке: алг Сунна квадратов (арг цел п, рез цел 5) дано | п > О надо | 5 - 1 1 + 2-2 + 3-3 + . . . + п-п нач цел 7 ввод п ; S:=0 нц для 7 от 1 до л 5:=5 + 7 7 кц вывод "5 = ", 5 кон 14.2. Способы записи алгоритмов 405 14.2.5. Программный способ представления алгоритмов При записи алгоритма в словесной форме, в виде блок-схемы или на псевдокоде допускается определенный произвол при изображении команд. Вместе с тем такая запись точна настолько, что позволяет человеку понять суть дела и исполнить ал горитм. Однако на практике в качестве исполнителей алгоритмов используются компьютеры или иные вычислительные устройства (однокристальные микроЭВМ, промышленные компьютеры, технологические контроллеры и др.), поэтому алго ритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполни телем. Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера. В настоящее время в мире существует несколько сотен реально используемых языков программирования. Для каждого есть своя область применения. В зависи мости от степени детализации предписаний обычно определяется уровень языка программирования — чем язык менее детален, тем выше его уровень. По этому кри терию можно выделить следующие уровни языков программирования (рис. 14.9)1: □ машинно-ориентированные языки — машинные языки и языки ассемблера; □ машинно-независимые языки — языки высокого уровня. Рис. 14.9. Классификация языков программирования Машинно-ориентированные языки — это языки низкого уровня, требующие указания мелких деталей процесса обработки данных. Языки же высокого уров ня имитируют естественные языки, используя некоторые слова естественного языка и общепринятые математические символы. Эти языки более удобны для человека. Языки высокого уровня делятся на процедурные, логические и объектно-ориен- тированные. □ Процедурные, или алгоритмические, языки (Basic, Pascal, С и др.) предназначены для однозначного описания алгоритмов в виде некоторой последовательности операторов языка. 1 Приведенная классификация не является единственной. 406 Глава 14. Основы теории алгоритмов □ Логические языки (Prolog, Lisp и др.) ориентированы не на разработку алгоритма решения задачи, а на систематическое и формализованное описание задачи, из которого должно следовать решение. □ Объектно-ориентированные языки (Object Pascal, C++, Java, C# и др.), в основе которых лежит понятие объекта, сочетают в себе данные и действия над ними. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути, описывает часть мира, относящуюся к этой задаче. Описание действитель ности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур. 14.3. Базовые алгоритмические конструкции Для выполнения типичных последовательностей действий в алгоритме разрабо таны базовые алгоритмические конструкции в виде определенного набора блоков и стандартных средств их соединения. К базовым алгоритмическим конструкциям относятся линейные, разветвляющиеся и циклические. Линейный щярэ&ррутщ v ****>»// ** ' /> , V Пример линейного алгоритма приведен на рис. 14.10. ( Начало ) j Ввод А , В Х = А * В j Вывод А, В ( Конец ^ Рис. 14.10. Линейный алгоритм В отличие от линейных алгоритмов, в которых команды выполняются после довательно одна за другой, в разветвляющиеся алгоритмы входит условие, в за висимости от выполнения или невыполнения которого выполняется та или иная последовательность команд (действий). Пример разветвляющегося алгоритма приведен на рис. 14.11. Р а з в е т в т ю т и й т ^ тцттрштк в котором действия выполняются по сщйой Ш | возможных ветвей рецшкия задачи ш тш и сш осии от выполнения условий. Л #? 14.3. Базовые алгоритмические конструкции 407 В качестве условия в разветвляющемся алгоритме может быть использовано любое понятное исполнителю утверждение, которое может соблюдаться (быть истинным) или не соблюдаться (быть ложным). Такое утверждение может быть выражено как словами, так и формулой. Таким образом, алгоритм ветвления со стоит из условия и двух последовательностей команд. Многократные повторения одних и тех же действий обеспечиваются при помо щи циклических алгоритмов (рис. 14.12). В цикл входят в качестве составляющих элементов блок проверки условия и блок, называемый телом цикла. Перед началом цикла осуществляются операции присваивания начальных значений тем объектам, которые используются в теле цикла. Вывод А, В ( Конец ) Рис. 14.11. Разветвляющийся алгоритм ГГг \ Вычисление С Н а ч ^ ° п\ = 1-2-...-П Рис. 14.12. Алгоритм с циклическим элементом 408 Глава 14. Основы теории алгоритмов Слово «многократно» в определении циклического алгоритма не значит «до бесконечности». Организация циклов, не приводящих к остановке в выполнении алгоритма, является нарушением требования его результативности — получения результата за конечное число шагов. Если тело цикла расположено после проверки условий (цикл с предусловием), то при определенных условиях тело цикла не выполнится ни разу. Такой вариант организации цикла, управляемый предусловием, называется циклом с предусловием (рис. 14.13). а) Общее обозначение б) Реализация по ГОСТ 19.701-90 Рис. 14.13. Цикл с предусловием Другой вариант построения цикла состоит в том, что тело цикла выполняется по крайней мере один раз, и будет повторяться до тех пор, пока условие не станет истинным. Такая организация цикла, когда его тело расположено перед проверкой условия, носит название цикла с постусловием (рис. 14.14). Истинность условия в этом случае является условием выхода из цикла. а) Общее обозначение б) Реализация по ГОСТ 19.701-90 Рис. 14.14. Цикл с постусловием 14.4. Представление и обработка данных разного типа 409 Таким образом, цикл с предусловием завершается, когда условие ложно, а цикл с постусловием — когда условие становится истинным. Третий тип циклов, в которых тело цикла выполняется заданное число раз (то есть еще до начала выполнения цикла точно известно, сколько раз он будет выпол нен), реализуется с помощью счетчика. В цикле со счетчиком значения счетчика в теле цикла итеративно увеличиваются. Процесс решения сложной задачи довольно часто сводится к решению несколь ких более простых задач методом последовательной детализации. Соответственно, процесс разработки сложного алгоритма может разбиваться на этапы составления отдельных алгоритмов, которые называются вспомогательными. Каждый такой вспомогательный алгоритм описывает решение какой-либо подзадачи. Процесс построения алгоритма методом последовательной детализации состоит в следующем. Сначала алгоритм формулируется в «обобщающих» блоках, которые могут быть непонятны исполнителю и записываются, как вызовы вспомогательных алгоритмов. Затем происходит детализация, и все вспомогательные алгоритмы детализируются до уровня команд, понятных исполнителю. 14.4. Представление и обработка данных разного типа 14.4.1. Общее представление о типах данных Алгоритм, реализующий решение некоторой конкретной задачи, всегда работает с данными. С точки зрения процесса обработки данные могут быть входными (исходными), выходными (результирующими) и промежуточными. Данные подразделяют на переменные и константы. Например, для алгоритма вычисления площади круга необходимы две пере менные: переменная R> в которую будет заноситься значение радиуса окружности, и переменная 5, в которую будет помещено значение площади круга, вычисленное по формуле S = nR2. Число тт — константа. Каждая переменная или константа в алгоритме должна иметь свое уникальное имя, которое задается идентификатором. Идентификатор представляет собой по следовательность букв и цифр, начинающуюся с буквы. С данными тесно связано понятие типа данных. Типы данных вводятся для того, чтобы использовать их в различных алгоритмах обработки. Следовательно, нужно иметь еще и множество операций, которые можно применять к данным того или иного типа. 410 Глава 14. Основы теории алгоритмов Тип данны х характеризует м нож ество значений, к которым относится константа и которы е м ож ет принимать перем енная или вы ражение. Н апример, если перемен ная i в алгоритм е м ож ет приним ать только зн ач ен ие и з м нож ества целы х чисел, то эта п ер ем ен н ая от н оси тся к ц ел ом у т ип у данны х. Типы данных принято делить на простые (базовые) и структурированные. К структурированным данным относят наборы данных, имеющие разное пред ставление: массивы, символьные цепочки, деревья, графы. Наиболее общий метод получения структурных типов заключается в объ единении элементов произвольных типов в одной переменной. Причем сами эти элементы могут быть в свою очередь структурными. Например, это могут быть комплексные числа, состоящие из вещественной и мнимой частей, или параметры точки, определяемые координатами и цветом. 14.4.2. Базовые типы данных К базовы м типам данны х относя тся сл едую щ и е типы: □ целые (INTEGER) — п о д м н о ж е с т в о д о п у ст и м ы х зн а ч ен и й и з м н ож еств а целых чисел; □ вещественные (REAL) — п одм н ож еств о доп усти м ы х зн ачен ий и з м нож ества ве щ ествен н ы х чисел; □ логические (BOOLEAN) — м н ож еств о доп уст и м ы х зн ачен ий состои т всего из двух зн ач ен ий , истина и ложь. □ символьные (CHAR) — буквы, циф ры , знаки препинания и т. д. Т и п INTEGER з а д а е т п о д м н о ж е с т в о ц ел ы х ч и сел , д и а п а зо н к о т о р о го зависит от т акой х а р а к т ер и ст и к и к ом п ью тер а, как р азм ер м аш и н н ого сл ова. Е сли для п р е д ст а в л е н и я в к о м п ь ю т ер е ц ел ы х ч и сел х и с п о л ь зу е т с я п р а зр я д о в (причем о д и н и з н и х отводи тся под ук азан и е знака чи сл а), то доп усти м ы е числа должны удов л етв ор я ть усл ов и ю - 2 ”-1 < х < 2 ”-1 (П р и в еден н ы й ди ап азон зн ачен ий целых ч и сел в я -р азр я дн ом п редстав лени и соответствует о дн ой и з в озм ож н ы х форм ко ди ров ан и я. Ч ащ е всего на практике и сп ол ь зует ся другая ф орм а кодирования, при котор ой м одул ь м иним ал ьного отрицательного числа на ед и н и ц у больш е модуля 14.4. Представление и обработка данных разного типа 411 максимального положительного числа, т. е. -(2 " _1) < х < (2"_1) - 1 .) Считается, что все операции над данными этого типа выполняются точно и соответствуют обычным правилам арифметики. Если результат выходит за пределы допустимых значений, то вычисления прерываются. Такое событие называется переполнением. Д л я целы х чисел б е з знака м ож ет быть оп р едел ен доп ол н и тел ьн ы й ст ан дар т ный тип — ц ел ое б ез знака (в н екоторы х язы ках програм м ирования, кром е того, м ож но о п р е д ел и т ь тип « н атур ал ь н ое ч и с л о » ), за д а ю щ и й п о д м н о ж е с т в о ц ел ы х неотрицательны х чисел (соотвеств ен н о, п одм н ож еств о натуральны х ч и сел ). Е сли для представления целых б ез знака испол ьзуется п разрядов, то перем енны м такого типа м ож н о присваивать значения, удов л етвор яю щ и е усл о в и ю 0 < х < 2я- 1 (с о о т ветственно, 0 < х < 2 я- 1 или 0 < х < 2 ”, в зав и си м ости от р еал и зац и и ). Пример. Целые числа обычно применяют в тех случаях, когда необходимо за писать некоторое значение, поддающееся подсчету: количество предметов, лет, дней, записей, слов. В алгоритмах тип INTEGER так же используют для подсчета итераций цикла или нумерации элементов массива. Тип REAL обозн ач ает п о д м н о ж еств о вещ ествен н ы х чисел, границы и зм е н е н и я которых такж е оп редел яю тся характеристикам и конкретного компью тера. И если считается, что ариф м етика с данны ми типа INTEGER дает точны й результат, то д о п у скается, что аналогичны е действия со значениям и типа REAL могут быть неточны м и в п р едел ах о ш и бок ок р угл ен и я , вы званны х вы ч и сл ен и я м и с кон ечн ы м ч и сл о м цифр. Э то п р и н ципиал ьное р азличие м еж д у типам и REAL и INTEGER. Пример, Тип REAL обычно применяется для представления величин, которые можно измерить прямым измерением (веса, температуры), а также результатов |