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

УДК 004.42:591.6 

К78 

Р е ц е н з е н т 
доцент ^.Я. Смирнов 

Крапухина Н.В., Светозарова Г.И. 

К78 
Информатика. Основы алгоритмизации и программирова
ния: Учеб. пособие. - М.: МИСиС, 2005. - 177 с. 

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

Предназначено для изучения основ алгоритмизации и программирования 
на языке Турбо-Паскаль студентами I курса, обучающимися по направлению 
подготовки 230400 «Прикладная математика» специальности 230410 «Прикладная математика», а также специальностей других направлений, и для самостоятельного изучения. 

© Московский государственный институт 
стали и сплавов (технологический 
университет) (МИСиС), 2005 

ОГЛАВЛЕНИЕ 

Предисловие 
6 

1. Введение в программирование 
10 

1.1. Понятие о компьютере. Языки программирования 
10 

1.2. Этапы решения задачи. Метод пошаговой детализации 
10 

1.3. Понятие алгоритма 
12 

1.4. Основные понятия программирования. Переменная. 
Присваивание. Условный и безусловный переход 
13 

1.5. Типовые структуры алгоритмов. Современные 
технологии программирования. Структурный подход к 
разработке программ 
15 

Вопросы для самопроверки 
17 

2. Основы языка Турбо-Паскаль 
18 

2.1. Вводные понятия. Структура программы 
18 

2.2. Переменные. Типы данных 
18 

2.3. Массивы 
21 

2.4. Записи 
23 

2.5. Арифметические выражения 
24 

2.6. Основные операторы 
25 

2.6.1. Оператор присваивания 
26 

2.6.2. Операторы ввода-вывода 
27 

2.6.3. Оператор безусловного перехода 
29 

2.6.4. Пустой оператор 
29 

2.6.5. Составной оператор 
30 

2.6.6. Условный оператор 
31 

2.6.7. Операторы цикла 
31 

2.6.8. Оператор выбора 
32 

2.7. Символьные данные 
33 

2.8. Логические данные и их использование 
35 

2.9. Файлы данных 
37 

Вопросы для самопроверки 
40 

3. Реализация простейших алгоритмов на языке Турбо-Паскаль 
41 

3.1. Организация циклов 
41 

Вопросы для самопроверки 
54 

Задания для самостоятельного выполнения 
54 

3.2. Организация разветвлений. Разветвления в цикле 
56 

Вопросы для самопроверки 
60 

Задания для самостоятельного выполнения 
61 

3 

3.3. Составление программ для обработки потока данных 
62 

Вопросы для самопроверки 
65 

Задания для самостоятельного выполнения 
65 

4. Типовые алгоритмы обработки массивов 
66 

4.1. Алгоритмы обработки одномерных массивов 
66 

Вопросы для самопроверки 
75 

Задания для самостоятельного выполнения 
76 

4.2. Работа с матрицами 
78 

Вопросы для самопроверки 
89 

Задания для самостоятельного выполнения 
89 

4.3. Использование записей 
92 

Вопросы для самопроверки 
94 

Задания для самостоятельного выполнения 
94 

5. Блочная структура программы. Процедуры и функции 
97 

5.1. Блочная структура программы. Локальные и глобальные 
переменные 
97 

5.2. Процедура 
98 

5.3. Функция 
100 

5.4. Использование массивов в качестве параметров 
процедур (функций) 
102 

5.5. Параметры без типа 
103 

5.6. Массивы открытого типа 
106 

5.7. Параметры-функции и параметры-процедуры 
108 

Вопросы для самопроверки 
112 

Задания для самостоятельного выполнения 
112 

6. Дополнительные средства языка Турбо-Паскаль 
114 

6.1. Обработка текстовых данных 
114 

Вопросы для самопроверки 
118 

Задания для самостоятельного выполнения 
118 

6.2. Графический режим 
119 

Вопросы для самопроверки 
125 

Задания для самостоятельного выполнения 
125 

6.3. Дополнительно о типах 
126 

Вопросы для самопроверки 
129 

6.4. Модули 
130 

Вопросы для самопроверки 
132 

6.5. Динамическое распределение памяти. Указатели 
132 

Вопросы для самопроверки 
134 

7. Некоторые практические рекомендации по разработке и 
отладке программ 
135 

4 

Вопросы для самопроверки 
139 

8. Работа в интегрированной среде Турбо-Паскаль 7.0 
(основные сведения) 
140 

9. Решение инженерных задач с использованием компьютера. 
Численные методы 
144 

9.1. Необходимость использования численных методов. 
Влияние ошибок на результаты численных решений 
144 

9.2. Решение алгебраических и трансцендентных уравнений 
145 

9.2.1. Метод половинного деления 
146 

9.2.2. Метод итераций 
147 

9.2.3. Метод Ньютона 
148 

Задания для самостоятельного выполнения 
151 

9.3. Вычисление определенных интегралов 
152 

9.3.1. Метод трапеций 
152 

9.3.2. Метод Симпсона 
153 

Задания для самостоятельного выполнения 
154 

9.4. Решение систем линейных уравнений 
157 

