Методические указания. Человек ежедневно встречается с необходимостью следовать тем или иным правилам, выполнять различные инструкции и указания
Понятие алгоритма
Человек ежедневно встречается с необходимостью следовать тем или иным правилам, выполнять различные инструкции и указания. В математике для решения типовых задач используют определенные правила, описывающие последовательности действий. Для решения задачи надо знать, что дано, что следует получить и какие действия и в каком порядке следует для этого выполнить. Чтобы заставит компьютер решить какую-либо задачу, необходимо прежде всего разработать алгоритм решения. Предписание, определяющее порядок выполнения действий над данными с целью получения искомых результата, и есть алгоритм.
Алгоритм – заранее заданное понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов.
Термин «алгоритм» (Alhorithmi –лат.) транскрипция имени великого среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми, жившего в 783 – 850 гг. Он в IX веке разработал правила выполнения четырех действий арифметики.
Однако не следует считать алгоритм чисто математическим понятием. Понятие алгоритма является одним из главных понятий современной науки.
Исполнитель алгоритма
Исполнитель алгоритма – это некоторая абстрактная или реальная система, способная выполнить действия, предписываемые алгоритмом.
Исполнителя характеризуют:
среда – «место обитания» исполнителя;
система команд: каждый исполнитель может выполнять команды только из некоторого строго заданного списка – системы команд исполнителя. Для каждой команды должны быть заданы условия применимости и описаны результаты выполнения команды;
элементарные действия;
отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.
В информатике универсальным исполнителем является компьютер.
Свойства алгоритмов
Дискретность – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов.
Определенность – каждое правило алгоритма должно быть четким, однозначным. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
Массовость – алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными.
Конечность – за конечное число шагов алгоритм либо должен приводить к решению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течении времени, отведенного для использования алгоритма, с выдачей промежуточных результатов.
Понятность – исполнитель алгоритма должен понимать, как его выполнять.
Способы представления алгоритмов
Словесный способ представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
Графический способ – алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое представление называется блок-схемой. В блок-схеме каждому типу действий соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий.
В таблице приведены блочные символы и их описание.
| Обозначение | Пояснение |
| Вычислительное действие или последовательность действий. |
| Проверка условий |
| Начало цикла |
| Вычисления по подпрограмме, стандартной программе. |
| Ввод – вывод в общем виде |
| Начало, конец алгоритма, вход и выход в подпрограмму |
| Вывод результатов на печать |
Базовые алгоритмические структуры
Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (т.е. основных) элементов. Естественно, что при таком подходе к алгоритмам изучение основных принципов их конструирования должно начинаться с изучения этих базовых элементов. Для их описания будем использовать язык схем алгоритмов.
Логическая структура любого алгоритма может быть представлена комбинацией трёх базовых структур: следование, ветвление, цикл.
Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.
1. Базовая структура «следование». Образуется последовательностью действий, следующих одно за другим:
 |
2. Базовая структура «ветвление». Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведёт к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь выбран. Структура ветвление существует в четырёх основных вариантах:
§ если-то;
§ если-то-иначе;
§ выбор;
§ выбор-иначе.
| 1. Если-то | 2. Если-то-иначе |
 
| |
| 3. Выбор | 4. Выбор-иначе |
 
|
3. Базовая структура «цикл». Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности:
| Цикл типа пока. Предписывает выполнять тело цикла до тех пор, пока выполняется условие | Цикл типа для. Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне |
 
