Алгоритмизация решения типовых задач и основы программирования на языке высокого уровня. Методические указания к самостоятельной работе студентов (стр. 1 )

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

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАМЫШИНСКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)

Волгоградского государственного технического

университета

КАФЕДРА «ИНФОРМАТИКА»

Алгоритмизация решения типовых

задач и основы программирования

на языке высокого уровня.

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

РПК «Политехник»

Волгоград

2004

УДК 681.3.06

А 15

Рецензент к. т.н.

Алгоритмизация решения типовых задач и основы программирования на языке высокого уровня: Методические указания к самостоятельной работе студентов / Сост. , ; Волгоград. гос. техн. ун-т. – Волгоград, 2004. – 36 с.

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

Методические указания предназначены для студентов специальности 2202 Автоматизированные системы обработки информации и управления (по отраслям).

Ил.10. Библиогр.: 7 назв.

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

Волгоградского государственного технического университета

Ó	Волгоградский государственный технический университет, 2004

СОДЕРЖАНИЕ

Введение........................................................................................................................ 4

Этапы создания программного обеспечения..................................................... 5

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

Анализ (определение спецификаций)................................................................... 6

Проектирование.......................................................................................................... 9

Понятие алгоритма. Свойства и способы описания алгоритма............. 10

Линейные алгоритмы.......................................................................................... 14

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

Разветвленные алгоритмы................................................................................. 15

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

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

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

Алгоритмы обработки последовательностей чисел (значений)............. 19

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

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

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

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

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

Алгоритмы обработки упорядоченных массивов. Поиск элементов в упорядоченном массиве 23

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

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

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

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

Реализация................................................................................................................. 28

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

Сопровождение......................................................................................................... 33

Модификация............................................................................................................ 33

Контрольные вопросы............................................................................................ 34

Список литературы................................................................................................. 35

Цель работы:

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

Введение

Создание программы – процесс сложный. В процессе программирования необходимо особое внимание уделять разработке алгоритмов.

Разработка алгоритма – это один из наиболее сложных этапов решения задачи с использованием ЭВМ, так как ошибки, допущенные при логическом проектировании, обычно влекут за собой ошибки на всех последующих этапах разработки программы. В начале обучения программированию целесообразно не привязываться сразу к какому-либо языку программирования, а научиться разрабатывать алгоритмы, например, с помощью блок-схем или иным аналогичным способом. После такой «чистой» алгоритмизации студентам проще перейти к записи того же алгоритма на определённом языке программирования высокого уровня. В процессе создания программы у студентов возникает проблема, связанная с усвоением специфических понятий, как в области информатики, так и по ряду смежных дисциплин. Одним из путей преодоления возникающих трудностей является практика (решение студентами большого числа задач). Большая часть времени при этом отводится на самостоятельную работу студентов.

Целью данного издания является выработка у студентов основ алгоритмического мышления, а также помощь в самостоятельной работе с учебной и технической литературой. Это издание может быть использовано при подготовке и проведении практических занятий со студентами различных специальностей по теме «Алгоритмизация и программирование». Кроме того, оно будет полезно студентам специальности 2202 – «Автоматизированные системы обработки информации и управления (по отраслям)» при подготовке выпускной работы.

Студенты должны знать:

·  этапы создания программного обеспечения;

·  основные понятия информатики в области алгоритмизации и программирования, такие как модель, алгоритм, алгоритмизация, программа, массив, переменная и т. д.;

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

·  основные структуры алгоритма (важным моментом усвоения основ алгоритмизации является четкое понимание студентами ветвления, циклов и рекурсии).

Студенты должны уметь:

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

·  изменять ветвление и циклы при решении задач (при переходе от модели к алгоритму);

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

·  составлять таблицы трассировки алгоритмов, мысленно совершая действия алгоритма и комментируя их.

Студенты должны понимать, что:

·  изучить язык программирования означает: узнать, как в нем называются те или иные допустимые действия и что при решении задач на ЭВМ можно пользоваться разными методами;

