Этапы решения задач на ЭВМ
Основы алгоритмизации и программирования.
Язык Си
Допущено Министерством образования Республики Беларусь
в качестве учебного пособия
для студентов учреждений, обеспечивающих получение
высшего образования по специальностям «Искусственный интеллект», «Программное обеспечение информационных технологий»,
«Автоматизированные системы обработки информации»,
«Электронные вычислительные средства»,
«Инженерно-психологическое обеспечение информационных технологий»
Минск БГУИР 2007
УДК 621.3 (075.8)
ББК 22.193 я 73
Б 28
Р е ц е н з е н т ы :
зав. кафедрой алгоритмики и дискретной математики БГУ,
д-р техн. наук, проф. В. М. Котов;
начальник кафедры систем автоматического управления Военной академии Республики Беларусь, д-р техн. наук, проф. В. А. Куренев
Батура, М. П.
Б 28 Основы алгоритмизации и программирования. Язык Си : учеб. пособие / М. П. Батура, В. Л. Бусько, А. Г. Корбит, Т. М. Кривоносова. – Минск : БГУИР, 2007. – 240 с. : ил.
ISBN 978-985-488-192-8
Материал пособия составлен на основе курса лекций по дисциплине «Основы алгоритмизации и программирования», читаемого авторами в Белорусском государственном университете информатики и радиоэлектроники на факультете информационных технологий и управления.
Содержание пособия охватывает темы, посвященные основным конструкциям языка Си. Приведенные примеры, иллюстрирующие основные возможности языка, прошли проверку в качестве консольных приложений среды программирования Visual C++ 6.0.
Неотъемлемой частью учебного пособия являются индивидуальные задания для практических и лабораторных работ. В приложениях рассматриваются некоторые элементы языка С++, приведены дополнительные задания.
УДК 621.3 (075.8)
ББК 22.193 я 73
ISBN 978-985-488-192-8 ã УО «Белорусский государственный
университет информатики
и радиоэлектроники», 2007
СОДЕРЖАНИЕ
ПРЕДИСЛОВИЕ. 8
ГЛАВА 1. Введение в алгоритмы.. 10
1.1. Этапы решения задач на ЭВМ.. 10
1.2. Понятие алгоритма. 10
1.3. Свойства алгоритмов. 11
1.4. Сложность алгоритма. 11
1.5. Способы описания алгоритмов. 12
1.6. Способы реализации алгоритмов. 14
1.7. Пример простейшего линейного процесса. 14
1.7. Пример циклического процесса. 15
ГЛАВА 2. Базовые средства языка Си. 17
2.1. Алфавит языка Си. 17
2.2. Лексемы.. 17
2.3. Идентификаторы и ключевые слова. 18
2.4. Комментарии. 19
2.5. Простейшая программа. 19
2.6. Основные типы данных. 20
2.7. Декларация объектов. 21
2.8. Данные целого типа (integer) 22
2.9. Данные символьного типа (char) 22
2.10. Данные вещественного типа (float, double) 23
2.11. Использование модификаторов при декларации производных типов данных 24
ГЛАВА 3. Константы в программах. 25
3.1. Целочисленные константы.. 25
3.2. Константы вещественного типа. 26
3.3. Символьные константы.. 26
3.4. Строковые константы.. 27
ГЛАВА 4. Обзор операций. 27
4.1. Операции, выражения. 27
4.2. Арифметические операции. 28
4.3. Операция присваивания. 28
4.4. Сокращенная запись операции присваивания. 29
4.5. Преобразование типов операндов арифметических операций. 30
4.6. Операция приведения типа. 31
4.7. Операции сравнения. 31
4.8. Логические операции. 32
4.9. Побитовые логические операции, операции над битами. 33
4.10. Операция «,» (запятая) 35
ГЛАВА 5. Обзор базовых инструкций языка Си. 35
5.1. Стандартная библиотека языка Си. 35
5.2. Стандартные математические функции. 35
5.3. Функции вывода данных на дисплей. 36
5.4. Функции ввода информации. 38
Советы по программированию.. 39
ЗАДАНИЕ 1. Составление линейных алгоритмов. 40
Первый уровень сложности. 40
Второй уровень сложности. 41
ГЛАВА 6. Составление разветвляющихся алгоритмов. 44
6.1. Краткая характеристика операторов языка Си. 44
6.2. Условные операторы.. 44
6.3. Условная операция «? :». 47
6.4. Оператор выбора альтернатив (переключатель) 48
ГЛАВА 7. Составление циклических алгоритмов. 52
7.1. Понятие циклического кода. 52
7.2. Оператор с предусловием while. 52
7.3. Оператор цикла с постусловием do – while. 54
7.4. Оператор цикла с предусловием и коррекцией for 55
ГЛАВА 8. Операторы и функции передачи управления. 58
8.1. Оператор безусловного перехода goto. 58
8.2. Операторы continue, break и return. 58
8.3. Функции exit и abort 59
Советы по программированию.. 59
ЗАДАНИЕ 2. Разветвляющиеся алгоритмы.. 60
Первый уровень сложности. 60
Второй уровень сложности. 61
ЗАДАНИЕ 3. Циклические алгоритмы.. 62
Первый уровень сложности. 62
Второй уровень сложности. 63
ГЛАВА 9. Указатели. 64
9.1. Определение указателей. 64
9.2. Операция sizeof 67
9.3. Инициализация указателей. 67
9.4. Операции над указателями. 69
ГЛАВА 10. Массивы.. 70
10.1. Понятие массива. 70
10.2. Одномерные массивы.. 71
10.3. Связь указателей и массивов. 72
10.4. Строки как одномерные массивы данных типа char 73
10.5. Указатели на указатели. 76
10.6. Многомерные массивы.. 77
10.7. Адресная функция. 79
10.8. Работа с динамической памятью.. 80
10.9. Библиотечные функции. 81
10.10. Пример создания одномерного динамического массива. 81
10.11. Пример создания двухмерного динамического массива. 83
ГЛАВА 11. Функции пользователя. 83
11.1. Декларация функции. 84
11.2. Вызов функции. 86
11.3. Передача аргументов в функцию.. 87
11.4. Операция typedef 88
11.5. Указатели на функции. 89
11.6. Рекурсивные функции. 93
11.7. Параметры командной строки функции main. 96
ГЛАВА 12. Классы памяти и область действия объектов. 97
12.1. Классы памяти объектов в языке Cи. 97
12.2. Автоматические переменные. 98
12.3. Статические и внешние переменные. 98
12.4. Область действия переменных. 101
Советы по программированию.. 103
ЗАДАНИЕ 4. Обработка массивов. 104
Первый уровень сложности. 104
Второй уровень сложности. 105
ЗАДАНИЕ 5. Функции пользователя. 106
Первый уровень сложности. 106
Второй уровень сложности. 106
ГЛАВА 13. Структуры, объединения, перечисления. 108
13.1. Структуры.. 108
13.2. Декларация структурного типа данных. 108
13.3. Создание структурных переменных. 109
13.4. Обращение к полям структур. 110
13.5. Вложенные структуры.. 111
13.6. Массивы структур. 112
13.7. Размещение структурных переменных в памяти. 113
13.8. Объединения. 114
13.9. Перечисления. 115
13.10. Битовые поля. 116
ГЛАВА 14. Файлы в языке Си. 117
14.1. Открытие файла. 118
14.2. Закрытие файла. 119
14.3. Запись – чтение информации. 120
14.4. Позиционирование в файле. 121
14.5. Дополнительные файловые функции. 122
Советы по программированию.. 124
ЗАДАНИЕ 6. Создание и обработка структур. 124
Первый уровень сложности. 124
Второй уровень сложности. 125
ЗАДАНИЕ 7. Создание и обработка файлов. 126
Первый уровень сложности. 126
Второй уровень сложности. 126
ГЛАВА 15. Динамические структуры данных. 127
15.1. Линейные списки. 127
15.2. Структура данных СТЕК.. 128
15.2.1. Алгоритм формирования стека. 129
15.2.2. Алгоритм извлечения элемента из стека. 131
15.2.3. Просмотр стека. 131
15.2.4. Алгоритм освобождения памяти, занятой стеком. 132
15.2.5. Алгоритм проверки правильности расстановки скобок. 133
15.3. Структура данных ОЧЕРЕДЬ. 133
15.3.1. Формирование очереди. 134
15.3.2. Алгоритм удаления первого элемента из очереди. 136
15.4. Двунаправленный линейный список. 136
15.4.1. Формирование первого элемента. 137
15.4.2. Добавление элементов в конец списка. 138
15.4.3. Алгоритм просмотра списка. 138
15.4.4. Алгоритм поиска элемента в списке по ключу. 138
15.4.5. Алгоритм удаления элемента в списке по ключу. 139
15.4.6. Алгоритм вставки элемента в список после элемента
с указанным ключом. 140
15.5. Нелинейные структуры данных. 141
15.5.1. Бинарные деревья. 142
15.5.2. Основные алгоритмы работы с бинарным деревом. 143
15.5.3. Формирование дерева. 144
15.5.4. Вставка нового элемента. 144
15.5.5. Удаление узла. 146
15.5.6. Алгоритмы обхода дерева. 148
15.5.7. Функция просмотра. 150
15.5.8. Освобождение памяти. 150
15.6. Построение обратной польской записи. 151
15.6.1. Алгоритм, использующий дерево. 151
15.6.2. Алгоритм, использующий стек. 152
15.6.3. Пример реализации. 153
15.7. Понятие хеширования. 156
15.7.1. Хеш-таблица и хеш-функции. 156
15.7.2. Примеры хеш-функций. 157
15.7.3. Схемы хеширования. 159
15.7.4. Примеры реализации схем хеширования. 160
ЗАДАНИЕ 8. Обработка списков. 162
Вариант 1. Однонаправленные списки. 162
Вариант 2. Двунаправленные списки. 163
ЗАДАНИЕ 9. Деревья и польская запись. 164
Вариант 1. Создание и обработка структур типа «дерево». 164
Вариант 2. Создание и использование польской записи. 165
ГЛАВА 16. Переход к ООП.. 166
16.1. Потоковый ввод-вывод. 166
16.2. Управление выводом. 166
16.3. Проблема ввода-вывода кириллицы в среде Visual C++.. 169
16.4. Операции new и delete. 170
16.5. Дополнительные возможности при работе с пользовательскими функциями 172
16.6. Шаблоны функций. 175
Советы по программированию.. 180
ЗАДАНИЕ 10. Перегрузка функций. 181
Первый уровень сложности. 181
Второй уровень сложности. 182
ПРИЛОЖЕНИЕ 1. Таблицы символов ASCII 184
ПРИЛОЖЕНИЕ 2. Операции языка Си. 185
ПРИЛОЖЕНИЕ 3. Возможности препроцессора. 187
ПРИЛОЖЕНИЕ 4. Интегрированная среда программирования Visual C++. 191
ПРИЛОЖЕНИЕ 5. Некоторые возможности отладчика Visual C++. 198
ПРИЛОЖЕНИЕ 6. Некоторые возможности графической подсистемы.. 204
6.1. Основные понятия. 204
6.2. Контекст устройства. 204
6.3. Примитивы GDI 204
6.4. Пример вывода текста. 205
6.5. Получение описателя контекста устройства. 216
6.6. Основные инструменты графической подсистемы.. 217
6.7. Закрашивание пустот. 223
6.8. Рисование линий и кривых. 223
6.9. Пример изображения графика функции sin. 225
6.10. Рисование замкнутых фигур. 227
6.11. Функция Polygon и режим закрашивания многоугольника. 229
6.12. Пример отображения линий. 229
6.13. Управление областями вывода и отсечением. 230
6.14. Растровая графика. 233
ЗАДАНИЕ 11. Создание графических изображений. 236
ЛИТЕРАТУРА.. 238
ПРЕДИСЛОВИЕ
Алгоритмический язык Си был разработан в 1972 г. сотрудником фирмы AT&T Bell Laboratory Денисом Ритчи на базе языка В (автор К.Томпсон), который в свою очередь основывался на языке системного программирования BCPL. Первая версия языка была опубликована в книге авторов Б. Кернигана и Д. Ритчи и получила название стандарт K&R. Минимальная стандартная реализация, поддерживаемая любым компилятором, содержала всего 27 ключевых слов. Началось успешное развитие языка и, чтобы избежать путаницы, Американский институт стандартизации (American National Standart Institute) ввел в 1983 г. общий стандарт языка – ANSI-стандарт.
Язык продолжает развиваться, и в 1985 г. появляется язык С++, который в основном сохраняет все черты обычного Си, но дополнен новыми существенными возможностями, которые позволили реализовать объектно-ориентированный стиль программирования.
Язык Си отражает возможности современных компьютеров и обладает следующими достоинствами – это современный, эффективный, переносимый (мобильный), мощный и гибкий, удобный и обладающий рядом присущих ассемблеру управляющих конструкций язык высокого уровня.
Программы на Си отличаются компактностью и быстротой исполнения. Структура языка Си побуждает программиста использовать в своей работе нисходящее программирование, структурное программирование, пошаговую разработку модулей.
Любой язык представляет собой описание определенного набора действий (операции, операторы, функции) над некоторыми данными. Данным, над которыми выполняются эти действия, вместо номеров ячеек в памяти принято давать имена (идентификаторы), а содержимое ячеек называть переменными, или константами, в зависимости от того, изменяется значение в процессе работы или нет.
Под системой программирования понимают совокупность языка программирования и виртуальной машины, обеспечивающей выполнение программ, составленных на этом языке.
Виртуальная машина – это программный комплекс, имитирующий работу реальной машины с определенным входным языком на ЭВМ с другим машинным языком, т.е. реализующий входной язык программирования. Виртуальная машина содержит транслятор и/или интерпретатор и может включать библиотеки стандартных подпрограмм, отладчик, компоновщик и другие сервисные средства.
Трансляторпредставляет собой программу, осуществляющую перевод текстов с входного языка на машинный язык. Одной из разновидностей транслятора является компилятор, обеспечивающий перевод программ с языка высокого уровня (приближенного к человеку) на язык более низкого уровня (близкий к ЭВМ), или машинозависимый язык.
Текст программы, записанный на языке высокого уровня и введенный с помощью клавиатуры в память компьютера, – исходный модуль. Программы, написанные в среде программирования, предназначенной для языка Си, например Turbo C, имеют расширение *.с. Расширение *.cpp имеют программы, написанные в интегрированных средах Borland C++, Visual C++, Builder C++, предназначенных для написания программ как на языке Си, так и на языке С++.
Большинство трансляторов языка Си – компиляторы.
Результат обработки исходного модуля компилятором – объектный модуль(расширение *.obj). На этом этапе компилятор выделяет лексемы (элементарные конструкции языка), затем на основе грамматики распознает выражения и операторы, построенные из этих лексем. При этом компилятор выявляет синтаксические ошибки и, в случае их отсутствия, создает объектный модуль.
Исполняемый (абсолютный, загрузочный) модуль создает вторая специальная программа – «компоновщик». Ее еще называют редактором связей (Linker). Она и создает загрузочный модуль (расширение *.exe) на основе одного или нескольких объектных модулей – это программный модуль, представленный в форме, пригодной для выполнения.
Главным классифицирующим признаком языков и, следовательно, систем программирования, является принадлежность к одному из оформившихся к настоящему времени стилей программирования, основные среди которых – процедурное, функциональное, логическое и объектно-ориен-
тированное.
ГЛАВА 1. Введение в алгоритмы
Этапы решения задач на ЭВМ
Условно программированием можно назвать научную и практическую деятельность по созданию программ. Основной частью программирования является процесс решения задачи на ЭВМ, который можно разбить на следующие этапы:
1) математическая или информационная формулировка задачи;
2) выбор численного или иного метода решения поставленной задачи;
3) построение алгоритма решения поставленной задачи;
4) выбор языка программирования и запись построенного алгоритма по его правилам, т.е. написание текста программы;
5) отладка программы – это процесс обнаружения, локализации и устранения возможных ошибок;
6) выполнение программы, т.е. получение требуемого результата.
Рассмотрим более подробно некоторые наиболее важные из приведенных этапов.
Понятие алгоритма
Понятие алгоритма занимает центральное место в современной математике и программировании.
Алгоритмизация – сведение задачи к последовательным этапам действий так, что результаты предыдущих действий используются при выполнении последующих.
Рассмотрим вначале некоторые наиболее важные (фундаментальные) понятия программирования.
1. Действие – это некоторая операция, имеющая конкретную продолжительность и приводящая к совершенно конкретному результату.
2. Каждое действие предполагает наличие некоторых данных, над которыми это действие совершается и по изменению состояния которых определяют результат этого действия.
3. Каждое действие должно быть таким, чтобы его можно было описать при помощи какого-либо языка (или набора формул); такое описание называют инструкция.
4. Если действие можно разложить на составные части, то его называют процессом(или вычислением).
5. Описание характера проведения процесса, т.е. последовательности выполняемых действий без привязки к какому-то конкретному процессору, называют алгоритмом.
Числовой алгоритм – детально описанный способ преобразования числовых входных данных в выходные при помощи математических операций. Существуют нечисловые алгоритмы, которые используются в экономике, технике и научных исследованиях.
В общем, алгоритм – строгий и четкий набор правил, определяющий последовательность действий, приводящих к достижению поставленной цели.
Свойства алгоритмов
Дискретность– значения новых величин (данных) вычисляются по определенным правилам из других величин с уже известными значениями.
Определенность(детерминированность)– каждое правило из набора однозначно, а сами данные однозначно связаны между собой, т.е. последовательность действий алгоритма строго и точно определена.
Результативность (конечность) – алгоритм решает поставленную задачу за конечное число шагов.
Массовость – алгоритм разрабатывается так, чтобы его можно было применить для целого класса задач, например, алгоритм вычисления определенных интегралов с заданной точностью.
Сложность алгоритма
Выполнение любого алгоритма требует определенного объема памяти компьютера для размещения данных и программы, а также времени по обработке этих данных – эти ресурсы ограничены и, следовательно, правомочен вопрос об эффективности их использования. Таким образом, в самом широком смысле понятие эффективности связано со всеми вычислительными ресурсами, необходимыми для работы алгоритма.
Однако обычно под «самым эффективным» понимается алгоритм, обеспечивающий наиболее быстрое получение результата, поэтому рассмотрим именно временнýю сложность алгоритмов.
Время работы алгоритма удобно выражать в виде функции от одной переменной, характеризующей «размер» конкретной задачи, т.е. объем входных данных, необходимых для ее решения. Тогда сравнительная сложность задач и может оцениваться через ее размер.
Поскольку описание задачи, предназначенной для решения посредством вычислительного устройства, можно рассматривать в виде слова конечной длины, представленной символами конечного алфавита, в качестве формальной характеристики размера задачи можно принять длину входного слова. Например, если стоит задача определения максимального числа в некоторой последовательности из n элементов, то и размер задачи будет n, поскольку любой вариант входной последовательности можно задать словом из n символов.
Временная сложность алгоритма – это функция, которая каждой входной длине слова n ставит в соответствие максимальное (для всех конкретных задач длиной n) время, затрачиваемое алгоритмом на ее решение.
Различные алгоритмы имеют различную временную сложность и выяснение того, какие из них окажутся достаточно эффективны, а какие нет, определяется многими факторами. Однако для сравнения эффективности алгоритмов был предложен простой подход, позволяющий прояснить ситуацию. Речь идет о различии между полиномиальными и экспоненциальными алгоритмами.
Полиномиальным называется алгоритм, временнàя сложность которого выражается некоторой полиномиальной функцией размера задачи n. Алгоритмы, временнáя сложность которых не поддается подобной оценке, называются экспоненциальными.
Задача считается труднорешаемой, если для нее не удается построить полиномиального алгоритма. Это утверждение не является категорическим, поскольку известны задачи, в которых достаточно эффективно работают и экспоненциальные алгоритмы. Примером может служить симплекс-метод, который успешно используется при решении задач линейного программирования, имея функцию сложности f(n) = 2n. Однако подобных примеров не очень много, и общей следует признать ситуацию, когда эффективно исполняемыми можно считать полиномиальные алгоритмы с функциями сложности n, n2 или n3.
Например, при решении задачи поиска нужного элемента из n имеющихся в худшем варианте сложность равна n; если же оценить среднюю трудоемкость (продолжительность поиска), то она составит (n+1)/2 – в обоих случаях функция сложности оказывается линейной n.
Сложность задачи вычисления определителя системы n линейных уравнений с n неизвестными характеризуется полиномом 3-й степени. Повышение быстродействия элементов компьютера уменьшает время исполнения алгоритма, но не уменьшает степень полинома сложности.