Рейтинг:  0 / 5

Звезда не активнаЗвезда не активнаЗвезда не активнаЗвезда не активнаЗвезда не активна
 

В повседневной жизни человеку часто приходится применять различные алгоритмы. Можно сказать, что значительная часть жизни заключается в изучении, составлении и выполнении разнообразных алгоритмов. Алгоритм - это описание процесса решения той или иной задачи. Человек часто сталкивается с необходимостью  решения типичных задач, то есть задач, возникающих систематически. Для каждой из них человечество придумало метод (а иногда несколько методов) решения. Этим методам обучают ребенка родители. педагоги в яслях, детском саду, учителя в школе, друзья и знакомые. Как правильно есть кашу, как перейти улицу, как решить квадратное уравнение, как добиться победы в том или ином виде спорта - для решения каждой из этих задач есть свои алгоритмы. В армии даже выпускают сборники алгоритмов - они называются уставами. Исполнение этих алгоритмов является срого обязательним для каждого военнослужащего.

Рецепт решения задачи создается для определенного исполнителя. Это может быть человек (например, караульный, охраняющий военный объект и действующий согласно Уставу караульной службы), механизм (например, кофейный автомат, наливающий в стакан тот или иной вид кофе) или электронное устройство (компьютер). Возможности любого исполнителя ограничены набором тех действий, которые он может выполнять. Может оказаться, что данный исполнитель не может решить поставленную задачу, потому что для него невозможно составить алгоритм. Кофейный автомат не сможет вычислить произведение двух чисел, а принтер вряд ли сможет исполнить налить Вам чашку чая. Иногда сложно определить, сможет ли исполнитель решить данную задачу. Классическим примером невыполнимой задачи является геометрическая задача о делении угла на три равных угла с помощью циркуля и линейки без делений. Исполнителем в этой задаче является комбинации из циркуля и линейки. Однако с помощью линейки и транспортира эта же задача рашается легко.

Проблемы существования алгоритмов решает наука — теория алгоритмов. Она же исследует их свойства.

Исполнителем является компьютер или ЭВМ (электронно-вычислительная машина — термин, уходящий из современного словаря программиста). В дальнейшем мы будем говорить об алгоритмах, составляемых для компьютера.

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

Само слово «алгоритм» возникло из названия латинского перевода книги арабского математика IХ века Аль-Хорезми «Algoritmi de numero Indorum», что можно перевести как «Трактат Аль-Хорезми об арифметическом искусстве индусов». Составление алгоритмов, вопросы их существования являются предметом серьезных математических исследований. Здесь мы познакомимся только с основными понятиями и фактами. касающимися алгоритмизации.

Алгоритм должен отвечать определенным требованиям. Принято выделять следующие четыре условия:

1) однозначность — компьютер «понимает» только однозначные инструкции;

2) массовость — алгоритм предназначен для решения не одной задачи, а целого класс однотипных задач:

3) корректность — алгоритм должен давать правильное решение задачи;

4) конечность — решение задачи должно быть получено за конечное число шагов;

Рассмотрим простейший пример алгоритма: вычисления суммы двух чисел.

Для начала программе нужно считать все необходимые данные. (В нашем случае это 2 числа. Назовем их а и b) Затем программе нужно вычислить значение данной суммы, после чего нужно вывести полученные данные.

Рассматривая данный пример, мы получили алгоритм вычисления суммы двух произвольных чисел:

1)Считать а;

2) Считать b;

3) Выполнить суммирование и запомнить результат в переменное S: S:=a+b;

4) Вывести значение переменной S;

Это пример записи алгоритма на естественном языке, то есть на языке человеческого общения. Мы видим, что формулировка алгоритма не зависит от конкретных значений переменных а и Ь, поэтому его можно применять для решения большого числа сходных задач, вместе составляющих целый класс задач суммирования. Алгоритм описывает действия не над конкретными значениями, а над абстрактными объектами.

Для каждого из шагов можно составить собственный алгоритм. Шаги этих алгоритмов будут содержать более детальные описания. Поэтому говорят, что алгоритм имеет иерархическую структуру. Степень детализации (подробности описания) может оказаться недостаточной для реализации с помощью машинных команд. Тогда процесс пошаговой детализации алгоритма может быть продолжен. Степень детализации зависит от разных обстоятельств, в том числе и от того языка программирования, который предполагается использовать для записи алгоритма. При программировании на языках низкого уровня требуется подробное описание действий, а языки высокого уровня такой подробной детализации не требуют.

Основными объектами программирования являются переменные. Переменные в программе отличаются от переменных, используемых в записи математических формул. Несмотря на сходство терминов, правила использования переменных в программах для компьютера отличаются от правил работы с математическими переменными. Это различие необходимо понять и усвоить. В программировании переменную можно трактовать как одну или несколько физических ячеек оперативной памяти компьютера, которым присвоено определенное имя. Содержимое этих ячеек может изменяться, но имя переменной остается неизменным. В математике значение переменной в рамках определенной задачи неизменно, но меняется в других задачах из данного класса. Именно поэтому конструкция

a=a+1

Воспринимается программистом совершенно естественно (к значению переменной a прибавляется 1), а математик же посчитает его неверным (поскольку, если привести подобные, то получим 0=1) .

Составим алгоритм решения следующей задачи: нахождение максимального значения двух переменных. Для решения этой задачи достаточно сравнить оба значения и в зависимости от результата сравнения вывести на печать наибольшее значение. Таким образом, алгоритм будет выглядеть так:

1. Ввести значение х.

2. Ввести значение у.

3. Если х < у, напечатать у, иначе напечатать х.

В этом алгоритме используются две алгоритмические структуры — линейная последовательность операции (шаги 1, 2) и ветвление (шаг 3, условный оператор).

