Ничушкина Т.Н., Гуренко В.В. - Разработка алгоритмов простейших программ, страница 2

Сначала проверяют выполнение первогоусловия. Из таблицы следует, что первое условие должно выполняться только для первоговарианта решения, поэтому после его проверки ветвь «да» соответствует случаю «неткорней». В ветви «нет» необходимо проверить условие D=0 и в зависимости от еговыполнения указать оставшиеся два случая. В итоге получаем алгоритм, схема которогоприведена выше.Иногда составленная таблица решений приобретает сложный вид.

Рассмотрим,например, таблицу:Р1 Р2 Р3 Р4Условие 1 Y - N YУсловие 2 N Y N NУсловие 3 Y - Nгде P1, P2, P3, P4 – варианты решений.Если сразу приступить к построению алгоритма, то будет получена схема довольногромоздкого алгоритма, приведенная на рисунке 1.2.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»9Рисунок 1.2 – Фрагмент схемы неоптимального алгоритмаТакой алгоритм нельзя считать приемлемым. Однако его можно существенноупростить, если в таблице поменять местами проверяемые условия.

Кроме того, дляудобства построения алгоритма целесообразно также поменять местами столбцы таблицы:Р1 Р4 Р3 Р2Условие 2 N N N YУсловие 1 Y Y N Условие 3 Y N -Алгоритм, построенный по такой оптимизированной таблице, окажется значительнопроще, и его построение потребует меньших усилий (см. рисунок 1.3).Рисунок 1.3 – Фрагмент схемы оптимизированного алгоритмаРассмотрим еще один пример использования таблиц решений.Пример 1.2.

Решить систему уравнений: ax b; xcy 1.При составлении алгоритма необходимо рассмотреть следующие 5 случаев:1) a=0, b=0, тогда x=1-cy, y - любое число;ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»102) a=0, b0, тогда решений нет;3) a0, c=0, a=b, тогда x=1, y любое число;4) a0, c=0, ab, тогда решений нет:5) a0, c0, тогда x=b/a, y=(a-b)/(ac).Составим таблицу решений, указывая в первом столбце условия, которые следуетпроверить:aabc12345b 0Y0Y0 YNYNYNNYNNТеперь преобразуем таблицу для более удобной реализации. На первое местоцелесообразно поставить условие a=0, т.к.

соответствующая строка не содержитпрочерков, а значит, действия однозначно разделятся на две ветви. Вторым лучшепроверять условие b=0, т.к. на оставшиеся два условия оно не оказывает никакоговлияния. Третьим условием удобно взять c=0. В результате получим следующуюоптимизированную таблицу:1a 0 Yb0 Yc0 a b 2YN3NYY4NYN5NNИспользуя эту таблицу, можно построить алгоритм, в котором достаточно сделатьвсего четыре проверки условий (см. рисунок 1.4).Рисунок 1.4 – Фрагмент схемы алгоритма решения системы уравненийОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»11Контрольные вопросы1. Какой вычислительный процесс называют разветвляющимся?2.

Что такое таблица решений и какова ее структура?3. В каких случаях следует применять таблицы решений?4. Каков принцип построения алгоритма по таблице решений?5. Как и с какой целью можно оптимизировать таблицу решений?ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»12ГЛАВА 2. ЦИКЛИЧЕСКИЕ ПРОЦЕССЫ. АЛГОРИТМЫ РЕШЕНИЯЗАДАЧ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ2.1. Типы циклических процессовПри решении задач нередко требуется многократно повторить одну и ту жепоследовательность действий, но над различными значениями переменных. Такиевычислительные процессы называют циклическими, а многократно повторяющиесяучастки алгоритмов – циклами.В любом процедурном языке программирования существуют средства реализациитрех типов циклов: цикла-пока, цикла-до и счетного цикла (см.

рисунки 2.1, а-в).Рисунок 2.1 – Структурные конструкции циклов:а – цикл-пока; б – цикл-до; в – счетный циклКаждый из трех алгоритмов циклических процессов состоит из несколькихосновных этапов:подготовка цикла – задание начальных значений переменным, изменяющимся в цикле;тело цикла – действия, выполняемые непосредственно в цикле;подготовка итерации – изменение значений переменных для очередного выполнениятела цикла;ОглавлениеНичушкина Т.Н., Гуренко В.В.

«Разработка алгоритмов простейших программ»13условие – проверка условия продолжения или окончания цикла;организация счетчика – задание начального и конечного значения, а также шагапеременной цикла.Тело цикла может иметь сложную структуру, в том числе включающую ветвления идругие циклы, которые называют вложенными циклами.

