П.П.Беленький Информатика Алгоритмизация 2
АЛГОРИТМИЗАЦИЯ
Основные сведения
Понятие алгоритма
Наша цель — научить компьютер решать те задачи, которые он самостоятельно и изначально решать не умеет. Что же для этого нужно?
А что, например, следует сделать, если нужно привлечь к решению задачи человека (назовем его исполнитель), не знакомого с ее решением? В общем виде последовательность действий здесь следующая:
а) выбрать способ (метод) решения задачи и изучить его во всех подробностях;
б) сообщить исполнителю выбранный метод в абсолютно понятном для него виде.
Первый этап этого процесса обычно не вызывает затруднений, так как для большинства встречающихся задач метод решения либо известен из практики, либо подсказывается здравым смыслом, либо описан в литературе. Главная трудность этого этапа — выбрать из нескольких методов более подходящий для решения данной задачи: наименее трудоемкий, максимально эффективный и т.д.
Второй этап значительно сложнее. Дело в том, что если способ (метод) решения задачи описан произвольно, то нет гарантии, что он будет верно понят исполнителем.
Попробуйте, например, небольшую игру. Попросите товарища на время забыть все, что он знает, например, о процессе варки картофеля. Если же выбранный вами помощник еще никогда не варил картошку, то эксперимент будет максимально «чистым». Опишите ему процесс приготовления этого нехитрого блюда и попросите его приготовить, точно следуя вашим инструкциям. После чего удалитесь с кухни и подождите результата в другой комнате. Ну как картошечка? Надеюсь, вы не забыли сказать вашему другу, чтобы он предварительно почистил ее?..
Именно поэтому описание метода следует выполнять в соответствии с определенными правилами, а именно:
выделить величины, являющиеся исходными для задачи;
[pic] [pic] разбить процесс решения задачи на такие этапы, которые известны исполнителю и которые он может выполнить однозначно без всяких пояснений;
указать порядок выполнения этапов;
указать признак окончания процесса решения задачи;
указать во всех случаях, что является результатом решения задачи.
Описание метода, выполненное в соответствии с этими правилами, называется алгоритмом решения задачи.
Составить такое описание обычно нелегко, но, следуя ему, механически выполняя все указанные в нем этапы в требуемом порядке, исполнитель может всегда правильно решить задачу.
Итак, мы подошли к центральному понятию информатики — алгоритму. Более строго это понятие можно дать следующим образом.
Алгоритм — это метод (способ) решения задачи, записанный по определенным правилам, обеспечивающим однозначность его понимания и механического исполнения при всех значениях исходных данных (из некоторого множества значений).
Или более коротко: алгоритм — это строго определенная последовательность действий, необходимых для решения данной задачи.
Примером алгоритма может служить уже упоминавшийся кулинарный рецепт — алгоритм варки картофеля:
Подготовить исходные величины — воду, картофель, соль, посуду (кастрюлю с крышкой для варки), нож.
С помощью ножа очистить картофель и промыть его водой.
Нарезать картофель для варки.
Поместить картофель в кастрюлю.
Залить содержимое кастрюли водой.
Посолить.
Довести воду до кипения.
Убавить огонь.
Варить картофель до готовности (приблизительно в течение 20—30 минут).
Снять кастрюлю с огня и слить воду.
Картофель готов. Процесс прекратить.
Свойства алгоритма
Для углубления понятия алгоритма выделим и раскроем его основные свойства, вытекающие из определения.
Дискретность алгоритма. Это свойство означает, что решение задачи, записанное в виде алгоритма, разбито на отдельные простейшие команды, которые расположены в порядке их выполнения.
Определенность алгоритма. Это свойство означает, что каждая команда алгоритма должна быть понятна исполнителю, не оставлять места для ее неоднозначного толкования и неопределенного исполнения.
Результативность алгоритма. Свойство алгоритма, состоящее в том, что он всегда приводит к результату через конечное число шагов.
Массовость алгоритма. Это свойство заключается в том, что каждый алгоритм, разработанный для решения некоторой задачи, должен быть применим для решения задач этого типа при всех допустимых значениях исходных данных.
Действительно, рассмотрим приведенный выше алгоритм варки картофеля с точки зрения его свойств.
Данный алгоритм дискретен, т.к. весь процесс разбит на отдельные шаги, которых у нас оказалось 11.
Алгоритм определен, т.к. каждая команда описана просто, коротко и достаточно понятно для исполнителя. Более того, команды даны именно в той последовательности, которая необходима для решения данной задачи. Действительно, попробуйте, например, поменять местами пункты 5 и 7 алгоритма. Вряд ли в этом случае вы получите нужный результат.
Алгоритм результативен, т.к. при его точном механическом исполнении вы сможете отведать вполне приемлемый вареный картофель.
Ну и наконец алгоритм обладает свойством массовости, т.к. применим при любых исходных данных: для любого сорта и величины картофеля и для любых кастрюль, ножей и т.п.
Способы описания алгоритмов.
Существует несколько способов описания алгоритмов.
[pic] [pic] Словесно-формульное описание алгоритма, т.е. описание алгоритма с помощью слов и формул.
Графическое описание алгоритма, т.е. описание с помощью специальных графических схем алгоритмов — блок-схем.
Способ, использующий псевдокоды. Псевдокоды — это интерпретация шагов алгоритма на обычном языке, которая описывает действие команды. Псевдокод используется в листингах, чтобы показать общую структуру программы, не применяя реальных операторов языка программирования.
Запись алгоритма на одном из языков программирования (Pascal, Basic и т.п.)
Рассмотрим два способа описания алгоритмов для следующего примера.
Пример.
Составить алгоритм начисления зарплаты согласно следующему правилу: «Если стаж работы сотрудника менее 5 лет, то зарплата 130 руб., при стаже работы от 5 до 15 лет — 180 руб., при стаже свыше 15 лет зарплата повышается с каждым годом на 10 рублей».
Сформулируем задачу в математическом виде:
Вычислить
[pic]
где ZP — зарплата; ST — стаж работы.
A. Словесно-формульное описание алгоритма решения задачи:
Ввести ST, перейти к п.2.
Если ST<5,to ZP:=130, перейти к п. 4, иначе — перейти к п.З.
Если 5<ST<15, то ZP:=180, перейти к п. 4, иначе ZP:=180+(ST-15)10, перейти к п. 4.
Вывести значение ZP, перейти к п. 5.
Конец работы.
B. Графическое описание алгоритма.
Прежде чем перейти к описанию алгоритма графическим способом, введем понятие блок-схемы алгоритма.
Блок-схема алгоритма представляет собой систему связанных геометрических фигур.
Каждая фигура обозначает один этап решения задачи и называется блоком. Порядок выполнения этапов указывается стрелками, соединяющими блоки. В схеме блоки стараются размещать сверху вниз в порядке их выполнения. Для наглядности операции разного вида изображаются в схеме различными геометрическими фигурами.
Наименование этапа
Изображение
Примечание
Прерывание
[pic]
Начало и конец алгоритма
Передача данных
[pic]
Ввод или вывод информации
Процесс
[pic]
Арифметический блок, определяющий действия, которые необходимо выполнить
Принятие решения
[pic]
Логический блок, проверяющий истинность или ложность некоторого условия
Каждый из описанных блоков № 2 и № 3 имеет один вход и один выход. Блок проверки некоторого условия (4) имеет два выхода — Да и Нет
[pic]
Если условие выполняется — выходим из блока по выходу Да, если не выполняется — по выходу Нет.
Вернемся к нашей задаче расчета заработной платы. Блок-схема описанного выше алгоритма будет иметь вид:
[pic]
ВЫВОД_____________________________________________________________
Алгоритм — это строго определенная последовательность действий, необходимая для решения данной задачи.
Алгоритм должен обладать определенным набором свойств.
Дискретность алгоритма: решение задачи, записанное в виде алгоритма, должно быть разбито на отдельные простейшие команды, расположенные в порядке их выполнения.
Определенность алгоритма: каждая команда алгоритма должна быть понятна исполнителю, не оставлять места для ее неоднозначного толкования и неопределенного исполнения.
Результативность алгоритма: алгоритм всегда должен приводить к определенному решению через конечное число шагов (или сообщать, что такого решения нет).
Массовость алгоритма: каждый алгоритм, разработанный для решения некоторой задачи, должен быть применим для решения задач этого типа при всех допустимых значениях исходных данных.
Существует несколько способов описания алгоритмов.
Словесно-формульное описание алгоритма, т.е. описание алгоритма с помощью слов и формул.
Графическое описание алгоритма, т.е. описание с помощью специальных графических схем алгоритмов — блок-схем.
Способ, использующий псевдокоды. Псевдокоды — это интерпретация шагов алгоритма на обычном языке, которая описывает действие команды. Псевдокод используется в листингах, чтобы показать общую структуру программы, не применяя реальных операторов языка программирования.
Запись алгоритма на одном из языков программирования (Pascal, Basic и т.п.)
Основные типы алгоритмов
Типы Алгоритмов
В зависимости от особенностей своего построения алгоритмы делятся на три основные группы:
линейные;
разветвляющиеся;
циклические.
Разнообразие алгоритмов определятся тем, что любой алгоритм распадается на части, фрагменты и каждый фрагмент представляет собой алгоритм одного из трех указанных видов. Поэтому важно знать структуру каждого из алгоритмов и принципы их составления.
Линейные алгоритмы
Л [pic] инейным называется алгоритм, в котором все этапы решения задачи выполняются строго последовательно, т.е. линейный алгоритм выполняется в естественном порядке его написания и не содержит разветвлений и повторений.
Структура такого алгоритма показана на рисунке.
Рассмотрим составление схем линейных алгоритмов на конкретных примерах.
[pic] [pic] [pic] Пример.
Даны переменные А и В. Требуется обменять их значения, т.е. переменная А должна получить значение В, а В — значение А.
Решение:
Исходные данные: А, В. Вспомогательная переменная DOP. Результат: А, В.
Метод решения задачи: в ЭВМ каждая величина хранится в отдельном участке памяти (переменной). Поэтому задача заключается в том, чтобы поменять местами содержимое двух ячеек.
Давайте решим следующую задачу: имеется два стакана: в одном из них вода, в другом молоко. Требуется поменять содержимое стаканов. Житейский опыт подсказывает, что нам для решения данной проблемы потребуется еще один стакан. В него мы перельем воду из первого, затем в первый стакан (из второго) нальем молоко, а из вспомогательного стакана во второй нальем воду.
Аналогично решается и задача обмена значениями двух переменных. Введем в рассмотрение еще одну величину, например С (вспомогательный стакан). Решение задачи распадается на три этапа. Соответствующие им блоки и порядок их выполнения изображены на схеме алгоритма.
[pic]
Мы получили запись алгоритма решения данной задачи с помощью блок-схемы. Рассмотрим теперь запись этого алгоритма с помощью псевдокода.
Напомним, что псевдокоды – это интерпретация шагов алгоритма на обычном языке, которая описывает действие команды.
При записи алгоритма с использованием псевдокодов языки арифметических операций обозначают так:
+, -, /, *.
Знак := (двоеточие и равно) означает операцию присвоения выбранной переменой некоторого значения.
К инструкциям линейных алгоритмов относятся инструкции ввода-вывода информации и инструкция присваивания. На языке псевдокода эти инструкции обозначаются следующим образом:
* Читается: « х присвоить значение 32».
Алгоритм Перемещение; {заголовок алгоритма}
Переменные А, В, Dop: целые числа; {описательный блок}
Начало
Ввод (А, В);
Dop := А;
А := В;
В := Dop;
Вывод (А, В);
Конец.
Проверим составленный алгоритм. Для этого нужно выполнить действия, предусмотренные в алгоритме в том порядке, в каком они записаны. Для того чтобы было легче контролировать значения переменных, исполняя алгоритм, будем составлять трассировочную (тестирующую) таблицу; такую таблицу также называют таблицей значений.
Пусть переменным А и В задаются значения 3 и 6 соответственно. В итоге переменная А должна содержать 6, а В – 3. проверим работу нашего алгоритма.
-
А
В
DOP
1
3
6
0
2
3
6
3
3
6
6
3
4
6
3
3
Результат работы алгоритма совпадает с ожидаемым. Значит, алгоритм составлен верно.
Логические выражения
Прежде чем перейти к рассмотрению ветвящихся и циклических алгоритмов, рассмотрим понятие логического выражения.
В некоторых случаях выбор варианта действий в программе должен зависеть от того, как соотносятся между собой значения каких-то переменных.
Например, расчет корней квадратного уравнения производится по-разному в зависимости от знака дискриминанта (вспомните школьную математику).
В результате сравнения значений двух выражений возможны два варианта ответа: сравнение истинно или ложно?
Например:
2+3 > 3+1 — да (истинно);
О < -7? — нет (ложно).
Выражения такого вида мы будем называть логическими выражениями.
Нам известны 6 операций сравнения:
- Знак
Операции
<
Меньше
>
Больше
<=
Меньше или равно
>=
Больше или равно
=
Равно
<>
Не равно
С помощью этих операций мы будем составлять логические выражения. Причем в выражениях обязательно присутствуют не только константы, но и переменные.
Часто встречаются задачи, в которых используются не отдельные условия, а совокупность связанных между собой условий (отношений). Например, в магазине вам нужно выбрать туфли, размер которых г = 45, цвет соl = белый, цена price не более 400 руб.
Другой пример: школьник выяснил, что сможет купить шоколадку, если она стоит 3 руб. или 3 руб. 50 коп.
В первом примере мы имеем дело с тремя отношениями, связанными между собой союзом «и» и частицей «не», во втором — с двумя отношениями, связанными союзом «или». Подобные условия назовем составными, и для их обозначения в алгоритме договоримся использовать союзы «и», «или», частицу «не», которые будем выделять жирным шрифтом и рассматривать как знаки логических операций, позволяющих из простых условий создавать составные, подобно тому, как из простых переменных и констант с помощью знаков +, - и т.д. можно создавать алгебраические выражения.
Так, условия наших примеров в алгоритме могут выглядеть таким образом:
первое: (г=45) и (со1=белый) и (не (price>400));
второе: (цена=3) или (цена=3,5).
Алгоритмы ветвящейся структуры
Алгоритмом ветвящейся структуры будем называть такой алгоритм, котором выбирается один из нескольких возможных путей (вариантов) вычислительного процесса.
Каждый подобный путь называется ветвью алгоритма.
Признаком разветвляющегося алгоритма является наличие операций условного перехода, когда происходит проверка истинности некоторого логического выражения (проверяемое условие) и в зависимости от истинности или ложности проверяемого условия для выполнения выбирается та или иная ветвь алгоритма. Алгоритм предполагает выполнение Действия 1, если записанное условие истинно (выполняется), и выполнение Действия 2, если условие ложно (не выполняется).
В частном случае может отсутствовать один из блоков «Действие 1» или «Действие 2».
[pic] Пусть, например, В — проверяемое условие, a S1, S2 — некоторые выполняемые инструкции (действия). Тогда: Если условие В выполняется (истинно), то
выбрать для исполнения S1,
иначе
выбрать для исполнения S2
Запишем ветвящийся алгоритм на псевдокоде и графически:
Если В то S1
Иначе
S2
4. Вывод (…)
5. Конец
Существуют задачи, связанные с вычислением функций, заданных несколькими арифметическими выражениями (формулами). Приведем пример такой задачи.
Пример.
Вычислить значение Y по одной из формул:
[pic]
Решение:
Исходные данные: х.
Результат: Y.
Метод решения задачи: необходимо выявить область, которой принадлежит значение х, для этого достаточно проверить заданные условия по порядку. Запишем алгоритм в псевдокодах:
Алгоритм Bemв l;
Переменные х, у: вещественные;
Начало
Ввод (х);
Если х<10 тогда у:=х+2
иначе у:=х-2;
Вывод (у);
Конец.
К задачам рассмотренного выше вида очень часто сводятся вполне реальные задачи. Например, расчет стипендии, если известно среднее арифметическое оценок студента за месяц. Стипендия отличника равна 100 рублям, хорошиста (5 < SRJ4) — 80 рублей, остальные стипендию не получают.
Математическая формула:
[pic]
т.е. мы пришли к задаче вычисления функции по разветвляющемуся алгоритму.
Еще один распространенный вид задач — логические задачи. К ним относятся задачи определения минимума, максимума некоторого числа величин, задачи упорядочивания и сортировки данных и др. Это достаточно сложные задачи, однако в простейших случаях, при небольшом числе данных они приводят к построению несложных алгоритмов разветвляющейся структуры. Рассмотрим примеры подобных задач.
Пример.
Определить: Найти максимальное из двух чисел X, Z:
Y = max{X,Z}.
Решение:
Исходные данные: X, Z.
Результат: Мах.
Метод решения задачи: нужно сравнить два числа и сделать вывод. Блок-схема алгоритма решения этой задачи выглядит следующим образом:
[pic]
Циклический Алгоритм
Реализует повторение некоторых действий. Иными словами, циклические алгоритмы включают в себя циклы.
Циклом называется последовательность действий, выполняемых многократно, каждый раз при новых значениях параметров.
Примером циклических алгоритмов может служить алгоритм покраски забора. Действительно, рассмотрим этот алгоритм в словесно-формульном виде:
Шаг I. Подготовить исходные данные (забор, краску, кисть).
Шаг II. Подойти к забору.
Шаг III. Обмакнуть кисть в краску.
Шаг IV. Нанести краску кистью на поверхность забора.
Шаг V. Если забор еще не весь окрашен, то повторить алгоритм, начиная с пункта (Шаг III).
Существует несколько видов циклических инструкций, с помощью которых можно организовать циклы.
1. Инструкция «цикл с параметром» (цикл с заданным количеством повторений).
Обозначим:
х — параметр цикла (является счетчиком количества повторений);
a, b — соответственно начальные и конечные значения параметра цикла;
h – шаг, с которым изменяется параметр цикла;
S – оператор (инструкция), повторяемый в цикле.
Общий вид структуры цикла с параметром будет:
Для х := а до b с шагом h повторять
S
2. Инструкция «цикл с предусловием» (цикл-«пока»):
Обозначим:
В — некоторое проверяемое логическое условие;
S — оператор (инструкция), повторяемый в цикле.
Тогда инструкция в псевдокоде примет вид:
Повторять
S
Блок-схема такого цикла имеет вид:
[pic]
3. Инструкция «цикл с постусловием» (цикл-«до»):
Пока В повторять
S
Б [pic] лок-схема такого цикла имеет вид:
S
[pic] [pic]
[pic]
[pic]
Да
Нет
[pic] [pic] [pic]
Выход из цикла
Всё вышесказанное об основных типах алгоритмов можно обобщить в виде следующей схемы:
[pic]
Контрольные вопросы
Тестирование
1 [pic] . Строго определенная последовательность действий, необходимая для решения данной задачи — это...
а) метод решения;
б) алгоритм;
в) блок-схема.
2. Ниже перечислены основные свойства алгоритма:
а) дискретность алгоритма;
б) определенность алгоритма;
в) актуальность алгоритма;
г) результативность алгоритма;
д) массовость алгоритма.
Некоторые из этих понятий не относятся к основным свойствам алгоритма. Укажите какие именно.
3. Свойство, означающее, что решение задачи, записанное в виде алгоритма, разбито на отдельные простейшие команды, которые расположены в порядке их выполнения, — это:
[pic] [pic] [pic] а) дискретность алгоритма;
б) определенность алгоритма.
Укажите правильный вариант ответа.
4. Массовость алгоритма — это свойство заключается в том, что каждый алгоритм, разработанный для решения некоторой задачи, должен быть применим для решения задач этого типа при всех допустимых значениях исходных данных.
Верно ли данное высказывание?
а) да;
б) нет.
5. Существует несколько способов описания алгоритмов:
а) словесно-формульное;
б) графическое (блок-схемы).
Все ли способы описания алгоритмов здесь перечислены?
а) да;
б) нет.
6. Псевдокоды — это:
а) описание алгоритма с помощью слов и формул;
б) описание с помощью специальных графических схем алгоритмов;
в) описание шагов алгоритма на обычном языке, которое характеризует действие команды, не применяя реальных операторов языка программирования.
7. Какие из перечисленных описаний можно рассмотреть как алгоритм?
а) порядок безопасного перехода проезжей части улицы по нерегулированному пешеходному переходу;
б) правила дорожного движения в целом;
в) доказательство теоремы Пифагора.
8. Для того, чтобы сделать алгоритм более наглядным, часто используют …
а) блок-схему;
б) таблицу;
в) псевдокоды.
9. Какой тип алгоритмической структуры необходимо применить, если команды данного алгоритма выполняются последовательно одна за другой?
а) циклический;
б) линейный;
в) разветвляющийся.
10. Укажите назначение этапа, соответствующего данному блоку:
[pic] [pic]
а) начало алгоритма;
б) выполнение действия;
в) условие выполнения действия.
1 [pic] 1. Блок имеет:
а) один вход и один выход;
б) один вход и два выхода;
в) два входа и два выхода.
12. Ниже приведены две блок - схемы некоторого алгоритма. Какая из приведенных блок-схем ошибочна?
[pic] [pic] а) б)
13. В зависимости от особенностей своего построения алгоритмы делятся на несколько основных групп:
а) линейные;
б) разветвляющиеся;
в) структурные;
г) циклические.
Некоторые из этих понятий не относятся к основным группам алгоритмов. Укажите, какие именно.
14. «Линейным называется алгоритм, в котором все этапы решения задачи выполняются строго последовательно».
Верно ли данное высказывание?
а) да;
б) нет.
15. «Алгоритмом ветвящейся структуры называется такой алгоритм, в котором выбирается один из нескольких возможных путей (вариантов) вычислительного процесса».
Верно ли данное высказывание?
а) да;
б) нет.
16. Циклом называется …
а) этап решения задачи, выполняемый строго последовательно;
б) последовательность действий, выполняемых многократно, каждый раз при новых значениях параметров;
в) выбор одного из нескольких возможных вариантов вычислительного процесса.
17. Структура какого типа алгоритмов показана на рисунке?
[pic]
а) линейные;
б) разветвляющиеся;
в) циклические.
18. Ниже приведены блок-схемы некоторых алгоритмов. Укажите, какая из вышеприведенных блок-схем является блок-схемой алгоритма линейной структуры?
а) б)
[pic]
19. Укажите, какая из вышеприведенных блок-схем является блок-схемой алгоритма циклической структуры?
а) б)
[pic]
20. Ниже приведены блок-схемы циклических алгоритмов. Укажите, какая из вышеприведенных блок-схем является блок-схемой цикла с постусловием?
а) б)
[pic]
Ответы
П [pic] равильный ответ — б.
Правильный ответ — в.
Правильный ответ — а.
Правильный ответ — а.
Правильный ответ — б.
Правильный ответ — в.
Правильный ответ — а.
Правильный ответ — а.
Правильный ответ — б.
Правильный ответ — в.
Правильный ответ — а.
Правильный ответ — б.
Правильный ответ — в.
Правильный ответ — а.
Правильный ответ — а.
Правильный ответ — б.
Правильный ответ — б.
Правильный ответ — б.
Правильный ответ — а.
Правильный ответ — б.
