Современный взгляд на алгоритмизацию
Теория алгоритмов строит и изучает конкретные модели алгоритмов. С развитием вычислительной техники и теории программирования возрастает необходимость построения новых экономичных алгоритмов, изменяются способы их построения, способы записи алгоритмов на языке, понятном исполнителю. Особый тип исполнителя алгоритмов – компьютер, поэтому необходимо создавать специальные средства, позволяющие, с одной стороны, разработчику в удобном виде записывать алгоритмы, а с другой – дающие компьютеру возможность понимать написанное. Такими средствами являются языки программирования или алгоритмические языки.
Способы описания алгоритмов
Алгоритмы и программы представляют с помощью конкретных форм записи.
К настоящему времени сложились пять наиболее употребительных способов записи: словесный, формульно-словесный, графический, при помощи псевдокодов и языков программирования.
Словесное описание алгоритма – инструкция о выполнении действий в определенной последовательности с помощью слов и предложений естественного языка.
В формульно-словесном способе записи инструкция о действиях содержит формальные символы и выражения (формулы) в сочетании со словесными пояснениями.
Графическая запись или схема – это изображение алгоритма с помощью геометрических фигур, называемых блоками. Последовательность блоков и соединительных линий образуют схему.
|
|
|
Наряду со схемами для изображения алгоритмов широко используется псевдокод. Псевдокодом называется система правил записи алгоритма с использованием набора определенных конструкций для описания управляющих действий.
Псевдокод позволяет формально изображать логику алгоритма, используя стандартизированные конструкции естественного языка для изображения управления и сохраняя возможности языка для описания действий по обработке информации. Данный способ тесно связан со структурным подходом к программированию. Псевдокод занимает промежуточное положение между естественным языком и языком программирования. Его применяют преимущественно для того, чтобы подробнее объяснить работу программы, что облегчает проверку правильности программы. Кроме того, псевдокод дает программисту большую свободу в изображении алгоритма. Требуется только употреблять стандартные управляющие конструкции и правила записи.
Последним способом записи алгоритмов является язык программирования.
Рассмотренные выше способы удобны для программиста, но не приемлемы для ЭВМ, поскольку они не могут быть однозначно поняты.
Язык программирования – это знаковая система, предназначенная для описания процессов решения задач и их реализации на ЭВМ. Реализация означает, что описания могут быть введены в ЭВМ и однозначно ею поняты. К языкам программирования относятся языки команд или машинные языки и языки высокого уровня.
|
|
|
Первая группа представляет собственный язык ЭВМ, и исполнение программы возможно только в том случае, если она записана на этом языке.
Однако программировать на машинном языке достаточно трудно, что обусловлено чрезмерной детализацией программы, необходимостью знать конкретную систему команд и детально представлять работу ЭВМ. Представление сложной программы на машинном языке неудобно для восприятия человеком.
Эти недостатки послужили стимулом для создания языков программирования высокого уровня, не совпадающих с машинными.
Идея таких языков состоит в представлении программ в виде не только приемлемом для ЭВМ, но и удобном для пользователя.
Средства графического изображения алгоритмов
Схемы алгоритмов
Описание алгоритмов с помощью схем – один из наиболее наглядных и распространенных способов задания алгоритмов. Правила построения алгоритмов определены соответствующими стандартами.
|
|
|
Основные символы схем алгоритмов представлены на рисунке. Символы схемы располагаются сверху вниз. Линии соединения символов – линии потока, показывают направление процесса обработки. Стрелки на соединяющих линиях не ставят при направлениях сверху-вниз и слева-направо; противоположные направления показывают стрелкой на линии потока.
Основные символы схем алгоритмов
Содержание действия, обозначенного символом, раскрывается внутри символа и может быть записано на формальном или естественном языке.
Алгоритмы бывают трех видов: линейные, разветвляющиеся и циклические.
Условные изображения и примеры простейших линейного, разветвляющегося и циклического алгоритмов приведены на рисунке.
Алгоритм независимо от его структуры – сложной или простой всегда имеет один «Останов». Все ветви алгоритма должны сойтись при движении по нему на символе «Останов».
Однако требования к графическому исполнению схем вызывают предубеждение некоторых программистов, представляются основным недостатком схем и заставляют искать новые способы записи алгоритмов.
Основные виды алгоритмов:
а – линейный, б – разветвляющий, с – циклический
|
|
|
В качестве иллюстрации изобразим алгоритм вычисления функции
в виде схемы.
Схема алгоритма вычисления функции
Псевдокодом называется подробное описание алгоритма на структурированном и частично формализованном подмножестве английского (русского) языка. Псевдокод, обладая всеми положительными качествами схем, имеет еще и собственные преимущества. Псевдокод менее схем ограничен правилами изображения. Основное – использование только служебных конструкций и соблюдение правил ступенчатой записи.
Структурограммы
Иллюстрация действий вычислительного процесса, выражающегося в передаче управления от одной части программы к другой, с помощью схем алгоритмов является старым, но не очень удобным средством.
Лучшим средством графического изображения процесса передачи управления (исполнения) являются так называемые структурограммы. Они дают полное визуальное представление деталей логических операций над группами операторов программы.
По имени их авторов такой способ изображения называют еще диаграммами или схемами Нэсси–Шнейдермана.
Диаграмма Нэсси–Шнейдермана – это схема, иллюстрирующая структуру передачи управления внутри модуля с помощью вложенных друг в друга блоков. Диаграммы представляют собой хорошую систему описания и понимания процесса передачи управления в программе.
Основные символы диаграмм показаны на рисунке.
Каждый блок имеет форму прямоугольника и может быть вписан в любой внутренний прямоугольник любого другого блока. Запись внутри блока производится на естественном языке или с помощью математических обозначений.
При использовании структурограмм следует иметь в виду ряд обстоятельств:
· структурограмма, описывающая полную разработанную программу, сама представляет собой большой символ обработки, содержащий внутри себя другие символы;
· в полной программе, описанной системой вложенных блоков (структурограммой), управление начинает свой путь на верхней стороне внешнего прямоугольника, проходит через каждый прямоугольник и завершает путь на нижней стороне внешнего прямоугольника;
· структурограмма законченной программы или ее логически завершенной части должна размешаться на одной странице; в отличие от схем алгоритмов разрыв структурограмм и перенос их на другую страницу недопустим, так как здесь отсутствуют явные линии передачи управления от блока к блоку.
Практическое занятие
Пример 1. Рассмотрим пример алгоритма с циклом, имеющим наперед неизвестное количество проходов. Для этого решим следующую задачу. Указать наименьшее количество членов ряда натуральных чисел 1, 2, 3, ..., сумма которых больше числа К.
Пример 3. Дан двумерный квадратный массив Z, состоящий из N строк и N столбцов. Необходимо найти среднее арифметическое S его отрицательных элементов и заменить положительные элементы побочной диагонали массива средним арифметическим S.
Пример 2. Рассмотрим задачу сортировки одномерного массива Z длины N. Отсортировать массив – значит расположить его элементы в порядке роста или убывания. Опишем метод сортировки массива в порядке роста. Сначала выполняется проход по массиву с целью определения в нем наименьшего элемента. Затем производится перестановка этого элемента с первым. Далее совершается второй проход по массиву, начиная со второго элемента. Найденный наименьший элемент переставляется со вторым и т. д. После (N-1)-го прохода с выполнением названных операций массив окажется отсортированным.
Дата добавления: 2020-12-12; просмотров: 461; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!