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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

рисунок 1.3).8AдаУсловие2 нетда Условие1даP2нетУсловие3 нетP1P4P3BРисунок 1.3 – Оптимизированный фрагмент схемы алгоритмаРассмотрим еще один пример использования таблиц решений.Пример 1.2. Решить систему уравнений: ax  b; x  cy  1.При составлении алгоритма решения задачи необходимо рассмотреть 5 случаев:1) a=0, b=0, тогда x=1-cy, y - любое число;2) 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).Составим таблицу решений, указывая в первом столбце условие, котороенеобходимо проверить:12345a b YNa 0 YYNNNb 0 YNc 0 YYNТеперь преобразуем таблицу для более удобной реализации.

На первое место целесообразно поставить условие a=0, т.к. соответствующая строка не содержит прочерков, и, следовательно, действия однозначно разделятся на две ветви.Вторым лучше проверять условие b=0, т.к. на оставшиеся два условия оно не оказывает никакого влияния. Третьим условием удобно взять c=0. В результате получили таблицу в следующем виде:12345a0YYNNNb0YNc0 YYNa b YNИспользуя эту таблицу, мы можем построить алгоритм, в котором достаточно сделать всего четыре проверки условий (см. рисунок 1.4).9AдадаСлучай 1b=0a=0нетСлучай 2нетнетСлучай 5c=0дадаСлучай 3a=bнетСлучай 4BРисунок 1.4 – Фрагмент схемы алгоритма решения системы уравнений102 Циклические процессы.

Алгоритмы решения задач вычислительной математики2.1Типы циклических процессовПри решении многих задач возникает необходимость многократного повторения одних и тех же действий, но над различными значениями переменных. Такие вычислительные процессы называются циклическими, а многократно повторяющиеся участки – циклами.В любом процедурном языке программирования существуют средства реализации трех типов алгоритмов циклической структуры: цикла-пока, цикла-до исчетного цикла (см.

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

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

Задано натуральное число a. Получить все члены последовательности a, a2, a3, …, не превышающие числа b.Схема алгоритма решения этой задачи представлена на рисунке 2.2.НачалоВводa, bс:=1с<bнетдаc:=c*aВыводcКонецРисунок 2.2 – Схема алгоритма получения последовательностиПри подготовке цикла присваивается начальное значение вспомогательнойпеременной с. Тело цикла включает последовательное вычисление переменной c,которая равна a, a2, a3, … Изменение значения с происходит до тех пор, пока ононе станет большим или равным значению b.

Если a  b, то не будет выведено неодного элемента последовательности.2.2Табулирование функцииТипичным примером циклического процесса с заданным числом повторенийявляется задача табулирования функции (получение таблицы значений функции).Задача сводится к вычислению значений функции y = f(x) при изменении x отначального значения a до конечного значения b с постоянным шагом h. Такаяпрограмма реализуется посредством цикла с заданным числом повторений, причем число повторений определяется по формуле:n ba1.hРешение задачи можно осуществить с помощью алгоритма, схема которогоприведена на рисунке 2.3.12НачалоВводa, b, hn:=((b-a)/h)+1x:=ai:=1,n,1y:=f(x)Выводx, yx:=x+hКонецРисунок 2.3 – Схема алгоритма вычисления значений функцииЗдесь при подготовке цикла вычисляется количество его повторений и присваивается начальное значение переменной x.

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

Общий вид схемы алгоритма решениятакой задачи приведен на рисунке 2.4.Условие окончания цикла зависит от поставленной задачи, как правило, оносвязано с достижением требуемой точности.Примеры постановок задач.1. Найти сумму первых n членов рядада из цикла: i > n.2. Вычислять сумму рядаS   rii 1S   rii 1. В этом случае условие выхо-до тех пор, пока очередной член ряда ri небудет меньше заданного . Здесь условием выхода из цикла будет: | ri | < .3.

Вычислить сумму рядаS   rii 1с точностью , если известно точное зна-чение суммы, равное A. Здесь условие выхода из цикла: | S - A | < .13НачалоВвод...S:=0r:=...S:=S+rнетУсловиедаВыводSКонецРисунок 2.4 – Обобщенная схема алгоритма вычисление суммы рядаОчередной член ряда вычисляют одним из следующих способов: в простейших случаях – по формуле общего члена ряда, например:1) S  n 112n 1rn  21 ;n 1,2) S   consn x ,rn cos nxnn 1; если в формулу общего члена входят целые степени и факториалы, то –по рекуррентным формулам через уже вычисленное значение предыдущего члена, исключая повторные вычисления.В этом случае каждый последующий член отличается от предыдущего наодин и тот же сомножитель, поэтому вычисления с использованием предыдущего значения будут наиболее эффективны, например:n1) S   x ,n 12) S  n 1n!n(  1) xn!rn  rn 1xnrn  rn 1(  1) xn2n,;2; если член ряда удобно представить в виде произведения, один из сомножителей вычисляется по рекуррентному соотношению (т.е.

по предыдущему члену), второй – непосредственно, например:S=k 1k(-1) xkk,rn  (  1) xnn1 npn p n 1(  1) xn p n 1  (  1) x 1n.142.4Приближенное вычисление определенных интеграловbПусть требуется вычислить определенный интеграл f ( x ) dx , где f(x) – некоaторая непрерывная функция, заданная на промежутке [a, b]. Как известно, значение определенного интеграла равно площади криволинейной трапеции, ограниченной подынтегральной функцией. Простейшими методами приближенного вычисления определенных интегралов являются метод прямоугольников и методтрапеций.2.4.1 Метод прямоугольниковРазобьем отрезок [a,b] точками a=x0 < x1 < x2 <... < xn-1 <xn=b, причем |xi,xi+1|=(b-a)/n.

