программирование тусур. Программирование учебное пособие. Учебное пособие Томск Эль Контент
 Скачать 0.93 Mb.
|
|
Глава 1. Введение в информатику Машинные операции кодируются с помощью цифрового кода (номера опера- ции) и информации об операндах — адрес ячейки памяти, отведенной для хранения операнда. Следовательно, машинная программа ненаглядна, трудно понимаемая для человека. Отличия алгоритмических языков от машинных языков: • большая выразительная возможность: алфавит алгоритмического языка ши- ре алфавита машинного языка; • набор операций не зависит от набора машинных операций и определяется удобством формулирования алгоритмов; • одно предложение языка задает достаточно содержательный процесс обработки; • удобное задание для человека операций, например математическая запись; • операнды имеют имена, выбираемые программистом (более удобно, чем адреса); • более широкий выбор типов данных и, более общо, широкий набор вычис- лительных структур. Алгоритм на алгоритмическом языке не может быть выполнен непосредственно на компьютере. Он должен быть переведен на машинный язык. Если возможен перевод алгоритмического языка на машинный по формальным правилам, то перевод осуществляется машиной, с помощью выполнения определенной машинной программы. Такая программа называется транслятором с данного алгоритмиче- ского языка (на данный машинный язык). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Транслятор — это алгоритм, для которого входом служит текст на алгоритмическом языке, а выходом — текст на машинном языке. Транслятор является, грубо говоря, либо компилятором, либо ин- терпретатором. Компилятор читает всю программу целиком, делает ее перевод на машинный язык и помещает команды в па- мять компьютера. После того, как программа откомпилирована, исходная программа больше не нужна. Интерпретатор преобразует лишь небольшой фрагмент исход- ной программы в машинные команды, а затем, дождавшись, ко- гда компьютер их выполнит, переходит к обработке следующего фрагмента (пример — Бейсик). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Если мы всегда пишем правильные программы и имеем возможность рабо- тать с хорошим компилятором, то для практических целей можно условно считать 1.8 Компьютеры фон Неймана 21 компилятор и вычислительную машину единой машиной, которая может непосред- ственно выполнять программы. Тем самым мы можем совершенно не задумываться о процессе компиляции. Комбинация компилятора и вычислительной машины иногда на- зывается виртуальной машиной. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Нам не нужно было бы вникать в структуру виртуальной машины, если бы не возможность возникновения ошибок. Существуют три типа ошибок в программах: • Синтаксические ошибки — ошибки, которые можно обнаружить при ком- пиляции. • Ошибки, обнаруживаемые при выполнении рабочей программы (при неко- торых входных данных программа не работает, например деление на нуль). • Ошибки, которые не обнаруживаются компьютером ни при компиляции, ни при выполнении программы (неправильный алгоритм). 1.8 Компьютеры фон Неймана Для того чтобы понимать проблематику традиционных языков программирова- ния, нам нужно сначала исследовать их интеллектуального прародителя, компью- тер фон Неймана. Джон (Янош) фон Нейман (1903–1957) Сын преуспевающего будапештского банкира, он рано зарекомендовал себя вундеркиндом. В шесть лет мальчик уже свободно владел древнегреческим, а в во- семь освоил основы высшей математики. С середины 30-х годов фон Нейман жил в США. Он был человеком добродушным и по-своему экстравагантным. Одевался он, скорее, как банкир, а не как профессор. Любил красивых женщин, изысканную еду, очень увлекался автомобилями, которые разбивал примерно раз в год. Что такое компьютер фон Неймана? Когда фон Нейман и другие задумывали его более 50 лет назад, это была изящная, практичная и объединяющая идея, ко- торая упрощала ряд существовавших тогда инженерных и программистских задач. Хотя условия, породившие архитектуру этого компьютера, с тех пор радикально из- менились, тем не менее мы по-прежнему идентифицируем понятие «компьютера» с этой концепцией пятидесятилетней давности. В своей простейшей форме компьютер фон Неймана состоит из трех частей: центрального процессорного устройства, памяти и соединительной шины, которая может за один шаг передавать только одно слово между процессором и памятью (и посылать некий адрес в память). Можно назвать (Дж. Бэкус) эту шину «бутылоч- ным горлышком» (узким местом) фон Неймана. В памяти размещаются программа и данные, с которыми эта программа работает. 22 Глава 1. Введение в информатику Задача программы состоит в том, чтобы неким существенным образом изме- нить содержимое памяти; если считать, что эта задача должна быть выполнена исключительно перекачиванием через узость фон Неймана, то становится ясной причина такого названия. Ирония ситуации состоит в том, что большую часть потока через эту узость составляют не полезные данные, а всего лишь имена данных, а также операции и данные, служащие лишь для вычисления таких имен. Прежде чем слово можно будет послать через шину, его адрес должен находиться в процессоре; поэтому он должен либо быть послан через шину из памяти, либо генерироваться посред- ством некоторой операции процессора. Если адрес посылается из памяти, то адрес этого адреса должен либо быть послан из памяти, либо генерироваться в процес- соре, и т. д. С другой стороны, если адрес генерируется в процессоре, он должен генерировать либо по фиксированному правилу (например, «добавить 1 к счетчи- ку исполняемых команд»), либо по команде, которая была послана через шину, в последнем случае ее адрес нужно было прежде послать и т. д. Итак, программирование на традиционных языках в основном сводится к пла- нированию и спецификации огромного потока слов через узость фон Неймана, причем большая часть этого потока состоит не из самих значащих данных, а из сведений о том, где их искать. Обычные языки программирования в основном являются высокоуровневыми, сложными версиями компьютера фон Неймана. Контрольные вопросы по главе 1 1. Примеры «почти» алгоритмов: медицинский и кулинарный рецепты. Как вы думаете, почему рецепты не являются алгоритмами? 2. Алгоритмически неразрешимая задача — это задача, для которой доказа- но отсутствие алгоритма для её решения. Существуют ли алгоритмически неразрешимые задачи в области программирования? 3. Почему для алгоритмически разрешимой задачи имеется бесконечно много различных алгоритмов ее решения? 4. Как можно обнаружить смысл (семантику) программы? 5. Какие трудности испытывает человек при программировании на традици- онных языках программирования? Рекомендуемая литература к главе 1 23 Рекомендуемая литература к главе 1 [1] Бауэр Ф. Л. Информатика. Вводный курс : в 2 ч. / Ф. Л. Бауэр, Г. Гооз. — М. : Мир, 1990. — Ч. 1. — 336 с. [2] Себеста Р. Основные концепции языков программирования / Р. Себеста. — 5-е изд. — М. : Вильямс, 2001. — 672 с. [3] Кнут Д. Искусство программирования / Д. Кнут. — 3-е изд. — М. : Вильямс, 2005. — Т. 1 : Основные алгоритмы. — 712 с. [4] Кнут Д. Искусство программирования / Д. Кнут. — 2-е изд. — М. : Вильямс, 2004. — Т. 3 : Сортировка и поиск. — 822 с. [5] Немнюгин С. А. Turbo Pascal / С. А. Немнюгин. — СПб. : Питер, 2001. — 496 г. [6] Фаронов В. В. Турбо Паскаль 7.0: Практика программирования / В. В. Фа- ронов. — М. : Нолидж, 2000. — 416 с. [7] Вирт Н. Алгоритмы + структуры данных = программы / Н. Вирт. — М. : Мир, 1985. — 405 с. Глава 2 АЗЫ ЯЗЫКА ПАСКАЛЬ Историческая справка Язык Pascal — разработан в 1968–1971 годах Никлаусом Виртом в Цюрихском Институте Информатики (Швейцария). Цель — создать инструмент для обучения программирования как систематической дисциплины. В результате получился до- статочно простой для использования язык программирования и в тоже время об- наружилась чрезвычайная эффективность при применении и надежность програм- мирования. Паскаль — язык, ориентированный на машину фон-неймановского типа; такие языки называются императивными (imperative — содержащий указание на выпол- нение некоторого действия) или процедурными. 2.1 Основные понятия языка Паскаль 2.1.1 Алфавит языка Паскаль Основные символы языка (лексемы) — либо отдельные литеры на клавиатуре, либо их некоторые комбинации. Используя БНФ- нотацию, определим алфавит языка Паскаль. <лексема> ::= <буква>|<цифра>|<спецсимвол> <буква> ::= a|b|. . .|z|A|B|. . .|Z| <цифра> ::= 1|2|3|4|5|6|7|8|9|0 2.1 Основные понятия языка Паскаль 25 <спецсимвол> ::= <знак арифметической операции>| <знак операции сравнение>| <разделитель>| <служебное слово> <знак арифметической операции> ::= *| /| +| − <знак операции сравнения> ::= =| <>| <| >| <=| >= <разделитель> ::= .| ,| ;| :| (| )| {| }| [| ]| ∧ | '| #| $| @ Служебные слова — «зарезервированные» слова — служат для определенных целей. <служебные слова> ::= begin| end| var| const| if| then| else| function| for|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Переменные Содержимое памяти (и определенных регистров) характеризует состояние фон- неймановской машины. Выполнение программ этими машинами ориентировано сугубо на изменение состояний. Соответственно этому в машине шаг за шагом выполняются определенные инструкции (команды), и с каждым шагом изменяется состояние памяти, т. е. содержимое определенных ячеек памяти. С любым элемен- том данных, используемым в алгоритмическом языке, связано такое понятие языка, как переменная. Любая переменная имеет имя (обозначение) и значение. Перемен- ная именует свое значение — элемент данных. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Значение переменной во время работы программы меняется, вообще говоря. В языке Паскаль любая переменная используется только в рамках какой-то опреде- ленной вычислительной структуры, т. е. значением конкретной переменной может быть только элемент данных определенного типа. Имя переменной в Паскале синтаксически описывается с помощью идентифи- каторов: <идентификатор> ::= <буква>{<цифра> | <буква>} Длина идентификатора произвольна, но компилятор с языка Турбо-Паскаль воспринимает только первые 63 символа. 26 Глава 2. Азы языка Паскаль 2.1.3 Операторы Каждый оператор представляет законченную фразу языка и определяет некоторый вполне законченный этап обработки данных. Основные операторы (не содержат в своем составе других опе- раторов): • оператор присваивания — предназначен для изменения значений переменных; • оператор ввода (чтения) — предназначен для ввода в про- грамму входных данных; • оператор вывода (записи) — предназначен для вывода из программы результатов работы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Из заданных операторов с помощью композиций различных форм можно снова получать операторы, которые называются производными операторами. Различные формы композиции операторов позволяют задавать последовательное выполнение, разветвление по условию и повторение. 2.1.4 Описания данных Программа на Паскале начинается с описания используемых переменных. Для каждой переменной указывается ее имя и тип значения. Описание последовательности действий, которые необходимо выполнить, сле- дует после описания всех переменных. Пример Описание переменных: var a:integer; x,y,z:real; Sinus:real; В программе на языке Паскаль любая используемая переменная, за исключе- нием системных (предописанных), должна быть определена, причем определение переменной должно текстуально предшествовать первому ее использованию. Об- ласть известности («видимости») переменной ограничивается блоком, в котором она определена. Каждая переменная, описанная в блоке, должна упоминаться в опи- саниях не более одного раза. Это относится не только к переменным, а вообще ко всем идентификаторам. 2.1 Основные понятия языка Паскаль 27 Паскаль допускает введение в программы объектов, внешне похожих на пере- менные, но которые, в отличие от них, не могут изменять свое значение. Такие объекты называются константами. Можно сказать, что идентификатор константы является синонимом некоторого определенного значения, которое сопоставляется с этим иден- тификатором при описании. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Пример Описание констант: const One=1; HighLimit=1000; pi=3.14159265358; Тип константы определяется по ее значению. Константа может входить во все конструкции, в которых может присутствовать связанное с ним значение. Естественно, не допускаются ситуации, когда иденти- фикатору константы предлагается изменить значение. Использование в программе идентификаторов констант вместо за- писи конкретных значений считается хорошим стилем програм- мирования, так как делает программу более «читабельной» и спо- собствует лучшему ее пониманию, без какого бы то ни было сни- жения эффективности (в части быстродействия и объема занимае- мой памяти). Кроме того, если некоторые важные для программы значения обозначены идентификаторами (например, границы мас- сивов, показатели точности вычислений), то при необходимости их легко изменить, исправив описание соответствующих констант. В противном случае эти значения будут «растворены» в тексте про- граммы и придется просматривать ее целиком, чтобы произвести нужные изменения. Грубая схема программы: const <описания констант> var <описания переменных> begin <операторы> end. 28 Глава 2. Азы языка Паскаль 2.1.5 Правила записи текста программы Для облегчения понимания текста программы и для упрощения трансляции требуется выполнение определенных правил написания текста программы. Нам потребуются следующие понятия. Разделители • Пробел — литера, которой соответствует пустая пози- ция в строке текста (на бумаге, на экране), не имеет графического изображения. • В текстах программ допускаются фрагменты поясни- тельного текста — комментарии. Наличие комментариев не изменяет смысл программы и не влияет на ее выпол- нение. Комментарии представляют собой произвольную последовательность символов (не обязательно из алфа- вита языка, т. е. допускаются и русские буквы), заклю- ченную в фигурные скобки. Пример: {это комментарий}. Комментарий может находиться между двумя любыми лексемами программы. • Конец строки — управляющая литера. Текст программы разбивается на строки, при работе редактора в конце строк помещается невидимая литера «конец строки». . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Правила записи 1. Между двумя конструкциями языка (являющимися иден- тификаторами, числами или служебными словами) дол- жен быть хотя бы один разделитель. 2. Разделители не должны быть внутри идентификаторов, чисел и служебных слов. 3. Если это не противоречит правилам 1, 2, то между двумя любыми лексемами может находиться любое число разде- лителей (транслятором они игнорируются). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.6 Система типов языка В Паскале используются несколько вычислительных структур. 2.1 Основные понятия языка Паскаль 29 Данные в этих структурах принадлежат определенным типам. Элементы данных представляются переменными в программе. Поэтому любая переменная характеризуется своим типом. Под типом в данном случае понимается множество значений, ко- торые может принимать переменная, и, как следствие, мно- жество операций, допустимых над данной переменной. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Паскаль является типизированным и статическим языком. Это означает, что тип переменной определяется при ее описании и не может быть изменен. Такой подход способствует большей аккуратности и ответственности при составлении программы, делает их поддающимися автоматической (при компиляции) провер- ке на корректность и, в конечном итоге, приводит к более высокой надежности создаваемых программ. Паскаль имеет развитую и изощренную систему вычислительных структур (ти- пов). На основании небольшого числа стандартных типов программист может скон- струировать данные произвольной структуры и сложности, адекватно отражающие информационную природу задачи. В табл. 2.1 перечислены предопределенные ти- пы языка. Кроме указанных типов, программист может сам определить ограничен- ные, перечислимые и свои ссылочные типы. Составные и ссылочные типы можно считать некоторыми правилами для построения более сложных типов из более простых. Процедурные типы в некотором отношении расширяют понятие подпро- грамм, позволяя обращаться с подпрограммами, как с переменными. Таблица 2.1 – Классификация предопределенных типов языка Turbo-Pascal Группа Подгруппа Название Идентификатор Простой Скалярный Короткий целый ShortInt Байтовый Byte Слово Word Целый Integer Длинный целый LongInt Символьный Char Булевский Boolean Вещественный Вещественный Real С ординарной точностью Single С двойной точностью Double С повышенной точностью Extended Сложный Comp Составной (структурный) Строковый String Массив Array Множество Set Файл File Запись Record продолжение на следующей странице |