Задания для самостоятельного выполнения 
159 

9.5. Интерполирование 
160 

Задания для самостоятельного выполнения 
161 

9.6. Аппроксимация 
162 

Задания для самостоятельного выполнения 
166 

9.7. Решение обыкновенных дифференциальных уравнений. 
Метод Эйлера 
168 

Задания для самостоятельного выполнения 
171 

9.8. Обеспечение необходимой точности 
173 

Вопросы для самопроверки 
174 

Библиографический список 
176 

5 

ПРЕДИСЛОВИЕ 

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

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

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

В качестве языка программирования используется Турбо-Паскаль 
(версия 7.0), являющийся современным языком, разработанным с 
использованием идей структурного программирования и ориентированным на обучение программированию. 

Пособие состоит из двух частей: первая (гл. 1-8) посвящена основам алгоритмизации и программирования, а вторая (гл. 9) - вычислительным методам решения типовых задач, часто встречающихся в 

6 

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

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

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

В главе 2 дается описание основных средств языка ТурбоПаскаль. 

Глава 3 посвящена разработке циклических и разветвляющихся 
программ, глава 4 - работе с массивами. 

Главы 1-4 формируют базовые понятия программирования и в 
сочетании с выполнением приведенных заданий позволяют освоить 
основы программирования. 

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

7 

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

Рекомендуется следующий порядок работы: прочитать гл. 1, прочитать гл. 2 (2.1, 2.2, 2.5, 2.6.1, 2.6.7) и перейти к гл. 3 (3.1), где рассматриваются типовые алгоритмы циклической структуры и приемы 
разработки циклических программ. Параллельно с изучением 3.1 необходимо решить задачи, предлагаемые для самостоятельного выполнения к гл. 3 (все или часть из них по указанию преподавателя). 
Если возникают трудности при разработке алгоритмов и программ на 
Турбо-Паскале, то необходимо вернуться к гл. 1 и соответствующим 
фрагментам гл. 2, а также использовать типовые алгоритмы циклической структуры, приведенные в гл. 3. Заметим, что для понимания 
алгоритма, записанного, как правило, в виде программы или фрагмента программы, его нужно выполнить, используя правила, по которым работают операторы Турбо-Паскаля, задавая, если необходимо, простые исходные данные, не требующие больших вычислений. 

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

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

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

Глава 4 посвящена работе с массивами (средства Турбо-Паскаля 
для работы с массивами изложены в 2.3). Усвоив типовые алгоритмы 
обработки одномерных массивов (4.1), матриц (4.2) и решив задачи 
для самостоятельного выполнения, можно перейти к решению реальных задач, требующих использования записей и массивов записей 
(4.3). Перед этим целесообразно более подробно изучить гл. 7 и воспользоваться содержащимися в ней рекомендациями. При решении 

8 

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

Главы 5 и 6 посвящены более сложным приемам программирования и средствам языка, используемым для реализации принципа программирования сверху вниз (гл. 5), обработке текстовых данных 
(6.1), использованию графического режима (6.2). 

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

9 

1. ВВЕДЕНИЕ В ПРОГРАММИРОВАНИЕ 

1.1. Понятие о компьютере. 
Языки программирования 

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

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

Пользователи ЭВМ в настоящее время пишут программы в более 
привычном и естественном для человека виде, используя так называемые языки программирования - алгоритмические языки. Языком 
программирования называется система обозначений и правил, позволяющая записать программу решения задачи в виде последовательного текста в удобном для человека виде. Преобразование программы, составленной на языке программирования (исходной программы 
или исходного модуля), в машинную программу (объектную программу или объектный модуль) осуществляется самим компьютером 
при помощи программы-транслятора (компилятора), входящей в 
состав программного обеспечения компьютера. 

1.2. Этапы решения задачи. 
Метод пошаговой детализации 

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

10 

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

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

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

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

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

11 

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

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

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

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

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

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

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

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

2. Определенность (или детерминированность): каждое правило 
алгоритма должно быть четким и однозначным. Благодаря этому 

12 

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

3. Результативность (или конечность): алгоритм должен приводить к решению задачи за конечное число шагов. 

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

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

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

1.4. Основные понятия программирования. 

Переменная. Присваивание. Условный 

и безусловный переход 

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

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

13 

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

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

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

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

Например: 
x:= 5; Выражение состоит из одной константы. В переменную 
x (т.е. в ячейку памяти с символическим адресом x) засылается значение 5. 

y:= x+1; Выражение представляет собой сумму переменной и 
константы. Если x = 5, то y будет присвоено значение 6. 

y:= y+1; Если перед этой операцией y имело значение 6, то после ее выполнения y будет равно 7. 

x:= y; Если y имеет значение 7, то после выполнения этой операции x будет иметь то же значение 7 (старое значение пропадает), 
при этом значение y не изменяется. 

Условный оператор в самом простом случае имеет вид 
if условие then оператор; 
Выполняется он следующим образом: если условие удовлетворяется, 
то выполняется оператор, если условие не удовлетворяется, то оператор не выполняется (просто осуществляется переход к следующей 
по порядку операции). 

14