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

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

СРЕДНЕЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАНИЕ

И.Г.СЕМАКИН, А.П.ШЕСТАКОВ

ОСНОВЫ

ПРОГРАММИРОВАНИЯ

Допущено

Министерством образования Российской

Федерации

в качестве учебника для

студентов образовательных учреждений

среднего профессионального

образования,

обучающихся

по

специальностям

2202

«Автоматизированные

системы

обработки инаюрмации

и управления (по отраслям)»,

2203

«Программное обеспечение вычислительной

техники

автоматизированных систем»

Москва

ИЗДДТЕЛЬС

Мастерство

2002

УДК

681.3.06

ББК22.18

Рецензент —

зав.

кафедрой прикладной математики и информатики Пермского

государственного университета, д-р физ.-мат. наук, проф.

С.

В.

Русаков

Семакин

И.

Г.,

Шестаков

А.

П.

С12 Основы программирования: Учебник.

—

М.: Мастерство,

2002.

- 432 с.

ISBN 5-294-00054-7

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

смотрены основы программирования на базе языка Паскаль (в версии Тур-

бо Паскаль-7.0). Изложен стандартный язык Си с некоторыми элементами

его расширения в версии Си++. Представлены задачи по программирова-

нию,

предназначенные для организации практикума на ЭВМ (более 800

заданий).

Для студентов средних профессиональных учебных заведений. Может

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

ми начальных курсов высших учебных заведений.

УДК 681.3.06

ББК 22.18

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

издательства «Мастерство», и его воспроизведение любым способом

без согласия издательства запрещается

ISBN 5-294-00054-7 © Издательство «Мастерство», 2001

ПРЕДИСЛОВИЕ

Программирование все в большей степени становится заняти-

ем лишь для профессионалов. Объявленный в середине 1980-х гг.

лозунг «Программирование

—

вторая грамотность» остался в про-

шлом.

понятие «компьютерная грамотность» сегодня входит преж-

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

ционных технологий. Решая ту или иную информационную зада-

чу, необходимо выбрать адекватное программное средство. Это

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

ных, математические пакеты и т.п. И только в том случае, когда

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

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

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

ных и системных. Системные программисты

—

это разработчики

базовых программных средств ЭВМ (операционных систем, транс-

ляторов, сервисных средств и т.п.). Они являются профессиона-

лами высочайшего уровня в программировании. Прикладные про-

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

обеспечения ЭВМ, предназначенные для решения задач из раз-

личных областей (наука, техника, производство, сфера обслу-

живания, обучение и т.п.). Требования к качеству как приклад-

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

ма должна не только правильно решать задачу, но и иметь

современный интерфейс, быть высоконадежной, дружественной

по отношению к пользователю и т.д. Только такие программы

могут выдерживать конкуренцию на мировом рынке программ-

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

годня никому не нужно.

По мере развития компьютерной техники развивались также

и методика, и технология программирования. Сначала возникает

командное и операторное программирование, в 1960-х гг. бурно

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

логического и функционального программирования, а в после-

днее время

—

объектно-ориентированное и визуальное програм-

мирование.

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

программирования,

—

освоение основ структурной методики про-

граммирования. Для указанной цели наиболее подходящим сред-

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

каль

—

швейцарский профессор Никлаус Вирт

—

создавал его имен-

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

ской культуры. Не освоив ее, человек, взявшийся изучать програм-

мирование, не имеет никаких шансов стать профессионалом.

Реализации Паскаля в версиях фирмы Borland для IBM, извест-

ных под названием Турбо Паскаль, значительно расширили язык по

сравнению с вариантом Вирта. Начиная с версии 5.5 Турбо Паскаль

становится также и языком объектного программирования.

Содержание третьей главы настоящего учебника ориентирова-

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

граммирования высокого уровня в их реализации на Паскале. Та-

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

вания. Изложение основ языков Си/Си++ в четвертой главе

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

чении Паскаля.

При изучении данного курса студентам понадобятся знания

основ алгоритмизации в рамках школьного базового курса ин-

форматики. Обычно в школе алгоритмизация изучается с исполь-

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

пешно освоить основы структурной методики, а именно:

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

• применение метода последовательной детализации.

Желательным является знакомство с архитектурой ЭВМ на уров-

не машинных команд (достаточно на модельных примерах учеб-

ных компьютеров, изучаемых в школьной информатике; совсем

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

ра).

