Основные этапы решения задачи на компьютере. Основы алгоритмизации. Свойства и типы алгоритмов. Линейные, разветвляющийся, циклические и обобщение алгоритмы.
Вопросы, подлежащие разбору: 1. Понятие алгоритма. 2. Свойства алгоритмов. 3. Алгоритмы для вычислений. 4. Способы описания алгоритмов Словесное описание алгоритма Графическое описание алгоритма Советы по составлению блок-схемы Описание на алгоритмическом языке. 5. Основные структуры алгоритмов 6. Алгоритмы линейной структуры. 7. Алгоритмы разветвляющиеся структуры. 8. Алгоритмы циклической структуры
Алгоритм – это одно из наиболее фундаментальных понятий информатики. Термин «алгоритм» своим происхождением обязан имени узбекского математика Мухаммад бен Муса Аль Хорезми, который еще в IX веке сформулировал правила выполнения четырех арифметических действий. Само слово «алгоритм» происходит от латинизированного произношения и написания имени Аль Хорезми, жившего в конце VIII и первой половины IX веков. Его научные трактовки по математике и алгебре (переведенные на латинский язык в XII веке) оказали большое влияние на развитие математики во всем мире. Аль Хорезми впервые сформулировал правила, позволяющие систематически составлять и решать квадратные уравнения.
В математике алгоритм - это точное предписание, задающее вычислительный процесс, или, другими словами, точное изложение последовательности действий над исходными данными, выполнение которых обеспечивает получение искомого результата.
Алгоритм, на основе которого составляется программа решения задачи, представляет собой последовательность действий, которые может вы- полнить ЭВМ. В нем отражаются не только арифметические действия, необходимые для реализации выбранного численного метода, но и логические связи, соотношения, условия, которые численный метод налагает на исходные данные. Алгоритм - это не только описания последовательностей решения различных задач. В форме различных инструкций и правил алгоритмы сопровождают человека во всей его жизни.
Под алгоритмом понимают понятие и точное указание исполнителю совершить последовательность решение поставленной задачи.
Алгоритм должен быть понятен не вообще, а конкретному его исполнителю - человеку или устройству, выполняющему предписанные действия.
Алгоритм и исполнитель После изучения этого пункта следует напомнить: 1. Алгоритм строится в расчете на конкретного исполнителя. 2. Алгоритм детализируется до тех пор, пока станут возможными для выполнения конкретным исполнителем. 3. Исполнение алгоритма не требует рассуждений.
Из этого следует сделать вывод: поручить исполнение алгоритма можно не только человеку, но и машине.
Свойства алгоритмов Алгоритм обладает следующими основными свойствами, раскрываю им и его определение: 1) Детерминированность (однозначность, определенность), которая означает, что набор указаний должен быть понятен, точен и однозначен, т.е. обеспечивать однозначность результата работы алгоритма при заданных исходных данных. 2) Результативность означает, что для любых допустимых исходных данных алгоритм должен через конечное число шагов (или итераций) завершить свою работу и выдать искомый результат решения. 3) Дискретность означает возможность расчленения определенного алгоритмического процесса на отдельные элементарные этапы, возможность выполнения которых человеком или машиной не вызывает сомнения, а результат выполнения каждого элементарного этапа (шага) вполне определен и понятен. 4) Массовость, которая предполагает возможность изменения исходных данных в определенных пределах, т.е. алгоритм должен быть пригоден для решения всех задач данного типа.
5. Свойство точности. Запись алгоритма должна быть такова, чтобы, выполнив очередную команду, исполнитель точно знал, какую команду надо выполнять следующей.
6. Свойство понятностью, для данного исполнителя. Каждый алгоритм строится в расчете на конкретного исполнителя, который должен быть в состоянии выполнить каждую команду алгоритма.
Способы описания алгоритмов Алгоритмы могут быть представлены в виде словесного или графического описания, а также описания на алгоритмических языках
Пример. Требуется записать последовательность элементарных действий для вычислений по формуле: Y=3x/8x+1 При составлении требуемой алгоритмической записи предположим, что правила выполнения арифметических операций сложения, умножения, деления, а также извлечение квадратного корня понятны вычислителю. При этом предположении искомый алгоритм в обычной словесной записи может иметь вид:
1) прочитать заданное значение х; 2) умножить х на 8; 3) из результата второго действия извлечь квадратный корень; 4) к результату третьего действия прибавить 1; 5) умножить х на 3; 6) результат пятого действия разделить на результат четвертого действия; 7) записать значение результата y. Получили словесную запись линейного вычисли- тельного алгоритма.
Ее можно сделать более компактной, если воспользоваться операцией присваивания :=. При этом мы приходим к весьма важному приему, широко используемому в практике алгоритмизации, - использование вспомогательных переменных (букв) для запоминания промежуточных числовых значений. Действительно, возьмем, к примеру, предписание 2: «Умножить х на 8». Выберем переменную «а» для обозначения результата этого действия, тогда само действие с использованием знака присваивания может быть записано значительно короче:
а:=8 х, что означает: умножить текущее значение х на 8 и полученный результат считать впредь значением переменной «а». Используя всюду, где можно, знак присваивания и вводя новые вспомогательные переменные, получим следующее представление приведенного выше алгоритма:
При записи вычислительных алгоритмов удобно использовать специальный знак присваивания := (иногда используют стрелки). Этот знак используется для изображения особой операции - операции присваивания, смысл которой состоит в следующем. Пусть имеется предписание вида В левой части команды присваивания всегда должна стоять переменная. Выражение в правой части в частном случае может быть переменной или числом, например y:=a; x:=12.
1) начало; 2) чтение х; 3) а:= 8 х; 4) b:=а; 5) с:= b+1; 6) d:= 3 х; 7) у:= d/с; 8) запись у; 9) конец.
Графическое описание алгоритма. Графическое описание алгоритма означает представление его в виде граф-схемы, или блок- схемы. Блок-схемой называется наглядное графическое изображение алгоритма, когда отдельные действия (этапы) алгоритма изображаются при помощи различных геометрических фигур (бло- ков), а связь между этапами (последовательность выполнения этапов) указываются при помощи стрелок, соединяющих эти фигуры.
Наиболее часто применяемые обозначения в блок-схемах алгоритмов Символ, название ОбозначениеПояснение Процесс Вычислительные действия или последовательность вычисли- тельных действий Решение Проверка условий Модификация Начало цикла Предопределенный процесс Вычисление по подпрограмме, стандартной подпрограмме Ввод-вывод Преобразование данных в фор- му, пригодную для обработки (ввод) или отображения результатов обработки (вывод)
Символ, название ОбозначениеПояснение Документ Вывод, печать результатов на бумаге Пуск-останов Начало, конец, прерывание процесса обработки данных или выполнения программы Дисплей Вывод данных на дисплей Ручной ввод Ввод данных с клавиатуры Соединитель Указание на связь между прерванными линиями потока, соединяющими символы
Определенный этап вычислений на схеме алгоритма обозначается прямоугольником, внутри которого записывается содержание этого этапа. Проверка условия изображается ромбом, внутри которого записывается это условие. В результате проверки условия, выбирается один из двух возможных путей вычислительного процесса. Если условие выполняется, то следующим реализуется этап по стрелке «да», если условие не выполняется, то осуществляется переход по стрелке «нет». Начало и конец вычислительного процесса изображается фигурой напоминающей овал (7). Внутри нее записывается слова «начало» или «конец».
Пример. Составить блок-схему алгоритма для вычислений по формуле: Y=3x/8x+1 Начало Чтение x a:=8·x b:=a c:=b+1 d:=3·x y:=d/c Запись y Конец
Основные структуры алгоритмов Основные структуры алгоритма - это ограниченный набор блоков и стандартных способов их соединения для выполнения типичных последовательностей действий.
Пример. Вычислить значение y по формуле: Y=(2x+3)/(3x-4)
Чтобы считать, что формула определяет алгоритм решения нашей задачи, необходимо принять некоторые дополнительные соглашения о порядке выполнения действий - например, условиться, что вычисления всегда производятся (с учетом скобок и старшинства операций) последовательно: слева направо, сначала в числителе, а потом в знаменателе.
Приведем словесное описание алгоритма: 1) умножить х на число 2; 2) к результату действия 1 прибавить число 3; 3) умножить х на число 3; 4) из результата действия 3 вычесть число 4; 5) результат действия 2 разделить на результат действия 4.
Такая форма записи алгоритма имеет свои преимущества. Во-первых, в ней явным образом указывается порядок выполнения действий. Во- вторых, она обладает большей универсальностью: словами можно выразить и то, что нельзя записать с помощью формулы.
Используя знак присваивания, и вводя новые вспомогательные переменные b, c и d, получим: 1) a:=2x; 2) b:=a+3; 3) c:=3x; 4) d:=c-4; 5) y:=b/d.
Начало Ввод х Вывод y Конец а:=2·х в:=а+3 с:=3·х d:=c-4 y:=b/d
Алгоритмы, все операторы которых выполняются однократно и последовательно один за другим, называются прямыми, или линейными, алгоритмам и
АЛГОРИТМЫ РАЗВЕТВЛЯЮЩЕЙСЯ СТРУКТУРЫ
На практике редко удается представить схему решения задачи в виде линейной структуры. Часто от каких-либо промежуточных результатов необходимо направлять обработку данных по тому или иному пути. То есть в зависимости от выполнения некоторого логического условия, вычислительный процесс должен идти по одной или другой ветви.
Пример 1. Алгоритм нахождения корней квадратного уравнения ax 2 + bx + c =0
Корни этого уравнения находятся по формуле: X 1,2 =(-b±b 2 -4ac)/(2a)
Порядок вычислений, прежде всего, зависит от того, будет ли численное значение подкоренного выражения D=b 2 -4ac положительным или отрица- тельным. Если D>0, то корни действительные, если D<0 - корни мнимые.
Процесс решения этой задачи можно разделить на следующие этапы: 1) вычисление D=b 2 -4ac; 2) проверка условия D>0 или D<0; 3) вычисление действительных корней, если D>0; 4) вычисление мнимых корней, если D<0.
Рассмотренный процесс решения задачи вклю- чает три арифметических этапа (1, 3, 4) и один логический (2). Арифметические этапы заключаются в прове- дении вычислений по выбранным формулам, а логический - в проверке выполнения условий, определяющих момент перехода к тому участку алгоритма, на котором начинается расчет по нужной формуле.
Составим словесную запись алгоритма решения уравнения ax 2 +bx + c = 0 1) ввод a, b, c ; 2) D := b 2 -4ac 3) если D >0 идти к 5; 4) вывод "Решений нет" идти к 7; 5) x 1,2 =-b 2 ±D 6) вывод x 1, x 2 ; 7) конец.
Блок-схема алгоритма решения квадратного уравнения представлена на рисунке. Как видно из схемы, за вычислением дискриминанта D следует логический оператор сравнения дискриминанта с нулем. В зависимости от результата сравнения дальнейший процесс вычислений должен пойти либо по первой (левой), либо по второй (правой) ветви.
Начало Ввод а,б,с D=b 2 -4ac D>0 x 1 =-b-D/(2a) x 2 =-b+D/(2a) Вывод х 1, х 2 Решений нет Конец Нет Да
Приведенная здесь блок-схема представляет собой графическое описание разветвляющегося алгоритма.
Разветвляющимися алгоритмами называют ал- горитмы с однократным повторением операторов, причем та или иная группа операторов должна или не должна выполняться в зависимости от соблюдения некоторых условий.
При разработке реальных алгоритмов часто возникает необходимость использовать "вложен- ные" управляющие структуры.
Пример. 2. Проиллюстрируем сказанное на простом примере выбора наименьшего из трех заданных чисел. Схема соответствующего алго- ритма изображена на рисунке. Отыскиваемое наименьшее значение обозначим через m.
Словесная запись: 1) начало; 2) ввода a, b, c ; m := a ; 3) если m>b то m:=b ; 4) если m>c то m:=c ; 5) вывод m ; 6) конец
Ввод а,d,с m:=a m>b m:=b m>c m:=c Вывод m
Алгоритмы циклической структуры
Вопросы, подлежащие разбору: 1. Алгоритмы циклической структуры. 2. Подчиненные алгоритмы. 3. Базовые алгоритмические структуры.
При составлении алгоритмов решения практичес- ких задач, нередко возникает случаи, когда приходится неоднократно повторять одни и те же предписания.
Пример 1. Требуется вычислить несколько значе- ний функции y=2x 2 -5 для значений x, начиная с x =1 и с шагом 0,5. Последовательность необходимых для этого действий может быть записана так:
1) x:= 1; 2) y:=2x 2 -5 ; 3) вывод x, y ; 4) x:=x+0,5 ; 5) y:=2x 2 -5 ; 6) вывод x, y ; 7) x:=x+0,5 ; 8) y:=2x 2 -5 и тд.
Желая получить значения функции для последующих значений y, мы должны были бы и дальше записывать абсолютно одинаковые тройки предписаний, таких как, тройки с номерами 2, 3, 4 или с номерами 5, 6, 7 и т.д. Этого можно и не делать, если попытаться предъявить исполнителю одну и ту же тройку предписаний несколько раз. Используем для этой цели предписание безусловного перехода:
1) x:=1 ; 2) y:=2x 2 -5 ; 3) вывод x, y ; 4) x:=x+0,5 ; 5) идти к 2.
Мы получили пример так называемого цикли- ческого алгоритма. В процессе исполнения этого алгоритма быстро устанавливается, что он, по существу, правильно решает поставленную задачу, но обладает существенным недостатком - никогда не приводит к остановке. Такого рода циклы обычно принято называть бесконечными, они не удовлетворяют требованиям, предъявленным к алгоритмическим предписаниям. Недостаток этот, однако, легко устраним. Дополним схему алгоритма логическим блоком так, как показано на рисунке 3, т.е. в каждом "обороте" цикла будем устраивать проверку условия x 10. Как только оно перестанет соблюдаться, процесс прекращается.
1) x:=1 ; 2) y:=2x 2 -5 ; 3) вывод x, y ; 4) x:=x+0,5 ; 5) если x 10 идти к 2; 6) конец.
Полученный алгоритм является типичным приме- ром простого циклического алгоритма с управ- ляемым окончанием.
X:=1 y:=2x 2 -5 x:=x+0,5 x10 Нет Да
Подчиненные алгоритмы
При записи алгоритмов могут использоваться алгорит- мы, составленные раньше. Алгоритмы, целиком, исполь- зуемые в составе других алгоритмов, будем называть, подчиненными алгоритмами или, коротко, подалгоритмами. В принципе не исключено, что алгоритм, содержащий в своем описании подчиненные алгоритмы, сам в определен- ной ситуации может выступить в роли подалгоритма. Составление и использование подалгоритмов находят широкое применение в практике алгоритмизации и являются одним из наиболее значительных и интересных в идейном отношении ее приемов. Действительно, такой подход позволяет исключить при записи алгоритмов повторение тех частей, описания которых уже имеются.
Базовые алгоритмические структуры
Опыт практической алгоритмизации, накопленный в связи с составлением программ для ЭВМ, привел к формированию особой методики структурной орга- низации алгоритмов, использование которой умень- шает вероятность ошибок и модификацию. Эту методику (или, как говорят дисциплину) алгоритми- зации называют структурным подходом.
При структурном подходе к конструированию алгоритмов они как бы "собираются" из трех основных (базовых) структур: развилка, цикл, следование, каждая их которых имеет один вход и один выход.
Развилка состоит из логического элемента с проверкой некоторого условия P и функциональных блоков S1 и S2, которые в простейшем случае являются арифметическими элементами. Развилка может быть двух типов. Первый тип организует выполнение лишь одного из двух указанных действий S1, или S2 в зависимости от справед- ливости условия P : если P истинно, то исполняется S1, в противном случае S2. Этот способ организации действий часто называют выбор или полной условной конструкцией. Словесную запись соответствующего предписания можно оформить так: если Р то S1 иначе S2.
Такое предписание также называется условным переходом. Р S1 S2 Да Нет
Второй тип - это когда альтернативное действие S2 отсутствует (безусловный переход или неполная условная конструкция). В этих случаях используется короткая запись: если P то S1.
Р S1 Да Нет
Базовая структура цикл также может быть двух типов. В состав цикла входит логический элемент с проверкой условия P и функциональный блок S, называемый телом цикла. В простейшем случае S является обычным арифметическим элементом. В первом случае блок S размещен после проверки условия P (цикл с предусловием) так, что может оказаться, что тело S при определенных условиях не выполняется ни разу. Этот вариант базовой структуры цикл, управляемый предусловием, назы- вается цикл-пока.
P S Да Нет
Во втором случае блок S расположен до проверки условия P (цикл с пост-условием) так, что в этом варианте цикла тело S в любом случае будет выполнено по крайней мере один раз. Этот вариант базовой структуры цикл называют цикл-до. Тот или иной вариант структуры цикл используется при составлении алгоритмов в зависимости от особенностей конкретной задачи. Расстановка значений истинности "да" и "нет" в изображении структур циклов, вообще говоря, может быть произвольной. В первом случае тело цикла исполняется пока - условие P истинно; условие P в этой базовой структуре называют условием продолжения цикла. Во втором случае тело цикла исполняется до истинности P, условие P в этой структуре называют условием окончания цикла.
P S Нет Да
Базовая структура следование изображена на рис. Эта структура состоит из двух функциональных блоков S1 и S2, каждый из которых в простейшем случае может быть арифметическим элементом. Структура следование означает, что два функцио- нальных блока могут быть размещены друг за другом.
Алгоритмы сложных структур. При решении сложных задач применяются все выше рассмотренные виды алгоритмов.
Создать алгоритм построения следующей таблицы
j ; Конец
При создании данного алгоритма требуется выполнение повторения в цикле. Повторение выполняется дважды. Одно из них внешнее, второе внутреннее. 1- параметр внешнего повтора (i =1, 3); 2- параметр внутненнего повтора ( j=1,5,2) Цифры при помощи (, ) печатаются после I в одном ряду со следующей зоны; Цифры при помощи ( ; ) печатаются после j в одном ряду сразу После окончания внутреннего повторения, выполняется один цикл внешнего повторения и переходит на следующую строку с помощью безпараметрного оператора печати.
Литература 1. Лобоцкая Н.Л. Высшая математика. Минск, " Вышэйшая школа", Ивашев-Мусатов О.С. Начала математического анализа, Москва "Наука" Персональный компьютер для начинающих /Составители Р. В. Дробышевский, А. П. Лифенко. -Л.: ИМА-пресс, АПН, с. 4. Светозарова Г. И., Мельников А. А., Козловский А. В. Практикум по программированию на языке Бейсик: Учеб. пособие для вузов. -М.: Наука, – 368 с. 5. Информатика с основами программирования: Пособие для студентов медико- биологического профиля /Х. К. Кадыров, Н. Мастибеков и др. -Т.: с. 6. Шафрин Ю. Основы компьютерной технологии: Справочник школьника. М., с. 7. Камилов Ш. М. Информатика: Учебник для лицеев и колледжей. –Т.: Ўқитувчи, с.
Вопросы для укрепления пройденного материала 1. Сколько свойств алгоритма Вы знаете? 2. В каких формах представляется алгоритм 3. Что такое графический алгоритм? 4. В графическом алгоритме прямоугольник что озночает? 5. Укажите способы задания алгоритма 6. По какой формуле определяется производная сложной функции? 7. По какой формуле вычисляется определенный интеграл? 8. Как интегрируются сложные функции?
СПАСИБО ЗА ВНИМАНИЕ ! СПАСИБО ЗА ВНИМАНИЕ !