Этапы решения технических задач
Этапы решения задачи наЭВМ
Бурное развитиевычислительной техники приводит к широкому проникновению математических методовв науку, технику и народное хозяйство. Происходит интенсивный процессматематизации не только естественных и технических, но и гуманитарных наук. Всеэто расширяет классы задач, решаемых на ЭВМ. Решение на ЭВМ задач каждогокласса имеет свою специфику, однако его можно разбить на несколько этапов,характерных для большинства задач,
Постановка задачи ипостроение алгоритма
Решение задачи начинаетсяс ее постановки, изложенной на языке строго определенных математическихпонятий. Поэтому, чтобы можно было решить задачу, связанную с исследованиемреального объекта, необходимо сначала описать этот объект в математическихтерминах, т. е. построить его математическую модель. Математическая модельобъекта позволяет поставить задачу математически и тем самым свести решениереальной задачи к решению задачи математической. Она, отражая наиболеесущественные свойства реального исследуемого объекта или явления, нетождественна этому объекту, а является лишь приближенным его описанием. В этомсмысле математические модели — те же относительные истины, через посредствокоторых познается реальная действительность с асимптотическим приближением кистине абсолютной. Степень соответствия модели реальному объекту проверяетсяпрактикой, экспериментом. Критерий практики дает возможность оценитьпостроенную модель и уточнить ее в случае необходимости.
Метод математическогомоделирования реальных явлений возник и получил свое развитие в физике.
Так, еще в XVII в. Г.Галилеем была предложена хорошо известная теперь математическая модель,описывающая движение тела, брошенного под углом к горизонту с заданнойначальной скоростью. Первая крупная математическая модель в физике — механикаНьютона.
Внедрение математическихметодов исследования в другие науки также тесно связано с созданиемматематических моделей. Например, такие модели успешно используются дляпрогноза погоды, исследования и предсказания поведения тропических тайфунов ит. п. Созданы модели, прогнозирующие глобальные последствия термоядерногоконфликта, которые играют значительную роль в борьбе за уничтожение ядерногооружия.
Все большее значениеприобретает математическое моделирование в экономике. Созданы, например, моделидля изучения общих закономерностей политической экономии, многоотраслевыемодели общегосударственного планирования, модели, описывающие функционированиеотдельных отраслей и отдельных предприятий.
Успехи применениявычислительной техники во многих областях человеческого знания определяются нетолько развитием метода математического моделирования. Например, созданиемощных информационно-поисковых систем может оказать существенное влияние наметоды научной работы в таких областях, как философия или история, а созданиечеловеко-машинных систем автоматизированного проектирования позволит не толькопо-новому организовать работу конструктора и сократить сроки проектирования, нои значительно сократить сроки и стоимость натурных испытаний и «доводки»разработанных конструкций.
Итак, построениематематической модели приводит к математической постановке реальной задачи.Далее необходимо найти способ решения этой задачи. Очень часто решение такойзадачи не удается получить в явном виде, т. е. в виде формулы, связывающейисходные данные и результаты. В таких случаях решение ищется в виде алгоритма.
Построение алгоритма —следующий этап решения задачи с использованием ЭВМ.
Описанные этапы решениязадачи выполняются человеком и носят творческий характер — каждая новая задачатребует новых подходов и новых способов решения, и этому вряд ли можно научитьдаже анализируя способы решения многих других уже известных задач.
Однако уже этаппостроения алгоритма включает помимо творческих и чисто технологическиевопросы. Используя определенную дисциплину при конструировании алгоритма, можнополучить алгоритм с явно выраженной структурой, что облегчает его понимание идальнейшую работу с ним.
Аналогичная технологияможет быть использована и на последующих этапах — при разработке программы дляЭВМ и работе с этой программой. Конечно, и здесь от человека требуется немалотворчества и изобретательности, тем не менее именно эти этапы решения задачи наЭВМ получили наибольшее технологическое развитие.
Единая технология, применяемая на этапах разработки алгоритма ипрограммы, может значительно облегчить и ускорить общий процесс решения задачина ЭВМ.
ЭВМ никаких решений не принимает. Решение принимает человек, аЭВМ только помогает найти варианты решении. Что же нужно сделать чтобы найтитакие варианты решении? Основные этапы решения задачи проектированиятехнологических установок. Рассмотрим эти этапы.
/>
Выбор задачи. Выбор задачи — важнейший вопрос. Решениезадачи, особенно достаточно сложной, — это очень трудное дело требующее многовремени. И если задача выбрана неудачно, то это может привести не только ксожалению о потерянном времени.
Выбор задачи завершается ее содержательнойпостановкой. Когда выбирается задача и производится ее содержательная постановка,естественно, приходится иметь дело со специалистами в предметной области(по управлению, проектированию, разработке технологических процессов) Этиспециалисты, как правило, очень добросовестные, с одной стороны, прекраснознают свой предмет, с другой — не всегда имеют представление о том, чтотребуется для решения задачи на ЭВМ. Поэтому содержательная постановка задачизачастую оказывается перенасыщенной сведениями, которые совершенно излишни дляработы на ЭВМ.
Поясним сказанное на простом примере. Пусть перед нами стоиттакая задача Требуется определить, сколько у пятилетней девочки Маши, котораяслушает папу, маму, дедушку и бабушку, каждое утро ест манную кашу, говорит«спасибо» и моет руки перед едой, было яблок, если, когда дворник соседнегодома тетя Даша дала ей еще два яблока, у этой чудесной белокурой девчушки, ужевторой год занимающейся фигурным катанием, коллекционирующей марки и поющей вхоре при Доме народного творчества, находящемся в прекрасном здании,построенном по проекту, удостоенному второй премии на республиканском конкурсе,их стало пять.
Вот так достаточно часто выглядит содержательная постановказадачи, сделанная эрудированными специалистами в предметной области, несколькодалекими от знания требований ЭВМ
Элементы теорииалгоритмов
1. Понятие алгоритма исвойства алгоритма
Понятие алгоритмаявляется основным при составлении любого вида программ для ЭВМ. Программадля ЭВМ — алгоритм, оформленный специальным образом, конечнаяпоследовательность предписаний, определяющих процесс переработки входных данныхв выходные.
Слово «Алгоритм» происходит от algorithmi — латинского написания имени аль-Хорезми, под которым в средневековой Европезнали величайшего математика из Хорезма (город в современном Узбекистане)Мухаммеда бен Мусу, жившего в 783-850 гг. В своей книге «Об индийскомсчете» он сформулировал правила записи натуральных чисел с помощьюарабских цифр и правила действий над ними столбиком. В дальнейшем алгоритмомстали называть точное предписание, определяющее последовательность действий,обеспечивающую получение требуемого результата из исходных данных. Алгоритмможет быть предназначен для выполнения его человеком или автоматическимустройством. Создание алгоритма, пусть даже самого простого, — процесстворческий. Он доступен исключительно живым существам, а долгое времясчиталось, что только человеку. Другое дело — реализация уже имеющегосяалгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать всущество дела, а возможно, и не способен его понять. Такой субъект или объектпринято называть формальным исполнителем. Примером формальногоисполнителя может служить стиральная машина-автомат, которая неукоснительноисполняет предписанные ей действия, даже если вы забыли положить в нее порошок.Человек тоже может выступать в роли формального исполнителя, но в первуюочередь формальными исполнителями являются различные автоматические устройства,и компьютер в том числе. Каждый алгоритм создается в расчете на вполнеконкретного исполнителя. Те действия, которые может совершать исполнитель,называются его его допустимыми действиями. Совокупность допустимыхдействий образует систему команд исполнителя. Алгоритм должен содержатьтолько те действия, которые допустимы для данного исполнителя.
Алгоритм— формальное предписание(указание), однозначно определяющее содержание и последовательность операций,переводящих совокупность исходных данных в искомый результат — решениепоставленной задачи.
обычно формулируют несколько общих свойств алгоритмов,позволяющих отличать алгоритмы от других инструкций.
Из определения алгоритмаи рассмотренных примеров можно сформулировать следующие требования к егосвойствам.
Такими свойствами являются:
· Дискретность(прерывность, раздельность) — алгоритм должен представлять процесс решения задачи какпоследовательное выполнение простых (или ранее определенных) шагов. Каждоедействие, предусмотренное алгоритмом, исполняется только после того, какзакончилось исполнение предыдущего.
· Определенность — каждое правилоалгоритма должно быть четким, однозначным и не оставлять места для произвола.Благодаря этому свойству выполнение алгоритма носит механический характер и нетребует никаких дополнительных указаний или сведений о решаемой задаче.
· Результативность(конечность) — алгоритм должен приводить к решению задачи за конечное числошагов.
· Массовость — алгоритм решениязадачи разрабатывается в общем виде, то есть, он должен быть применим длянекоторого класса задач, различающихся только исходными данными. При этомисходные данные могут выбираться из некоторой области, которая называется областьюприменимости алгоритма.
Средства, используемые для записи алгоритмов, в значительнойстепени определяются тем, для какого исполнителя предназначается алгоритм. Если алгоритм предназначен для исполнителя — человека, то егозапись может быть не полностью формализована, на первое местоздесь выдвигаются понятность и наглядность, поэтому для записи таких алгоритмовможет использоваться естественный или графический язык, лишь бы запись отражалавсе основные особенности алгоритма. Для записи алгоритмов, предназначенных дляисполнителей — автоматов, необходима формализация, поэтому в такихслучаях применяют специальные формальные языки.
Словесная запись алгоритма. Словеснаяформа обычно используется для алгоритмов, ориентированных на исполнителя —человека. Команды алгоритма нумеруют, чтобы иметь возможность на них ссылаться.Приведем в качестве еще одного примера словесной формы записи алгоритмаклассический алгоритм Евклида для нахождения наибольшего общего делителядвух натуральных чисел:
Даны два целыхположительных числа m и n. Требуется найти их наибольший общий делитель, т.е.наибольшее положительное число, на которое делится без остатка как m, так и n.
Суть алгоритма Евклидаможно представить следующими тремя этапами.
1. Нахождение остатка.Разделим m на n. Пусть остаток равен г:
0
2. Проверка остатка наравенство нулю. Если г = О, вычисление кончается, n — искомое число.
3. Замена m ← n, n ←г. Повторить этап 1.
Пример
1. Даны m = 125, n = 75. Нашинаибольший общий делитель.
1) 125: 75 = 1. Частноеравно 1, остаток от деления равен 50,
2) Остаток от деления неравен 0. Проводим замену переменных:
m = 75, n = 50 иповторяем процесс,
1) 75: 50= 1, m = 25.
2) m = 50, n = 25, г = 0.
Повторяем процедуру.
1) 50:25= 2.
2) Остаток от деленияравен 0, поэтому n = 25 является наибольшим общим делителем.
2. К отрезку АВ в точке Мвосстановить перпендикуляр. Алгоритм решения этой геометрической задачи можетбыть описан в виде четырех последовательных шагов (рис. 1).
1) Из произвольной точкиО плоскости радиусом ОМ описать окружность, пересекающую отрезок АВ.
2) Отметить точку Спересечения окружности с отрезком АВ,
3) Найти точку Dпересечения окружности с прямой ОС.
/>
Рис. 1. Восстановлениеперпендикуляра к отрезку в данной точке
4) Соединить точку М и D.
Если строго выполнять всепредписания, то будет получен однозначный ответ,
Форма записи команд не формализуется. В командах помимо слов могут использоваться символы и формулы.Важно лишь то, чтобы каждая команда была понятна исполнителю, точно определялавсе его действия и могла бы быть им выполнена.
Для решения задачи можноразработать несколько алгоритмов. Каждый алгоритм создается в расчете навполне конкретного исполнителя. Если планируется реализация алгоритма намашине, следует учитывать его приспособляемость к ЭВМ, простоту и времяреализации на машине. Алгоритм должен быть разработан таким образом, чтобыисполнитель мог даже не вникать в смысл того, что он делает, и вместе стем получать нужные результаты. Исполнение уже имеющегосяалгоритма можно поручить субъекту или объекту, который не обязан вникать всущество дела, а возможно, и не способен его понять.
Описание алгоритма
Правила выполненияарифметических операций или геометрических построений представляют собойалгоритмы.
Указание формулы или последовательностиформул, расчеты по которым нужно выполнить для получения результатов.
Пример
Вычислить объем круглогоконуса. Для вычисления следует воспользоваться формулой
/>
При заданных двухразмерах (r — радиус основания и h — высота конуса) эта формула даетпредписание исполнителю, как действовать, т. е. определены характер ипоследовательность действий.
Представление алгоритма ввиде схемы.
При реализации задачи наЭВМ, особенно в случае написания программ на машинно-ориентированных языках, изадач сложных алгоритмов используются схемы алгоритмов.
Схема алгоритма —графическое представление хода решения задачи.
При выполнении схемалгоритмов и программ отдельные функции алгоритмов и программ (с учетом ихдетализации) отображаются в виде условных графических обозначений — символов(ГОСТ 19.003—80 и ГОСТ 19.002—80). В табл. 1 приведены основные символы,используемые в схемах алгоритмов. Схемы должны быть выполнены в форматах,установленных по ГОСТ 2.301—68.
Такое графическое представление называется схемой алгоритма или блок-схемой.В блок-схеме каждому типу действий (вводу исходных данных, вычислению значенийвыражений, проверке условий, управлению повторением действий, окончаниюобработки и т.п.) соответствует геометрическая фигура, представленная в виде блочногосимвола. Блочные символы соединяются линиями переходов,определяющими очередность выполнения действий. В таблице приведены наиболеечасто употребляемые символы.
При выполнении схемсимволам присваивают порядковые номера. Порядковый номер проставляют слева вверхней части символа в разрыве его контура. Символы соединяются прямымилиниями (линиями потока).
Линии потока должны бытьпараллельны линиям внешней рамки схемы. Направления линий потока сверху вниз ислева направо принимают за основные и, если они не имеют изломов, их можнострелками не обозначать. В остальных случаях направление линии потокаобозначать стрелкой обязательно.
Записи внутри символавыполняются чертежным шрифтом по ГОСТ 2.304—81. Записи внутри символа или рядомс ним должны быть краткими. Символы применяются с учетом выполняемых функций.
Таблица 1. Основныесимволы для схем алгоритмовНазвание символа Обозначение и пример заполнения Пояснение Процесс
/>
Вычислительное действие или
последовательность действий Решение
/> Проверка условий Модификация
/> Начало цикла Предопределенный процесс
/>
Вычисления по подпрограмме,
стандартной подпрограмме Ввод-вывод
/> Ввод-вывод в общем виде Пуск-останов
/>
Начало, конец алгоритма,
вход и выход в подпрограмму Документ
/> Вывод результатов на печать № п/п Графическое изображение элемента Описание элемента
/>1
а
b
Процесс — блок обработки данных, в котором указываются действия, изменяющие значение, форму представления или расположение данных. 2
Данные – блок описания операции ввода/вы-вода данных, для которой не определено конкретное устройство. 3
Решение – блок выбора направления выполнения алгоритма в зависимости от некоторых условий. В результате проверки условия осуществляется выбор одного из нескольких возможных путей.
/>4 · · ·
Границы цикла — символ состоит из двух частей и определяет начало и конец цикла.
/>5
Предопределенный процесс – блок описания процесса из одной или нескольких операций, описанных в отдельном модуле (самостоятельном алгоритме).
/>/>/>/>6
Комментарий – содержит пояснение функции блока, с которым связан.
/>7
Терминатор – обозначает начало и конец алгоритма.
/>8
Линия потока – отображает потоки данных и управления в алгоритме.
/>9
Соединитель – указание связи между прерванными линиями потока, связывающими блоки.
Пример описания алгоритманахождения максимального из трех чисел XI, Х2, ХЗ с помощью схемыалгоритма представлен на рис. 2.
Графический метод описанияалгоритма очень наглядный, но в случае сложного алгоритма схема получаетсягромоздкой и это ее достоинство теряется. Использование схем алгоритмовзначительно упрощает написание программ начинающими программистами.
/> />
Рис. 2 Схемаалгоритма поиска Схема алгоритма Евклида максимального числа из трех чисел
/>
/>