·  одни методы могут быть эффективнее других (например, метод деления пополам обычно эффективнее метода простого перебора).

Этапы создания программного обеспечения

В процессе разработки программ можно выделить следующие основные этапы:

1. Постановка задачи – определение требований к программному продукту.

2. Анализ (определение спецификаций) – осуществление анализа, формальной постановки задачи и выбор методов ее решения.

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

4. Реализация – составление программы на выбранном языке программирования, ее тестирование и отладка.

5. Сопровождение – эксплуатация программного продукта.

6. Модификация – выпуск новых версий программного продукта.

Рекомендуется изучить теоретический материал [3] стр. 12-23, [7] стр. 85-88.

Далее будут рассмотрены эти этапы более подробно.

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

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

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

«Что должна делать программа?», «В чем состоят реальные проблемы, разрешению которых она должна способствовать?», «Что представляют собой входные данные?», «Какими должны быть выходные данные?», «Какими ресурсами располагает проектировщик?».

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

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

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

В результате согласования между заказчиком и исполнителем всех перечисленных вопросов составляют техническое задание в соответствии с ГОСТ 19.201-78, которое служит основанием для дальнейшей работы.

Анализ (определение спецификаций).

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

Данный этап можно разбить на следующие подэтапы:

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

2.  Построение модели задачи (представление объекта, процесса или явления в некоторой форме, представляющей его с необходимой степенью достоверности и подробности).

3.  Выбор метода решения задачи (метод преобразования исходных данных в результат).

4.  Определение ограничений.

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

Константы (постоянные) – это такие данные, которые сохраняют свои значения в процессе решения задачи.

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

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

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

Рис. 1. Классификация данных по структурному признаку.

Простые данные определяют такое отношение: «одно имя – одно значение». К простым данным относят числовые данные (целые, вещественные и т. д.) и нечисловые (символьные, логические и т. д.). Диапазон изменения возможных значений определяется типом данных. Например, диапазон изменения данных логического типа: истина (1), ложь (0).

К структурированным данным применимо другое отношение: «одно имя – много значений». Если все элементы, входящие в такую структуру, однотипны, то такая структура называется однородной, в противном случае – неоднородной.

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

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

Пример 1. Требуется указать из N городов некоторой страны название города с максимальным количеством жителей. Каждый город характеризуют с одной стороны – название города (нечисловые данные), с другой стороны – численность населения города (числовые данные).

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

Таблица 1. Пример неоднородной структуры – запись.

Имя поля	Тип поля	Пример значения
Название города	строковый	Москва
Число жителей	целый	8578676

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

Рекомендуется ознакомиться с понятием данных в [6] стр. 8-9, [5] стр. 78-87, а также проверить себя, выполняя задания из[5] стр. 88.

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

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

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

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

С основными приемами и методами рекомендуется ознакомиться в {5] стр. 68-77, {6] стр. 273-293, {7] стр. 60-76.

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

Рекомендуется выполнить практикум из [6] стр. 24-26.

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

Пример 2. Сделать анализ задачи: По заданным длинам сторон прямоугольника определить его площадь.

Решение: Исходные данные: длины сторон прямоугольника (числовые значения, для которых должны быть заданы диапазон изменения и точность). Математическая абстракция для представления исходных данных – переменные а, b (изменяемые значения).

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

Модель задачи: S = a × b, где a, b – длины сторон, S – площадь прямоугольника.

Метод решения – результат получают перемножением аргументов.

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

Проектирование

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

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

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

Понятие алгоритма. Свойства и способы описания алгоритма.

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

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

Алгоритмизация – процесс составления алгоритмов решения задачи.

Из определения алгоритма выделим его основные свойства:

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

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

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

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

Пример 3. Разработать алгоритм варки картофеля. Рассмотреть алгоритм варки картофеля с точки зрения его свойств.

Решение:

