Алгоритмизация вычислений Понятие алгоритма такое же основополагающее для информатики, как и понятие информации. Название "алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783—850 гг. В своей книге "Об индийском счете" он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними "столбиком", знакомые теперь каждому школьнику. В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе. Алгоpитм — заранее заданное понятное и точное пpедписание возможному исполнителю совеpшить определенную последовательность действий для получения решения задачи за конечное число шагов. ^ Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом. В информатике универсальным исполнителем алгоритмов является компьютер.Основные свойства алгоритмов следующие: 1. Понятность для исполнителя — исполнитель алгоритма должен понимать, как его выполнять. Иными словами, имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма. 2. Дискpетность (прерывность, раздельность) — алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов). 3. Опpеделенность — при выполнении алгоритма с одним и тем же набором исходных данных всякий раз должен получаться один и тот же результат. 4. Pезультативность (или конечность) состоит в том, что за конечное число шагов алгоpитм либо должен пpиводить к pешению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов. 5. Массовость означает, что алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными. Пpи этом исходные данные могут выбиpаться из некотоpой области, котоpая называется областью пpименимости алгоpитма. На практике наиболее распространены следующие формы представления алгоритмов: словесная (запись на естественном языке); графическая (изображения из графических символов); псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.); программная (тексты на языках программирования). ^ Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Словесный способ не имеет широкого распространения, так как такие описания: строго не формализуемы; страдают многословностью записей; допускают неоднозначность толкования отдельных предписаний. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление называется схемой алгоритма или блок-схемой. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. В таблице приведены наиболее часто употребляемые символы. ^ Название символа Обозначение и пример заполнения Пояснение Процесс Вычислительное действие или последовательность действий с присваиванием вычисленного значения переменной Решение Проверка условия и выбор одного из двух возможных путей дальнейшей реализации алгоритма Модификация Начало цикла с параметром Предопределенный процесс Вызов подпрограммы Ввод данных Ввод значений переменных с клавиатуры Пуск-останов Начало, конец алгоритма, вход и выход в подпрограмму Документ Вывод результатов на печать Блок "процесс" применяется для обозначения действия или последовательности действий, изменяющих значение, форму представления или размещения данных. Для улучшения наглядности схемы несколько отдельных блоков обработки можно объединять в один блок. Блок "решение" используется для обозначения переходов управления по условию. В каждом блоке "решение" должны быть указаны вопрос, условие или сравнение. Блок "модификация" используется для организации циклических конструкций. Внутри блока записывается параметр цикла, для которого указываются последовательно слева направо его начальное значение, конечное значение и шаг изменения значения параметра. Блок "предопределенный процесс" используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращений к библиотечным подпрограммам. Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых элементов. Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл. Характерной особенностью базовых структур является наличие в них одного входа и одного выхода. Базовая структура "следование". Образуется последовательностью действий, следующих одно за другим: Базовая структура "ветвление". Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура ветвление существует в четырех основных вариантах: 1. если—тогда 2. если—тогда—иначе 3. выбор 4. выбор—иначе Базовая структура "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов представлены в таблице: Цикл типа «для» Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне. Цикл с предусловием Цикл с постусловием Цикл типа «пока» Предписывает выполнять тело цикла до тех пор, пока выполняется условие. ^ Типовые алгоритмы Линейный алгоритмЗадача. Составить алгоритм вычисления значения функции y = a * sin (x) для произвольных значений x и a, вводимых с клавиатуры. Значение х задано в градусах. При вычислении значения функции sin(x) необходимо использовать значение x в радианах. Для перевода x из градусов в радианы используем формулу x= x * 3.14/180Блок-схема алгоритмаДанный алгоритм содержит только базовые алгоритмические структуры «следование». Такие алгоритмы называются линейными.Разветвленный алгоритм^ Задача. Составить алгоритм вычисления действительных корней квадратного уравнения y=ax2 + bx + c. Значения a, b, c вводятся с клавиатуры. Дискриминант квадратного уравнения d вычисляется по формуле d=(b2-4ac). Если d>=0, то корни уравнения вычисляются по формулам x1=(-b+d), x2=(-b-d), иначе выполняется остановка и на экран выводится сообщение о тои, что действительных корней не существует.^ Блок-схема алгоритма d >=0данетДанный алгоритм содержит кроме базовых алгоритмических структур «следование» еще структуру «ветвление». Такие алгоритмы называются разветвленными.Разветвленный алгоритм со структурой «выбор-иначе»^ Задача. Составить алгоритм программы, имитирующей работу калькулятора. С клавиатуры вводятся 2 числа a и b и код операции k: k=1 соответствует операции сложения ( r:=a+b );k=2 соответствует операции вычитания ( r:=a-b );k=3 соответствует операции умножения ( r:=a*b );k=4 соответствует операции деления ( r:=a/b . Вычисляется результат выполнения операции либо выводится сообщение о невозможности выполнить операцию деления, если введено значение b=0 и k=4.^ Блок-схема алгоритма b =0Циклический алгоритм Задача. Составить алгоритм вычисления значений функции y = 10 * sin (x) на интервале изменения x, равном [a,b] в n равноотстоящих точках. Значения a, b, n вводить с клавиатуры. Значение функции вычисляется сначала в точке a, затем в точке a+dx, затем в точке a+2*dx и т.д., где dx= (b-a)/(n-1).Блок-схема алгоритма. Используется цикл с параметром. Параметром цикла является переменная i-номер расчетной точки .Блок-схема алгоритма. Используется цикл с предусловием. Блок-схема алгоритма. Используется цикл с постусловием.