Файл: Основные структуры алгоритмов сравнительный анализ и примеры их использования.pdf

12

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

Пример 1.
Исполнитель Черепаха перемещается на экране компьютера, оставляя след в виде линии. Система команд Черепахи состоит из следующих команд:

Вперёд n (где n — целое число) — вызывает передвижение Черепахи на n шагов в направлении движения — в том направлении, куда развёрнуты её голова и корпус;

Направо m (где m — целое число) — вызывает изменение направления движения Черепахи на m градусов по часовой стрелке

Запись Повтори k [<Команда1> <Команда2> … <Командаn>] означает, что последовательность команд в скобках повторится k раз.

Пример 2.
Система команд исполнителя Вычислитель состоит из двух команд, которым присвоены номера:

1 — вычти 1
2 — умножь на 3

Первая из них уменьшает число на 1, вторая увеличивает число в 3 раза. При записи алгоритмов для краткости указываются лишь номера команд. Например, алгоритм 21212 означает следующую последовательность команд:

13

умножь на 3
вычти 1
умножь на 3
вычти 1
умножь на 3
С помощью этого алгоритма число 1 будет преобразовано в 15: ((1 · 3 – 1) · 3 – 1) · 3 = 15.
 

14

2.Построения Алгоритмов на языке паскаль

В 1970 г. профессор Никлаус Вирт из Швейцарии обосновал и разработал язык высокого уровня – Паскаль. Этот язык отличается простотой и стройностью, качествами, которые обеспечивают Паскалю популярность уже на протяжении нескольких десятилетий.
Паскаль – это процедурный язык, имеющий блочную структуру. Набор операторов языка отражает принципы структурного программирования.
Паскаль-программа является текстовым файлом с собственным именем и с расширением pas.

Структура программы
В целом программа на языке Паскаль состоит из двух основных частей: описания всех данных, с которыми производятся действия и описания самих действий. Кроме этого, в самом начале программы может присутствовать ее название – заголовок. В самом конце программы ставиться точка «.».
Правила языка Паскаль предусматривают единую для всех программ форму основной структуры:

ЗАГОЛОВОК
program <Имя программы>;
Содержит служебное слово program;

РАЗДЕЛ ОПИСАНИЙ
Раздел внешних модулей, процедур и функций – Uses
Пример: uses Crt;

Раздел констант – const
Константа – переменная, которая не изменяется в процессе выполнения программы. Под константу не выделяется память. Тип константы определяется ее значением.
Пример: const
N=10;
p=0.14;

---

15

Раздел типов – type
В Паскале существуют стандартные типы, которые описывать не надо (они считаются уже описанными: integer, real, char, Boolean и т.д.)
В Паскале есть возможность создать свой новый тип данных.

Раздел переменных – var
Переменная – это величина способная изменяться в процессе выполнения программы. Под переменную выделяется память. Каждая переменная, до работы с ней должна быть описана, т.е. указан тип переменной.
Попытка в процессе выполнения программы присвоить переменной значение иного типа расценивается как ошибка в программе. Пример: var
I, j, r: integer;
X, h, sum: real;
D, f, r: string;

Раздел процедур и функций – procedure и function
Раздел процедур и функций не начинается каким-то специальным служебным словом – начало данного раздела легко определяется по служебным словам procedure или function.

БЛОК ОСНОВНЫХ ОПЕРАТОРОВ
begin
Оператор 1;
Оператор 2;
Оператор N
end.
Это основной раздел программы – именно здесь задаются те действия, которые должны быть выполнены в данной программе.

Имена программы и используемых величин (констант, переменных) выбираются программистом самостоятельно в соответствии с правилами построения идентификаторов:

идентификатор должен быть уникальным, то есть одним и тем же именем разные объекты не могут быть названы;

16

идентификатор имеет ограничение по длине (зависит от конкретной реализации языка на компьютере);

идентификатор может состоять только из символов латинского алфавита, цифр и знака подчеркивания («_»);

идентификатор не может начинаться с цифры.



Данные. Типы данных

Набор величин, с которыми работает компьютер, обычно называется данными. Каждая величина имеет три основных свойства: имя, значение и тип. В алгоритмах и языках программирования величины делятся на константы и переменные.

Константа-это величина, которая не изменяется во время выполнения программы. Память не выделяется под константой. Тип константы определяется ее значением.

Переменная-это величина, способная меняться во время выполнения программы. Память выделяется переменной. Каждая переменная, прежде чем работать с ней, должна быть описана в разделе Var, то есть указан тип переменной.

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

