Geum.ru

Лекция Алгоритмы и ЭВМ

Вид материалаЛекция

Содержание


Способы описания алгоритмов.
Подобный материал:





Лекция

Алгоритмы и ЭВМ.


Цель- познакомить учащихся с понятиями алгоритма, его свойствами, способами описания.


Рассмотрим простую жизненную ситуацию: вы хотите, чтобы ваш младший брат вместо вас выполнил какую-то неприятную работу, вроде мытья полов, но которую он, к сожалению, не умеет делать! В таком случае надо его научить! Так же, как поступают и в 1000 подобных случаев:

а) выбирают способ решения задачи и изучают его во всех подробностях;

б) сообщают исполнителю выбранный метод в абсолютно понятном для него виде;

в) исполнитель решает задачу строго в соответствии с методом.

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

Второй этап значительно сложнее. Дело в том, что, если способ решения задачи описан произвольно, нет гарантии, что он будет верно понят исполнителем. Поэтому описание метода следует выполнять в соответствии с определёнными правилами, а именно:

- выделить величины, являющиеся исходными для задачи;

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

- указать порядок выполнения этапов;

- указать признак окончания процесса решения задачи;

- указать во всех случаях, что является результатом решения задачи.

Описание метода, выполненное в соответствии с этими правилами, называется алгоритмом решения задачи.

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

Примером алгоритма может служить кулинарный рецепт приготовления блюда.

Рассмотрим простейший алгоритм – алгоритм заваривания чая:

1. Подготовить исходные величины – чай, воду, чайник, стакан, ложку.

2. Налить в чайник воду.

3. Довести воду до кипения и снять с огня.

4. Всыпать в чайник чай.

5. Довести воду до кипения, снять с огня.

6. Чай готов. Процесс прекратить.

Основные свойства алгоритма, вытекающие из его определения.

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

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

3. Результативность алгоритма. Свойство алгоритма, состоящее в том, что он всегда приводит к результату через конечное, возможно, очень большое число шагов.

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

Оказывается, процесс решения задачи с помощью ЭВМ, в целом, мало чем отличается от только что рассмотренного процесса решения этой же задачи человеком – исполнителем. Так же следует выбирать и изучать метод решения задачи, так же составлять алгоритм и решать задачи строго в соответствии с ним, только решать должна ЗВМ, а не человек.

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

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

Существует значительное число подобных языков – БЕЙСИК, ФОРТРАН, ПЛ/1, ПАСКАЛЬ и др. Они называются языками программирования. Запись алгоритма на таком языке называется программой, а процесс перевода алгоритма на указанный язык – программированием.


Способы описания алгоритмов.

Словесно-формульное описание алгоритма, т. е. описание алгоритма с помощью слов и формул. Это наиболее простой способ. Кулинарный рецепт – пример такого описание алгоритма.

Задача 1.1. Составить алгоритм начисления зарплаты согласно следующему правилу:

Если стаж работы сотрудника менее 5 лет, то зарплата 130000 рублей, при стаже работы от 5 до 15 лет – 180000 рублей, при стаже свыше 15 лет зарплата повышается с каждым годом на 10000 рублей.

Сформулируем задачу в математическом виде: вычислить


130, если ST<5;

ZP = 180, если 5< ST<15;

180 + ( ST – 15 )10, если 15
где ZP - зарплата; ST- стаж работы.

Словесно – формульное описание алгоритма решения задачи 1.1:

1. Ввести ST, перейти к п. 2.

2. Если ST<5, то ZP:=130, перейти к п. 4, иначе- перейти к п. 3.

3. Если ST<15,то ZP:=180, перейти к п. 4, иначе ZP: = 180+(ST – 15)10, перейти к п. 4.

4. вывести значение ZP, перейти к п. 5.

5. Вычисление прекратить.

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

Операция присваивания изображается прямоугольником, например:


Блок “Процесс”


Y: =In2+3B




Операция ВВОД и ВЫВОД изображается параллелограммом, например:





Каждый из трёх указанных блоков имеет 1 вход и 1 выход.

Операция Условный переход изображается ромбом; блок имеет два входа – Да и Нет, например:


Если условие выполняется – выходим из блока по выходу Да, если не выполняется – по выходу Нет.

Начало процесса решения задачи обознается блоком Начало.

Завершение процесса решения задачи обозначается блоком Останов.

Последние два блока изображаются так:





3. Описание алгоритма на алгоритмическом языке.

Алгоритмический язык – это средство для записи алгоритмов в аналитическом виде, промежуточном между записью алгоритма на естественном языке и записью на языке ЭВМ ( языке программирования .)

Пример: запись алгоритма решения задачи 1.1 на алгоритмическом языке:

алг зарплата ( цел ST, вещ ZP)

арг ST

рез ZP

нач

если ST<5

То ZP:=150

иначе

если ST<=15

то ZP:=180

иначе ZP:=180+(ST-15)*10

все

все

кон

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