Сократить интервал определения x
Московский государственный технический университет
имени Н. Э. Баумана
Факультет Информатика и системы управления
Кафедра Компьютерные системы и сети
«УТВЕРЖДАЮ»
Заведующий кафедрой ИУ-6
_________ Сюзев В.В.
Г. С. Иванова, Т.Н. Ничушкина
Разработка алгоритмов программ Разветвленной и циклической структуры
Методические указания по выполнению домашнего задания № 1
по курсу «Алгоритмические языки и программирование»
для студентов 1 курса специальностей ИУ6 и АК5
МОСКВА 2011
Оглавление
1. Понятие алгоритма. Основные алгоритмические структуры.. 3
2. Схемы алгоритма и псевдокоды.. 3
3. Метод пошаговой детализации. 8
4. Методические указания по выполнению домашнего задания. 11
Список литературы.. 11
Понятие алгоритма. Основные алгоритмические структуры
Алгоритмом называют формально описанную последовательность действий, которые необходимо выполнить для получения требуемого результата.
Различают последовательности действий (вычислений) линейной, разветвленной и циклической структуры.
Линейная структура процесса вычислений предполагает, что для получения результата необходимо выполнить некоторые операции в определенной последовательности. Например, для определения площади треугольника по формуле Герона необходимо сначала определить полупериметр треугольника, а затем по формуле рассчитать его площадь.
|
|
|
Разветвленная структура процесса вычислений предполагает, что конкретная последовательность операций зависит от значений одного или нескольких параметров. Например, если дискриминант квадратного уравнения не отрицателен, то уравнение имеет два корня, а если отрицателен, то действительных корней оно не имеет.
Циклическая структура процесса вычислений предполагает, что для получения результата некоторые действия необходимо выполнить несколько раз. Например, для того, чтобы получить таблицу значений функции на заданном интервале изменения аргумента с заданным шагом, необходимо соответствующее количество раз определить следующее значение аргумента и посчитать для него значение функции.
Процессы вычислений циклической структуры в свою очередь делятся на три группы:
· счетные циклы или циклы с заданным количеством повторений – циклические процессы, для которых количество повторений известно;
· итерационные циклы – циклические процессы, завершающиеся по достижении или нарушении некоторых условий;
· поисковые циклы – циклические процессы поиска некоторой информации в таблицах, выход из которых происходит при нахождении необходимой информации или по завершению процесса поиска, если необходимая информация не найдена.
|
|
|
Схемы алгоритма и псевдокоды
Формальное описание алгоритмов осуществляют с использованием схем алгоритмов и псевдокодов. На изображение схем алгоритмов существует ГОСТ 19.701–90, согласно которому каждой группе действий ставится в соответствие блок особой формы. Некоторые, часто используемые обозначения приведены в таблице 1.
Таблица 1
| Название блока | Обозначение | Назначение блока |
| 1. Терминатор | 
| Начало, завершение программы или подпрограммы |
| 2. Процесс | 
| Обработка данных (вычисления, пересылки и т.п.) |
| 3. Данные | 
| Операции ввода-вывода |
| 4. Решение | 
| Ветвления, выбор, итерационные и поисковые циклы |
| 5. Подготовка | 
| Счетные циклы |
| 6. Граница цикла | 
| Любые циклы |
| 7. Предопределенный процесс | 
| Вызов процедур |
| 8. Соединитель | 
| Маркировка разрывов линий |
| 9. Комментарий | 
| Пояснения к операциям |
При разработке алгоритма каждое действие обозначают соответствующим блоком, показывая их последовательность линиями, идущими слева направо и сверху вниз. Для удобства чтения схемы желательно, чтобы линия входила в блок сверху, а выходила снизу. Если направление линии отлично от стандартного, то в конце линии ставится стрелка, в противном случае ее можно не ставить.
|
|
|
Если схема алгоритма не умещается на листе, то используют соединители. При переходе на другой лист или получении управления с другого листа в комментарии указывается номер листа, например, «с листа 3», «на лист 1».
Доказано, что для записи любого, сколь угодно сложного алгоритма достаточно трех базовых управляющих структур:
следование – обозначает последовательное выполнение действий (см. рисунок 1, а);
ветвление – соответствует выбору одного из двух вариантов действий (см. рисунок 1, б);
цикл-пока – определяет повторение действий, пока не будет нарушено некоторое условие, выполнение которого проверяется в начале цикла (см. рисунок 1, в).
Рисунок 1 -Базовые алгоритмические структуры: следование (а), ветвление (б) и цикл-пока (в)
Помимо базовых структур используют еще три дополнительные структуры, производные от базовых:
· выбор – обозначающий выбор одного варианта из нескольких в зависимости от значения некоторой величины (см. рисунок 2, а);
Рисунок 2 - Дополнительные структуры и их реализация через базовые структуры: выбор (а-б), цикл-до (в-г) и цикл с заданным числом повторений (д-е)
|
|
|
· цикл-до – обозначающий повторение некоторых действий до выполнения заданного условия, проверка которого осуществляется после выполнения действий в цикле (см. рисунок 2, в);
· цикл с заданным числом повторений (счетный цикл) – обозначающий повторение некоторых действий указанное количество раз (см. рисунок 2, д).
На рисунке 2 (б, г и е) показано, как каждая из дополнительных структур может быть реализована через базовые структуры.
Перечисленные структуры были положены в основу структурного программирования – технологии, которая представляет собой набор рекомендаций по уменьшению количества ошибок в программах. В том случае, если в схеме алгоритма отсутствуют другие варианты передачи управления, алгоритм называют структурным, подчеркивая, что он построен с учетом рекомендаций структурного программирования.
Схема алгоритма детально отображает особенности разработанного алгоритма. Иногда такой высокий уровень детализации не позволяет выделить суть алгоритма. В этих случаях для описания алгоритма используют псевдокод.
Псевдокод базируется на тех же основных структурах, что и структурные схемы алгоритма. Описать на псевдокоде неструктурный алгоритм нельзя.
Для каждой структуры используют свою форму описания. В специальной литературе были предложены несколько вариантов псевдокодов. Один из них приведен в таблице 2.
Таблица 2
| Структура | Псевдокод | Структура | Псевдокод |
| 1. Следование | <действие 1> <действие 2> | 4. Выбор | Выбор <код> <код1>: <действие 1> <код2>: <действие 2> ... Все-выбор |
| 2. Ветвление | Если <условие> то <действие 1> иначе <действие 2> Все-если | 5. Цикл с заданным количеством повторений | Для<индекс> = <n>,<k>,<h> <действие> Все-цикл |
| 3. Цикл-пока | Цикл-пока <условие> <действие> Все-цикл | 6. Цикл-до | Выполнять <действие> До<условие> |
Пример 1.Разработать алгоритм определения наибольшего общего делителя двух натуральных чисел.
Существует несколько способов определения наибольшего общего делителя двух натуральных чисел. Самым простым из них является так называемый «алгоритм Евклида». Суть этого метода заключается в последовательной замене большего из чисел на разность большего и меньшего. Вычисления заканчиваются, когда числа становятся равны.
Например:
| а) | A B | б) | A B |
| 225 125 | 13 4 | ||
| 225-125=100 125 | 13-4=9 4 | ||
| 100 125-100=25 | 9-4=5 4 | ||
| 100-25=75 25 | 5-4=1 4 | ||
| 75-25=50 25 | 1 4-1=3 | ||
| 50-25=25 = 25 | 1 3-1=2 | ||
| 1 = 2-1=1 |
Программа должна начинаться с ввода чисел. Заметим, что любой ввод данных пользователем должен сопровождаться запросом на ввод, чтобы пользователь знал, чего от него ждет программа после запуска. На схеме алгоритма и при записи псевдокодов этот запрос часто не указывают.
В основе алгоритма лежит циклический процесс, количество повторений которого заранее не известно (итерационный). Условие выхода из цикла – получение одинаковых чисел. Поскольку нельзя исключить, что пользователь введет равные числа, проверку будем осуществлять на входе в цикл, т. е. имеет смысл использовать цикл-пока. Если числа не равны, то при каждом проходе цикла одно из чисел (большее) должно заменяться разностью большего и меньшего. Для реализации этой замены потребуется описать оба варианта, т.е. использовать ветвление с проверкой, какое из чисел больше. После выхода из цикла можно выводить пользователю любое из двух полученных чисел, так как они равны между собой.
На рисунке 3 показана схема алгоритма, а ниже приведено его описание на псевдокоде.
Рисунок 3 - Схема алгоритма Евклида
Алгоритм Евклида:
Ввести A,B
цикл-пока A¹B
если A>B
то A:=A-B
иначе B:=B-A
Все-если
Все-цикл
Вывести А
Конец алгоритма
Алгоритмы более сложных программ разрабатывают, используя специальный метод.
Метод пошаговой детализации
С использованием метода пошаговой детализации разработку алгоритмов выполняют поэтапно. На первом этапе описывают решение поставленной задачи, выделяя подзадачи и считая их решенными. На следующем – аналогично описывают решение подзадач, формулируя уже подзадачи следующего уровня. Процесс продолжают, пока не доходят до подзадач, алгоритмы решения которых очевидны. При этом, описывая решение каждой задачи, желательно использовать не более одной-двух конструкций, таких как цикл или ветвление, чтобы четче представить себе структуру программы.
Пример 2. Разработать программу, которая с заданной точностью e находит значение аргумента x по заданному значению функции y при известном значении n.
(x+1)n+1
y = ---------- , где n>1, x>0.
x
При n>1 данная функция является монотонно возрастающей. Следовательно, для нахождения значения x можно применить метод половинного деления. Суть метода заключается в следующем. Вначале определяют отрезок [x1,x2], такой что f(x1)£y£f(x2). Затем делят его пополам xt=(x1+x2)/2 и определяют, в какой половине отрезка находится x, для чего сравнивают f(xt) и y. Полученный отрезок опять делят пополам и так до тех пор, пока разность x1 и x2 не станет меньше заданного значения e.
Для разработки алгоритма используем метод пошаговой детализации.
Шаг 1.Определяем общую структуру программы:
Программа:
Ввести y, n, eps.
Определить x.
Вывести x, y.
Конец.
Шаг 2. Детализируем операцию определения x:
Определить x:
Определить x1, такое что f(x1)£y.
Определить x2, такое что f(x2)³y.
Определить x на интервале [x1,x2].
Все.
Шаг 3. Детализируем операцию определения x1. Значение x1 должно быть подобрано так, чтобы выполнялось условие f(x1)£y. Известно, что x>0, следовательно, можно взять некоторое значение x, например, x1=1, и последовательно уменьшая его, например, в два раза определить значение x1, удовлетворяющее данному условию:
Определить x1:
x1:=1
цикл-пока f(x1)>y
x1:=x1/2
все-цикл
Все.
Шаг 4. Детализируем операцию определения x2. Значение x2 находим аналогично x1, но исходное значение будем увеличивать в два раза.
Определить x2:
x2:=1
цикл-пока f(x2)<y
x2:=x2*2
все-цикл
Все.
Шаг 5. Детализируем операцию определения x. Определение x выполняется последовательным сокращением отрезка [x1, x2].
Определить x:
цикл-покаx2-x1>eps
Сократить отрезок [x1,x2].
Все-цикл
Все.
Шаг 6. Детализируем операцию сокращения интервала определения x. Сокращение отрезка достигается делением пополам и отбрасыванием половины, не удовлетворяющей условию f(x1)£y£f(x2)
Сократить интервал определения x.
xt:=(x1+x2)/2
если f(xt)>y
то x2:=xt
иначе x1:=xt
Все-если
Все.
Таким образом, за шесть шагов мы разработали весь алгоритм. Полностью он выглядит следующим образом.
Программа:
Ввести y,n,eps.
x1:=1
цикл-пока f(x1)>y
x1:=x1/2
Все-цикл
x2:=1
цикл-пока f(x2)<y
x2:=x2/2
Все-цикл
цикл-покаx2-x1>eps
xt:=(x1+x2)/2
если f(xt)>y
то x2:=xt
иначе x1:=xt
Все-если
Все-цикл
Вывести xt,y.
Конец.
При разработке алгоритма методом пошаговой детализации мы использовали псевдокод, но можно было использовать и схемы алгоритма.
Достоинством метода является то, что в процессе разработки на каждом шаге мы решали одну достаточно простую задачу. Использование метода, таким образом, существенно облегчает разработку алгоритмов.
Дата добавления: 2018-04-04; просмотров: 307; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!