Семакин И.Г., Шестаков А.П. Основы программирования

Подождите немного. Документ загружается.

Для данной задачи в качестве подзадачи можно рассматривать

возведение числа в целую положительную степень.

Учитывая, что

1/х~"

= (1/х)~

, запишем основной алгоритм ре-

шения этой задачи.

алг Степенная функция

цел п; вещ х, у

нач ввод х,п

если п=0

•го у:=1

иначе если п>0

то СТЕПЕНЬ(х,П,у)

иначе СТЕПЕНЬ(1/х,-п,у)

вывод у

кон

Здесь дважды присутствует команда обращения к вспомогатель-

ному алгоритму с именем СТЕПЕНЬ. Это алгоритм возведения ве-

щественного основания в целую положительную степень путем

его многократного перемножения. Величины, стоящие в скобках

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

ся фактическими параметрами.

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

оформляются в виде процедур. Запишем на

АЯ

процедуру СТЕПЕНЬ.

процедура СТЕПЕНЬ(вещ

а,цел

к,вещ

цел i

нач z:=l; i:=l

пока i<k, повторять

нц z:=z*a

i:=i+l

кц

кон

Заголовок вспомогательного алгоритма начинается со слова «про-

цедура», после которого следует имя процедуры и в скобках —

список формальных параметров. В этом списке перечисляются пе-

ременные-аргументы и переменные-результаты с указанием их

типов. Здесь а и к — формальные параметры-аргументы, z

—

па-

раметр-результат. Следовательно, процедура СТЕПЕНЬ произво-

дит вычисления по формуле z

—

. В основном алгоритме «Сте-

пенная функция» обращение к процедуре производится путем

указания ее имени с последующим в скобках списком фактичес-

ких параметров. Между формальными и фактическими парамет-

рами процедуры должны выполняться следующие правила соот-

ветствия:

• по количеству (сколько формальных, столько и фактических

параметров);

• по последовательности (первому формальному соответствует

первый фактический параметр, второму — второй и т.д.);

• по типам (типы соответствующих формальных и фактических

параметров должны совпадать).

Фактические параметры-аргументы могут быть выражениями

соответствующего типа.

Обращение к процедуре инициирует следующие действия:

Значения параметров-аргументов присваиваются соответству-

ющим формальным параметрам.

Выполняется тело процедуры (команды внутри процедуры).

Значение результата передается соответствующему фактичес-

кому параметру, и происходит переход к выполнению следующей

команды основного алгоритма.

В процедуре СТЕПЕНЬ нет команд ввода исходных данных и вы-

вода результатов. Здесь присваивание начальных значений аргу-

ментам (а, п) производится через передачу параметров-аргумен-

тов.

А присваивание результата переменной (у) происходит через

передачу параметра-результата (z). Таким образом, передача зна-

чений параметров процедур — это третий способ присваивания

(наряду с командой присваивания и командой ввода).

Использование процедур позволяет строить сложные алгорит-

мы методом

последовательной

детализации.

Упражнения

Даны декартовы координаты трех вершин треугольника на плос-

кости. Составить алгоритм определения площади треугольника.

Дана скорость ракеты при выходе за пределы атмосферы Земли.

Составить алгоритм определения того, как будет двигаться ракета

после выключения двигателей. (Напомним величины трех косми-

ческих скоростей: 7,5 км/с; 11,2 км/с; 16,4 км/с.)

Даны три положительных числа. Составить алгоритм, опреде-

ляющий, могут ли они быть длинами сторон треугольника.

Пусть компьютер способен выполнять только две арифмети-

ческие операции

—

сложение и вычитание. Составить алгоритмы:

а) умножения двух целых чисел;

б) целочисленного деления двух чисел;

в) получения остатка от целочисленного деления двух чисел.

Построить алгоритм решения биквадратного уравнения, ис-

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

уравнения.

6. Составить алгоритм нахождения НОД трех натуральных чи-

