 |
алгоритмизация и программирование 1 глава
|
|
|
|
высшего профессионального образования
«Северо-Кавказский федеральный университет»
Непретимова Е. В., Корнеев П.К., Ионисян А.С.
алгоритмизация и программирование
Учебное пособие
Ставрополь
Печатается по решению
редакционно-издательского совета
Северо-Кавказского федерального
университета
Непретимова Е. В., Корнеев П.К., Ионисян А.С. Алгоритмизация и программирование: Учебное пособие. – Ставрополь: Издательство Северо-Кавказского федерального университета, 2014.– 183 с.
Пособие соответствует государственному образовательному стандарту дисциплины «Информатика» раздел «Программирование» специальности 010400 –физика, а также может быть использовано при преподавании дисциплины «Алгоритмизация и программирование» для студентов специальности 010100 - математика и дисциплины «Информатика» специальности 010500 - прикладная математика и информатика.
В учебном пособии изложены основные положения алгоритмизации и программирования, вводятся и иллюстрируются примерами основные управляющие конструкции, типы данных, функции на примере языка программирования С/С++. Уделено внимание типам данных, определяемым программистом: одномерные, двумерные, динамические массивы, структуры, файлы. Кроме того, показаны особенности программной реализации решения задач обработки текстовой информации, алгоритмов решения задач внутренней сортировки и поиска данных, а также рекурсивных алгоритмов. Приводится большое количество задач для самостоятельного решения, причем задачи не привязаны к конкретному языку программирования, компилятору или среде.
Предназначено для студентов физико-математических специальностей СКФУ. Может быть использовано учителями информатики при обучении программированию учащихся старших классов.
|
|
|
Содержание
Предисловие. 6
1. Основные понятия алгоритмизации и программирования. 8
1.1. Этапы решения задач на ЭВМ... 8
1.2. Основы алгоритмизации. 10
1.3. Теоретические основы программирования. 18
1.4. Правила записи в С++ арифметических выражений. 19
Лабораторная работа № 1 Запись арифметических выражений. 21
2. Программирование алгоритмов линейной структуры.. 24
2.1. Общая характеристика языка программирования С++. 24
2.2. Основные понятия языка. 24
2.3. Данные и способы их организации. 27
2.4. Стандартные простые типы данных. 29
2.5. Структура программы.. 32
2.6. Операторы.. 35
2.7. Организация ввода/вывода данных. 36
Лабораторная работа № 2 Программирование алгоритмов линейной структуры.. 43
3. Операторы ветвления. 52
3.1. Простые и составные условия. 52
3.2. Составной оператор. 53
3.3. Условная операция (?:) 54
3.4. Условный оператор if. 54
3.5. Оператор switch. 57
3.6. Оператор перехода goto. 58
Лабораторная работа № 3 Программирование алгоритмов разветвляющейся структуры.. 60
4. Циклы.. 68
4.1. Оператор цикла с параметром (for) 69
4.2. Оператор цикла с предусловием (while) 70
4.3. Оператор цикла с постусловием (do while) 71
4.4. Вложенные циклы.. 72
Лабораторная работа № 4 Программирование алгоритмов циклической структуры.. 74
5. Подпрограммы.. 83
5.1. Понятие подпрограммы.. 83
5.2. Формальные и фактические параметры.. 83
5.3. Локальные и глобальные переменные. 84
5.4. Функции. 86
Лабораторная работа №5 Использование функций для решения прикладных задач. 89
6. Итерация и рекурсия. 93
6.1. Понятие итеративного процесса. 93
6.2. Понятие рекурсии. 93
Лабораторная работа №6 Программирование рекурсивных алгоритмов. 95
7. Одномерные массивы.. 102
7.1. Понятие структурированного типа данных. 102
7.2. Понятие и описание типа массив. 102
7.3. Одномерные массивы.. 103
7.4. Основные действия над элементами массивов. 104
|
|
|
Лабораторная работа №7 Использование числовых одномерных массивов. 107
8. Двумерные массивы.. 112
Лабораторная работа №8 Двумерные массивы.. 116
9. Алгоритмы решения задач внутренней сортировки и алгоритмы поиска информации. 121
9.1. Сложность алгоритмов. 121
9.2. Постановка задачи поиска. 122
9.3. Последовательный (линейный) поиск. 122
9.4. Бинарный поиск. 123
9.5. Постановка задачи сортировки данных. 123
9.6. Прямые и быстрые методы внутренней сортировки. 124
9.7. Сортировка вставками. 125
9.8. Сортировка с помощью прямого выбора. 126
9.9. Сортировка с помощью прямого обмена. 127
Лабораторная работа № 9 Задачи сортировки и поиска. 128
10. Указатели и массивы.. 129
10.1. Понятие статической и динамической переменной. 129
10.2. Указатели. 129
10.3. Взаимосвязь между массивами и указателями. 130
10.4. Порядок объявления динамических массивов. 133
10.5. Передача массивов в качестве параметров функции. 133
Лабораторная работа №10 Применение массивов и указателей для решения прикладных задач 136
11. Особенности работы с функциями. 144
11.1. Способы передачи параметров в функцию.. 144
11.2. Передача имен функций в качестве параметров. 145
11.3. Перегрузка функций. 146
Лабораторная работа № 11 Исследование способов работы с функциями. 148
12. Строки как массив элементов типа char. 153
12.1. Способы представления строк в СИ; реализация некоторых типовых операций над строками 153
12.1. Основные функции Си для работы со строками. 156
Лабораторная работа № 12 Обработка символьных массивов. 157
13. Строки как объект специального класса string. 162
13.1. Описание строк в С++ и типовые операции над ними. 162
13.2. Основные функции класса string для работы со строками. 163
Лабораторная работа № 13 Программирование задач на обработку данных строкового типа 165
14. Структуры.. 168
14.1. Порядок объявления и инициализации структур. 168
14.2. Программирование с использованием структур. 169
14.3. Использование функций для работы с производными типами данных. 170
Лабораторная работа № 14 Применение структур для решения прикладных задач. 172
Контрольные вопросы.. 176
15. Файлы.. 177
15.1. Подход с использованием возможностей языка Си. 177
15.2. Подход с использованием возможностей языка С++. 180
Лабораторная работа № 15 Исследование методов доступа к файлам данных. 182
|
|
|
Литература. 184
Приложение 1 Порядок выполнения лабораторных работ. 185
Приложение 2 Базовые функции. 186
Предисловие
Существует достаточно света для тех, кто хочет видеть, и достаточно мрака для тех, кто не хочет.
Блез Паскаль (1623 - 1662)
Язык программирования Си (англ. C – третья буква латинского алфавита) разработанный в 1969 - 1973 годах сотрудниками Bell Labs Кеном Томпсоном и Деннисом Ритчи как развитие языка Би (B – вторая буква латинского алфавита) предназначался для реализации операционной системы UNIX, но, впоследствии, был перенесён на множество других платформ. Благодаря близости по скорости выполнения программ, написанных на Си, к языку ассемблера, этот язык получил широкое применение при создании системного программного обеспечения (ПО) и прикладного ПО для решения широкого круга задач. Язык программирования Си оказал существенное влияние на развитие индустрии ПО, а его синтаксис стал основой для таких языков программирования как C++, C# и Java.
В конце 1970-х годов Си начал вытеснять Бейсик с позиции ведущего языка для программирования микрокомпьютеров. В 1980-х годах он был адаптирован для использования в IBM PC, что привело к резкому росту его популярности. В то же время Бьёрн Страуструп и другие в лабораториях Bell Labs начали работу по добавлению в Си возможностей объектно-ориентированного программирования. Язык, который они в итоге сделали, C++, оказал большое влияние на разработку ПО, но так и не смог сравняться по популярности с Си, особенно в UNIX-подобных системах.
В 1983 году Американский национальный институт стандартов (ANSI) сформировал комитет для разработки стандартной спецификации Си. По окончании этого процесса в 1989 году он был утверждён как «Язык программирования Си» ANSI X3.159-1989. Эту версию языка принято называть ANSI C или C89. В 1990 году стандарт ANSI C был принят с небольшими изменениями Международной организацией по стандартизации (ISO) как ISO/IEC 9899:1990.
ANSI C сейчас поддерживают почти все существующие компиляторы.
После стандартизации в ANSI спецификация языка Си оставалась относительно неизменной в течение долгого времени, в то время как C++ продолжал развиваться. Однако в конце 1990-х годов стандарт подвергся пересмотру, что привело к публикации ISO 9899:1999 в 1999 году. Этот стандарт обычно называют «C99». В марте 2000 года он был принят и адаптирован ANSI.
|
|
|
8 декабря 2011 опубликован новый стандарт для языка Си (ISO/IEC 9899:2011).
Язык программирования Си отличается минимализмом. Авторы языка хотели, чтобы программы на нём легко компилировались с помощью однопроходного компилятора, чтобы каждой элементарной составляющей программы после компиляции соответствовало весьма небольшое число машинных команд, а использование базовых элементов языка не задействовало библиотеку времени выполнения. Однопроходный компилятор компилирует программу, не возвращаясь назад, к уже обработанному тексту. Поэтому использованию функции и переменных должно предшествовать их объявление. Код на Си можно легко писать на низком уровне абстракции, почти как на ассемблере. Иногда Си называют «универсальным ассемблером» или «ассемблером высокого уровня», что отражает различие языков ассемблера для разных платформ и единство стандарта Си, код которого может быть скомпилирован без изменений практически на любой модели компьютера. Си часто называют языком среднего уровня или даже низкого уровня, учитывая то, как близко он работает к реальным устройствам. Однако, в строгой классификации, он является языком высокого уровня.
Си создавался с одной целью: сделать более простым написание больших программ с минимумом ошибок по правилам процедурного программирования, не добавляя на итоговый код программ лишних накладных расходов для компилятора, как это всегда делают языки очень высокого уровня, такие как Бейсик.
Одним из последствий высокой эффективности и переносимости Си стало то, что многие компиляторы, интерпретаторы и библиотеки других языков высокого уровня часто написаны на языке Си.
Многие элементы Си потенциально опасны, а последствия неправильного использования этих элементов зачастую непредсказуемы. Керниган говорит: «Си — инструмент, острый, как бритва: с его помощью можно создать и элегантную программу, и кровавое месиво». В связи со сравнительно низким уровнем языка многие случаи неправильного использования опасных элементов не обнаруживаются и не могут быть обнаружены ни при компиляции, ни во время исполнения. Это часто приводит к непредсказуемому поведению программы. Иногда в результате неграмотного использования элементов языка появляются уязвимости в системе безопасности. Необходимо заметить, что использования многих таких элементов можно избежать.
|
|
|
Язык программирования C++ произошёл от Си. Однако в дальнейшем Си и C++ развивались независимо, что привело к росту несовместимости между ними. Редакция C99 добавила в язык несколько конфликтующих с C++ особенностей. Эти различия затрудняют написание программ и библиотек, которые могли бы нормально компилироваться и работать одинаково и в Си и в C++, что, конечно, запутывает тех, кто программирует на обоих языках.
Бьёрн Страуструп, придумавший C++, неоднократно выступал за максимальное сокращение различий между Си и C++ для создания максимальной совместимости между этими языками. Противники же такой точки зрения считают, что так как Си и C++ являются двумя различными языками, то и совместимость между ними не так важна, хоть и полезна. Согласно этому лагерю, усилия по уменьшению несовместимости между ними не должны препятствовать попыткам улучшения каждого языка в отдельности [1].
В данном учебном пособии, несмотря на то, что решаются задачи, не выходящие за рамки процедурного программирования, рассматривается язык программирования С++. Тем не менее, пособие не ориентировано на конкретную среду программирования, однако при выполнении заданий лабораторных работ целесообразно реализовывать свои программы в более современных и наиболее распространенных на рабочих местах системах программирования. Это существенно облегчит дальнейшее изучение языка и приведет к большей профпригодности.
1. Основные понятия алгоритмизации и программирования
1.1. Этапы решения задач на ЭВМ
Задачи, решаемые с помощью ЭВМ, можно классифицировать по различным критериям: по типу информации и информационным технологиям, по способу поиска решения (простые и переборные), по характеру целей (задачи оптимизации, управления, обучения, информационного поиска), по функциональному назначению, а также по уровню достижения цели и уровню их решения, в т. ч. по уровню автоматизации этапов их решения.
Задача становится разрешимой, если найдено правило, способ получения результата. В информатике такое правило называют алгоритмом.
Решение задачи на ЭВМ состоит из нескольких этапов, среди которых основными являются следующие:
1. Постановка задачи:
- сбор информации о задаче;
- формулировка условия задачи;
- определение конечных целей решения задачи;
- определение формы выдачи результатов;
- описание данных (их типов, диапазонов величин, структуры и т. п.).
2. Формализация (анализ и исследование задачи, модели, представление ее в виде уравнений, соотношений, ограничений и т.п.):
- анализ существующих аналогов задачи;
- анализ технических и программных средств;
- разработка математической модели;
- разработка структур данных.
Понятие моделирования
При решении задачи обычно исследуют не реальный объект, а его модель.
Модель – искусственно созданный объект, обладающий всеми существенными признаками реального объекта, явления или процесса.
Моделирование – это метод познания, состоящий в создании и исследовании моделей.
Цели моделирования:
1) понять сущность изучаемого объекта;
2) научиться управлять объектом и определять наилучшие способы управления;
3) прогнозировать прямые или косвенные последствия;
4) решать прикладные задачи.
Математическая модель – это система математических соотношений (данных) – формул, уравнений, неравенств и т.д. и отношений между ними, описывающих поведение объекта с некоторой степенью точности и отражающих существенные свойства моделируемого процесса (объекта или явления).
Порядок составления математической модели:
- выделить реальный объект, на котором будет основываться математическая модель, и из множества его свойств, закономерностей, внутренних связей, отдельных характеристик явления и параметров выделяем те, которые являются существенными для решаемой задачи, и отбросить несущественные;
- определить, что считать исходными данными и результатами;
- подобрать математический объект с тем же числом подобных параметров, отражающий суть реального объекта; записать математические соотношения, связывающие результаты с исходными данными.
3. Выбор метода решения.
4. Разработка алгоритма:
- выбор метода проектирования алгоритма;
- выбор формы записи алгоритма (блок-схемы, псевдокод и др.);
- выбор тестов и метода тестирования;
- проектирование алгоритма.
5. Программирование:
- выбор языка программирования;
- уточнение способов организации данных;
- запись алгоритма на выбранном языке программирования.
6. Тестирование, отладка и исправление обнаруженных ошибок:
- синтаксическая отладка;
- отладка семантики и логической структуры;
- тестовые расчёты и анализ результатов тестирования;
- совершенствование программы.
Отладка программы
Отладка программы – это процесс поиска и устранения ошибок в программе, производимый по результатам ее прогона на компьютере.
В современных программных системах отладка осуществляется с использованием специальных программных средств, называемых отладчиками. Эти средства позволяют исследовать внутреннее поведение программы.
Программа-отладчик обычно обеспечивает следующие возможности:
- пошаговое исполнение программы с остановкой после каждой команды (оператора);
- просмотр текущего значения любой переменной или нахождение значения любого выражения, в том числе, с использованием стандартных функций; при необходимости можно установить новое значение переменной;
- установку в программе "контрольных точек", т.е. точек, в которых программа временно прекращает свое выполнение, так что можно оценить промежуточные результаты, и др.
При отладке программ важно помнить следующее:
- в начале процесса отладки надо использовать простые тестовые данные;
- возникающие затруднения следует четко разделять и устранять строго поочередно;
- не нужно считать причиной ошибок машину, так как современные машины и трансляторы обладают чрезвычайно высокой надежностью.
Тест и тестирование программы
Тестирование – это испытание, проверка правильности работы программы в целом либо ее составных частей.
При отладке происходит локализация и устранение синтаксических ошибок и явных ошибок кодирования, в процессе же тестирования проверяется работоспособность программы, не содержащей явных ошибок. Тестирование устанавливает факт наличия ошибок, а отладка выясняет причину неправильной работы программы.
Как бы ни была тщательно отлажена программа, решающим этапом, устанавливающим ее пригодность для работы, является контроль программы по результатам ее выполнения на системе тестов.
Программу условно можно считать правильной, если её запуск для выбранной системы тестовых исходных данных во всех случаях дает правильные результаты. Но, как справедливо указывал известный теоретик программирования Э. Дейкстра, тестирование может показать лишь наличие ошибок, но не их отсутствие. Нередки случаи, когда новые входные данные вызывают "отказ" или получение неверных результатов работы программы, которая считалась полностью отлаженной.
Для реализации метода тестов должны быть изготовлены или заранее известны эталонные результаты. Вычислять эталонные результаты нужно обязательно до, а не после получения машинных результатов. В противном случае имеется опасность невольной подгонки вычисляемых значений под желаемые, полученные ранее на машине.
7. Анализ результатов решения задачи и уточнение математической модели с повторным выполнением этапов 2 - 6 (при необходимости).
8. Сопровождение программы: это работы, связанные с обслуживанием программ в процессе их эксплуатации:
- доработка программы для решения конкретных задач;
- составление документации к решённой задаче, к математической модели, к алгоритму, к программе, к набору тестов, к использованию программы.
1.2. Основы алгоритмизации
Алгоритм – это метод (способ) решения задачи, записанный по определённым правилам, в виде конечной последовательности однозначных предписаний, исполнение которых позволяет с помощью конечного числа шагов получить решение задачи, однозначно определяемое исходными данными из некоторого множества значений.
Свойства алгоритма
1. Дискретность (прерывность, раздельность). Алгоритм должен представлять процесс решения задачи как последовательное выполнение конечного числа простых (или ранее определенных) законченных действий шагов.
2. Понятность для исполнителя — т.е. исполнитель алгоритма должен знать, как его выполнять.
3. Определенность (точность, детерминированность). Каждое правило алгоритма должно быть четким и однозначным, содержать действия над известными данными. Каждое действие должно быть понятно исполнителю (для каждого алгоритма предполагается конкретный исполнитель).
Замечание. Часто под свойством детерминированности алгоритма понимается одновременное выполнение свойств точности и понятности.
4. Результативность (или конечность). Алгоритм должен приводить к решению задачи, получение определенного результата за конечное число шагов.
5. Правильность. Способность алгоритма обеспечить получение именно того результата, который требуется. Неправильность может объясняться неполнотой наших представлений о свойствах объекта или упущением в решении. Для доказательства правильности алгоритма задача часто делится на блоки и правильность доказывается для каждого блока, хотя такая проверка не является полной.
6. Массовость. Алгоритм решения задачи pазpабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
7. Универсальность. Алгоритм должен быть составлен так, чтобы им мог воспользоваться любой исполнитель для решения аналогичной задачи. (Например, правила сложения и умножения чисел годятся для любых чисел, а не для каких-то конкретных.)
8. Эффективность. Выбор алгоритмы, который будет выполнен за минимальное время, с минимальными затратами ресурсов.
Таким образом, исполнитель действует формально, т.е. отвлекается от содержания поставленной задачи, а только строго выполняет некоторые правила, инструкции и вместе с тем получать нужный результат.
Критерии качества алгоритма
1. Связанность. Определяется количеством промежуточных результатов. Чем выше количество промежуточных результатов, тем ниже связанность.
2. Объем алгоритма. Это количество операций или шагов, которые необходимо выполнить, а также сложность этих шагов.
3. Логическая сложность. Определяется количеством ветвлений и циклов.
Порядок выполнения алгоритма
1. Действия в алгоритме выполняются в порядке их записи.
2. Нельзя менять местами никакие два действия алгоритма.
3. Нельзя не закончив одного действия переходить к следующему.
Способы описания алгоритмов
1. Словесно-формульный. Описание алгоритма с помощью слов и формул на естественном языке.
Словесный способ не имеет широкого распространения по следующим причинам:
- такие описания строго не формализуемы;
- страдают многословностью записей;
- допускают неоднозначность толкования отдельных предписаний. «Он встретил ее на поле с цветами».
Пример. Составить алгоритм начисления зарплаты согласно следующему правилу: если стаж работы сотрудника менее 5 лет, то зарплата130 руб., при стаже работы от 5 до 15 лет – 180 руб., при стаже свыше15 лет зарплата повышается с каждым годом на10 руб.
Словесно-формульное описание алгоритма решения задачи:
1. Ввести ST, перейти к п. 2.
2. Если ST<5, то ZP:.=l30, перейти к п. 4, иначе — перейти к п. 3.
3. Если ST <15, то ZP:=180, перейти к п.4, иначе ZP:=180+(ST -15)10, перейти к п. 4.
4. Вывести (отпечатать) значение ZP, перейти к п. 5.
5. Вычисления прекратить.
2. Табличный. Алгоритм представляется в форме таблицы и расчётных формул (физика, химия и т. д.).
3. Структурограмма
4. Синтаксическая диаграмма (формулы Бэкуса-Наура)
5. Псевдокоды. Полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.
Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.
В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд. Однако в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда.
Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.
Примером псевдокода является школьный алгоритмический язык.
Алгоритмический язык – это средство для записи алгоритмов в аналитическом виде, промежуточном между записью алгоритма на естественном (человеческом) языке и записью на языке ЭВМ (языке программирования).
Запись алгоритма решения задачи примера 1 на алгоритмическом языке:
алг зарплата (цел. ST, вещ ZP )
арг ST
рез ZP
нач
если ST<5
то ZP:=150
иначе
если ST<=15
то ZP:=180
иначе ZP:=180+(ST-15)*10
все
все
кон
6. Программный. Описание алгоритма с помощью языков программирования.
7. Графический. Алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.Такое графическое представление называется схемой алгоритма или блок-схемой.
Блок-схема алгоритма представляет собой систему связанных геометрических фигур.
Правила построения блок-схем
1. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа. Для наглядности операции разного вида изображаются в схеме различными геометрическими фигурами.
2. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. Порядок выполнения действий указывается стрелками, соединяющими блоки.
3. В схеме блоки стараются размещать сверху вниз, в порядке их выполнения.
4. Все повороты соединительных линий выполняются под углом 90 градусов.
В таблице приведены наиболее часто употребляемые символы.
| Название | Обозначение и пример заполнения | Выполняемая функция (пояснение) |
| Начало/конец (вход/выход) | 
| Начало или конец программы, вход или выход в подпрограмму |
| Блоки ввода/вывода | 
| Ввод-вывод данных |
| Вывод данных на печатающее устройство | |
| Блок вычислений | 
| Арифметический блок определяет вычислительное действие или последовательность действий |
| Логический блок | 
| Логический блок проверяет истинность или ложность условия и выбирает направления выполнения алгоритма в зависимости от условия. В блоке должны быть указаны вопрос, условие или сравнение, которые он определяет. |
| Предопределенный процесс | 
| Вычисления по стандартной или пользовательской подпрограмме |
| Блок модификации | 
| Выполнение действий, изменяющих пункты алгоритма, начало цикла. Внутри блока записывается параметр цикла, для которого указываются его начальное значение, граничное условие и шаг изменения значения параметра для каждого повторения. |
| Межстраничный соединитель | 
| Указание связи между частями схемы, расположенной на разных страницах |
|
|
|
