УМП Алгоритмизация и программирование. Алгоритмизация
 Скачать 0.62 Mb.
|
|
МИНИСТЕРСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ДЕЛАМ ГРАЖДАНСКОЙ ОБОРОНЫ, ЧРЕЗВЫЧАЙНЫМ СИТУАЦИЯМ И ЛИКВИДАЦИИ ПОСЛЕДСТВИЙ СТИХИЙНЫХ БЕДСТВИЙ Академия Государственной противопожарной службы АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ Москва 2009 2 УДК 004.4(075.8) ББК 32.973.202-018.2 я73 Б93 Р е ц е н з е н т ы: Доктор технических наук, профессор А. В. Фёдоров Кандидат юридических наук, доцент И.В. Задорожная Бутузов С.Ю., Пранов Б.М., Хабибулин Р.Ш. Б93 Алгоритмизация и программирование. Учебно-методическое посо- бие. – М.: Академия ГПС МЧС России, 2009. − 57 с. Учебно-методическое пособие содержит задания и методику выполнения прак- тических заданий и лабораторных работ по изучению основ алгоритмизации и программирования на языке Visual Basic. Учебно-методическое пособие включа- ет: контрольные вопросы, примеры, задания, которые выполняются с использова- нием персонального компьютера. Использование материалов учебно- методического пособия будет способствовать развитию практических навыков по программированию на языках высокого уровня. Издано в авторской редакции УДК 004.4(075.8) ББК 32.973.202-018.2 я73 © Академия Государственной противопожарной службы МЧС России, 2009 3 Введение Разработка алгоритмических структур и специализированного при- кладного программного обеспечения является важной задачей внедрения информационных технологий в системе Государственной противопожар- ной службы и МЧС в целом. Применение компьютерных программ посто- янно расширяется, оно обеспечивает использование информационно- справочных систем, экспертных программ, инженерных моделей. С ис- пользованием программного обеспечения проводятся анализ эксперимен- тальных данных, математическое моделирование различных процессов для исследования динамики пожара, разработки оптимальных тактических планов действий подразделений пожарной охраны, проектирования по- жарной техники, средств защиты пожарного и т.д. Алгоритмическая подготовка слушателя связана, в первую очередь, с умением самостоятельно разрабатывать алгоритмические структуры, вла- дением методами обработки информации, ее структурирования и оптими- зации представления. Изучение языка программирования необходимо для реализации конкретного алгоритма на компьютере. Таким образом, изуче- ние алгоритмизации и программирования играет важную роль в подготов- ке специалистов по проблемам обеспечения пожарной безопасности. В целях изучения и получения практических навыков программиро- вания используется язык программирования Visual Basic, который дает возможность решать любые современные задачи разработки приложений. Язык Visual Basic представляет собой интегрированную среду разработки — IDE (Integrated Development Environment), в которой имеется набор ин- струментов, облегчающих и значительно ускоряющих процесс разработки готового приложения. Такая реализация языка Visual Basic с полным пра- вом позволяет отнести его к средствам быстрой разработки приложений — RAD (Rapid Application Development). С помощью Visual Basic можно создавать приложения практически для любой области современных компьютерных технологий: специальные приложения, мультимедиа, базы данных, Интернет-приложения. Простота и мощность языка Visual Basic позволили сделать его встро- енным языком для различных приложений. Поэтому в настоящее время знание языка программирования Visual Basic становится необходимостью для современного программиста любого уровня. 4 Раздел 1. Конструирование алгоритмов Практическое занятие 1 Понятия алгоритма и программы Цель занятия: изучение понятия алгоритма, его свойств, форм представления и построения базовых структур алгоритма. Алгоритмом называется формализованное описание последователь- ности необходимых действий компьютера для выполнения какой-либо операции, решения задачи. Алгоритм предназначен для использования при подготовке программы – системы команд для компьютера. Алгоритмы, в соответствии с которыми решение поставленных задач сводится к математическим действиям, называются вычислительными алгоритмами. Примерами вычислительных алгоритмов могут служить ал- горитмы расчетов по различным математическим формулам. Алгоритмы, в соответствии с которыми решение поставленных задач сводится к логиче- ским действиям, называются логическими алгоритмами. Примерами ло- гических алгоритмов могут служить алгоритмы поиска минимального чис- ла, поиска пути на графе, сортировки. Реализация алгоритма за конечное число шагов приводит к решению задачи. Разделение алгоритма решения задачи на отдельные операции - важное свойство алгоритмов, называемое дискретностью. Каждая команда алгоритма должна определять однозначное действие. Такое свойство алгоритмов называется определенностью. Реализация алгоритма должна заканчиваться получением некоторого результата. Это свойство алгоритма называется эффективностью. Конечность алгоритма: алгоритм всегда должен заканчиваться после выполнения конечного числа операций. Массовость алгоритма позволяет, пользуясь одним и тем же алго- ритмом, решать множество однотипных задач, изменяя лишь исходные данные. Алгоритм может быть: - записан на естественном языке (словесная запись); - изображен в виде блок-схемы; - записан на алгоритмическом языке. В блок-схеме алгоритма каждый вид действия отображается на схеме некоторой геометрической фигурой – блоком и дополняется элементами словесной записи (табл. 1.1.). 5 Таблица 1.1 Основные элементы блок-схем алгоритмов № п/п Блок Наименование Содержание 1. Блок вычислений Вычислительные действия или после- довательность действий 2. Логический блок Выбор направления выполнения ал- горитма в зависимости от условия 3. Блок ввода-вывода данных Общие обозначения ввода-вывода данных 4. Начало (конец) Начало или конец алгоритма 5. Соединитель Указание связи между потоками ин- формации в пределах одного листа 6. Межстраничное соединение Указание связи между информацией на разных листах Структура алгоритма - определенный набор блоков и стандартных способов их соединений для выполнения типичных последовательностей действий. Основные структуры: линейные (рис. 1.1, а), разветвляющиеся (рис. 1.1, б), циклические (рис. 1.1, в, г). Ввод А А=В+С А<В В А Начало Тело цикла да нет Условие Действие 2 Действие 1 да Действие 1 Действие 2 а) б) в) Условие нет Условие Тело цикла да нет г) Рис. 1.1. Базовые структуры алгоритмов 6 Линейныминазываются алгоритмы, в которых действия осуществля- ются последовательно друг за другом. Пример 1. Составить блок-схему алгоритма решения задачи: вычислить площадь пожара в виде круга при заданном радиусе (рис. 1.2). Решение. R – радиус, S – площадь пожара. Практические задания 1. Разработать блок-схему алгоритма решения задачи: вычислить ко- личество пожарной техники в двух частях, при этом во второй части тех- ники больше, чем в первой, в 1,1 раза. 2. Разработать блок-схему алгоритма решения задачи: вычислить процент присутствующих на занятии слушателей. Контрольные вопросы 1. Дайте определение алгоритма. 2. Какие существуют формы представления алгоритмов? 3. Объясните понятие "дискретность алгоритма". 4. Назовите основные элементы блок-схем алгоритма и их назначе- ние. 5. Назовите базовые структуры алгоритмов. Начало Ввод R S=π·R 2 Вывод S Конец Рис. 1.2. Блок-схема алгоритма к примеру 1 7 Практическое занятие 2 Разветвляющийся алгоритм Цель занятия: изучение построения разветвляющихся алгорит- мов. Разветвляющимся называется алгоритм, в котором действие выпол- няется по одной из возможных ветвей решения задачи, в зависимости от выполнения условий. В качестве условия в разветвляющемся алгоритме может быть использовано любое понятное исполнителю утверждение, ко- торое может соблюдаться (быть истинно) или не соблюдаться (быть лож- но). Такое утверждение может быть выражено как словами, так и форму- лой. Таким образом, алгоритм ветвления состоит из условия и двух после- довательностей команд. Пример 2. Составить блок-схему алгоритма решения задачи: с датчика темпера- туры последовательно снимаются два показания, осуществить вывод толь- ко положительных значений температур (рис. 1.3). Решение. Т 1 , Т 2 , – показания температурного датчика. да да Начало Ввод Т 1 , Т 2 Вывод Т 1 Конец Т 1 >0 нет Рис. 1.3. Блок-схема алгоритма к примеру 2 Т 2 >0 Вывод Т 2 нет 8 Пример 3. Составить блок-схему алгоритма решения задачи: определить макси- мальное время прибытия пожарных автомобилей из 3 пожарных частей к месту пожара (рис. 1.4). Решение. t 1 , t 2 , t 3 – время прибытия пожарного автомобиля из 1, 2 и 3 пожарной части соответственно. Практические задания 1. Составить блок-схему алгоритма решения задачи: определить средний балл 4 слушателей по результатам контрольной работы. Если средний балл ≥ 3, то вывести сообщение "Контрольная работа написана удовлетворительно". 2. Составить блок-схему алгоритма решения задачи: найти мини- мальное количество пожаров по данным из 2 районов, вычислить разницу. 3. Составить блок-схему алгоритма вычисления значения функции: Начало Ввод t 1 , t 2 , t 3 Вывод t 1 Конец t 1 > t 2 да нет t 1 > t 3 t 2 > t 3 да Вывод t 2 да Вывод t 3 нет Рис. 1.4. Блок-схема алгоритма к примеру 3 при x ≤ 0 при x > 0 y = ⎩ ⎨ ⎧ x x cos sin 2 9 Контрольные вопросы 1. Какой алгоритм называется разветвляющимся? 2. Приведите пример разветвляющегося алгоритма. Практическое занятие 3 Циклический алгоритм Цель занятия: изучение построения циклических алгоритмов. Циклическим называется алгоритм, в котором некоторая часть опера- ций выполняется многократно. Перед операцией цикла осуществляются операции присвоения начальных значений тем объектам, которые исполь- зуются в теле цикла. В цикл входят в качестве базовых следующие струк- туры: блок проверки условия и блок, называемый телом цикла. В качест- ве тела цикла могут выступать линейные, разветвляющиеся или другие циклические структуры, а также сочетание этих структур. Если тело цикла расположено после проверки условий (стр. 6, рис. 1.1, в), то такой вариант называется циклом с предусловием. Организация цикла, когда его тело расположено перед проверкой ус- ловия, носит название цикла с постусловием (стр. 6, рис. 1.1, г). Истин- ность условия в этом случае - условие окончания цикла. Пример 4. Составить блок-схему алгоритма решения задачи: вычислить площадь пожара в виде круга при 10 значениях радиуса (рис. 1.5). Решение. R – радиус, S – площадь пожара. В этой задаче необходимо 10 раз повторить одни и те же действия: - ввод значений переменной R; - вычисление площади по формуле S = π·R 2 ; - вывод полученного в результате значения S. Таким образом, алгоритм решения задачи будет циклическим с из- вестным количеством повторений. 10 В данном случае параметр цикла является счетчиком, определяю- щим, который раз выполняются команды тела цикла. Обозначим его пере- менной i. i = 1, 2, …, 10. Предлагаемая далее задача фактически является частным случаем циклического накапливания суммы. Пример 5. Составить блок-схему алгоритма решения задачи: площадь разлива нефтепродуктов составляет S м 2 , каждый час площадь увеличивается на 5 %. Какая будет площадь разлива через 4 часа (рис. 1.6)? Решение. S – площадь разлива нефтепродуктов в начальный момент времени; 5 % - изменение площади за час. нет Рис. 1.5. Блок-схема алгоритма к примеру 4 Начало Ввод R Конец i ≤ 10 да Вывод S i = 1 S=π·R 2 i = i + 1 11 Алгоритм решения задачи должен иметь циклическую структуру с параметром, где параметр – номер часа. i = 1, 2, 3, 4. Практические задания 1. Составить блок-схему алгоритма решения задачи: вычислить сред- ний балл успеваемости 3 слушателей для 5 значений оценок. 2. Составить блок-схему алгоритма вычисления значения функции: y = ⎩ ⎨ ⎧ + t t sin 1 2 нет да Начало Конец i ≤ 4 i = i + 1 Рис. 1.6. Блок-схема алгоритма к примеру 5 i = 1 S = S + 0,05·S Вывод S при t ≤ 0 при t > 0 для t = -1; -0,9; -0,8; … 0,9; 1. Ввод S 12 3. Составить блок-схему алгоритма решения задачи: на начальный момент времени площадь пожара составляет S м 2 , за минуту она уменьша- ется на 10 %. Через сколько минут площадь пожара станет меньше или равным R м 2 ? Контрольные вопросы 1. Какой алгоритм называется циклическим? 2. Дайте определение цикла с предусловием. 3. Дайте определение цикла с постусловием. 4. Что такое тело цикла? 5. Приведите пример циклического алгоритма. Практическое занятие 4 Операции с одномерными массивами Цель занятия: изучение построения алгоритмов по обработке од- номерных массивов. Массив представляет собой упорядоченную структуру однотипных данных, которые называются элементами массива. Доступ к каждому от- дельному элементу массива осуществляется с помощью индекса – в общем случае порядкового номера элемента в массиве. Каждый элемент массива имеет три характеристики: - имя, совпадающее с именем массива; - индекс – это целое число (или множество целых чисел), однозначно определяющее местоположение элемента в массиве. В качестве индекса может выступать также переменная или арифметическое выражение. Примеры индексов: 3, 15, i, i-1. Индексы принято указывать в скобках после имени массива; - значение. 1 2 3 4 5 6 Пример: массив A = {12; -3; 0; 45; 20; -11} состоит из 6 элементов. А(5) = 20. Здесь А – имя массива, 5 – индекс, 20 – значение. Массивы могут быть числовыми и символьными (текстовыми). На- пример, список слушателей группы – символьный массив, а список оценок по дисциплине – числовой массив. 13 Массивы могут быть как одномерными (адрес каждого элемента оп- ределяется значением одного индекса), так и многомерными (адрес каждо- го элемента определяется значением нескольких индексов). Одномерный массив определяется именем и размером, обозначается А(k), где А – имя массива, k – количество элементов массива. Пример: А(4). Каждый элемент одномерного массива имеет один индекс, равный порядковому номеру элемента в массиве. Пример 6. Составить блок-схему алгоритма решения задачи: найти сумму значе- ний элементов числового массива (рис. 1.7). Решение. А – имя массива, i – счетчик элементов массива, k – количество эле- ментов массива, Sum – сумма значений элементов массива. нет да Начало i = i +1 Конец i < k Sum = 0 Вывод Sum Рис. 1.7. Блок-схема алгоритма к примеру 6 i = 1 Sum = Sum + A(i) 14 Пример 7. Составить блок-схему алгоритма решения задачи: найти отрицатель- ные элементы числового массива (вывести в отдельный массив) (рис. 1.8). Решение. А – имя исходного массива, i – счетчик элементов исходного массива А, k – количество элементов исходного массива А, В – имя массива отрица- тельных элементов, j – счетчик элементов массива В. да нет Начало В(j) = А(i) Конец А(i) < 0 да нет i = 1 Вывод В i = i + 1 i < k Рис. 1.8. Блок-схема алгоритма к примеру 7 j = 1 j = j + 1 15 Практические задания 1. Составить блок-схему алгоритма решения задачи: вычислить сум- му положительных элементов числового массива. 2. Составить блок-схему алгоритма решения задачи: подсчитать ко- личество элементов числового массива, значения которых равны нулю. 3. Составить блок-схему алгоритма решения задачи: найти макси- мальный элемент числового массива. 4. Составить блок-схему алгоритма решения задачи: сложить элемен- ты двух числовых массивов А и В. Результат записать в массив С. 5. Составить блок-схему алгоритма решения задачи: найти среднее значение из отрицательных элементов числового массива. Контрольные вопросы 1. Дайте определение массива. 2. Дайте определение индекса массива. 3. Виды массивов. 4. Запишите, что такое одномерный массив. 5. Приведите пример циклического алгоритма? Практическое занятие 5 Двумерные массивы Цель занятия: изучение построения алгоритмов по обработке дву- мерных массивов. Понятие двумерный массив определим на конкретном примере. Рас- смотрим ведомость: Номер факультета Число выпускников Число медалистов 1 180 8 2 210 10 3 150 5 4 25 1 Ведомость представляет собой множество из 12 числовых элементов, которые расположены в 4 строки по 3 элемента в каждом (3 столбца). Двумерный массив определяется именем, числом строк и столбцов и обозначается: А(n, m), где А – имя массива, n – число строк, m – число 16 столбцов. Данная ведомость обозначается: А(4, 3). Строки двумерных мас- сивов нумеруются по порядку сверху вниз, а столбцы - слева направо. А(1, 1) А(1, 2) А(1, 3) 1 180 8 А(4, 3) = А(2, 1) А(2, 2) А(2, 3) = 2 210 10 А(3, 1) А(3, 2) А(3, 3) 3 150 5 А(4, 1) А(4, 2) А(4, 3) 4 25 1 Каждый элемент двумерного массива определяется номерами строки и столбца, на пересечении которых он находится, и обозначается именем массива с двумя индексами: первый – номер строки, второй – номер столбца. Элементы ведомости, представленной в нашем примере, получат такие обозначения: А(1, 2) = 180, А(2, 3) = 10, А(4, 2) = 25 и т.д. Пример 8. Составить блок-схему алгоритма решения задачи: дан двумерный массив А(n, m). Каждый элемент умножить на 20. Вывести новый массив (рис. 1.9). Решение. А – имя массива, i – счетчик строк, j – счетчик столбцов, n – количест- во строк, m – количество столбцов. нет да Начало i = i +1 Конец j < m j = 1 Вывод A i = 1 A(i, j) = A(i, j)·20 j = j+1 i < n да нет Рис. 1.9. Блок-схема алгоритма к примеру 8 17 Пример 9. Составить блок-схему алгоритма решения задачи: найти сумму значе- ний элементов главной диагонали двумерного массива А(3, 3) (рис. 1.10). Решение. Главной диагональю двумерного массива называют совокупность эле- ментов, имеющих одинаковые индексы (i = j). В данном случае главную диагональ матрицы А(3, 3) составляют элементы А(1, 1), А(2, 2), А(3, 3). Сумма значений элементов главной диагонали матрицы вычисляется по формуле: S = А(1, 1) + А(2, 2) + А(3, 3). А(3, 3) – исходный массив, i – счетчик строк и столбцов, S – сумма значений элементов главной диагонали. Практические задания 1. Составить блок-схему алгоритма решения задачи: найти строчку матрицы в которой находится максимальный элемент. 2. Составить блок-схему алгоритма решения задачи: найти сумму значений элементов последнего столбца матрицы. нет да Начало Конец i < 3 i = 1 Вывод S S = 0 S = S + A(i, i) i = i+1 Рис. 1.10. Блок-схема алгоритма к примеру 9 18 Контрольные вопросы 1. Что называется двумерным массивом? 2. Приведите пример двумерного массива. Задачи для самостоятельного решения 1. Составить блок-схему алгоритма решения задачи: найти разность наибольшего и наименьшего значений элементов числового массива. 2. Составить блок-схему алгоритма решения задачи: найти произве- дение значений всех ненулевых элементов числового массива. 3. Составить блок-схему алгоритма решения задачи: найти количест- во отрицательных элементов числового массива. 4. Составить блок-схему алгоритма решения задачи: все отрицатель- ные элементы числового массива заменить на ноль. 5. Составить блок-схему алгоритма решения задачи: найти номер ми- нимального элемента числового массива. 6. Составить блок-схему алгоритма решения задачи: найти среднее значение элементов числовой матрицы. 7. Составить блок-схему алгоритма решения задачи: вычислить сум- му значений положительных элементов в каждой строке матрицы. 8. Составить блок-схему алгоритма решения задачи: вычислить про- изведение значений элементов главной диагонали матрицы. 9. Составить блок-схему алгоритма решения задачи: найти номер столбца с минимальным значением элемента числовой матрицы. 10. Составить блок-схему алгоритма решения задачи: вычислить ко- личество отрицательных и положительных элементов матрицы. |