Общие сведения об алгоритмизации

Тема Общие сведения об алгоритмизации

 

 

 

1. Понятия алгоритма и алгоритмизации

 

Алгоритм − это строго определенная последовательность действий (команд),  выполнение которой над исходными данными задачи приводит к получению результата.

Т.о. алгоритм представляет собой  последовательность действий, которая необходима для решения задачи. 

 

Слово «алгоритм» произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ал-Хорезми (Alhorithmi), жившего в 783—850 гг. В своей книге "Об индийском счете" он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними «столбиком», знакомые теперь каждому школьнику. В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.

 

Исполнитель алгоритма  – это объект или субъект, для управления которым составлен алгоритм.

В качестве исполнителей могут быть как живые существа, так и технические устройства. В частности, автоматическим исполнителем алгоритмов по обработке информации является компьютер.

 

Правила построения алгоритма

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

- выделяются величины, являющиеся исходными для задачи;

- процесс решения задачи  разбивается на этапы, которые  будут выполнены однозначно без всяких пояснений;

- указывается порядок  выполнения этапов;

- указывается признак  окончания процесса решения задачи;

- указывается, что  является результатом решения  задачи.

 

Алгоритмизация − раздел информатики, изучающий методы, приемы построения алгоритмов и их свойства.

Существует и другое толкование термина «алгоритмизация».

Алгоритмизация − это процесс построения алгоритма решения задачи, результатом которого является выделение этапов процесса обработки данных, формальная запись содержания этих этапов и определение порядка их выполнения.

 

 

2. Свойства алгоритма

 

Из определения алгоритма  вытекают следующие его свойства:

• Дискретность алгоритма – это свойство, которое означает, что решение задачи, записанное в виде алгоритма, разбито на отдельные простейшие команды, которые расположены в порядке их выполнения.
• Определенность алгоритма – это свойство означает, что каждая команда алгоритма должна быть понятна исполнителю, не оставлять места для ее неоднозначного толкования и неопределенного исполнения.
• Результативность алгоритма – это свойство алгоритма, состоящее в том, что он всегда приводит к результату через конечное число шагов.
• Массовость алгоритма - это свойство заключается в том, что каждый алгоритм, разработанный для решения некоторой задачи, должен быть применим для решения задач этого типа при всех допустимых значениях исходных данных.    

 

 

 

3. Способы записей алгоритмов

 

Существует несколько  способов описания алгоритмов:

 

1. Словесно-формульное описание алгоритма, т.е. описание алгоритма с помощью слов и формул.
2. Графическое описание алгоритма, т.е. описание с помощью специальных графических схем алгоритмов – блок-схем. Описание данного способа далее будет рассмотрено более подробно. 
3. Запись алгоритма на одном из языков программирования (на языках Pascal, Basic, Delphi и т.д.).

 

 

 

4. Состав схемы алгоритма

 

Блок-схема алгоритма  представляет собой систему связанных  геометрических фигур.

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

 

 

№	Наименование этапа	Изображение	Примечание
1	Прерывание		Начало и конец алгоритма.
2	Передача данных		Ввод или вывод информации (имеет один вход и один выход).
3	Процесс		Арифметический блок, определяющий действие, которое необходимо выполнить (имеет один вход и один выход).
4	Принятие решения		Логический блок, проверяющий истинность или ложность некоторого условия (имеет один вход и два выхода).

 

 Рассмотрим более подробно блок проверки некоторого условия:

Если условие выполняется –  выходим из блока по выходу Да, если условие не выполняется  - по выходу Нет.

 

 

Рассмотрим пример, в  котором алгоритм составляется в  виде блок-схемы.

 

Задача: 

Составить алгоритм начисления зарплаты согласно следующему правилу:

• Если стаж работы сотрудника менее 5 лет, то зарплата 7000 руб.
• Если стаж работы от 5 до 15 лет, то зарплата  10000 руб.
• При стаже работы свыше 15 лет зарплата повышается с каждым годом на 300 рублей.

Сделать графическое  описание алгоритма (в виде блок-схемы).

 

Решение:

Согласно третьему условию задачи (при стаже работе свыше 15), если стаж работы увеличивается на один год, то зарплата увеличивается на 300, если стаж работы увеличивается на два год, то зарплата увеличивается на 2*300 и т.д., таким образом, вырисовывается зависимость (St-15)*300.  

 