---

На языке Паскаля тип величия задается заранее. Все переменные, используемые в программе, должны быть объявлены в разделе Описание с их типом. Обязательное описание типа приводит к избыточности в тексте программ, но эта избыточность является важным вспомогательным инструментом для разработки программ и

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

В языке Паскаль существует пять простых типов данных:


Integer Целочисленные данные, во внутреннем представлении занимают 2 байта

Real Вещественные данные, занимают 6 байтов

Char Символ, занимает 1 байт

String Строка символов, занимает МАХ+1 байт, где МАХ – максимальное число символов в строке

Boolean Логический тип, занимает 1 байт и имеет два значения: false (ложь) и true (истина)

Целый и вещественный тип имеют подтипы целого типа








18

Над данными целого типа определены следующие арифметические операции.

Знаки операции
+ Сложение Приоритет 2
- Вычитание Приоритет 2
* Умножение Приоритет 1
/ Деление Приоритет 1
div Целая часть от деления Приоритет 1
mod Остаток от деления Приоритет 1

Результат выполнения этих операций над целыми операндами получается также целого типа (исключение составляет операция / – результат всегда вещественное число).
Над данными целого типа определены следующие операции отношения: =, <>, <, >, <=, >=. Результат выполнения этих операций – логический тип.
Приоритет – это последовательность выполнения действий в строке операций. Если приоритет = 1, то эти действия выполняются в первую очередь, если приоритет = 2, то эти действия выполняются во вторую очередь. Для изменения приоритета используются круглые скобки.
Пример выполнения операций div и mod:
7 div 2 = 3
3 div 5 = 0
7 mod 2 = 1
3 mod 5=3
Список стандартных функции, дающие целый результат.

Abs(x) Х – целое-Абсолютная величина X
Sqr (x) Х – целое-Возведение X в квадрат
Trunc (x) Х – веществ-Выделение целой части числа X
Round (x) Х – веществ-Округление X до целого числа
Succ (x) Х – целое-Следующее за X число
Pred (x) Х – целое-Предыдущее перед X число
Random (x) Х – целое-Случайное число от 0 до х-1 .Если функция не содержит аргумента, то генерируется случайное число от 0 до 1.
Randomize-Оператор, позволяющий генерировать новую последовательность случайных чисел при новом запуске программы

19

---

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

С фиксированной точкой
5600
-0.023
570
0.26
-0.003
С плавающей точкой
Математическая. запись
0.56 * 104
-23 *10- 3
0.57 *103
26 * 10-2
-3 *10-3
Запись на языке Паскаль
0.56Е+04
-23Е-03
0.57Е+03
26Е-02
-3Е-03
Над данными вещественного типа определены следующие арифметические операции.
Знаки операции
+ Сложение Приоритет 2
- Вычитание Приоритет 2
* Умножение Приоритет 1
/ Деление Приоритет 1
Операции div и mod над вещественными величинами не допустимы.

Список стандартных функции, дающие вещественный результат.




20

Математическая запись
sin x- Синус числа X
cos x- Косинус числа X
arctg x- Арктангенс числа X
ln x- Натуральный логарифм числа X
ex- Экспонента числа X
vx- Корень квадратный числа X




Запись на языке Паскаль
sin (x)- Синус числа X
cos (x)- Косинус числа X
arctan (x)- Арктангенс числа X
ln (x)- Натуральный логарифм числа X
exp (x)- Экспонента числа X
sqrt (x)- Корень квадратный числа X
Функция ln (x) и exp (x) используются для возведения в степень по правилу: ln() n xenx = . Например, выражение x9 вычисляется по формуле exp(9*ln(x)).

Логический тип данных имеет всего два значения True (истина), False (ложь) и является упорядоченным типом True > False. В программе логический тип переменной задается служебным словом Boolean.
Самая простая операция Сравнения
> – больше;
< – меньше;
= – равно;
<> – не равно;
>= – больше либо равно;
<= – меньше либо равно.



21

Выражения

Арифметические выражения

