Практическая работа №12

Решение задач на составление линейных алгоритмов

1. Цель работы: овладеть практическими навыками разработки и анализа алгоритмов линейной структуры.

 

2. Теоретическое обоснование

Для составления программы, предназначенной для решения на ЭВМ какой-либо задачи, требуется составление алгоритма ее решения.

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

Алгоритм — это точное предписание, определяющее про­цесс перехода от исходных данных к результату.

Алгоритм — это конечная последовательность действий (команд) приводящая к определенному конкретному результату.

Свойства, которыми должен обладать алгоритм:

1. Конечность (финитность) алгоритма. Алгоритм должен приводить к решению задачи обязательно за конечное время. Последовательность правил, приведшая к бесконечному циклу, алгоритмом не является.

Другими словами - конечность — обязательное завершение каждого из дей­ствий, составляющих алгоритм, а также завершение вы­полнения алгоритма в целом;

2. Определенность,(Однозначность) или детерминированность, алгоритма. Это свойство означает, что неоднозначность толкования записи ал­горитма недопустима.

Другими словами - однозначность — наличие единственного толкования пра­вил выполнения действий и порядка их выполнения;

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

Другими словами - результативность — получение при выполнении алго­ритма определенного результата;

4. Массовость алгоритма. Это означает, если правильный ре­зультат по алгоритму получен для одних исходных данных, то правильный результат по этому же алгоритму должен быть полу­чен и для других исходных данных, допустимых в данной задаче.

Другими словами - массовость — возможность применения алгоритма для решения целого класса задач (предполагается его пра­вильная работа при меняющихся в заданных пределах значениях исходных данных);

5. Эффективность алгоритма. Под эффективностью алгорит­ма будем понимать такое его свойство (качество), которое позво­ляет решить задачу за приемлемое для разработчика время. К па­раметру, характеризующему эффективность алгоритма, следует отнести также объем памяти компьютера, необходимый для ре­шения задачи.

Другими словами - правильность — способность алгоритма давать правиль­ные результаты при решении поставленных задач.

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

· линейный — набор команд (указаний), выполняемых последовательно друг за другом;

· разветвляющийся — алгоритм, содержащий хотя бы одну проверку условия, в результате которой обеспечивается переход на один Из возможных вариантов решения;

· циклический — алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К цикличе­ским алгоритмам сводится большинство методов вычисле­ний и перебора вариантов.

В зависимости от степени детализации, поставленных целей, методов и технических средств решения задачи используются различные формы представления алгоритмов. На практике наи­более распространены следующие способы:

· словесный;

· формульно-словесный;

· блок-схемный; 

· языки программирования.  

Блок-схемный — это графическое изображение алгоритма, в котором каждый этап процесса обработки данных представляет­ся в виде геометрических фигур (блоков), имеющих определен­ную конфигурацию в зависимости от характера выполняемых операций.

Блок-схемы строятся по определенным правилам и вклю­чают в себя геометрические фигуры (блочные символы), соединенные между собой стрелками (линиями), указыва­ющими порядок выполнения операций. Блочные символы стандартизированы и различаются по типу выполняемых действий (ГОСТ 19.002-80 и 19.003-80, международные стандарты 13О 2636-73 или 15О 1028-73).

Таблица 1 - Условные обозначения блоков схем алгоритмов

Наименование	Обозначение	Функции
Процесс		Выполнение операции или группы операций, в результате которых изменяется значение, форма представления или расположение данных.
Ввод-вывод		Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод).
Решение		А) Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий.     Б) Выбор одного из N направлений выполнения алгоритма, в зависимости от некоторых условий.
Модификация		Организация циклических конструкций
Пуск-останов		Начало, конец, прерывание процесса обработки данных.
Соединитель		Указание связи между прерванными линиями, соединяющими блоки.
Межстраничный соединитель		Указание связи между прерванными линиями, соединяющими блоки, расположенные на разных листах.

Пример 1. Рассчитать площадь и периметр прямоугольника по двум известным сторонам.

Составим алгоритм решения подобных задач:

1) Прочитать задачу.

2) Выписать известные и неизвестные нам переменные в «дано». (В задаче №1 к известным переменным относятся стороны: a,b;к неизвестным — площадь S и периметр P)

3) Вспомнить либо составить необходимые формулы. (У нас: S=a*b; P=2*(a+b))

4) Составить блок-схему.

5) Записать решение на языке программирования Pascal. Запишем условие в более кратком виде.

Дано: a,b

Найти: S,P

Блок-схема:

Пример 2. Разработать алгоритм вычисления гипотенузы прямоугольного треугольника по известным значениям длин его катетов a и b.

На примере данной задачи рассмотрим все три этапа разработки алгоритма решения задачи:

Этап 1. Математическое описание решения задачи.

Математическим решением задачи является известная формула:

где с-длина гипотенузы, a, b – длины катетов.

Этап 2. Определение входных и выходных данных.

Входными данными являются значения катетов a и b. Выходными данными является длина гипотенузы – c.

Этап 3. Разработка алгоритма решения задачи.

Словесное описание алгоритма	Запись алгоритма на языке блок-схем
Начало алгоритма. Ввод значений длин катетов a и b. Вычисление длины гипотенузы с по формуле Вывод значения длины гипотенузы. Конец алгоритма	На данной схеме цифрами указаны номера элементов алгоритма, которые соответствуют номерам пунктов словесного описания алгоритма.

3. Алгоритм выполнения работы: