Введение в алгоритмизацию
Понятие алгоритма.
В повседневной жизни, для достижения какой либо цели нам постоянно приходиться сталкиваться с различными правилами, определяющими последовательность действий. Подобные правила очень многочисленны. Например, для того, чтобы позвонить по телефону –автомату нежно выполнить определенную последовательность действий (опустить монету, снять трубку, набрать номер), вычислить результат какой либо функции или решить уравнение. Правила такого рода встречаются нам на каждом шагу, такие правила называют алгоритмами.
Решение любой задачи из любой области в основном представляет собой нахождение правил, то есть последовательности решения, или по другому алгоритма.
Первым свойством алгоритма, является то, что он носит пошаговый(дискретный) характер определяемого им процесса.
Вторым свойством алгоритма является массовость, то есть существует некоторое множество объектов, которые могут служить исходными данными для рассматриваемого алгоритма. Например, для алгоритмов выполнения арифметических операций – сложения, вычитания умножения и деления, такими данными являются все действительные числа.
Например, для того, чтобы сложить два числа 15 и 17 используется алгоритм сложения в столбик.
+17 |
Суть этого алгоритма заключается в поразрядном сложении всех разрядов чисел, а если в результате сумм разрядов получается числа большее 9, то старший разряд полученной суммы переноситься в следующий разряд числа. Если записать последовательность действий, которые мы выполняем при сложении двух то это и будет алгоритм выполнения операции сложения:
- Текущий разряд - крайний правый;
- Складываем значения цифр текущего разряда;
- Если значение суммы больше 9, добавляем единицу при сложении значений следующего разряда;
- Записываем значение правого разряда суммы;
- Если текущий разряд является последним, то сложение завершено, если нет, то текущим разрядом становиться следующий слева;
- Если сложение не завершено, то повторяем начиная со второго пункта.
Попробуем проделать операцию сложения тех же чисел (15 и 17) по представленному алгоритму:
- Текущий разряд - крайний правый (будем складывать 5 и 7);
- Складываем значение цифр текущего разряда 5+7=12;
- Значение суммы больше 9? Да, больше, при сложении значений следующего разряда будим добавлять единицу;
- Записываем значение сумм правого разряда 2;
- Текущий разряд не последний, переходим к следующему разряду;
- Складываем значение цифр следующего разряда 1+1=2 и дописываем единицу, так как значение суммы чисел предыдущего разряда было больше 9: 2+1=3.
- Значение суммы не больше 9, записываем значение суммы чисел разряда 3;
- Этот разряд является последним, поэтому сложение завершено. Получили результат 32.
Заметим, что алгоритм сложения является одним и тем же для любой пары чисел, что и определяет его массовость.
Аналогичным образом можно составить алгоритм умножения, деления, вычитания и так далее.
Третьим свойством алгоритма, является то, что алгоритм должен быть понятен для исполнителя, то есть исполнитель знает как его выполнять. При этом исполнитель алгоритма выполняет «механически». Очевидно, что формулировка алгоритма должна восприниматься однозначно, а следовательно должна быть на столько точна, чтобы полностью определять все действия исполнителя.
Если применять один и тот же алгоритм к одним и тем же исходным данным, то мы всегда должны получать один и тот же результат. Например сколько бы раз мы не складывали числа «15» и «17», всегда будем получать один и тот же результат «32». И если при этом сравнивать результаты на каждом шаге выполнения алгоритма, то они так же будут идентичны. Таким образом можно говорить об однозначности алгоритмов.
Исходя из выше изложенного можно сформулировать определение алгоритма. Алгоритм – это система правил, сформулированная на языке понятном исполнителю и определяющая последовательность действий, в результате выполнения которых, исполнитель придет от исходных данных к конечному результату. Механический характер алгоритм, его определенность и однозначность позволяют в качестве исполнителя использовать не только человек, но и устройства вычислительной техники. Нет разницы, кто является исполнителем, человек или устройства вычислительной техники. Алгоритм остается идентичным, различен лишь язык, на котором формулируются правила.
Последовательность действий, алгоритма называется алгоритмическим процессом, а каждое действие шагом. Число шагов, для достижения результата обязательно должно быть конечно. Кроме того, алгоритм должен обладать свойствами массовости, определенности и однозначности.
Для любой задачи может как существовать несколько алгоритмов решения, так и не существовать ни одного. Так для подсчета количества зрителей на трибунах стадиона существует как минимум два алгоритма, первый это посчитать всех зрителей отдельно, а второй подсчитать количество зрителей в секторе и умножить на количество секторов. Или для поиска простого числа (числа, которое можно разделить нацело только на себя и на единицу) пока не существует алгоритма (если не учитывать перебор), и задача древности об удвоении куда (с помощью циркуля и линейки требуется построить куб, объем которого в два раза больше исходного объема куба), так же не существует алгоритма.
Существует три основных вида шагов алгоритмов это:
1. действие(процесс) – выполнение какой либо операции, например вычисление суммы a=15+17 или положить монету в телефон автомат или набрать номер телефона, эти операции называются шагами действия – требуется что либо сделать.
2. условие(развилка) – сравнение каких либо исходных данных и определение на основе результата сравнения дальнейших действий, например если после набора номера телефон, по которому вы звонили занят, то появляется шаг условия повторить или нет, если повторить, то следует повторно набрать номер, а если нет, то перестать звонить.
3. повтор(цикл) – повторение каких либо операций, до тех пор, пока не выполнится какое либо условие, например – набирать номер телефона до тех пор, пока не дозвонитесь.
Одним из важнейших условий, которое должно выполняться для любого алгоритма - это возможность быстрого восприятия и анализа его другим человеком. Например в области вычислительной техники это необходимо, для однозначного восприятия информации человеком, производящим ввод алгоритма в устройства вычислительной техники. Кроме того, если исполнителем алгоритма является человек, то информация алгоритма также должна быть воспринята однозначно. Психологически человек лучше воспринимает графическую информацию о последовательности и сути действий, чем текстовое описание тех же самых действий. Для удовлетворения этого условия была разработана специальная система графических изображений процессов, выполняемых в алгоритме их взаимосвязей. Эта система получила название блок-схема, а процесс перевода алгоритма в графическую последовательность – построение блок-схемы.
Основным назначение блок-схем является однозначная передача информации от одного человека другому, то есть если цепочка от разработчик алгоритма до исполнителя имеет промежуточные звенья, например: алгоритм разрабатывает специалист в области математики, а исполнителем является устройство вычислительной техники, и при этом разработчик алгоритма(как чаще всего бывает), не знает языка, понятного данному устройству (поскольку элементы вычислительной техники достаточно разнообразны, они встречаются в компьютерах, телефонах, телевизорах, микроволновых печах и т.д., причем в основном каждое устройство говорит на своем языке), то для ввода алгоритма в это устройство используется специалист, переводящий математические формулы на язык устройства вычислительной техники(кодер) и для его однозначного понимания алгоритма и правильного перевода оптимальным представлением алгоритма является его графическое изображение, тое есть блок-схема. Основные элементы блок-схем приведены в таблице 15.
Таблица 15.
Основные элементы графического изображения алгоритма.
Элемент | Назначение |
Начало алгоритма, говорит о том, что с этой точки начинается процесс решения какой-либо задачи. | |
Завершение алгоритма, говорит о том, что в этой точке процесс решения задачи завершен. | |
Ввод исходных данных, говорит о том, что здесь необходимо заменить символическое представление переменных, используемых в алгоритме, конкретными исходными данными. | |
Вывод результатов, говорит о том, что здесь необходимо прочитать результаты работы алгоритма. | |
Выполнение шага, говорит о том, что здесь необходимо выполнить какое либо действие предусмотренные в алгоритме на данном шаге. | |
Условие, говорит о том, что дальнейшие шаги алгоритма определяются тем, что выполнится условие или нет. |