1.1 Понятие алгоритма
Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787 – 850) выдающегося математика средневекового Востока. В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. В дальнейшем алгоритмом стали называть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных. Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Создание алгоритма, пусть даже самого простого, - процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами.
Алгоритм- это точная последовательность предписаний, исполнение которых позволяет посредством конечного числа шагов получить решение задачи, однозначно определяемое исходными данными.
Алгоритмы являются объектом систематического исследования пограничной между математикой и информатикой научной дисциплины, примыкающей к математической логике - теории алгоритмов.
Особенность положения состоит в том, что при решении практических задач, предполагающих разработку алгоритмов для реализации на ЭВМ, и тем более при использовании на практике информационных технологий, можно, как правило, не опираться на высокую формализацию данного понятия. Поэтому представляется целесообразным познакомиться с алгоритмами и алгоритмизацией на основе содержательного толкования сущности понятия алгоритма и рассмотрения основных его свойств. При таком подходе алгоритмизация более выступает как набор определенных практических приемов, особых специфических навыков рационального мышления в рамках заданных языковых средств. Можно провести аналогию между этим обстоятельством и рассмотренным выше подходом к измерению информации: тонкие математические построения при «кибернетическом» подходе не очень нужны при использовании гораздо более простого «объемного» подхода при практической работе с компьютером.
Можно сказать, что алгоритм описывает процесс преобразования исходных данных в результаты, т.к. для решения любой задачи необходимо:
1. Ввести исходные данные.
2. Преобразовать исходные данные в результаты (выходные данные).
3. Вывести результаты.
Разработка алгоритма решения задачи - это разбиение задачи на последовательно выполняемые этапы, причем результаты выполнения предыдущих этапов могут использоваться при выполнении последующих. При этом должны быть четко указаны как содержание каждого этапа, так и порядок выполнения этапов. Отдельный этап алгоритма 2 представляет собой либо другую, более простую задачу, алгоритм решения которой известен (разработан заранее), либо должен быть достаточно простым и понятным без пояснений.
1.2 Понятие исполнителя алгоритма
Понятие исполнителя невозможно определить с помощью какой-либо формализации. Исполнителем может быть человек, группа людей, робот, станок, компьютер, язык программирования и т.д. Важнейшим свойством, характеризующим любого из этих исполнителей, является то, что исполнитель умеет выполнять некоторые команды. Так, исполнитель-человек умеет выполнять такие команды как «встать», «сесть», «включить компьютер» и т.д., а исполнитель-язык программирования Паскаль - команды BEGIN, END, WRITELN и другие аналогичные. Вся совокупность команд, которые данный исполнитель умеет выполнять, называется системой команд исполнителя (СКИ).
В качестве примера рассмотрим исполнителя-робота, работа которого состоит в собственном перемещении по рабочему полю (квадрату произвольного размера, разделенному на клетки) и перемещении объектов, в начальный момент времени находящихся на «складе» (правая верхняя клетка).
Одно из принципиальных обстоятельств состоит в том, что исполнитель не вникает в смысл того, что он делает, но получает необходимый результат. В таком случае говорят, что исполнитель действует формально, т.е. отвлекается от содержания поставленной задачи и только строго выполняет некоторые правила, инструкции.
Это - важная особенность алгоритмов. Наличие алгоритма формализует процесс решения задачи, исключает рассуждение исполнителя. Использование алгоритма дает возможность решать задачу формально, механически исполняя команды алгоритма в указанной последовательности. Целесообразность предусматриваемых алгоритмом действий обеспечивается точным анализом со стороны того, кто составляет этот алгоритм.
Введение в рассмотрение понятия «исполнитель» позволяет определить алгоритм как понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение поставленной цели. В случае исполнителя-робота мы имеем пример алгоритма «в обстановке», характеризующегося отсутствием каких-либо величин. Наиболее же распространенными и привычными являются алгоритмы работы с величинами - числовыми, символьными, логическими и т.д.
1.3 Свойства алгоритма
При составлении и записи алгоритма необходимо обеспечить, чтобы он обладал рядом свойств.
Однозначность (определенность) алгоритма, под которой понимается единственность толкования исполнителем правила построения действий и порядок их выполнения. Чтобы алгоритм обладал этим свойством, он должен быть записан командами из системы команд исполнителя.
Конечность алгоритма – обязательность завершения каждого из действий, составляющих алгоритм, а также работа алгоритма должна заканчиваться за конечное число шагов.
Результативность алгоритма, предполагающая, что выполнение алгоритма должно завершиться получением определённых результатов.
Массовость, т. е. возможность применения данного алгоритма для решения целого класса задач, отвечающих общей постановке задачи. Для того чтобы алгоритм обладал свойством массовости, следует составлять алгоритм, используя обозначения величин и избегая конкретных значений.
Правильность алгоритма, под которой понимается способность алгоритма давать правильные результаты решения поставленных задач.
Эффективность– для решения задачи должны использоваться ограниченные ресурсы компьютера (процессорное время, объём оперативной памяти и т. д.). Общее время работы алгоритма должно быть в разумных пределах.
1.4 Способы записи алгоритма
На практике наиболее распространены следующие способы представления алгоритмов:
- Словесно-формульный способ (запись на естественном языке);
Словесно-формульный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
Например.Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида).
Алгоритм может быть следующим:
1. задать два числа;
2. если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма;
3. определить большее из чисел;
4. заменить большее из чисел разностью большего и меньшего из чисел;
5. повторить алгоритм с шага 2.
Словесный способ не имеет широкого распространения, так как такие описания:
- строго не формализуемы;
- страдают многословностью записей;
- допускают неоднозначность толкования отдельных предписаний.
- Графический способ (с использованием графических примитивов, блок-схем);
Для разработки структуры программы удобнее пользоваться записью алгоритма в виде блок-схемы (в англоязычной литературе используется термин flow-chart).
Блок-схемойназывают графическое изображение алгоритма, в котором этапы решения задачи изображаются в виде различных геометрических фигур.
- псевдокоды(полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов.
Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.
В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя.
Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются.
Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.
Примером псевдокода является школьный алгоритмический язык в русской нотации (школьный АЯ), описанный в учебнике А.Г. Кушниренко и др. «Основы информатики и вычислительной техники», 1991. Этот язык в дальнейшем мы будем называть просто «алгоритмический язык».
Пример записи алгоритма на школьном АЯ:
алг Сумма квадратов (арг цел n, рез цел S)
дано| n > 0
надо| S = 1*1 + 2*2 + 3*3 + ... + n*n
нач цел i
ввод n; S:=0
нц дляi от 1 до n
S:=S+i*i
кц
вывод "S = ", S
кон
- Формальные языки (QBasic, Pascal и тд.).
1.5 Линейный алгоритм
В алгоритмическом языке линейным является алгоритм, состоящий из команд, выполняющихся одна за другой. Они в записи алгоритма располагаются в том порядке, в каком должны быть выполнены предписываемые ими действия. Такой порядок выполнения называется естественным. Последовательность команд образует составную команду «цепочка», которая в записи блок-схемой имеет вид, приведенный на рисунке 2.
В математике к линейным алгоритмам относятся алгоритмы, представленные формулами. Они наиболее просты для программирования.
Рассмотрим несколько примеров линейных алгоритмов.
ПРИМЕР :Зная длины трех сторон треугольника, вычислить площадь и периметр треугольника.
Пусть a, b, c - длины сторон треугольника. Необходимо найти S - площадь треугольника, P - периметр.
Для нахождения площади можно воспользоваться формулой Герона:
где r – полупериметр.
Входные данные: a, b, c.
Выходные данные: S, P.
Внимание!!! В этих блоках знак "=" означает не математическое равенство, а операцию присваивания. Переменной, стоящей слева от оператора, присваивается значение, указанное справа. Причем это значение может быть уже определено или его необходимо вычислить с помощью выражения.
Например, операция r = (a+b+c)/2 - имеет смысл (переменной r присвоить значение r=(a+b+c)/2), а выражение (a+b+c)/2=r - бессмыслица.
1.6 Разветвляющийся алгоритм
При исполнении алгоритмов приходится не только находить значения величин, но и анализировать их свойства, сравнивать их друг с другом и в зависимости от результата сравнения выбирать ту или иную ветвь алгоритма. Алгоритмы, имеющие несколько ветвей, называются нелинейными. К таким относятся разветвляющиеся и циклические алгоритмы. Для их записи применяются составные команды.
Базовая структура «ветвление». Определяет выполнение действий в зависимости от выполнения условия. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.
Ветвление - управляющая структура, организующая выполнение лишь одного из двух указанных действий в зависимости от справедливости некоторого условия.
Условие - вопрос, имеющий два варианта ответа: да или нет (истина, ложь).
Ветвление может быть в полной и неполной форме.
ПРИМЕР: Известны коэффициенты и с квадратного уравнения. Вычислить корни квадратного уравнения.
Входные данные: a, b, c.
Выходные данные: x1, x2.
1. Ввод коэффициентов квадратного уравнения a, b и c. 2.
2. Вычисление дискриминанта d по формуле d = b2 - 4ас.
3. Проверка знака дискриминанта. Если d >= 0, то вычисление действительных корней по формуле и вывод их на экран
1.7 Алгоритмы циклической структуры
Циклом называют повторение одних и тех же действий (шагов). Последовательность действий, которые повторяются в цикле, называют телом цикла. Существует несколько типов алгоритмов циклической структуры. На рис. изображен цикл с предусловием (здесь условие-это условие на продолжение цикла), а на рис- цикл с постусловием (истинность условия –условие окончания цикла), которые называют условными циклическими алгоритмами.
Нетрудно заметить, что эти циклы взаимозаменяемы и обладают некоторыми отличиями.
· в цикле с предусловием условие проверяется до тела цикла, в цикле с постусловием - после тела цикла;
· в цикле с постусловием тело цикла выполняется хотя бы один раз, в цикле с предусловием тело цикла может не выполниться ни разу;
· в цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием - условие выхода из цикла.
При написании условных циклических алгоритмов следует помнить следующее:
Во-первых, чтобы цикл имел шанс когда-нибудь закончиться, содержимое его тела должно обязательно влиять на условие цикла.
Во-вторых, условие должно состоять из корректных выражений и значений, определенных еще до первого выполнения тела цикла.
Итак, цикл с постусловием завершается, когда условие становится истинным, а цикл с предусловием- когда становится ложным.
Кроме того, существует так называемый безусловный циклический алгоритм, который удобно использовать, если известно, сколько раз необходимо выполнить тело цикла.
Выполнение безусловного циклического алгоритма начинается с присвоения переменной i стартового значения in. Затем следует проверка, не превосходит ли переменная i конечное значение iк. Если превосходит, то цикл считается завершенным, и управление передается следующему за телом цикла оператору. В противном случае выполняется тело цикла, и переменная i меняет свое значение в соответствии с указанным шагом di. Далее, снова производится проверка значения переменной i и алгоритм повторяется. Понятно, что безусловный циклический алгоритм можно заменить любым условным (рис. 9)
Отметим, что переменную i называют параметром цикла, так как это переменная, которая изменяется внутри цикла по определенному закону и влияет на его окончание.
Рассмотрим использование алгоритмов циклической структуры на конкретных примерах.
ПРИМЕР 2.1. Найти наибольший общий делитель (НОД) двух натуральных чисел А и В.
Входные данные: А и В.
Выходные данные: А - НОД.
Для решения поставленной задачи воспользуемся алгоритмом Евклида: будем уменьшать каждый раз большее из чисел на величину меньшего до тех пор, пока оба значения не станут равными, так, как показано в таблице 2.
В блок-схеме решения задачи, представленной на рис. 2.5, для решения поставленной задачи используется цикл с предусловием, то есть тело цикла повторяется до тех пор, пока А не равно В.