Практика 2012_Самостоятельно
.docxПрограммирование и основы алгоритмизации. Практикум. 1 семестр ТТИ ЮФУ. ©Е.Ю.Косенко |
2012 |
Тема 1. ФОРМАЛИЗОВАННЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ АЛГОРИТМОВ
Цель: Дать понятие алгоритма и его свойств. Ознакомить студентов с основными формализованными способами представления алгоритмов. Рассмотреть принципы представления базовых структур алгоритмов различными способами.
Аннотация темы: Понятие алгоритма. Свойства алгоритма. Словесный алгоритм. Язык блок-схем. Структурограммы (схемы Насси-Шнайдермана). Язык псевдокода (или языка проектирования программ PDL – Process Design Language). Основные (базовые) структуры алгоритмов: следование, выбор, повторение. Способы представления основных (базовых) структур.
1.2.4. Структурограммы. Структурные диаграммы ‑ могут использоваться в качестве структурных блок-схем, для показа межмодульных связей, для отображения структур данных, программ и систем обработки данных. Существуют различные структурные диаграммы: схемы Насси-Шнейдермана, диаграммы Варнье, Джексона, МЭСИД и др. Все они основываются на общей идее ‑ графическое представление алгоритма в виде схемы действий.
Рассмотрим методику представления схем Насси-Шнайдермана. Они реализуют идеи структурного программирования в схемах алгоритмов. Они представляют собой схему передач управления от блока к блоку не с помощью потоков информации, а с помощью представления вложенности структур.
Поскольку структурное программирование основано на использовании базового набора элементарных структур, то необходимо определить этот набор и здесь. Он включает в себя (рис.1.8):
Рис.1.8.Структурограммы базовых конструкций алгоритмов
В остальном изображение алгоритмов с помощью структурограмм аналогично изображению с помощью блок-схем.
Рассмотрим структурограмму алгоритма умножения чисел n и m с использованием операции сложения (рис.1.9).
Рис.1.9.Структурограмм алгоритма умножения двух чисел
1.2.5. Язык проектирования программ PDL. Альтернативный способ описания логики программы на этапе проектирования – использование псевдокода (или языка проектирования программ PDL – Process Design Language). Он занимает промежуточное положение между естественным языком и языком программирования и состоит из внешнего синтаксиса и внутреннего синтаксиса.
Внешний синтаксис – заданный набор операторов, построенных по образцу языков программирования и описывающий логику программы. Внешний синтаксис соответствует базовым структурам алгоритмов. Кроме того, к внешнему синтаксису также относятся процедуры и модули.
Процедура – это хранимые в памяти машины подпрограммы, которые могут вызываться для выполнения из различных мест основной программы, либо из других процедур. Она вызывается и выполняется до завершения без сохранения внутренних данных.
Модуль – это несколько процедур, организованных в систему для удобства работы пользователя. Модуль имеет доступ к общим данным, которые сохраняются между последовательными вызовами модуля.
Внутренний синтаксис – общий, обычно специально не определяемый синтаксис, пригодный для описания задач в данной области. Практически любое предложение, написанное на естественном языке, либо на специализированном языке (например, математические формулы) может быть использовано.
Рассмотрим Операторы внешнего синтаксиса псевдокода, используемые для представления базовых структур алгоритмов.
линейной (процедура следования);
разветвляющейся (процедура выбора);
циклической (процедура повторения).
Л
первая операция
вторая операция
do
третья операция
end-do
инейная конструкция (следование). Записываются последовательно операции одна под другой. Для отделения части последовательности операторов используются операторы – do…end-do.
Р
if
if-тест
then
then-часть
else
else-часть
end-if
азветвляющейся конструкция (выбор). Записывается условие в конструкции if-тест. В случае истинного значения условия выполняется блок then? в противном случае блок else. Для отделения части последовательности операторов используются операторы – if…end-if.
Множественный выбор. Записывается условие выбора в конструкции "case". В случае совпадения значения условия со значением "список 1" выполняется блок "case-часть1", в случае совпадения значения условия со значением "список 2" выполняется блок "case-часть2" и т.д. В случае несовпадения значения условия с никаким из "списков" , выполняется блок "else" Для отделения части последовательности операторов используются операторы – case…end-case.
case
список 1
case-часть 1
список 2
case-часть 2
…список n
case-часть n
else
else-часть
end-case
Циклическая конструкция (повторение). Цикл-До. Операции структуры "do", включая модификацию until-теста, выполняются один или более раз до тех пор, пока условие "until-тест" не примет значение истина. Для отделения части последовательности операторов используются операторы – do…end-do.
do
do-часть
until
until-тест
end-do
Цикл-Пока. "Do"-часть выполняется пока условие "while-тест" имеет значение истина. "Do"-часть модифицирует условие "while-теста" для того, чтобы окончить вычисления. Для отделения части последовательности операторов используются операторы – while…end-do.
while
while-тест
do
do-часть
end-do
Индексная последовательность (цикл по счетчику). Цикл с заранее определенным числом шагов .
for
индексный список
do
do-часть
end-do
Рассмотрим пример алгоритма вычисления суммы квадратов первых N целых чисел по формуле S=12+22+...+N2 с использованием псевдокода:
Ввести Число слагаемых
Сумма = 0
Номер = 1
do
Сумма = Сумма + Номер2
Увеличить Номер на единицу
Until
Номер > Число слагаемых
end-do
Напечатать Сумму
Алгоритм решения данной задачи при помощи блок-схем представлен на рис.1.10.
Рис.1.10.Блок-схема алгоритма вычисления по формуле S=12+22+...+N2
Пример 1"Ветвление". Составить программу вычисления значения функции f(x,y) для заданных значений a, b, c и произвольного x с автоматическим выбором необходимой формулы:
где .
Алгоритм решения задачи в виде блок-схемы
Алгоритм решения задачи в виде псевдокода
начало
ввод х
если то
иначе
если то
иначе
вывод
конец
Пример 2"Цикл". Составить программу для табулирования функции f(x) от Xmin = 1,2 рад. до X = 2.0 рад. с шагом ΔX = 0,1 рад. (Принять А = 24,398; В = -9,004; Ψ = 340.) Если
Алгоритм решения задачи в виде блок-схемы
Алгоритм решения задачи в виде псевдокода
начало
ввод xmin, xmax, dx, A, B, ,
цикл x = xmin до xmax шаг dx
вывод x, y
конец цикла
конец
Пример 3 "Арифметического цикла со счетчиком". Составить программу для вычисления выражения
Алгоритм решения задачи в виде блок-схемы
При решении данной задачи цикл следует организовывать таким образом, чтобы параметр цикла менялся от значения 20 до 1 с шагом –1.
Блок-схема алгоритма имеет вид:
Алгоритм решения задачи в виде псевдокода
начало
ввод х
цикл n = 20 до 1 шаг –1
конец цикла
вывод s
конец
Пример 4 "Алгоритм нахождения суммы ряда (бесконечной суммы)". Вычислить сумму ряда с точностью ε = 10-3
Нахождение рекуррентной формулы
Суммирование членов ряда продолжаем до тех пор, пока очередной член ряда | | > ε
Решение указанной задачи удобнее вычислять с помощью рекуррентного соотношения, вычисляющего очередной член ряда.
Нахождение рекуррентной формулы:
находим n-й член ряда
находим n+1-й член ряда
находим отношение / = .
записываем рекуррентную формулу = *
Алгоритм решения задачи в виде блок-схемы
Алгоритм решения задач в виде псевдокода
начало
ввод x, eps
s=1
n=0
u=x
цикл пока | u | > eps
s=s+u
n=n+1
u = -u * x * x / (2 n (2n+1))
конец цикла
вывод s
конец
Пример 3 " Алгоритм нахождения конечной суммы ". Составить программу для вычисления выражения вычисления суммы
Алгоритм решения задачи в виде блок-схемы
Алгоритм решения задачи в виде псевдокода
начало
ввод а, n, pi
s = 0
цикл i = 1 до n
конец цикла
s = s * pi
вывод s
конец
Вопросы для самоконтроля
Дайте определение алгоритму.
Охарактеризуйте основные свойства алгоритма.
Перечислите основные (базовых) структуры алгоритмов.
Назовите основные методы формального описания.
В чем особенности словесного описания алгоритмов? Каковы недостатки этого метода?
В чем особенности описания алгоритмов при помощи блок-схем?
Каковы основные элементы блок-схемы? Какие требования к их оформлению?
Как отображается линейная конструкция на языке блок-схем?
Принцип работы разветвляющейся конструкции.
В чем особенности конструкции "обход"?
Принцип работы разветвляющейся конструкции множественный выбор.
Принцип работы циклической конструкции.
Типы циклов.
Что такое итерация цикла?
Принцип работы и особенности Цикла «До» (цикла с постусловием);
Принцип работы и особенности Цикла «Пока» (цикла с предусловием).
Особенности реализации индексной последовательности (цикл по счетчику).
Принципы структурного представления алгоритмов. Диаграммы: схемы Насси-Шнейдермана.
Язык проектирования программ PDL.
Понятие внешнего синтаксиса и внутреннего синтаксиса PDL.
В чем отличие между процедурой и модулем в языке PDL?
Представление основных базовых конструкций на языке PDL.
Составить блок схему алгоритма решения математической задачи и проверить ее на конкретном примере при a=2, b=-7, c=3, a1=-7.5, b1=-7, c1=0.5, a2=2.5, b2=-4, c2=1.5
Составить алгоритм поиска максимального и минимального элемента множества M={a1, a2,…, an}.
Составить алгоритм упорядочивания трех чисел x1, x2, x3.