сел,

используя вспомогательный алгоритм нахождения НОД двух

чисел.

ГЛАВА 2. ВВЕДЕНИЕ В ЯЗЫКИ ПРОГРАММИРОВАНИЯ

2.1.

История и классификация языков программирования

Язык программирования — это способ записи программ реше-

ния различных задач на ЭВМ в понятной для компьютера форме.

Процессор компьютера непосредственно понимает язык машин-

ных команд (ЯМК). Программы на ЯМК программисты писали лишь

для самых первых ламповых машин — ЭВМ первого поколения.

Программирование на ЯМК

—

дело непростое. Программист дол-

жен знать числовые коды всех машинных команд, должен сам рас-

пределять память под команды программы и данные.

В 1950-х гг. появляются первые средства автоматизации про-

граммирования — языки Автокоды. Позднее для языков этого

уровня стало применяться название «Ассемблеры». Появление язы-

ков типа Автокод-Ассемблер облегчило участь программистов. Пе-

ременные величины стали изображаться символическими име-

нами. Числовые коды операций заменились на мнемонические

(словесные) обозначения, которые легче запомнить. Язык про-

граммирования стал понятнее для человека, но при этом уда-

лился от языка машинных команд. Чтобы компьютер мог испол-

нять программы на Автокоде, потребовался специальный пере-

водчик — транслятор. Транслятор — это системная программа,

переводящая текст программы на Автокоде в текст эквивалент-

ной программы на ЯМК.

Компьютер, оснащенный транслятором с Автокода, понимает

Автокод.

этом случае можно говорить о псевдо-ЭВМ (аппаратура

плюс транслятор с Автокода), языком которой является Автокод.

Языки типа Автокод-Ассемблер являются машинно-ориентиро-

ванными, т.е. они настроены на структуру машинных команд кон-

кретного компьютера. Разные компьютеры с разными типами про-

цессоров имеют разный Ассемблер. Языки программирования вы-

сокого уровня (ЯПВУ) являются машинно-независимыми языками.

Одна и та же программа на таком языке может быть выполнена на

ЭВМ разных типов, оснащенных соответствующим транслятором.

Форма записи программ на ЯПВУ по сравнению с Автокодом

еще ближе к традиционной математической форме, к естествен-

ному языку. Очень скоро вы увидите, что, например, на языке

Паскаль она почти такая же, как на школьном Алгоритмическом

языке. ЯПВУ легко изучаются, хорошо поддерживают структур-

ную методику программирования.

Первыми популярными языками высокого уровня, появивши-

мися в 1950-х гг., были Фортран, Кобол (в США) и Алгол (в

Европе). Языки Фортран и Алгол были ориентированы на науч-

но-технические расчеты математического характера. Кобол

—

язык

для программирования экономических задач. В Коболе по сравне-

нию с двумя другими названными языками слабее развиты мате-

матические средства, но зато хорошо развиты средства обработки

текстов, организация вывода данных в форме требуемого доку-

мента. Для первых ЯПВУ предметная ориентация языков была ха-

рактерной чертой.

Большое количество языков программирования появилось в

1960—1970-х гг. А за всю историю ЭВМ их было создано более

тысячи. Но распространились, выдержали испытание временем не-

многие. В 1965 г. в Дартмутском университете был разработан язык

Бейсик. По замыслу авторов это простой язык, легко изучаемый,

предназначенный для программирования несложных расчетных за-

дач.

Наибольшее распространение Бейсик получил на микроЭВМ

и персональных компьютерах. На некоторых моделях школьных ком-

пьютеров программировать можно только на Бейсике. Однако Бей-

сик — неструктурный язык, и потому он плохо подходит для обу-

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

дует заметить, что последние версии Бейсика для ПК (например,

QBasic) стали более структурными и по своим изобразительным

возможностям приближаются к таким языкам, как Паскаль.