Заменим площадь каждой криволинейной трапеции с основанием [xi,xi+1] площадью прямоугольника со сторонами (b-a)/n и f(xi) (см. рисунок 2.5).y0ax1x2bxРисунок 2.5 – Метод прямоугольниковТогда площадь каждого такого прямоугольника вычисляется по формуле:Si=f(xi)(b - a)/n. Сумма всех площадей полученных прямоугольников приближенноравна значению определенного интеграла:bn 1 f ( x )dx  ai0(b  a ) f ( xi )n(b  a )nn 1 f (x ) .ii0Очевидно, что чем больше количество отрезков разбиения, тем выше точность вычислений.Пример схемы алгоритма вычисления определенного интеграла методомпрямоугольников приведен на рисунке 2.6.В этом алгоритме через N обозначено количество точек разбиения, d –длина отрезков разбиения. Тело цикла алгоритма содержит внутренний цикл с заданным числом повторений. Число повторений внутреннего цикла представляетсобой количество прямоугольников, на которые мы разбили криволинейную трапецию.

После отработки внутреннего цикла проверяется условие достижения требуемой точности вычисления. Если точность недостаточна, то количество отрезков разбиения увеличивается (например, удваивается) и вычисления площади повторяются вновь.15НачалоN:=10N:=2Nd:=(b-a)/Nx:=aS:=f(x)i:=1,N-1S:=S+f(x)x:=x+dS:=S*dнетУсловиедаВыводSКонецРисунок 2.6 – Схема алгоритма вычисления интеграла методом прямоугольниковУсловие точности зависит от поставленной задачи. Будем пользоватьсядвумя способами оценки погрешности:1. Если задано точное значение интеграла, равное I, то условием выхода изцикла будет условие | S - I | < .2. Если не задано точное значение интеграла, то будем сравнивать сумму,полученную при последнем разбиении n, с суммой, полученной при предыдущемзначении параметра n.2.4.2 Метод трапецийМетод трапеций аналогичен методу прямоугольников, только здесь криволинейная трапеция заменяется не прямоугольниками, а трапециями (см.

рисунок2.7).16y0x1ax2bxРисунок 2.7 – Метод трапецийФормула приближенного вычисления определенного интеграла методомтрапеций примет вид:n 1baf ( x ) dx( b  a )( f ( x i )  f ( x i  1 ))2ni0(b  a )nn 1f ( xi )  f ( xi 1 )i02илиbf ( x ) dxa f ( a )  f (b )2n 1i 1 (b  a )f ( xi ) nОпределение корней уравненияРассмотрим уравнение f(x)=0, о котором известно, что оно имеет кореньна отрезке [a, b], причем функция f(x) на этом интервале непрерывна и на концахотрезка [a, b] принимает различные знаки (т.е.

Характеристики

Список файлов книги