Раздел 3. Программирование

3.1. Алгоритмы

Алгоритм и его свойства. Слово алгоритм происходит от латинского написания имени выдающегося математика IX века аль-Хорезми (настоящее имя ученого из города Хорезма – Мухаммед Бен Муссу), который сформулировал правила записи арабских чисел и выполнения арифметических операций над ними в столбик. Под алгоритмом понимают точное предписание, определяющее последовательность действий, обеспечивающую достижение требуемого результата из исходных данных. Создание алгоритма, пусть даже самого простого, – процесс творческий. Он доступен исключительно живым существам. Другое дело – реализация уже имеющегося алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно, и не способен его понять. Такой субъект или объект принято называть формальным исполнителем. Примером формального исполнителя может служить стиральная машина-автомат, которая неукоснительно исполняет предписанные ей действия, даже если вы забыли положить в нее порошок. Человек тоже может выступать в роли формального исполнителя, но в первую очередь формальными исполнителями являются различные автоматические устройства, и компьютер в том числе.

Любой реализуемый алгоритм должен обладать следующими свойствами:

• дискретность;

• определенность (детерминированность);

• результативность (конечность);

• массовость.

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

Виды и представление алгоритмов. Существует несколько классификаций алгоритмов. Мы рассмотрим только те алгоритмы, с которыми работает компьютер: линейный, разветвляющийся и циклический. Если все команды алгоритма идут строго друг за другом (за первой командой – вторая, за второй – третья и т.д.), то такой алгоритм называется линейным.

Разветвляющийся алгоритм содержит условие. Условие – это утверждение, которое может быть истинным или ложным (например, 5>4 – истинное утверждение, 6=9 – ложное утверждение). В зависимости от того истинное условие или ложное выполняется та или другая команда (или команды). К примеру, рассмотрим нахождение модуля числа а. Условие – . Если условие выполняется (истинное), то. Если условие не выполняется (, а значит– ложное условие), то.

Циклический алгоритм многократно повторяет некоторую серию команд. Эта серия команд называется телом цикла. Циклические алгоритмы бывают двух типов: циклы со счетчиком и циклы с условием. Когда заранее известно, какое число повторений тела цикла необходимо выполнить используют цикл со счетчиком. Если заранее неизвестно сколько раз необходимо повторить тело цикла, используется цикл с условием. В таком цикле количество повторений зависит от условия. Пока условие выполняется, тело цикла повторяется.

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

Графическое изображение алгоритма называется блок-схемой. Каждое действие алгоритма изображается с помощью определенной фигуры. Между собой эти фигуры соединены стрелками (в упрощенном варианте прямыми). Рассмотрим основные фигуры (табл.3.1.).

Действие	Фигура
Начало или конец алгоритма
Ввод или вывод данных
Выполнения действия
Условие
Цикл

Таблица 3.1. Основные фигуры в блок-схеме.

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

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

Рассмотрим запись основных действий с помощью псевдокода (табл. 3.2.).

Действие	Псевдокод
Имя алгоритма	алг<имя алгоритма> (арг<список аргументов и их типов>,рез<список результатов и их типов>)
Начало алгоритма	нач
Ввод данных	ввод
Действия	не обозначаются
Условие	если
Условие выполнено	то
Условие не выполнено	иначе
Цикл со счетчиком	для
Цикл с условием	пока
Вывод данных	вывод
Конец алгоритма	кон

Таблица 3.2. Псевдокод основных действий.

Задача 3.1. Написать алгоритм нахождения наибольшего из двух чисел в словесной, графической форме и в виде псевдокода.

Решение:

Запишем словесный алгоритм:

Определим переменные и их тип: A,B: действительные числа.

Определим результат и его тип: С: действительное число.

Начало алгоритма.

Введем числа А и В.

Если А>В, то С=А,

иначе С=В.

Выведем С.

Конец алгоритма.

Графический алгоритм и псевдокод запишем в таблице 3.3.

Блок-схема	Псевдокод
	алг Наибольший (арг дейс А,Bрез дейсС) нач вводA,B еслиА>В то С=А иначеС=В выводС кон

Таблица 3.3. Блок-схема и псевдокод.

Ответ: см. словесный алгоритм и таблицу 3.3. 

Задача 3.2. Написать алгоритм нахождения корней квадратного уравнения в словесной, графической форме и в виде псевдокода.

Решение:

Запишем словесный алгоритм:

Определим переменные и их тип: A,B,C,D: действительные числа.

Определим результаты и их тип: Х1,Х2: действительные числа.

Начало алгоритма.

Введем коэффициенты A,B и С.

Найдем дискриминант: .

Если D≥0, то найдем корни: ,и выведем результатыX1 и Х2,

иначе выведем сообщение: «Корней нет».

Конец алгоритма.

Графический алгоритм и псевдокод запишем в таблице 3.4.

Блок-схема	Псевдокод
	алгКвадрат(аргдейсA,B,C,DрездейсХ1,Х2) нач ввод A,B,C еслиD≥0 то выводX1,X2 иначе вывод «Решений нет» кон

Таблица 3.4. Блок-схема и псевдокод.

Ответ: см. словесный алгоритм и таблицу 3.4.

Задача 3.3. Написать алгоритм нахождения наибольшего общего делителя двух чисел в словесной, графической форме и в виде псевдокода.

Решение:

Запишем словесный алгоритм:

Определим переменные и их тип: A,B,X,Y,Z: целые числа.

Определим результаты и их тип: D: целое числа.

Начало алгоритма.

Введем числа А и В.

Если А>В, то X=А, Y=B

иначе X=В, Y=A

Пока Y≠0 выполняем следующие действия:

Z=остаток от деления X на Y, X=Y, Y=Z.

D=X

Выводим D

Конец алгоритма.

Графический алгоритм и псевдокод запишем в таблице 3.5.

Блок-схема	Псевдокод
MOD– функция нахождения остатка от деленияXнаY	алгНод(арг целА,В,X,Y,Zрез целD) нач вводA,B еслиА>В то X=А,Y=B иначеX=В,Y=A покаY≠0 Z=XMODY X=Y Y=Z D=X выводD кон

Таблица 3.5. Блок-схема и псевдокод.

Ответ: см. словесный алгоритм и таблицу 3.5. 

Рассмотренные виды представления алгоритмов не могут быть использованы компьютером. Алгоритм, записанный на «понятном» компьютеру языке, называетсяпрограммой, а вид представления алгоритма – программным. Программные алгоритмы записываются с помощью языков программирования, речь о которых пойдет ниже.

Вопросы:

1. Для чего нужны алгоритмы?

2. Какие существуют свойства алгоритмов? Что они означают?

3. Почему словесные, графические алгоритмы и псевдокоды не могут быть использованы компьютером?

4. Чем должны отличаться программные алгоритмы от остальных?

Задачи для самостоятельного решения:

Задача 3.4. Написать алгоритм нахождения наименьшего из двух чисел в словесной, графической форме и в виде псевдокода.

Задача 3.5. Написать алгоритм нахождения корней линейного уравнения в словесной, графической форме и в виде псевдокода.

Задача 3.6. Написать алгоритм нахождения наименьшего общего кратного двух чисел в словесной, графической форме и в виде псевдокода.