В эпоху ЭВМ третьего поколения получил большое распростра-

нение язык PL/1

{Program

Language One), разработанный фирмой

IBM. Это был первый язык, претендовавший на универсальность,

т.

е.

на возможность решать любые задачи: вычислительные, обра-

ботки текстов, накопления и поиска информации. Однако PL/1

оказался слишком сложным языком. Для машин типа IBM 360/370

транслятор с него не мог считаться оптимальным, содержал ряд

невыявленных ошибок. На ЭВМ класса мини и микро он вообще

не получил распространения. Однако тенденция к универсализа-

ции языков оказалась перспективной. Старые языки были модер-

низированы в универсальные варианты

—

Алгол-68, Фортран-77.

Значительным событием в истории языков программирования

стало создание в 1971 г. языка Паскаль. Его автор

—

швейцарский

профессор Н.Вирт — разрабатывал Паскаль как учебный язык

структурного программирования.

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

персональные компьютеры. Фирма

Borland

International,

Inc (США)

разработала систему программирования Турбо Паскаль для ПК.

Турбо Паскаль

—

это не только язык и транслятор с него, но еще

и операционная оболочка, обеспечивающая пользователю удоб-

ство работы. Турбо Паскаль вышел за рамки учебного предназна-

чения и стал языком профессионального программирования с

универсальными возможностями. Транслятор с Турбо Паскаля

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

удачному в этом отношении транслятору

—

транслятору с Фор-

трана. В силу названных достоинств Паскаль стал основой многих

современных языков программирования, например, таких как

Ада, Модула-2 и др.

Язык программирования Си (английское название — С) со-

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

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

кладных программ. Так же как и Паскаль, Си — это язык струк-

турного программирования, но, в отличие от Паскаля, в нем

заложены возможности непосредственного обращения к некото-

рым машинным командам, к определенным участкам памяти ком-

пьютера. Дальнейшее развитие Си привело к созданию языка объек-

тно-ориентированного программирования Си++.

Модула-2

—

это еще один язык, предложенный Н.Виртом, осно-

ванный на языке Паскаль и содержащий средства для создания

больших программ.

ЭВМ будущего, пятого поколения называют машинами «ис-

кусственного интеллекта». Но прототипы языков для этих машин

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

языки ЛИСП и Пролог.

ЛИСП появился в 1965 г. Язык ЛИСП основан на понятии ре-

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

бой алгоритм может быть описан с помощью некоторого набора

рекурсивных функций, то ЛИСП, по сути, является универсаль-

ным языком. С его помощью на ЭВМ можно моделировать доста-

точно сложные процессы, в частности интеллектуальную деятель-

ность людей.

Язык Пролог разработан во Франции в 1972 г. также для реше-

ния проблемы «искусственного интеллекта». Пролог позволяет в

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

суждений и заставляет ЭВМ давать ответы на заданные вопросы.

Реализовать тот или иной язык программирования на ЭВМ —

это значит создать транслятор с этого языка для данной ЭВМ.

Существуют два принципиально различных метода трансляции. Они

называются соответственно

компиляция

интерпретация.

Для объяс-

нения их различия можно предложить следующую аналогию: лек-

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

Перевод можно организовать двумя способами:

• полный предварительный перевод

—

лектор заранее переда-

ет текст выступления переводчику, тот записывает перевод, раз-

множает его и раздает слушателям (после чего лектор может и не

выступать);

• синхронный перевод — лектор читает доклад, переводчик

одновременно с ним слово в слово переводит выступление.

Компиляция является аналогом полного предварительного пе-

ревода; интерпретация

—

аналогом синхронного перевода. Транс-

лятор, работающий по принципу компиляции, называется ком-

пилятором; транслятор, работающий методом интерпретации,

—

интерпретатором.

При компиляции в память ЭВМ загружается программа-ком-

пилятор. Она воспринимает текст программы на ЯПВУ как исход-

