Часть 4. Алгоритмизация и программирование
Глава 8. Основы алгоритмизации
8.1. Понятие и свойства алгоритма
Алгоритм это последовательность арифметических, логических и прочих операций, необходимых для выполнения на ЭВМ. Применительно к ЭВМ алгоритм определяет вычислительный процесс, начинающейся с обработки некоторой совокупности возможных исходных данных и направленный на получение определенных этими исходными данными результатов. Термин «вычислительный процесс» распространяется и на обработку других видов информации, например, символьной, графической или звуковой.
Алгоритм – одно из фундаментальных понятий информатики. Алгоритмизация наряду с моделированием выступает в качестве общего метода информатики.
Алгоритмы являются объектом систематического исследования пограничной между математикой и информатикой научной дисциплины, примыкающей к математической логике – теории алгоритмов. Понятие алгоритма и определение его свойств позволяет познакомиться с алгоритмизацией.
Основными свойствами алгоритмов являются:
1. Универсальность (массовость) – применимость алгоритма к различным наборам исходных данных.
2. Дискретность – процесс решения задачи по алгоритму разбит на отдельные действия.
3. Однозначность (детерминированность) – правила и порядок выполнения действий алгоритма имеют единственное толкование.
4. Конечность – каждое из действий и весь алгоритм в целом обязательно завершаются.
5. Результативность – по завершении выполнения алгоритма обязательно получается конечный результат.
6. Выполнимость – алгоритм достигает результата за конечное число шагов.
Алгоритм должен быть всегда результативен, иметь свойство повторяемости и рассчитан на конкретного исполнителя.
В технике таким исполнителем является ЭВМ. Для обеспечения возможности реализации на ЭВМ алгоритм должен быть описан на языке, понятном ЭВМ, то есть на машинном языке, созданным с помощью языка программирования.
Алгоритм может быть представлен различными способами, в частности:
1) словесно;
2) таблично;
3) в виде блок-схемы;
4) на алгоритмическом языке.
Достаточно распространенным способом представления алгоритма является его запись на алгоритмическом языке, представляющем в общем случае систему обозначений и правил для единообразной и точной записи алгоритмов и исполнения их, т.е. запись в виде прораммы.
Предпочтительнее до записи на алгоритмическом языке представить алгоритм в виде блок-схемы.
Для построения алгоритма в виде блок-схемы необходимо знать назначении каждого из блоков.
В таблице 8.1 представлены типы блоков и их назначение.
8.2. Таблица блоков
Таблица 8.1
№
|
блок
|
Назначение блока
|
комментарий
{блоку соответствует оператор}
|
1
|
|
Начало или конец
блок-схемы
|
-
|
2
|
|
Ввод данных с клавиатуры
|
ввода
|
3
|
|
Процесс (в частности вычислительный)
|
присваивания
|
4
|
|
решение
|
условия
|
5
|
|
вывод
|
вывода
|
6
|
|
Модификатор цикла
|
цикла
|
7
|
|
Типовой процесс
|
Процедура, функция
|
Примечание.
В блок-схемах ввод и вывод может быть представлен в виде параллелограмма.
Алгоритмизация выступает как набор определенных практических приёмов, особых специфических навыков рационального мышления в рамках заданных языковых средств. Алгоритмизация вычислений предполагает решение задачи в виде последовательности действий, т.е. решение, представленное в виде блок-схемы. Можно выделить типичные алгоритмы. К ним относятся:
-
Линейные алгоритмы;
-
Разветвляющиеся алгоритмы;
-
Циклические алгоритмы;
Из перечисленного списка простейшими является линейные алгоритмы.
Задачи, приводящие к линейным алгоритмам, рассматриваются в примере, представленном в виде блок-схемы на рис. 8.1.
8.3. Линейные алгоритмы
Задача 1. Вычислить и вывести на экран значение функции:
Y = sin (2 x) / (a + x) b;
Представить выполнение задачи в виде блок-схемы.
Решение.
На рис. 8.1 представлена блок-схема для задачи 1.
Рис. 8.1. Блок-схема линейного алгоритма
8.4. Ветвления
Разветвляющиеся алгоритмы редполагают проверку условий для выбора решения. Соответственно в алгоритме появится столько разветвлений, сколько условий. Во второй задаче рассматривается один из примеров разветвляющихся алгоритмов.
Пример 2.
Найти максимальное значение из трёх различных целых чисел, введенных с клавиатуры.
Представить выполнение задачи в виде блок-схемы.
Решение.
Для этой простой задачи можно представить несколько различных алгоритмов. Алгоритм задачи 2, представленный в виде блок-схемы на рис. 8.2, предусматривает проверку каждого условия отдельно. Такой вариант ветвления позволяет анализировать каждое из условий.
Рис. 8.2. Блок-схема алгоритма ветвления
Алгоритм ветвления задачи 2, представленный в виде блок-схемы на рис. 8.3, предусматривает проверку сразу двух условий одновременно.
Такой вариант ветвления проще, но не позволяет анализировать каждое из условий.
Рис. 8.3. Блок-схема алгоритма ветвления
8.5. Циклы. Повтор с заданным количеством циклов
Пример 3.
Дано количество циклов n. Требуется найти произведение значений счётчика цикла.
В этом примере известно количество циклов. Поэтому произведение будет равно р=123,…,n. С клавиатуры вводится любое количество циклов и р=1. Данный алгоритм можно назвать «вычисление факториала», который применим в разделах 3.13.3 для вычисления перестановок, размещений и сочетаний. Алгоритм этой эадачи дан на рис. 8.4.
Рис. 8.4. Блок-схема циклического алгоритма решения задачи 3
8.6. Вопросы для самоконтроля по теме «Алгоритмизация»
1. Определите правильный ответ.
Выбрать из списка значения переменных, которые следует ввести с клавиатуры, чтобы алгоритм закончил работу:
a) A = -5; C=-2. b) A = - 2; C=-5. c) A=0; C=0. d) A=1; C=1.
2. Определите правильный ответ.
После выхода из цикла переменные равны:
a) A=3; C=-1. b) A=1; C=7. c) A=0; C=0. d) A=-1; C=5.
3. Определите правильный ответ.
Выбрать из списка значения переменных, которые следует ввести с клавиатуры, чтобы алгоритм закончил работу:
a) A =2; C =-2. b) A=-2; C =-2. c) A=0; C=0. d) A=2; C=2.
4. Определите правильный ответ.
Выбрать из списка значения переменных, которые следует ввести с клавиатуры, чтобы алгоритм закончил работу:
a) A=1; C=1. b) A=-1; C=1. c) A=0; C=0. d) A=1; C=-2.
5. Определите правильный ответ.
Выбрать из списка значения переменных, которые следует ввести с клавиатуры, чтобы алгоритм закончил работу:
a) A=-5; C=5. b) A=5; C=-5. c) A=5; C=5. d) A=0; C=0.
6. Определите правильный ответ.
Выбрать из списка значения переменных, которые следует ввести с клавиатуры, чтобы алгоритм закончил работу:
a) A=1; C=1. b) A=1; C=-1. c) A=0; C=0. d) A=0; C=-2.
7. Определите правильный ответ
Выбрать из списка значения переменных, которые следует ввести с клавиатуры, чтобы алгоритм закончил работу:
a) A=7; C=7. b) A=5; C=-5. c) A=-5; C=5. d) A=0; C=0.
8. Определите правильный ответ.
Выбрать из списка значения переменных, которые следует ввести с клавиатуры, чтобы алгоритм закончил работу:
a) A=5; C=5. b) A=-5; C=5. c) A=0; C=0. d) A=5; C=-5.
9. Определите правильный ответ.
Выбрать из списка значения переменных, которые следует ввести с клавиатуры, чтобы алгоритм закончил работу:
a) A=-10; C=-10. b) A=10; C=-1. c) A=10; C=-10. d) A=-10; C=10.
|