|
Вложенные циклы
Возможны случаи, когда внутри цикла необходимо повторять некоторую последовательность операторов, т.е. организовать внутренний цикл. Такая структура называется цикл в цикле или вложенный цикл. Глубина вложения циклов может быть различной.
При использовании такой структуры необходимо выносить из внутреннего цикла во внешний все операторы, которые не зависят от параметра внутреннего цикла.
Основные компоненты и основные понятия алгоритмического языка
Основой алгоритмического языка является алфавит, синтаксис, семантика.
Алфавит – это фиксированный набор основных символов для данного языка.
Синтаксис – это набор правил, устанавливающих, какие комбинации символов являются осмысленными предложениями на этом языке.
Семантика – устанавливает, какие последовательности действий описываются теми или иными фразами языка.
Понятие алгоритмического языка определяется во взаимодействии синтаксических и семантических правил. Синтаксические правила показывают, как образуется данное понятие из других понятий и букв алфавита, а семантические правила определяют свойства данного понятия.
Основные понятия алгоритмического языка:
1. Имена (идентификаторы) – употребляются для обозначения объектов программы.
2. Операции:
ü арифметические ( + , – , * , / , и др.);
ü логические (и, или, не);
ü операции отношения (< , > , <= , >= , = , <>);
ü операция сцепки или конкатенация (обозначается знаком «+»).
3. Данные – величины, обрабатываемые программой. Виды данных:
ü константы – это данные, которые зафиксированные в тексте программы и не изменяются в процессе ее выполнения. Константы бывают числовые, логические, символьные и литерные;
ü переменные – обозначаются именами и могут изменять свои значения в ходе выполнения программы. Переменные бывают целые, вещественные, логические, символьные и литерные;
ü массивы – последовательности однотипных элементов, число которых фиксировано и которым присвоено одно имя. Положение элемента в массиве однозначно определяется его индексами. Массивы бывают одномерными, двумерными.
4. Выражения – предназначены для выполнения необходимых вычислений. Выражения состоят из констант, переменных, указателей функций, объединенных знаками операций. Выражения бывают арифметические, логические и строковые.
5. Операторы (команды) – это наиболее крупное и содержательное понятие языка. Каждый оператор представляет собой законченную фразу языка и определяет некоторый вполне законченный этап обработки данных. Оператор состоит из ключевых слов, данных, выражений и т.д. Операторы подразделяются на исполняемые и неисполняемые. Неисполняемые операторы предназначены для описания данных и структуры программы, а исполняемые – для выполнения различных действий.
Стандартные функции
| Название функции | Указатель функции |
| Синус угла | sin(x) |
| Косинус угла | cos(x) |
| Тангенс угла | tg(x) |
| Котангенс угла | ctg(x) |
| Арксинус угла | arcsin(x) |
| Арккосинус угла | arccos(x) |
| Арктангенс угла | arctg(x) |
| Арккотангенс угла | arcctg(x) |
| Случайное число в диапазоне от 0 до (х-1) | rnd(x) |
| Остаток от деления целого х на целое у | mod(x,y) |
| Частное от деления целого х на целое у | div(x,y) |
| Наибольшее из чисел х и у | max(x,y) |
| Наименьшее из чисел х и у | min(x,y) |
| Целая часть числа х | int(x) |
| Знак числа х | sign(x) |
| Экспонента | exp(x) |
| Десятичный логарифм | lg(x) |
| Натуральный логарифм | ln(x) |
| Корень квадратный | sqrt(x) |
| Абсолютная величина (модуль) | abs(x) |
| Квадрат числа х | sqr(x) |
Правила записи арифметических и логических выражений
- Нельзя опускать знак умножения между сомножителями.
- Нельзя ставить рядом два знака операций.
- Индексы элементов массива записываются в квадратных (Pascal) или круглых (Basic) скобках.
- Для обозначения переменных используют буквы латинского алфавита.
- Операции выполняются в порядке старшинства: сначала вычисление функций, затем возведение в степень, затем умножение и деление и в последнюю очередь сложение и вычитание.
- Операции одного старшинства выполняются слева направо.
- В записи логических выражений помимо арифметических операций используются логические операции и операции отношения.
Пример1: Составьте программу для вычисления величины силы тока на участке электрической цепи сопротивлением R Ом при напряжении U В.
Решение:
алг сила тока (аргвещ R,U, резвещ I)
начвещ I, R, U
ввод R, U
I:= U/R
вывод ‘I=’, I
кон
Пример2: Составить блок-схему для вычисления значения функции
Решение: схема алгоритма имеет вид:
 |
Рекомендуемая литература
1. Практикум по информатике: учеб. пособие для студ. высш. учеб. заведений/ А.В. Могилев, Е.К. Хеннер, Н.И. Пак; под ред. Е.К. Хеннера. – М.: Изд. центр Академия, 2008, ISBN 978-5-7695-4949-6
2. TURBO PASCAL/ С. А. Немнюгин. – СПб.: Питер, 2000, ISBN 978-5-94723-509-8
3. Симонович С.В. Информатика. Базовый курс: учебник для вузов. – СПб.: Питер, 2006 – 640 с.: ил., ISBN 5-94723-752-0
4. Острейковский В.А. Информатика: учебник для вузов – М.: Высшая школа, 2004. – 511 с.: ил., ISBN 5-06-003533-6
5. Лабораторный практикум по информатике: учебное пособие для вузов / В.С. Микшина, Г.А. Еремеева, Н.Б. Назина, В.А.Острейковский. – М.: Высш. шк., 2003, ISBN 5-06-004273-1