Эти знания позволяют освоить основные понятия программи-

рования, такие как переменная, присваивание; «входить в поло-

жение транслятора» и благодаря этому не делать ошибок, даже не

помня каких-то деталей синтаксиса языка; предвидеть те «под-

водные камни», на которые может «напороться» ваша программа

в процессе выполнения. По существу, все эти качества и отличают

профессионального программиста от дилетанта.

Еще одно качество профессионала — способность восприни-

мать красоту программы, получать эстетическое удовольствие

оттого, что она хорошо написана. Нередко это чувство помогает

интуитивно отличить неправильную программу от правильной.

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

но,

не интуиция, а грамотно организованное тестирование.

Процесс изучения и практического освоения программирова-

ния делится на три части:

• изучение методов построения алгоритмов;

• изучение языка программирования;

• изучение и практическое освоение определенной системы про-

граммирования.

Решению первой задачи посвящены вторая и пятая главы учеб-

ника. Во второй главе даются основные, базовые понятия и прин-

ципы построения алгоритмов работы с величинами.

пятой главе

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

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

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

Языки программирования Турбо Паскаль и Си/Си++ излага-

ются в третьей и четвертой главах учебника соответственно. Под-

черкнем, что данная книга

—

это прежде всего учебник по про-

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

вающего описания данных языков вы здесь не найдете. Языки

излагаются

том объеме, который необходим для начального курса

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

в книгах, приведенных в списке литературы.

учебнике нет инструкций по работе с конкретными система-

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

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

другие источники.

Шестая глава представляет собой достаточно большой задач-

ник по программированию. Этот задачник можно использовать

для организации практических и лабораторных занятий по любо-

му из изучаемых языков.

ГЛАВА 1. ОСНОВЫ АЛГОРИТМИЗАЦИИ

1.1. Алгоритмы и величины

Этапы решения задачи на ЭВМ. Работа по решению любой за-

дачи с использованием компьютера делится на следующие этапы:

Постановка задачи.

Формализация задачи.

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

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

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

6. Проведение расчетов и анализ полученных результатов.

Часто эту последовательность называют

технологической

цепоч-

кой решения задачи на ЭВМ. Непосредственно к программирова-

нию в этом списке относятся пункты 3, 4, 5.

На этапе постановки задачи должно быть четко сформулирова-

но,

что дано

что требуется

найти. Здесь очень важно определить

полный набор исходных данных, необходимых для получения ре-

шения.

Второй этап

—

формализация задачи. Здесь чаще всего задача

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

ношений. Если решение требует математического описания ка-

кого-то реального объекта, явления или процесса, то форма-

лизация равносильна получению соответствующей математи-

ческой модели.

Третий этап

—

построение алгоритма. Опытные программисты

часто сразу пишут программы на языках, не прибегая к каким-

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

псевдокодам). Однако в учебных целях полезно использовать эти

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

граммирования.

Первые три этапа предусматривают работу без компьютера. Даль-

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

ке,

в определенной системе программирования. Последний (шес-

той) этап — это использование уже разработанной программы в

практических целях.

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

ниями и навыками:

• уметь строить алгоритмы;

• знать языки программирования;

• уметь работать в соответствующей системе программирования.

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

горитмическое мышление.

Понятие алгоритма. Одним из фундаментальных понятий в ин-

форматике является понятие алгоритма. Происхождение самого

термина «алгоритм» связано с математикой. Это слово происхо-

дит от

Algorithmi

— латинского написания имени Мухаммеда аль-

Хорезми (787

—

850),

выдающегося математика средневекового

Востока. В XII в. был выполнен латинский перевод его математи-

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

позиционной системе счисления и правилах арифметики много-

значных чисел. Именно эти правила в то время называли алго-

ритмами. Сложение, вычитание, умножение столбиком, деле-

ние уголком многозначных чисел

—

вот первые алгоритмы в ма-

тематике. Правила алгебраических преобразований, способы

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

тическим алгоритмам.

В наше время понятие алгоритма трактуется шире. Алгоритм

—

это

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

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

лем.

В школьном курсе информатики с понятием алгоритма, с ме-

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

учебных исполнителей: Робота, Черепахи, Чертежника и т.д. Эти

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

не,

перемещаются в лабиринтах, перетаскивают предметы с мес-

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

работающими в обстановке.

В разделе информатики под названием «Программирование»

изучаются методы программного управления работой ЭВМ. Сле-

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