Сформулируем задачу в математическом виде.

Введем обозначение: Zp – зарплата, St – стаж работы

 

       

                         

Блок-схема будет иметь  следующий вид:

 

 

 

 

 

 

 

 

 

 

Основные типы алгоритмов

 

В зависимости от особенностей своего построения алгоритмы делятся  на  три основные группы:

1) линейные;

2) разветвляющиеся;

3) циклические.

Любой алгоритм состоит  из фрагментов, и каждый фрагмент представляет собой алгоритм одного  из трех указанных видов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 1. – Классификация  алгоритмов

 

 

 

2. Понятие цикла. Классификация циклов

 

Циклом называется последовательность действий, выполняемых многократно, каждый раз при новых значениях параметров.

Циклический алгоритм – реализует повторение некоторых действий, т.е. включает в себя циклы.

 

Классификация циклов:

Существует несколько  видов циклических инструкций, с  помощью которых можно организовать циклы:

1. Инструкция «цикл с параметром» (цикл с заданным количеством повторений).
2. «Цикл с предусловием» (цикл - «пока»).
3. «Цикл с постусловием» (цикл – «до»).

 

 

3. Составление схем линейных алгоритмов

 

Линейным называется алгоритм, в котором все этапы решения задачи выполняются строго последовательно, т.е. линейный алгоритм выполняется в естественном порядке его написания и не содержит разветвлений и повторений.

 

Рис. 2. – Структура  линейного алгоритма

 

Рассмотрим составление  схем линейных алгоритмов на примере.

 

Пример:

Даны переменные А  и В. Требуется обменять их значения, т.е. переменная А должна получить значение В, а В – значение А.

 

Прежде чем решать данную задачу, давайте подумаем над  решением другой задачи: имеется два стакана. В одном из стаканов – вода, в другом – молоко. Требуется поменять содержимое стаканов. Житейский опыт подсказывает, что нам для решения данной проблемы потребуется еще один стакан. В него мы перельем воду из первого, затем в первый стакан  (из второго) нальем молоко, а из вспомогательного стакана во второй нальем воду.

Аналогично решается и задача обмена значениями двух переменных.

 

Решение:

Согласно условию, исходными  данными являются переменные  А, В. Вводиться вспомогательная переменная, необходимая для обмена значениями двух переменных – переменная k. Данная вспомогательная переменная называется буферной (буфер обмена). На рисунке 3 показана блок-схема алгоритма.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 3. – Блок-схема  алгоритма, реализующего обмен 

значениями переменных 

 

Проверим составленный алгоритм. Для того, чтобы было легче  контролировать значения переменных, составим таблицу значений.

А	В	k
10	3	0
10	3	10
3	3	10
3	10	10

 

Результат работы алгоритма совпадает с ожидаемым. Значит, алгоритм составлен верно. 

 

 

 

 

 

 

5. Составление схем разветвляющихся алгоритмов

 

 

Алгоритм ветвящейся структуры – это алгоритм, в котором выбирается один из нескольких возможных путей (вариантов) вычислительного процесса. Каждый подобный путь называется ветвью алгоритма. 

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

 

Рис. 4. – Структура  ветвящегося  алгоритма

 

 

Рассмотрим составление  схем ветвящихся алгоритмов на примере.

 

Пример 1:

Вычислить значение Y:

Y =

 

Решение:

Согласно условию, если переменная х принимает любое значение меньше 10, тогда у вычисляется по формуле у=х+2; иначе, если х принимает значение 10 или больше 10 – следовательно, у вычисляется по формуле  у=х –2.

Например, х=2 (значение меньше 10), следовательно, у вычисляется по формуле   у=х+2, подставим в эту формулу х=2, получим   у=2+2=4.

Ответ: если х=2 

 тогда  у=4

 

Исходные данные задачи: х

Результат:   Y

 

Алгоритм решения данной задачи будет выглядеть так, как показано на рисунке 5. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 5. – Алгоритм вычисления значения У

 

 

Пример 2:

Найти максимальное из двух чисел X и Y.

 

Решение:

Исходные данные: X и Y.

Результат: max.

Нужно сравнить два числа  и сделать вывод.

 

Алгоритм решения данной задачи будет выглядеть так, как  показано на рисунке 6. 

 

Рис. 6. – Алгоритм нахождения максимального из двух чисел