ную информацию. После завершения компиляции получается про-

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

ко программа на ЯМК, которая выполняется, и получаются

требуемые результаты.

Интерпретатор

течение всего времени работы программы на-

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

ОЗУ помещается и программа на

ЯПВУ. Интерпретатор в последовательности выполнения алгоритма

«читает» очередной оператор программы, переводит его в коман-

ды и тут же выполняет эти команды. Затем переходит к переводу и

выполнению следующего оператора. При этом результаты преды-

дущих переводов в памяти не сохраняются. При повторном вы-

полнении одной и той же команды она снова будет транслиро-

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

два этапа: трансляцию и выполнение. При интерпретации, по-

скольку трансляция и выполнение совмещены, программа на ЭВМ

проходит

один этап. Однако откомпилированная программа вы-

полняется быстрее, чем интерпретируемая. Поэтому использова-

ние компиляторов удобнее для больших программ, требующих бы-

строго счета. Программы на Паскале, Си, Фортране всегда ком-

пилируются. Бейсик чаще всего реализован через интерпретатор.

2.2.

Структура и способы описания языков

программирования высокого уровня

Во всяком языке программирования определены способы орга-

низации данных и способы организации действий над данными.

Кроме того, существует понятие «элементы языка», включающее

в себя множество символов (алфавит), лексемы и другие изобра-

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

образие указанных

языков,

их изучение происходит приблизитель-

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

ных языков программирования высокого уровня, которая

схематически отражена на рис. 5.

Изложение языков Паскаль и Си в данном учебном пособии

будет соответствовать этой схеме.

Надо сказать, что в изучении естественных языков и языков

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

чтобы читать и писать на иностранном языке, нужно знать

алфа-

Язык программирования

Элементы языка

Организация действий

над данными

Организация данных

Алфавит, лексемы,

синтаксис, оформление

программы

Ввод-вывод

данных, работа

с файлами

Обработка

данных

Операции

и выражения

Типы

и структуры

данных

Операторы:

—

присваивания

—

ветвления

—

цикла и др. ,

Организация

и использование

подпрограмм

Рис.5

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

правила записи предложений, т.е. то, что называется синтаксисом

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

ватно реагировать на них: ведь из грамотно написанных слов можно

составить абсолютно бессмысленную фразу. Например, в салоне са-

молета засветилось табло, на котором написано:

Fasten

belts!

(При-

стегните ремни!). Зная правила чтения английского языка, вы, к

зависти соседа, правильно прочитаете эту фразу. Однако смысл ее

вам может быть непонятен, и поэтому соответствующих действий

вы не предпримете, за что получите замечание от стюардессы. Смыс-

ловое содержание языковой конструкции называется

семантикой.

Всякий язык программирования имеет три основные составля-

ющие: алфавит, синтаксис и семантику.

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

более строгим, чем в разговорном языке. Человеческая речь со-

держит значительное количество избыточной информации. Не рас-

слышав какое-то слово, можно понять смысл фразы в целом. Слу-

шающий или читающий человек может додумать, дополнить, ис-

править ошибки в воспринимаемом тексте.

Компьютер же — автомат, воспринимающий все «всерьез». В

текстах программ нет избыточности, компьютер сам не исправит

даже очевидной (с точки зрения человека) ошибки. Он может

лишь указать на место, которое «не понял», и вывести замечание

о предполагаемом характере ошибки. Исправить же ошибку дол-

жен программист.

Для описания синтаксиса языка программирования тоже ну-

жен какой-то язык. В этом случае речь идет о метаязыке («надъ-

языке»), предназначенном для описания других языков. Наибо-

лее распространенными метаязыками в литературе по програм-

мированию являются металингвистические формулы Бекуса—

Наура (язык БНФ) и синтаксические диаграммы. В дальнейшем

мы чаще всего будем использовать язык синтаксических диаг-

