Алгоритмы и их свойства (стр. 2 )

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

В соответствии с тремя основными структурами выделяют три типа алгоритмов:

Ø  линейный,

Ø  разветвляющийся,

Ø  циклический.

Формальное исполнение алгоритма

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

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

Для проверки необходимо формальное испол­нение алгоритма. При этом действовать надо строго механически, следуя инструкциям. Формальное исполнение алгоритма позволяет обнаружить ошибки и определить пути их исправления.

Этапы решения задачи с помощью компьютера

Решение задач с помощью компьютера можно разделить на несколько этапов.

1.  Формулировка задачи.

2.  Составление математической модели.
Прежде чем решать задачу с помощью компьютера необходимо разработать ее модель, т. е. выделить наиболее существенные признаки задачи. Мы будем использовать математическое моделирование – составление модели задачи с помощью математических символов. Т. о. составить математическую модель – это значит записать последовательно все формулы, используемые для решения задачи.

3.  Построение алгоритма решения задачи.
На этом этапе, используя словесный способ, составляется алгоритм решения задачи.

4.  Описание величин.
Вводится буквенное обозначение величин, с пояснением и указанием вида величины (исходная, промежуточная или результат)

5.  Построение блок-схемы (переход от словесного способа к графическому)

6.  Составление программы (перевод алгоритма на язык программирования)

7.  Трансляция программы, получение и анализ результатов, корректировка программы.

Рассмотрим эти этапы на примере решения конкретной задачи: «Вычислить периметр прямоугольного треугольника по двум катетам»

1) Формулировка задачи

Дано: два катета прямоугольного треугольника

Надо: вычислить периметр треугольника

2) Математическая модель

p = a + b + c;

3) Словесный алгоритм

а) Задать величины катетов

б) Вычислить гипотенузу с

в) Вычислить периметр р

г) Сообщить ответ р

4) Описание величин

Объект алгоритма	Объект задачи	Примечание
a, b	катеты	исходные
c	гипотенуза	промежуточные
p	периметр	результат

5) Блок-схема

вывод

ввод

6) Программа

Program perimetr;

var a, b, c, p: real;

Begin

write(‘Введите длины катетов’); readln(a, b);

c := sqrt(sqr(a) + sqr(b));

p := a + b + c;

writeln(‘Периметр прямоугольного треугольника равен’, p);

End.

7) На этом этапе необходимо:

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

Вопросы

Что такое алгоритм? Кто может быть исполнителем алгоритма? Дайте характеристику основным свойствам алгоритма. К чему может привести невыполнение свойств алгоритма? Что такое формализация Перечислите основные способы описания алгоритмов. Чем вызвано разнообразие способов записи алгоритмов? Дайте характеристику и приведите примеры словесного и табличного способа. Перечислите основные элементы блок-схемы и их назначение. Назовите требования, предъявляемые к составлению алгоритма. В чем суть структурного подхода к составлению алгоритмов? Перечислите базовые алгоритмические структуры, изобразите их графически. Какие типы алгоритмов вы знаете? Что понимается под формальным исполнением алгоритма? В чём важность возможности формального исполнения алгоритма? Перечислите основные этапы решения задач с помощью компьютера.

Задания

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

2. Исполнитель РОБОТ умеет выполнять пять команд: вправо, влево, вниз, вверх, закрасить. Составьте для РОБОТА следующие алгоритмы, используя линейную или циклическую структуры.

а) сделать ход конем

б) закрасить 10 клеток вправо

в) закрасить квадрат 2х2 клетки

3. Составьте словесный алгоритм и блок-схему решения задач:

а) Вычислить площадь равностороннего треугольника со стороной a.

б) Вычислить значение функции

в) Вводятся N чисел. Вычислить среднее арифметическое этих чисел.

г) Вычислить площадь квадрата, если его периметр равен a.

д) Вычислить значение функции