1. Подготовить исходные величины — воду, картофель, соль, посуду (кастрюлю с крышкой для варки), нож.

2. С помощью ножа очистить картофель и промыть его водой.

3. Нарезать картофель для варки.

4. Поместить картофель в кастрюлю.

5. Залить содержимое кастрюли водой.

6. Посолить.

7. Довести воду до кипения.

8. Убавить огонь.

9. Варить картофель до готовности (в течение 20-30 минут).

10. Снять кастрюлю с огня и слить воду.

11. Картофель готов. Процесс прекратить.

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

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

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

Алгоритм обладает свойством массовости, т. к. применим при любых исходных данных: для любого сорта и величины картофеля и для любых кастрюль, ножей и т. п.

Основные способы описания алгоритмов:

1. Словесно-формульное описание алгоритма – описание алгоритма на естественном языке с помощью слов и формул. В примере 3 дано словесно-формульное описание алгоритма варки картофеля.

2. Блок-схема – это графическое описание алгоритма.

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

4. Программа – это запись алгоритма на одном из языков программирования (Pascal, Basic, Си и т. п.).

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

Блок-схема алгоритма представляет собой систему связанных геометрических фигур. Каждая фигура обозначает один этап решения задачи и называется блоком.

На изображение схем алгоритмов существует ГОСТ 19.701-90, согласно которому каждой группе действий ставится в соответствие блок особой формы. Некоторые, часто используемые обозначения приведены в табл. 2.

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

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

Таблица 2. Виды блоков.

Название блока	Обозначение	Назначение блока
действие   Терминатор		Начало, завершение программы или подпрограммы.
Процесс		Обработка данных (вычисления, пересылки и т. п.)
Данные		Операции ввода-вывода
Решение		Ветвления, выбор, итерационные и поисковые циклы
Подготовка		Счетные циклы
Предопределенный процесс		Вызов процедур
Соединитель		Маркировка разрывов линий
Комментарий	---[Комментарий	Пояснения к операциям

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

1. Следование – последовательное выполнение действий.

2. Ветвление – выбор одного из двух вариантов действий.

3. Цикл-пока – повторение действий, пока не будет нарушено условие, выполнение которого проверяется в начале цикла.

Кроме этих структур используют три дополнительные структуры:

4. Выбор – выбор одного варианта из нескольких в зависимости от значения некоторой величины.

5. Цикл-до – повторение некоторых действий до выполнения заданного условия, проверка которого осуществляется после выполнения действий в цикле.

6. Цикл с заданным числом повторений (счетный цикл) – повторение некоторых действий указанное количество раз.

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

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

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

При записи алгоритма с использованием псевдокодов знаки арифметических операций будем обозначать так: +, -, /, *. Знак := (двоеточие и равно) означает операцию присвоения выбранной переменной некоторого значения. Ввод (<список переменных через запятую>) – инструкция ввода данных. Вывод (<список переменных через запятую>) – инструкция вывода данных.

Для каждой из перечисленных выше 6 структур используют свою форму описания. В литературе были предложены несколько вариантов форм псевдокодов. Один из вариантов приведен в табл. 3.

Таблица 3. Основные структуры.

Структура	Блок схема	Псевдокод
1.  Следование		<действие 1> <действие 2>
2. Ветвление		Если <условие> то <действие 1> иначе <действие 2> Все-если
3. Цикл-пока		Цикл-пока <условие> <действие> Все-цикл
4. Выбор		Выбор <код> <код1>: <действие 1> <код2>: <действие 2> … Все-выбор
5. Цикл с заданным числом повторений		Для <индекс>=<n>, <k>, <h> <действие> Все-цикл
6. Цикл-до		Выполнять <действие> до <условие>

Пример 4. Имеются два стакана: в одном из них вода, в другом сок. Требуется поменять содержимое стаканов. Алгоритм решения задачи записать с помощью блок-схемы и с помощью псевдокода. Составить таблицу трассировки.