Процессор электронно-вычислительной машины, это чудо техники, умеет, тем не менее, выполнять лишь простейшие команды. Каким же образом компьютер решает сложнейшие задачи обработки информации? Для решения этих задач программист должен составить подробное описание последовательности действий, которые необходимо выполнить центральному процессору компьютера. Составление такого пошагового описания процесса решения задачи называется алгоритмизацией, а алгоритмом называется конечный набор правил, расположенных в определенном логическом порядке, позволяющий исполнителю решать любую конкретную задачу из некоторого класса однотипных задач. В разных ситуациях в роли исполнителя может выступать электронное или какое-либо иное устройство или человек (например, военнослужащий, охраняющий склад боеприпасов и действующий согласно алгоритмам, записанным в устав караульной службы).
Само слово алгоритм возникло из названия латинского перевода книги арабского математика IX века Аль-Хорезми Algoritmi de numero Indorum, что можно перевести как Трактат Аль-Хорезми об арифметическом искусстве индусов. Составление алгоритмов и вопросы их существования являются предметом серьезных математических исследований. Здесь мы познакомимся только с основными понятиями и фактами, касающимися алгоритмизации.
Алгоритм должен удовлетворять определенным требованиям. Принято выделять следующие семь:
Наличие ввода исходных данных.
Наличие вывода результата выполнения.
Однозначность (компьютер понимает только однозначные инструкции).
Общность -алгоритм предназначен для решения некоторого класса задач.
Корректность -алгоритм должен давать правильное решение задачи.
Конечность -решение задачи должно быть получено за конечное число шагов.
Эффективность -для решения задачи должны использоваться ограниченные ресурсы компьютера (процессорное время, объем оперативной памяти и т. д.).
Если речь идет о составлении алгоритмов для процессора ЭВМ (электронно-вычислительной машины), исполнителем является процессор. Упрощенная модель процессора содержит устройство считывания данных, стек (специальную оперативную память небольшого объема, предназначенную для временного хранения данных) и арифметическое устройство, которое может выполнять арифметические действия.
Предположим, что программа, составленная для такого процессора, содержит числовые данные и символы арифметических действий над этими данными. Вот пример такой программы, предназначенной для вычисления суммы двух чисел 2 и 3:
2, 3, +
Проследим выполнение этой программы. Первая операция — считывание в стек значения 2. Затем в стек считывается второе значение (3). Первое значение при этом сдвигается во вторую ячейку памяти. Третий шаг выполнения программы — вычисление суммы двух считанных значений (они называются операндами). Результат этой операции — значение 5 — записывается в первую ячейку стека.
Мы рассмотрели пример простейшей программы. Она является записью алгоритма решения некоторого класса задач — задач вычисления суммы двух чисел. Обозначим эти числа a и b. Тогда алгоритм можно записать следующим образом:
Считать число a.
Считать число b.
Выполнить суммирование c := a + b.
Вывести число c.
Это пример записи алгоритма на естественном языке, то есть на языке человеческого общения. Мы видим, что формулировка алгоритма не зависит от конкретных значений переменных a и b, поэтому его можно применять для решения достаточно большого числа сходных задач, вместе составляющих целый класс задач суммирования. Алгоритм описывает действия не над конкретными значениями, а над абстрактными объектами.
Основными объектами программирования являются переменные. Переменные в программе отличаются от переменных, используемых в записи математических формул. Несмотря на сходство терминов, правила использования переменных в программах для компьютера отличаются от правил работы с математическими переменными. Это различие необходимо уяснить. В программировании переменную можно трактовать как одну или несколько ячеек оперативной памяти компьютера, которым присвоено определенное имя. Содержимое этих ячеек может меняться, но имя переменной остается неизменным. В математике значение переменной в рамках определенной задачи неизменно, но меняется в других задачах из данного класса. Именно поэтому конструкция
a := a + 1
воспринимается программистом совершенно естественно, а уравнение
a = a + 1
математик сочтет неверным. В первом случае имеется в виду вычисление суммы содержимого ячейки a и числовой константы 1 и занесение полученного результата в ту же ячейку a. Второй случай равносилен неверному тождеству 0 = 1.
Составим алгоритм решения следующей задачи. Пусть заданы два значения, x и y. Необходимо сравнить эти значения и напечатать имя большей переменной. Для решения этой задачи достаточно сравнить оба значения и в зависимости от результата сравнения вывести на печать символ x или символ y:
Ввести значение x.
Ввести значение y.
Если x y, то напечатать y, иначе напечатать x.
В этом алгоритме используются алгоритмические структуры — линейная последовательность операций и ветвление (шаг 3, условный оператор). Последняя структура называется так потому, что после передачи в нее управления выполнение алгоритма может пойти по одной из двух возможных ветвей. То, какая ветвь будет выбрана, зависит от выполнения условия. Линейная последовательность в данном примере состоит из блоков ввода/вывода данных.
Рассмотрим еще один пример составления алгоритма. Пусть необходимо вычислить целую степень числа xn для произвольных значений степени и основания, используя только операцию умножения. Проблема здесь заключается в том, что конкретное значение степени заранее неизвестно, следовательно, неизвестно и необходимое количество умножений. Чтобы решить эту проблему, введем в алгоритм вспомогательную переменную — счетчик числа выполненных умножений, а степень будем вычислять по рекуррентной формуле:
z0 = 1,
zn = zn-1x x.
Запись алгоритма вычисления произвольной целочисленной степени числа приводится ниже:
Ввести значения x и n.
Переменной z присвоить начальное значение 1.
Вспомогательной переменной i присвоить начальное значение 0.
Переменной z присвоить результат выполнения операции zx x.
Переменной i присвоить значение i + 1.
Если i n, то перейти к шагу 4, иначе остановить работу программы.
Этот алгоритм содержит ввод данных (шаг 1), блок вычислений (шаги 2, 3), ветвление (шаг 6), а также еще одну алгоритмическую структуру — цикл (шаги 4, 5 и 6). Цикл представляет собой многократно повторяющуюся последовательность операторов и играет в программировании важнейшую роль. Кроме уже перечисленных структур иногда выделяют еще одну — обход, который представляет собой передачу управления с пропуском нескольких шагов алгоритма.
Для записи алгоритмов мы пользовались естественным языком. Иногда используют полуформальный язык с ограниченным словарем (часто на основе английского языка), промежуточный между естественным языком и языком программирования. Такой язык называется псевдокодом. Запись алгоритма на псевдокоде называется структурным планом. Псевдокод удобен тем, что позволяет программисту сосредоточиться на формулировке алгоритма, не задумываясь над синтаксическими особенностями конкретного языка программирования.
Для разработки структуры программы удобнее пользоваться записью алгоритма в виде блок-схемы (в англоязычной литературе используется термин flowchart). Для изображения основных алгоритмических структур и блоков на блок-схемах используют специальные графические символы. Они приведены на рис. 1.1.
Составим алгоритм вычисления квадратного корня из произвольного положительного вещественного числа x методом Герона и запишем его на естественном языке, а также в виде блок-схемы. Напомню (см. Учебник, урок 1), что метод основан на многократном применении формулы
zn+1=½*(zn+x/zn)
при
z0 = 1.
Числовая последовательность z n в пределе при n сходится к искомому значению. Мы, разумеется, не сможем устремить нашу последовательность к бесконечности, поэтому примем самое простое (но не самое верное!) решение — выполним только 5 итераций метода, считая, что при этом будет достигнута достаточно хорошая точность. Обычно десяти итераций метода Герона более чем достаточно для достижения хорошей точности расчета. На рис. 1.2 приводятся оба варианта записи алгоритма.
Рис. 1.2. Алгоритм вычисления квадратного корня методом Герона: слева — блок-схема, справа — запись алгоритма на естественном языке
Ну а теперь займемся самым любимым занятием школьников всех времен и народов — решением квадратного уравнения:
ax2 + bx + c = 0.
Будем полагать, что коэффициенты этого уравнения a, b и c представляют собой вещественные числа. Простейший случай предполагает, что все коэффициенты отличны от нуля. В зависимости от знака дискриминанта квадратного уравнения
D = b2 — 4ac
возможны три случая:
1.Если D 0, то имеются два различных вещественных корня, которые можно вычислить по следующим формулам:
2.Если D = 0, то имеется единственный корень (точнее, двукратный корень): x=-b/2a.
3. Если D 0, то вещественных корней нет.
Блок-схема алгоритма приведена на рис. 1.3.
Рис. 1.3. Блок-схема упрощенного алгоритма решения квадратного уравнения
Следует заметить, что приведенный алгоритм предназначен для решения узкого класса задач квадратных уравнений с хорошими коэффициентами. Если допустить, что коэффициенты могут принимать произвольные вещественные значения, есть опасность, что при определенных значениях коэффициентов (например, a = 0) возникнет аварийная ситуация (деление на ноль). Качественный алгоритм и качественная программа должны быть устойчивыми, то есть при любых входных параметрах завершение работы программы должно быть нормальным, хотя, возможно, и сопровождаться предупреждающим сообщением о некорректности входных данных. Свойством устойчивости обладает алгоритм решения квадратного уравнения, приведенный на рис. 1.4.
Разработанный программистом алгоритм должен давать правильный ответ. Проверка алгоритма может оказаться непростым делом. В простых случаях такая проверка может быть выполнена с помощью заполнения трассировочной таблицы. Каждый столбец такой таблицы соответствует определенной переменной, а каждая строка одному шагу алгоритма. Для заполнения таблицы необходимо шаг за шагом проследить выполнение алгоритма, записывая в таблицу текущие значения выбранных для трассировки переменных. Такой метод позволяет выявить логические ошибки, допущенные при составлении или записи алгоритма, и определить, верен ли окончательный ответ.
Составление алгоритма решения задачи Полет снаряда
Рассмотрим задачу вычисления траектории снаряда, двигающегося в поле притяжения Земли недалеко от ее поверхности (рис. 1.5). Это -постановка задачи, первый этап разработки программы. Замечу, что первоначальная формулировка задачи может быть самой общей, без задания конкретных условий движения снаряда.
Второй шаг выбор или разработка математической модели. На этом этапе важно выявить те факторы, которые определяют поведение системы (в нашем случае — движение снаряда) и определить, действием каких факторов можно пренебречь. Мы будем считать, что движение снаряда определяется полем тяготения. Сопротивлением воздуха, притяжением других планет Солнечной системы, наличием деформаций ствола орудия и плохим настроением командира расчета (сказываются последствия отмечавшегося накануне дня рождения) можно пренебречь. Можно считать также, что поверхность Земли на расстоянии полета снаряда плоская, поле притяжения не изменяется, а снаряд не имеет геометрических размеров, но имеет вполне определенную массу. Анализ влияния различных факторов на полет снаряда можно продолжать, он занял бы не одну страницу, но мы на этом остановимся и перейдем к математической формулировке модели. Для этого напишем уравнения, описывающие движение снаряда, то есть зависимость его координат x и y от времени t, прошедшего с момента выстрела:
УРОК № 1