При алгоритмизации задач сиспользованием вложенных циклов необходимо соблюдать правило: внутренний операторцикла и принадлежащая ему область действий должны полностью содержаться в областивнешнего оператора цикла. Иными словами, внешний цикл всегда начинается раньше, азаканчивается позже, чем внутренний цикл.Различают циклы с заданным числом повторений и циклы с заранее неизвестнымчислом повторений – так называемые итерационные циклы. Последние характеризуютсяпостепенным приближением к требуемому значению с заданной точностью илидостижением некоторого другого условия.В конкретных случаях циклических процессов указанные выше этапы цикла могутприсутствовать в различных сочетаниях, однако порядок их проектирования не меняется:1) определяются действия, составляющие тело цикла;2) заполняется блок подготовки итерации;3) определяется условие выхода из цикла (счетчик или логическое выражение);4) заполняется блок подготовки цикла.Рассмотрим пример.Пример2.1.Заданодействительноечислоa>1.Получитьвсечленыпоследовательности a, a2, a3, …, не превышающие действительного числа b.Из условия задачи ясно, что исходными данными являются числа a и b, которые,например, вводятся с клавиатуры.

Именно с их помощью будет формироваться нужноечисло степеней a. Степени можно получить последовательным умножением a на самосебя. Результат умножения будем хранить во вспомогательной переменнойc. Этидействия и являются телом цикла. Так как a0=1, то в блоке подготовки цикла переменнойc устанавливаем начальное значение, равное 1. Условие выхода из цикла – это превышениечисла b числом c.Схема алгоритма решения задачи представлена на рисунке 2.2.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»14Рисунок 2.2 – Схема алгоритма получения последовательности чиселВ теле цикла последовательно вычисляется переменная c, которая принимаетзначения a, a2, a3, … Процесс вычисления продолжается до тех пор, пока c не станетбольшим или равным значению b. Если a  b, то будет выведено только само число а.2.2.

Табулирование функцииТипичным примером циклического процесса с заданным числом повторенийявляется задача табулирования функции, то есть получения таблицы ее значений.Задача сводится к вычислению значений функции y=f(x) при изменении x отначального значения a до конечного значения b с некоторым постоянным шагом h. Такаяпрограмма реализуется посредством цикла с заданным числом повторений n, котороеопределяется по формуле:n b  ah  1,где скобки [ ] означают целую часть от деления. Для решения задачи можно предложитьалгоритм, схема которого приведена на рисунке 2.3.ОглавлениеНичушкина Т.Н., Гуренко В.В.

«Разработка алгоритмов простейших программ»15Рисунок 2.3 – Схема алгоритма табулирования функцииПри подготовке цикла определяется число его повторений n и присваиваетсяначальное значение переменной x. В теле цикла рассчитывается значение функции в точкеx и выводятся значения x и y. При подготовке итерации изменяется значение x,получающее приращение на величину h.2.3.

Нахождение суммы рядаМногие задачи вычислительной математики сводятся к вычислению суммы ряда видаS   rii 1 .Определение суммы предполагает последовательное вычисление членов ряда ri икаждый раз прибавление очередного вычисленного значения к частичной сумме S.Процесс продолжается, пока не будет выполнено условие выхода из цикла. Общий видсхемы алгоритма решения такой задачи приведен на рисунке 2.4. Условие завершенияцикла зависит от поставленной задачи.

Как правило, оно связано с достижениемтребуемой точности.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»16Примеры постановки задачи.S   rii 11. Найти сумму первых n членов ряда. В этом случае условием выхода из циклабудет выполнение неравенства i > n.2. Вычислять сумму рядаS   rii 1до тех пор, пока не будет достигнут очередной член рядаri , меньший заданного .

Здесь условие выхода из цикла следующее: | ri | < .3. Вычислить сумму рядаS   rii 1с точностью , если известно точное значение суммы,равное A. Условие выхода из цикла: | S - A | < .Рисунок 2.4 – Обобщенная схема алгоритма вычисление суммы рядаОчередной член ряда вычисляют одним из следующих способов:в простейших случаях – по формуле общего члена ряда, например:Sа)n 1Sб)n 11rn  n211n 1 ,2cos nxn,rn;cos nxn;по рекуррентным формулам через уже вычисленное значение предыдущего члена ряда,если в формулу общего члена входят, к примеру, целые степени и факториалы.