Алгоритмические структуры описывают последовательность выполнения шагов алгоритма. В линейной последовательности шаги выполняются последовательно, один за другим, без повторений и без вариантов. Алгоритмическая структура "Ветвления называется так потому, что после передачи ей уравнения выполнение алгоритма может пойти по одной из двух (в общем случае — из нескольких) возможных ветвей. То, какая ветвь будет выбрана, зависит от выполнения условия. Линейная последовательность в данном примере состоит из блоков ввода-вывода данных.

Рассмотрим еще один пример составления алгоритма. Пусть необходимо вычислить целую степень числа хn для произвольных значений степени и основания, используя только операцию умножения. Проблема здесь заключается в том, что конкретное значение степени заранее не известно, следовательно, не известно и необходимое количество умножении. Для того чтобы решить эту проблему, введем в алгоритм вспомогательную переменную — счетчик числа выполненных умножении, а степень будем вычислять по рекуррентной формуле:

z0=1, zn=zn-1*x

Запись алгоритма вычисления произвольной целочисленной степени числа приводится ниже.

1. Ввести значения х и n.

2. Присвоить z0 начальное значение 1.

3. Присвоить вспомогательной переменной i начальное значение 0.

4. Присвоить z результат выполнения операции z*x

5. Присвоить значение суммы i +1.

6) Если i<n, перейти к шагу 4, иначе - остановить работу программы.

Этот алгоритм содержит ввод данных (шаг 1), блок вычислений (шаги 2, З), ветвление (шаг 6). а также еще одну алгоритмическую структуру — цикл (шаги 4, 5 и 6). Цикл представляет собой многократно повторяющуюся последовательность операторов и играет в программировании важнейшую роль. Кроме уже перечисленных структур иногда выделяют еще одну — обход, который представляет собой передачу управления, минуя несколько шагов алгоритма.

Для записи алгоритмов мы пользовались естественным языком. Иногда используют полуформальный язык с ограниченным словарем (часто на основе английского языка) — как промежуточный между естественным языком и языком программирования. Такой язык называется псевдокодом. Запись алгоритма на псевдокоде называется структурным планом. Псевдокод удобен тем, что позволяет программисту сосредоточиться на формулировке алгоритма, не задумываясь над синтаксическими особенностями конкретного языка программировання.

При разработке структуры программы удобнее пользоваться записью алгоритма в виде блок-схемы. Для изображения основных алгоритмических структур и блоков на блок-схемах используют специальные графические символы.

 

В некоторых учебниках принято и другое обозначение, но мы будем использовать предыдущее обозначение.

Ну а теперь займемся самым любимым занятием школьников всех времен и народов — решением квадратного уравнения

ах2 + Ьх + с = О .

Будем полагать, что коэффициенты этого уравнения а, Ь и с представляют собой вещественные числа. Простейший случай предполагает, что все коэффициенты отличны от нуля. В зависимости от знака дискриминанта квадратного уравнения

D = b2 — 4ас

возможны три случая:

1. Если D > 0, то имеются два различных вещественных корня, которые можно

вычислить по формулам:

 

2. Если D = 0, то имеется единственный корень (точнее, двукратный корень):

З. Если D < О, вещественных корней нет.

Следует заметить, что данный алгоритм предназначен для решения узкого класса задач квадратных уравнений с «хорошими» коэффициентами. Если допустить, что коэффициенты могут принимать произвольные вещественные значения то, есть опасность, что при определенных значениях коэффициентов (например, при а = 0) возникнет аварийная ситуация (деление на ноль). Качественный алгоритм и качественная программа должны обрабатывать все возможные ситуации. (Хотя бы выдать сообщение о некорректных данных и завершение работы)

Разработанный программистом алгоритм должен давать правильный ответ. Проверка алгоритма может быть непростым делом. В простых случаях такая проверка может быть вьхполнена с помощью заполнения трассировочной таблицы. Каждый столбец трассировочной  таблицы соответствует определенной переменной, а каждая строка — шагу алгоритма. Для заполнения таблицы необходимо шаг за шагом проследить выполнение алгоритма, записывая в таблицу текущие значения выбранных для трассировки переменных. Такой метод позволяет выявить логические ошибки, допущенные при составлении или записи алгоритма, и определить, верен ли окончательный ответ.

Составим алгоритм вычисления суммы натуральных (то есть целых положительных) чисел от 1 до 20. Можно составить простой алгоритм суммирования фиксированного числа слагаемых, однако этот алгоритм недостаточно унивесален. Если изменится количество слагаемых, алгоритм придется переделывать.

Составим алгоритм суммирования произвольного числа (m) слагаемых. Это число должно быть определено в начале выполнения алгоритма, затем должен быть задан и массив значений слагаемых. Для вычисления суммы применим формулу

Здесь m<=n. Эту формулу следует применить несколько раз, положив предварительно S0 = 0. Для многократного выполнения одной последовательности операций применяется цикл.

Рассмотрим более сложную задачу. Пусть необходимо найти все положительные целые числа х и у, удовлетворяющие уравнению х + у = с, где С — целое число. Это можно сделать методом перебора. Интервал перебора — от 1 до с. Для каждой пары целых чисел следует проверить выполнение равенства.

Подумайте, можно ли улучшить этот алгоритм, сократив, например, количество операций?

Обратите внимание на то, что в программировании, как и в математике исключительно важную роль играют алгоритмы. Профессиональный программист и профессиональный математик должны развивать у себя алгоритмическое мышление. Без этого программирование может превратиться в простое и малоэффективное «перетаскивание иконок». Серьезные занятия математикой очень полезны начинающему программисту!