е) Вводятся N чисел. Вычислить среднее геометрическое этих чисел.

4. Составить алгоритмы решения задач

а) Как переправиться на другой берег трем рыцарям и трем оруженосцам, если имеется двухместная лодка и известно, что оруженосец не плывет и не остается на берегу с чужими рыцарями без товарищей?

б) Как набрать из реки 7 литров воды, если имеются сосуды емкостью 3 и 8 литров?

в) Из 9 монет одна фальшивая (из более легкого металла). Как определить фальшивую монету с помощью весов без гирь за два взвешивания?

§2. Основы языка программирования ПАСКАЛЬ

Язык Паскаль (Pascal) был создан профессором Швейцарского Федерального института технологии в Цюрихе Никлаусом Виртом в 1971 г. Вирт разрабатывал Паскаль как язык структурного программирования, преследуя две цели:

1) создать язык, пригодный для обучения программированию как систематической дисциплине, основанной на ряде фундаментальных понятий, ясно и естественно отраженных в этом языке;

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

Алфавит

Алфавит языка ПАСКАЛЬ содержит:

а) прописные и строчные латинские буквы: А, B,...,Z, a, b, ..., z;

б) цифры арабские: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9;

в) знаки арифметических операций

* умножение / деление

+ сложение - вычитание

DIV - целочисленное деление

MOD - остаток от целочисленного деления

г) знаки отношений

= равно < меньше > больше

д) знаки логических операций: АND (И), OR (ИЛИ), NOT (НЕ) и др.

е) скобки ( ) [ ] (* *) { }

ж) разделители. , : ; '

з) прописные и строчные русские буквы: А, Б, ..., Я, а, б, ..., я;

Из символов алфавита могут быть получены основные конструкции языка – константы, переменные, выражения, операторы, служебные слова.

Константы

Константа – это величина, которая не изменяется в процессе выполнения программы.

Константы в программе могут быть представлены либо непосредственно своим значением, либо именем. Константы бывают четырех типов:

Константы
Символьные	Логические (Булевы)	Числовые
Целые	Вещественные

Символьные константы - набор любых символов алфавита, заключенных в апострофы ‘ ’.

Длина не более 255 символов.

Пример: ‘COMPUTER’, ‘Решений нет’, ‘2000 год’.

Логические константы – выражение, записанное с помощью знаков отношения, значением которого является: TRUE (ИСТИННО) или FALSE (ЛОЖНО).

Пример: 5 + 2 > 4; 7 – 4 = 2.

Числовые константы

Знак "+" перед числом не ставится, а целая часть при записи десятичных дробей отделяется точкой. Нулевую целую часть дробного числа можно опускать.

Пример:

Целые 0 143 -362

Вещественные .01 12.7 -24.356

Числовые вещественные константы записываются в десятичном виде в формах с фиксированной или плавающей точкой.

фиксированная 5.171 731.1371 12.56

плавающая 517.1*10-2 0.7311371*103 0.1256*102

При плавающей форме записи символы *10 обозначаются буквой Е, после которой указывается степень, например:

517.1*10-2 записывается в Паскаль: 517.1Е-02,
0.7311371*103 записывается в Паскаль: 0.7311371Е03.

Переменные

Переменная – это величина, которая изменяет свое значение в процессе выполнения программы.

Каждая переменная имеет три характеристики: имя, значение и тип.

Совокупность латинских букв и цифр, обозначающих переменную, называют ее именем (или идентификатором). Имя переменной должно обязательно начинаться с латинской буквы, нельзя использовать пробелы. В имени переменной могут использоваться квадратные скобки. Служебные слова нельзя использовать в качестве имен. Примеры имен переменных: F, Y1, B3, FUN, E[1], F[4,3] Значение переменной – число или последовательность символов, которые хранятся в данный момент времени в этой переменной. Тип переменной определяется типом принимаемых ею значений:

Символьные	Логические	Числовые
Целые	Вещественные

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