Способы представления (записи) алгоритмов
Лекция 7
Алгоритмизация
1. Понятие алгоритма
2. Свойства алгоритмов
3. Способы представления (записи) алгоритмов
4. Типы алгоритмов
5. Линейные алгоритмы
6. Логические выражения
7. Разветвляющиеся алгоритмы
8. Циклические алгоритмы
Понятие алгоритма
Наша цель — научить компьютер решать те задачи, которые он самостоятельно и изначально решать не умеет. Что же для этого нужно?
А что, например, следует сделать, если нужно привлечь к решению задачи человека (назовем его исполнитель), не знакомого с ее решением? В общем виде последовательность действий здесь следующая:
1) выбрать способ (метод) решения задачи и изучить его во всех подробностях;
2) сообщить исполнителю выбранный метод в абсолютно понятном для него виде.
Первый этап этого процесса обычно не вызывает затруднений, так как для большинства встречающихся задач метод решения либо известен из практики, либо подсказывается здравым смыслом, либо описан в литературе. Главная трудность этого этапа — выбрать из нескольких методов более подходящий для решения данной задачи: наименее трудоемкий, максимально эффективный и т. д.
Второй этап значительно сложнее. Дело в том, что если способ (метод) решения задачи описан произвольно, то нет гарантии, что он будет верно понят исполнителем.
Именно поэтому описание метода следует выполнять в соответствии с определенными правилами, а именно:
|
|
|
—выделить величины, являющиеся исходными для задачи;
—разбить процесс решения задачи на такие этапы, которые известны исполнителю и могут быть выполнены однозначно без всяких пояснений;
—указать порядок выполнения этапов;
—указать признак окончания процесса решения задачи;
—указать во всех случаях, что является результатом решения задачи.
Описание метода, выполненное в соответствии с этими правилами, называется алгоритмом решения задачи.
Составить такое описание обычно нелегко, но, следуя ему, механически выполняя все указанные в нем этапы в требуемом порядке, исполнитель может всегда правильно решить задачу.
Итак, мы подошли к центральному понятию информатики — алгоритму. Более строго это понятие можно дать следующим образом:
Алгоритм— это метод (способ) решения задачи, записанный по определенным правилам, обеспечивающим однозначность его понимания и механического исполнения при всех значениях исходных данных (из некоторого множества значений).
Или (более коротко):
Алгоритм — это строго определенная последовательность действий, необходимых для решения данной задачи.
Примером алгоритма может служить уже упоминавшийся кулинарный рецепт — алгоритм варки картофеля:
|
|
|
1. Подготовить исходные величины — воду, картофель, соль, посуду (кастрюлю для варки с крышкой), нож.
2. С помощью ножа очистить картофель и промыть его водой.
3. Нарезать картофель для варки.
4. Поместить картофель в кастрюлю.
5. Залить содержимое кастрюли водой.
6. Посолить.
7. Довести воду до кипения.
8. Убавить огонь.
9. Варить картофель до готовности (приблизительно в течение 20-30 минут).
10.Снять кастрюлю с огня и слить воду.
11. Картофель готов. Процесс прекратить.
Свойства алгоритма
Для углубления понятия алгоритма выделим и раскроем егоосновные свойства, вытекающие из определения.
1. Дискретность алгоритма . Это свойство означает, что решение задачи, записанное в виде алгоритма, разбито на отдельные простейшие команды, которые расположены в порядке их выполнения.
2. Определенность алгоритма . Это свойство означает, что каждая команда алгоритма должна быть понятна исполнителю, не оставлять места для ее неоднозначного толкования и неопределенного исполнения.
3. Результативность алгоритма . Свойство алгоритма, состоящее в том, что он всегда приводит к результату через конечное число шагов.
4. Массовость алгоритма . Это свойство заключается в том, что каждый алгоритм, разработанный для решения некоторой задачи, должен быть применим для решения задач этого типа при всех допустимых значениях исходных данных.
|
|
|
Действительно, рассмотрим приведенный выше алгоритм варки картофеля с точки зрения его свойств.
Данный алгоритм дискретен, так как весь процесс разбит на отдельные шаги, которых у нас оказалось 11.
Алгоритм определен, так как каждая команда описана просто, коротко и достаточно понятно для исполнителя. Более того, команды даны именно в той последовательности, которая необходима для решения данной задачи. Действительно, попробуйте, например, поменять местами пункты 5 и 7 алгоритма. Вряд ли в этом случае вы получите нужный результат.
Алгоритм результативен, так как при его точном механическом исполнении вы сможете отведать вполне приемлемый вареный картофель.
Ну и, наконец, алгоритм обладает свойством массовости, так как применим при любых исходных данных: для любого сорта ивеличины картофеля и для любых кастрюль, ножей и т. п.
Способы представления (записи) алгоритмов
Существует несколько способов описания алгоритмов:
1) словесно-формульноеописание алгоритма, т. е. описание алгоритма с помощью слов и формул;
|
|
|
2) графическоеописание алгоритма, т.е. описание с помощью специальных графических схем алгоритмов — блок-схемы;
3) способ, использующий псевдокоды. Псевдокоды— это интерпретация шагов алгоритма на обычном языке, которая описывает действие команды. Псевдокод используется в листингах, чтобы показать общую структуру программы, не применяя реальных операторов языка программирования;
4) запись алгоритма на одном из языков программирования (Pascal, Basic и т.п.).
Рассмотрим два способа описания алгоритмов для следующего примера.
Пример
Составить алгоритм начисления зарплаты согласно следующему правилу:
если стаж работы сотрудника менее 5 лет, то его зарплата 130 руб., при стаже работы от 5 до 15 лет — 180 руб., при стаже свыше 15 лет зарплата повышается с каждым годом на 10 рублей.
Сформулируем задачу в математическом виде.
Вычислить
где ZP — зарплата; ST — стаж работы.
Дата добавления: 2020-12-12; просмотров: 499; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!