пьютер работает с величинами — различными информационны-

ми объектами: числами, символами, кодами и т. п. Поэтому алго-

ритмы, предназначенные для управления компьютером, принято

называть

алгоритмами работы

с величинами.

Данные и величины. Совокупность величин, с которыми рабо-

тает компьютер, принято называть

данными.

По отношению к про-

грамме данные делятся на исходные, результаты (окончательные

данные) и промежуточные (рис. 1), которые получаются в про-

цессе вычислений.

Например, при решении квадратного уравнения ах

Ьх +

с =

исходными данными являются коэффициенты а, Ь, с; результата-

Исходные данные

ПРОГРАММА

(промежуточные даные)

Рис.

Результаты

ми — корни уравнения х

; промежуточным данным

—

дискри-

минант уравнения D = Ь

—

4ас.

Для успешного освоения программирования необходимо ус-

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

ленное место в памяти ЭВМ (иногда говорят — ячейку памяти).

Хотя термин «ячейка» с точки зрения архитектуры современных

ЭВМ несколько устарел, однако в учебных целях его удобно ис-

пользовать.

У всякой величины имеются три основных свойства: имя, зна-

чение и тип. На уровне команд процессора величина идентифи-

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

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

лятся на константы и переменные. Константа — неизменная

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

нием, например: 15, 34.7, k, true и т.д. Переменные величины мо-

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

ставляются символическими именами — идентификаторами, на-

пример: X, S2, cod

15.

Любая константа, как и переменная, занимает

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

кодом в этой ячейке.

Теперь о типах величин

—

типах

данных.

С понятием типа дан-

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

ки базы данных и электронные таблицы. Это понятие является

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

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

ция типов данных, своя система типов. Тем не менее в любой

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

ных, к которому относятся: целый,

вещественный,

логический и сим-

вольный

типы. С типом величины связаны три ее характеристики:

множество допустимых значений, множество допустимых опера-

ций, форма внутреннего представления. В табл. 1.1 представлены

эти характеристики основных типов данных.

Таблица 1.1

Тип

Целый

Значения

Целые положитель-

ные и отрицатель-

ные числа в некото-

ром диапазоне.

Примеры: 23, —12,

387

Операции

Арифметические опе-

рации с целыми чис-

лами: +, —, •, целое

деление и остаток от

деления.

Операции отношений

(<,

>, =идр.)

Внутреннее

представле-

ние

Формат с

фиксирован-

ной точкой

Окончание табл. 1.1

Тип

Вещест-

венный

Логичес-

кий

Символь-

ный

Значения

Любые (целые и

дробные) числа в

некотором диапа-

зоне.

Примеры:

2,5,-0,01,

45,0,

3,6- 10

True (истина),

False (ложь)

Любые символы

компьютерного

алфавита.

Примеры: 'а', '5', '+',

Операции

Арифметические

операции: +, —, •, /.

Операции отношений

Логические опера-

ции: И (and), ИЛИ

(or),

HE (not).

Операции отношений

Внутреннее

представле-

ние

Формат с

плавающей

точкой

1 бит:

1 - true;

0 - false

Коды табли-

цы символь-

ной кодиров-

ки.

символ

—

1 байт

Типы констант определяются по контексту (т.е. по форме за-

писи в тексте), а типы переменных устанавливаются в описаниях

переменных.

Есть еще один вариант классификации данных

—

классифи-

кация по структуре. Данные делятся на

простые

структуриро-

ванные.

Для простых величин (их еще называют скалярными)

справедливо утверждение: одна величина

—

одно значение, для

структурированных: одна величина — множество значений.

К структурированным величинам относятся массивы, строки,

множества и т.д.

ЭВМ — исполнитель алгоритмов. Как известно, всякий алго-

ритм (программа) составляется для конкретного исполнителя в

рамках его системы команд. О каком же исполнителе идет речь

при обсуждении вопроса о программировании для ЭВМ? Ответ

очевиден: исполнителем является компьютер. Точнее говоря, ис-

полнителем является комплекс ЭВМ + Система программирова-

ния (СП). Программист составляет программу на том языке, на

который ориентирована СП. Иногда

литературе такой комплекс

называют виртуальной ЭВМ. Например, компьютер с работаю-

щей системой программирования на Бэйсике называют Бэйсик-

машиной; компьютер с работающей системой программирования

на Паскале называют Паскаль-машиной и т.п. Схематически это

изображено на рис. 2.