рамм. Они более наглядны, легче воспринимаются. В некоторых

случаях для удобства мы будем обращаться к отдельным эле-

ментам языка БНФ.

В БНФ всякое синтаксическое понятие описывается в виде фор-

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

::=,

смысл которого эквивалентен словам «по определению есть».

Слева от знака ::= записывается имя определяемого понятия (ме-

тапеременная), которое заключается в угловые скобки < >, а в

правой части записывается формула или диаграмма, определяю-

щая все множество значений, которые может принимать метапе-

ременная.

Синтаксис языка описывается путем последовательного услож-

нения понятий: сначала определяются простейшие (базовые), за-

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

в качестве составляющих.

В такой последовательности, очевидно, конечным определяе-

мым понятием должно быть понятие программы.

В записях метаформул приняты определенные соглашения. На-

пример, формула БНФ, определяющая понятие «двоичная циф-

ра»,

выглядит следующим образом:

<двоичная цифра>::=0|1

Значок | эквивалентен слову «или». Это определение можно

представить на языке синтаксических диаграмм (рис. 6).

<Двоичная цифра>

Рис.6

В диаграммах стрелки указывают на последовательность распо-

ложения элементов синтаксической конструкции; кружками об-

водятся символы, присутствующие в конструкции.

Понятие «двоичный код» как непустую последовательность дво-

ичных цифр БНФ описывает так:

<двоичный код>::=<двоичная цифра>|<двоичный

кодхдвоичная цифра>

Определение, в котором некоторое понятие определяется само

через себя, называется

рекурсивным.

Рекурсивные определения ха-

рактерны для БНФ.

Синтаксическая диаграмма

двоичного

кода представлена

на

рис.

<Двоичный код>

-*• <Двоичная

цифра>-

Рис.7

Возвратная стрелка обозначает возможность многократного

повторения. Очевидно, что диаграмма более наглядна, чем БНФ.

Синтаксические диаграммы были введены

Н.

Виртом и исполь-

зованы для описания созданного им языка Паскаль.

следующем

разделе, посвященном Паскалю, мы также будем пользоваться

синтаксическими

диаграммами.

литературе по языку Си исполь-

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

дет применяться традиционный для этого языка способ описания

правил синтаксиса.

ГЛАВА 3. ПРОГРАММИРОВАНИЕ НА ПАСКАЛЕ

3.1.

Первое знакомство с Паскалем

Структура программы на Паскале. По определению стандартно-

го Паскаля программа состоит из заголовка программы и тела

программы (блока), за которым следует точка — признак конца

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

раздел операторов.

Program <имя программы>;

Label <раздел меток>;

Const <раздел констант>;

Туре <раздел типов>;

Var <раздел переменных>;

Procedure (Function) <раздел подпрограмма-

Begin

<раздел операторов>

End.

Раздел операторов имеется в любой программе и является ос-

новным. Предшествующие разделы носят характер описаний и не

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

В Турбо Паскале, в отличие от стандарта, возможно следующее:

• отсутствие заголовка программы;

• разделы Const, Type, Var, Label могут следовать друг за

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

ко угодно раз.

Примеры программ. Уже было сказано, что Паскаль разрабаты-

вался Н.Виртом как учебный язык. Основной принцип, зало-

женный в нем, — это поддержка структурной методики про-

граммирования. Этот же принцип лежит в основе псевдокода,

который мы здесь называем Алгоритмическим языком (АЯ). По

сути дела, расхождение между АЯ и Паскалем заключается в следу-

ющем: АЯ — русскоязычный, Паскаль — англоязычный; синтак-

сис Паскаля определен строго и однозначно в отличие от сравни-

тельно свободного синтаксиса АЯ.

Запись программы на Паскале похожа на английский перевод

алгоритма, записанного на Алгоритмическом языке. Сравните ал-

горитм деления простых дробей, записанный на АЯ, с соответ-

ствующей программой на Паскале.