Понятие о структурном подходе к разработке алгоритмов

Понятие о языках программирования

Языки программирования близки к естественному, но имеют более жестокие правила, так как их должны понимать ЭВМ. Программа, составленная на языке программирования, не может быть непосредственно реализована на ЭВМ, так как она умеет выполнять только последовательность элементарных операций, а в программе на языке программирования в одном выражении может, например, содержаться несколько операций. Форма записи такой программы понятна человеку, но недоступна ЭВМ. Поэтому необходимо какое-то промежуточное звено, которое осуществляло бы работу по расчленению отдельных действий программы и записи их на машинном языке. Работа эта несложная, но требует скрупулезного внимания и педантичности. К такой работе больше всего и приспособлена ЭВМ. Поэтому перевод программы с языка программирования на машинный осуществляется самой ЭВМ с помощью специальной программы, называемой транслятором. В программе-трансляторе «заложены» все правила языка программирования и способы преобразования различных его конструкций на машинный язык. Поэтому при составлении программы на языке программирования нужно точно придерживаться правил этого языка, иначе ЭВМ вас не поймет или поймет неправильно.

Хотя языки программирования имеют сходство с естественным (при их создании специально ставилась такая цель), но между ними есть и важное различие. Естественный язык ориентирован на человека и может использоваться как промежуточный этап в разработке программы (особенно в начальной стадии изучения программирования). Язык программирования ориентирован на ЭВМ. Отсюда следует, что в программе на языке программирования обязательно присутствуют операции ввода-вывода информации.

Под каждую переменную, использованную в программе, ЭВМ выделяет ячейки памяти. Перед началом вычислений в некоторые из этих ячеек вводятся исходные значения, что осуществляется операцией ввода. После окончания вычислений в определенных ячейках памяти получаются результаты вычислений. Чтобы их узнать, нужно выполнить операцию вывода, которая заключается в том, что значения переменных, хранящиеся в указанных в команде вывода переменных (ячейках памяти), преобразуются в привычную для человека форму и печатаются на бумаге или высвечиваются на экране дисплея.

Основные структуры алгоритмов – это ограниченный набор стандартных способов соединения блоков (команд) алгоритма для выполнения типичных последовательностей действий. Структурный подход к разработке алгоритмов и программ предлагает использование только нескольких основных структур, комбинация которых дает все многообразие алгоритмов и программ. К основным структурам относятся:

1. следование;

2. цикл «До»;

3. цикл «Пока»;

4. разветвление;

5. обход.

Следование – последовательное размещение блоков и групп блоков (в программе достигается последовательным размещением команд), также часто называется алгоритмом с линейной структурой.

Цикл «До» (рисунок 9) – применяется при необходимости выполнять какие-либо вычисления несколько раз до тех пор, пока выполняется некоторое условие. Особенность этого цикла состоит в том, что он всегда выполняется хотя бы один раз, так как первая проверка условия выхода из цикла происходит после того, как тело цикла выполнено. Тело цикла – та последовательность действий, которая выполняется многократно (в цикле). Инициализация – задание начальных значений тем переменным, которые используются в теле цикла.

В программе вычисления произведения двух натуральных чисел при помощи операции сложения как раз был использован цикл «До». На естественном языке циклу «До» соответствует алгоритм: 1 Инициализация 2 Тело цикла 3 Если условие идти к 2

Рисунок 9. Блок-схема цикла «До»

Цикл «Пока» (рисунок 10) отличается от цикла «До» тем, что здесь проверка условия проводится до выполнения цикла. Если при первой проверке условие не выполняется, то тело цикла также не выполнится ни разу. На естественном языке циклу «Пока» соответствует алгоритм: 1 Инициализация 2 Если не условие идти к 5 3 Тело цикла 4 Идти к 2 5... где 5 – номер команды после цикла.

Рисунок 10. Блок-схема цикла «Пока»

