metod_15.03.04_atppp_oaip_up_2016 (Методические документы)

МИНОБРНАУКИ РОССИИФедеральное государственное бюджетное образовательное учреждение высшегообразования«Московский технологический университет»МИРЭАСОГЛАСОВАНОУТВЕРЖДАЮУчебно-методический советДиректор Института информационныхИнститута информационных технологийтехнологий________________________________________А.С. Зуев«____» ______________ 2016 г.«____» ______________ 2016 г.Учебное пособие по дисциплинеОсновы алгоритмизации и программированиядля направления 15.03.04 Автоматизация технологических процессови производствПрофиль: «Автоматизация технологических процессови производств в промышленности»Авторы доц., к.т.н. Каширская Е.Н., студент Никольская О.С.Москва 2016ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ1. ВВЕДЕНИЕ В ПРОГРАММИРОВАНИЕ1.1. Основные этапы решения задач на ЭВМ: постановка задачи; построение математических моделей; разработка методики решения задач; разработка алгоритма решения задачи; составление программы по разработанному алгоритму; ввод программы в ЭВМ; отладка программы (поиск и исправление ошибок); проведение расчетов по программе; вывод результатов; анализ результатов.При составлении любого вида программы для ЭВМ понятие алгоритмаявляется ключевым.Само слово «алгоритм» означает правило выполнения арифметическихдействий с использованием арабских цифр.В средние века были две враждующие партии, среди приверженцевразличных традиций счета.

Абакисты считали на абаках, алгоритмики жеиспользовали зачатки математической символики.Слово «алгоритм» происходит от латинской формы написания имениматематика IX века Аль-Хорезми, автор учебника арифметики, которыйсформулировал правила выполнения арифметических действий.Первоначально под алгоритмом понимали только правила выполнениячетырех арифметических действий над многозначными числами. В дальнейшемже это понятие стали использовать вообще для обозначенияпоследовательности действий, приводящих к решению поставленной задачи.Будем под алгоритмом решения задачи понимать систему правил,задающих строго определенную последовательность операций, приводящих кискомому результату за конечное число шагов.Итак, алгоритм – это набор инструкций, который описывает, какнекоторое задание может быть выполнено. Первоначально этот терминиспользовался для чисто численных процессов, но в вычислительной техникеон приобрел более широкое значение.Примеры алгоритмов в этом широком смысле встречаются вповседневной жизни: рецепт какого-нибудь блюда можно считать алгоритмом,описывающим процесс приготовления пищи, выкройку – алгоритмомизготовления одежды.

Программы для ЭВМ являются алгоритмами, тольковыраженныминекоторымиспециальнымисредствамиязыкапрограммирования.Пять характеристик алгоритмов:1) вход алгоритма;22) выход алгоритма;3) определенность шагов алгоритма;4) выполнимость шагов;5) конечность.Пример невыполнимого шага: присвоить Х значение, равное наибольшемувещественному числу, меньшему 1.Это невозможно сделать, какое бы значение для Х мы не выбрали, всегдаможно составить большее, добавив к десятичной части числа любую цифру:0,999→0,9994 и т.д.Пример.

Алгоритм сложения столбиком:315+48363Указана последовательность действий, приводящих к результату законечное число шагов. Можно дать точное словесное описание алгоритма:Шаг 1. Ввод – любых двух слагаемых (из класса объектов, к которымприменим алгоритм).Шаг 2. Сложить цифры, стоящие в разрядах единиц; единицы полученногорезультата записать в разряд единиц суммы.Шаг 3.

Сложить цифры, стоящие в разрядах десятков и прибавить к нимединицу, если результат шага 2 не меньше десяти.Шаг 4. То же для разряда сотен и т.д., пока не закончатся разряды слагаемых.Шаг N. Вывод – значение суммы.1.2. Схемы алгоритмовСхема – это графическое изображение алгоритма. При ее построениисодержимое каждого шага алгоритма записывается в произвольной формевнутрь блока, представленного геометрической фигурой.

