6. Алгоритмизация и программирование
"Алгоритм" является базовым основополагающим понятием информатики, а алгоритмизация (программирование) – основным разделом курса информатики.
Современное значение слова алгоритм во многом аналогично таким понятиям как рецепт, процесс, метод, способ, процедура, программа, но все-таки слово алгоритм имеет дополнительный смысловой оттенок.
Алгоритм — это не просто набор конечного числа правил, задающих последовательность выполнения операций для решения задачи. Помимо этого, он имеет 5 важных особенностей:
конечность. Алгоритм всегда должен заканчиваться после выполнения конечного числа шагов;
определенность. Каждый шаг алгоритма должен быть однозначно определен;
ввод. Алгоритм имеет некоторое (возможно, равное нулю) число входных данных, т.е. величин, которые задаются до начала его работы или определяются динамически во время его работы;
вывод. У алгоритма есть одно или несколько выходных данных, т.е. величин, имеющих вполне определенную связь с входными данными.
эффективность. Алгоритм обычно считается эффективным, если все его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени.
Любой алгоритм ориентирован на некоторый общий метод решения класса задач и представляет собой формализованную запись метода, процедуры.
Алгоритм, записанный на некотором алгоритмическом, формальном языке, состоит из заголовка алгоритма (описания параметров, спецификаций класса задач) и тела алгоритма (последовательности команд исполнителя, преобразующих входные параметры в выходные).
Для записи, исполнения, обмена и хранения алгоритмов существуют различные средства, языки, псевдокоды – блок-схемы, различные языки программирования и др.
Приведем общую структуру алгоритмического обеспечения. Критерии, по которым алгоритмы могут быть классифицированы, бывают разными, поэтому предлагаемая ниже схема отражает основные элементы структуры и в некоторых случаях является условной, в том смысле, что блоки приведенной на рис. 6.1 структуры могут "перекрываться".
Рис. 6.1. Структура алгоритмического обеспечения
Основные формы использования алгоритмов – автономное, библиотечное, пакетное.
Автономный алгоритм определяется решаемой задачей, структурой используемых данных, структурой логических связей частей (модулей) алгоритма и языком псевдокодов, на котором представлен, описан алгоритм.
Библиотека алгоритмов определяется множеством задач, решаемых с помощью библиотеки, множеством алгоритмов для решения типовых задач предметной области и структурой используемых данных.
Пакет алгоритмов, как и библиотека, определяется множеством задач, решаемых с помощью пакета, набором алгоритмов для решения типовых задач или их составных частей из предметной области, структурой используемых данных и обменом данными между задачами (модулями), специальным языком, на котором формулируется задание (последовательность этапов решаемой задачи, последовательность задач задания).
В качестве языка описания алгоритмов будет использоваться далее язык программирования С++.
Порядок выполнения операций (старшинство операций – по убыванию) в языке С++:
Вычисление выражений в скобках;
Вычисление стандартных функций;
Умножение и деление (обозначаются "*" и "/");
Сложение и вычитание (обозначаются "+" и "–").
Рассмотрим базовые простые команды языка С++ [8-9].
Команда описания главной функции:
< тип > main ()
{
…
}
2. Команда описания неглавной функции:
< тип > <имя функции > ( < передаваемые параметры>)
{
…
}
Ввод – команда ввода в рассмотрение (в тело алгоритма) тех или иных входных параметров:
cin>>вводимый параметр;
Вывод – команда вывода на экран тех или иных входных или выходных параметров алгоритма:
cout<<выводимый параметр;
Присваивание – команда изменения текущего значения переменной вида:
<идентификатор> = <выражение>;
где <идентификатор> соответствует имени переменной, <выражение> – корректно записанное выражение. Знак "=" означает последовательное выполнение двух действий: определение текущего значения <выражения> и замена текущего значения переменной, имя которой задано <идентификатором>, на новое значение, равное значению <выражения>.
Символ начала блока {.
Символ конца блока }.
Команда вставки комментариев в текст алгоритма имеет вид:
/* комментарий в несколько строк */
// комментарий в одну строку
Комментировать можно любой объект программы. Обычно комментируют переменную, структуру данных, команду, группу команд.
Различают три базовые алгоритмические структуры: следование, ветвление, повторение.
Действие следования состоит из двух команд с указанной очередностью их выполнения и имеет вид:
<команда – предшественник>;
<команда – преемник>.
Структура типа ветвления в полной форме состоит из некоторого условия, проверяемого на истинность при выполнении структуры, команды, выполняемой при выполнении проверяемого условия, и команды, выполняемой при невыполнении условия. Условный оператор имеет вид
if <условие> <команда, выполняемая при выполнении условия>;
else <команда, выполняемая при невыполнении условия>;
Пример. Команда вида
if (х>y) ( если текущее значение х больше текущего значения y )
у = х ;
else x= y; (иначе x=y)
Структура повторения (цикл) служит для компактной записи одного и того же набора команд, повторяемых для различных значений параметров команд.
Структура повторения типа "пока (while)" записывается в виде:
while <условие продолжения повторения>
{
<повторяемая команда 1>;
<повторяемая команда 2>;
. . .
<повторяемая команда N>;
}
Следующим оператором цикла в языке С++ является оператор for
for(<присваивание начального значения счетчику цикла>; <условие проверки выхода из цикла>; <изменение счетчика цикла>)
{
< операторы цикла>
}
Данный цикл выполняется по правилу: если условие повторения для текущих его параметров не выполнено, то повторение команд (тела) цикла на этом завершается; если же оно выполнено, то выполняется тело цикла и опять проверяется условие повторения команд тела цикла.