Разветвление (рисунок 11, а) применяется, когда в зависимости от условия нужно выполнять либо одно, либо другое действие. «Действие 1» или «действие 2» может в свою очередь содержать несколько команд.

На естественном языке эта структура изображается алгоритмом:

1 Если условие идти к 4

2 Действия 2

3 Идти к 5

4 Действия 1

5...

где 5 – номер первой команды общей части программы (после разветвления).

а)

б)

Рисунок 11. Блок-схемы «Разветвления» и «Обхода»

Обход (рисунок 11, б) – частный случай разветвления, когда одна ветвь не содержит никаких действий.

На естественном языке эта структура изображается алгоритмом:

1 Если не условие идти к 3

2 Действия

3...

где 3 – номер первого оператора общей части программы.

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

Обычно при составлении блок-схемы управление идет сверху вниз, возвращаясь назад только в циклах. Это дает простую и наглядную структуру алгоритма, по которой далее легко составить программу.

Один из приемов разработки алгоритма решения более сложных задач – метод пошаговой детализации, при котором первоначально продумывается и фиксируется общая структура алгоритма без детальной проработки отдельных его частей, но при этом также используются лишь основные структуры алгоритмов. Блоки, требующие дальнейшей детализации, обозначаются пунктирной линией. Далее прорабатываются (детализируются) отдельные блоки, не детализированные на предыдущем шаге. Таким образом, на каждом шаге разработки уточняется реализация фрагмента алгоритма (или программы), т.е. решается более простая задача. Полностью закончив детализацию всех блоков, получаем решение задачи в целом.

Пример 1. Разделить натуральное число x на натуральное число y, получить в качестве результата частное от деления q и остаток r, т.е. представить число x в виде x = qy + r, где q – целое число; r < y. Операцию деления не использовать.

Решение. Операцию деления можно представить как последовательность вычитаний делителя из делимого, тогда количество вычитаний будет частным от деления q. Последовательные вычитания нужно проводить до тех пор, пока результат вычитания не станет меньше делителя. Эта последняя разность и будет остатком от деления r.

Ниже приводятся блок-схема алгоритма (рисунок 12) и программа на естественном языке для решения этой задачи.

Исходные данные: x, y – натуральные числа.

Результат: q, r.

1 r = x 2 q = 0 3 Если r < y идти к 7 4 r = r – y 5 q = q + 1 6 Идти к 3 7 Останов

Рисунок 12. Блок-схема алгоритма примера 1

Здесь условие выхода из цикла проверяется до входа в цикл (цикл «Пока») и при x < y, тело цикла не выполняется ни разу, т.е. остается r = x и q = 0.

Пример 2. Задано число x. Вычислить функцию знака числа

Далее приводится блок-схема алгоритма (рисунок 13) и программа на естественном языке для решения этой задачи. Алгоритм представляет собой «разветвление», содержащее «разветвление» в одной из ветвей.

Исходные данные: x – любое число.

Результат: S.

1 Если x < 0 идти к 7

2 Если x = 0 идти к 5

3 S = 1

4 Идти к 8

5 S = 0

6 Идти к 8

7 S = -1

8 Останов

Рисунок 13. Блок-схема алгоритма примера 2

Здесь команды 4 и 6 «идти к N» позволяют обойти одну из ветвей разветвления, если уже выполнена другая.

Пример 3. Выбрать максимальное из двух чисел x, y и присвоить его значение переменной u.

Решение. Просматривая числа по очереди, мы «видим» сначала только первое число x. Будем считать его максимальным и присвоим u значение x, т.е. u = x. Затем u сравним со вторым числом y, и если окажется, что старое значение u меньше y, то u присвоим новое значение, иначе u оставим без изменения.

Ниже приводится блок-схема алгоритма и программа на естественном языке.

Исходные данные: x, y – любые числа.

Результат: u – максимальное из x и y.

1 u = x 2 Если u ≥ y идти к 4 3 u = y 4 Останов

Рисунок 14. Блок-схема алгоритма примера 3