Порядок выполненияшагов указывается с помощью стрелок, соединяющих блоки.Использование различных геометрических фигур отражает различныйхарактер выполняемых действий.В прямоугольнике (блок вычислений) записываются действия, врезультате которых данные изменяют свои значения.В ромб (блок сравнения) записывают условия, подлежащие проверке сцелью выбора варианта продолжения работы.Параллелограмм (блок ввода-вывода) содержит информацию о входных ивыходных данных.Овал означает начало или окончание вычислительного процесса.Блок сравнения, в отличие от остальных, имеет 2 выхода – “да” и “нет”.Если условие, записанное внутри блока, выполняется, выход из негопроисходит по стрелке “да”, в противном случае – по стрелке “нет”.Наиболее часто употребляемые символы схем алгоритмовПуск (начало), останов (конец)Вычислительные действия, приводящие к изменениюзначения данных (процесс)3Ввод, выводПроверка условия (принятие решения)Вычисления по подпрограмме или стандартнойпрограмме (предопределенный процессПодготовительные операции (задание массива, началоцикла), модификацияПечать на бумагеСоединитель на одной страницеПереход на часть схемы, расположенную на другойстранице (межстраничный соединитель)Ручная операцияДисплейКомментарий1.3.

Линейные алгоритмыЛинейным называется алгоритм, выполнение шагов которого происходитпоследовательно в порядке возрастания их номеров. В схеме он изображаетсяпоследовательностью вычислительных блоков и блоков ввода-вывода.Общий вид линейного участка:- ввод4- вычисления1.4. Разветвляющиеся алгоритмыРазветвляющимся называется алгоритм, в котором предусмотренопрохождение различных вариантов работы в зависимости от выполнения илине выполнения некоторого условия. В блок-схеме это условие записывается вромб-блок сравнения.Общая структура ветвления:даВар «да»УсловиеетВар.

«нет»1.5. Циклические алгоритмыАлгоритм циклической структуры – алгоритм, в котором предусмотреновыполнение одной и той же последовательности действий.Циклом называется участок алгоритма, реализующий многократноповторяющееся при различных значениях параметров однотипные вычисления(например, расчеты по одной и той же формуле), Алгоритм, содержащий цикл,называется циклическим.Циклический алгоритм позволяет существенно сократить объемпрограммы.Для организации цикла необходимо предусмотреть:- задание начального значения параметра цикла – переменной, котораябудет изменяться при повторениях цикла;- изменение значения этой переменной перед каждым новымповторением цикла;- проверку условия окончания повторений по значению параметра ипереход к началу цикла, если повторения не закончены.5Пример. Вычислить сумму: S=12+22+32+…+n2=∑i2 ,где n – заданное число.Предлагается следующий алгоритм решения задачи.Шаг 1. Ввести n.Шаг 2.

Положить S=0 (обнуление ячейки суммы).Шаг 3. Положить i = 1.Шаг 4. Вычислить i2 и прибавит к текущему значению S: обозначение: S=S+i2 .Шаг 5. Увеличить i на 1; обозначение: i = i + 1.Шаг 6. Сравнить i с n; если i < n, вернуться к шагу 4, иначе перейти к шагу 7.Шаг 7. Вывести S.Шаг 8. Останов.Основная повторяющаяся операция: S=S+i2 выполняется при различныхзначениях i.

Величина i называется параметром цикла. В рассмотренномпримере параметр цикла изменяется от начального значения i = 1 до конечногоi = n с шагом 1.Варианты:1) S=12+32+52+…2) S=1*2*3*…*nЗадача. Задача табулирование функции. Требуется построить таблицузначений функции y=f(x) на отрезке [a, b] с шагом h, т.е. вычислить значенияфункции в точках x=a, a+h, a+2h, … , b вывести их на печать.Задача. Составить схему алгоритма вычисления 100 значений функцииy=sin(ax)/x при xi=1,2,3,…,100. Очевидно, что для определения всех значенийфункции y необходимо 100 раз вычислять по этой формуле значения y ипечатать их, изменяя каждый раз аргумент x на единицу.

Цикл долженповторяться, пока x<100. Если х станет больше 100, то будет осуществленвыход из цикла, т.е. переход к следующему по порядку действию.6Пример алгоритма.Вкл.Нетрогайее !Никому неговори!данетЭта штукаработает?нетТы ее трогал?нетОх, и зря тыэто сделал!Кто-нибудь об этомзнает?даТы – самыйнесчастный человек насвете!нетТысможешь свалить винуна кого-нибудьдругого?даКто-нибудь из-заэтого рассердился?нетЗабудь обэтом!даНет проблем!Конец2. ОСНОВНЫЕ ПОНЯТИЯ ЯЗЫКА ПРОГРАММИРОВАНИЯ ПАСКАЛЬЛюбая программа, выполняемая на ЭВМ, обрабатывает данные с цельюполучения требуемого результата. В современных языках программированияимеются базовые типы данных и средств построения структурных типовданных из базовых; они облегчают составление программ для решениясложных задач,однако не избавляют программиста от проблем разработкиалгоритмов и выбора подходящей структуры данных. При разработкеалгоритма выбирается некоторая удобная абстрактная структура данных иалгоритм разрабатывается в терминах операций над этим абстрактным типом7данных.

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

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