Выражения строятся из операндов (переменные, константы, вызовы функций), знаков операций и круглых скобок. При составлении выражений необходимо знать следующие правила:
1) все выражение записывается в строку, то есть двухэтажные выражения, а также верхние и нижние индексы не допускаются. Например: (a1*x1 - a2*x2)/(x1-x2);
2) в выражении можно использовать только круглые скобки. Примеры арифметических выражений:
b+a*x
sin(x)+2*x
При составлении выражения следует учитывать приоритет операций:
1) *,/,div, mod
2) +,-
Для изменения приоритета используются круглые скобки. Выражения используются для вычисления новых значений. Тип выражения определяется в зависимости от типов операндов, участвующих в выражении и входящих в него операций.
Правила определения типа выражения:
1) Если в выражении есть хотя бы один вещественный операнд, то выражение будет иметь вещественный тип.
2) Если все операнды в выражении целого типа, выражение будет иметь целый тип, исключение – наличие операции деления (/) – всегда вещественный тип.
Например, если переменная x имеет вещественный тип, а переменные a и b – целый тип, то тип выражений будет определен следующим образом:
2*x+3 – вещественный тип (т.к. x – вещественный тип);
2*a-3 – целый тип (т.к. все операнды – целые);
a/b+3 – вещественный тип (т.к., хотя все операнды – целые, но есть операция деления).



22

---

Логические выражения
При решении задач часто возникают ситуации, когда последующие действия зависят от выполнения некоторого условия, например, вычислять корни квадратного уравнения можно только в случае, когда дискриминант положителен. Для этого используется структура ветвления, которая реализуется в языке Паскаль условным оператором. В качестве условия такого оператора используется логическое выражение. Логическое выражение дает либо истинное, либо ложное значение (true, false).
В логическом выражении могут учувствовать несколько логических операций, приоритет выполнения операций следующий:
1) логическое отрицание;
2) конъюнкция;
3) дизъюнкция;
4) операции сравнения.
Для изменения очередности предназначены круглые скобки.
Пример. Записать логические выражения, истинные при соблюдении следующих условий:
В волейбольную секцию примут детей не старше 13 лет и с ростом не ниже 160 см.
Ответ: (x<=13) and (y>=160), где x – возраст ребенка, а y – его рост.
Примеры записи логических выражений:
(a>3) and (a<5) or (b>2) and (b<10)
not (a<15) or (b>30)
c or d and (b=10)
Приоритет всех операций (от высшего к низшему):
1) операции и функции в скобках;
2) not;
3) *, /, and, div, mod;
4) +, -, or;
5) =, <>, <, >, <=, >=.
23

Основные операторы языка

Оператор присваивания
Оператор используется, чтобы явно присвоить переменной результат вычисления выражения. Формат оператора:
Формат оператора:
<Имя переменной> := <Выражение>;
Примеры:
S:=0;
Name:=’Ваня’;
S:=S+1;
Выполнение оператора присваивания заключается в следующем: сначала вычисляется результат выражения, затем полученное значение записывается в переменную, имя которой стоит слева от знака присваивания.
Оператор присваивания считается верным, если тип выражения соответствует или может быть приведен к типу переменной слева от знака присваивания.
Переменной вещественного типа можно присвоить выражение вещественного или целочисленного типов. Переменной целочисленного типа можно присвоить значение выражения только целочисленного типа.
Например, если объявлены следующие переменные.
Var

i, n : integer;
D : real;
то операторы присваивания:
i:=n/10; – неправильный,
i:=1.0; – неправильный,
d:=i; – правильный.
Если тип выражения не соответствует типу переменной, то компилятор выдает сообщение об ошибке.


24

Составной оператор
Этот оператор, строго говоря, оператором не является. Дело в том, что также как арифметические действия иногда необходимо заключать в скобки, последовательности команд (операторов) тоже иногда требуют объединения. Это позволяют сделать так называемые операторные скобки.
Формат оператора:
Begin
<Оператор 1>;
<Оператор 2>;
......
<Оператор N>
End;
Составной оператор предоставляет возможность выполнить произвольное количество команд там, где подразумевается использование только одного оператора. Такая необходимость встречается довольно часто.

Оператор ввода

Оператор ввода позволяет вводить данные в переменные во время выполнения программы с клавиатуры. Элементами списка ввода являются переменные, которые должны быть заполнены значениями, введенными с клавиатуры.

Формат оператора:
Read(<Список ввода>);
Readln(<Список ввода>);
Например,
read(x,y);
Выполнение оператора ввода происходит следующим образом: ход программы приостанавливается, на экран выводится курсор, компьютер ожидает от пользователя набора данных для переменных, имена которых указаны в списке ввода. Пользователь с клавиатуры вводит необходимые значения в том порядке, в котором они требуются списком ввода, нажимает клавишу Enter.



25

---