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

При этомОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»17исключаются повторные вычисления. В этом случае каждый последующий член рядаотличается от предыдущего на один и тот же сомножитель, поэтому вычисления сиспользованием предыдущего значения будут наиболее эффективны, например:S xn!nn 1а)Sб)rn  rn1 xn;,(1n)! xnn 12n(1) xn ;2,rn  rn1если член ряда удобно представить в виде произведения, то один из сомножителейвычисляется по рекуррентному соотношению (т.е. по предыдущему члену ряда), а второй– непосредственно, например:S=n 1n(-1 ) xnn( 1) xn n 11rn  ( 1) x pn1 pn1  ( 1) x   nnnpn,.2.4.

Приближенное вычисление определенных интеграловbПусть требуется вычислить определенный интеграл f ( x)dxa, где f(x) – некотораяфункция, непрерывная на отрезке [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).ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»18Рисунок 2.5 – Метод прямоугольниковПлощадь каждого такого прямоугольника вычисляется по формуле: Si=f(xi)(b-a)/n.Сумма всех площадей полученных прямоугольников приближенно равна значениюопределенного интеграла:bf ( x)dx an 1n1(ba)nf ( x )  (bna)  f ( x )iii 0i 0.Очевидно, чем больше количество отрезков разбиения, тем выше точностьвычислений.Примерсхемыалгоритмавычисленияопределенногоинтеграламетодомпрямоугольников приведен на рисунке 2.6.В этом алгоритме через N обозначено количество точек разбиения, d – длинаотрезков разбиения. Тело цикла алгоритма содержит внутренний цикл с заданным числомповторений.

Число повторений внутреннего цикла представляет собой количествопрямоугольников, на которые мы разбили криволинейную трапецию. После отработкивнутреннего цикла проверяется условие достижения требуемой точности вычисления.Если точность недостаточна, то количество отрезков разбиения увеличивается (например,удваивается как в приведенном алгоритме), и вычисления площади повторяются вновь.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»19Рисунок 2.6 – Схема алгоритма вычисления интеграла методом прямоугольниковУсловие точности, обозначенное на схеме алгоритма блоком решения "Условие",зависит от поставленной задачи. Будем пользоваться двумя способами оценкипогрешности:1) если задано точное значение интеграла, равное I, то условием выхода из циклабудет выполнение неравенства | S - I | < ;2) если точного значения интеграла не задано, то будем сравнивать сумму,полученную при последнем разбиении N, с суммой, полученной при предыдущемзначении параметра N.ОглавлениеНичушкина Т.Н., Гуренко В.В.

«Разработка алгоритмов простейших программ»202.4.2. Метод трапецийМетод трапеций аналогичен методу прямоугольников. Отличие состоит в том, чтокриволинейная трапеция заменяется не прямоугольниками, а прямоугольными трапециями(см. рисунок 2.7).Рисунок 2.7 – Метод трапецийПлощадь i-той прямоугольной трапеции вычисляется следующим образом:Si (b  a )1f (x )  f (x)ii 12nТогда формула приближенного вычисления определенного интеграла методомтрапеций принимает вид:bn 1 f ( x)dx  a(b  a )( f ( xi )  f ( xi  1 ))2ni 0(b  a )nn 1f ( xi )  f ( xi  1 )2i 0илиbf ( x ) dxa f ( a )  f (b) n 1 (b  a )  f ( xi ) 2ni 1.Схема алгоритма разрабатывается аналогично предыдущему методу.2.5. Определение корней уравненияРассмотрим уравнение f(x)=0, о котором известно, что оно имеет корень на отрезке[a, b], причем функция f(x) на данном отрезке непрерывна и на его концах принимаетзначенияпротивоположныхзнаков(т.е.f(a)f(b)<0).ИзлагаемыенижеОглавлениеНичушкина Т.Н., Гуренко В.В.

«Разработка алгоритмов простейших программ»методы21предусматривают некоторую последовательность действий, приводящую к нахождениюнового интервала [ai, bi] такого, чтоa  ai < x0 < bi  b,где x0 – корень уравнения, i – номер итерации. Очевидно, условие существования корнясохраняется: f(ai)f(bi)<0. Сокращение интервала [ai, bi] продолжается до достижениядопустимойпогрешности:|f(xi)|<,гдеxi  [ai,bi] вычисляетсяспособом,реализованным в конкретном методе. За корень уравнения на отрезке [a, b] принимаетсяабсцисса xi: xi  x0 с точностью .2.5.1. Метод половинного деленияМетод является одним из самых простых.

Приближение к корню уравненияосуществляется путем нахождения средней точки c отрезка [a, b], т.е. деления егопополам: |a c| = |c b| (см. рисунок 2.8).Рисунок 2.8 – Метод половинного деленияДалее проверяется, является ли точка cкорнем уравненияf(x)=0. В случаеположительного ответа задача решена. В случае отрицательного необходимо сравнить знакфункции в точке c со знаками функции на концах отрезка и далее рассматривать тот изотрезков [a, c] и [c, b], на концах которого функция принимает значения разных знаков.Новый отрезок вновь делится пополам, и все действия повторяются. Таким образом, рольабсциссы xi, являющейся приближением к корню уравнения на текущей итерации, играеткоордината c, которая вычисляется заново на каждой итерации алгоритма и становитсялевой или правой границей сокращаемого интервала.

В процессе сокращения длинырабочего отрезка искомый корень уравнения остается внутри него. Вычисленияпрекращаются, когда будет достигнута заданная точность вычислений , т.е. |f(с)|< .ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»222.5.2. Метод хордМетод хорд аналогичен методу половинного деления, но обладает лучшейсходимостью, т.е. дает более быстрое приближение к корню уравнения. Новая абсцисса,являющаяся приближением к корню на текущей итерации, находится следующим образом.Точки с координатами (a, f(a)) и (b, f(b)) соединяются отрезком (хордой).

Абсцисса c точкипересечения полученной хорды с осью Ох дает очередное значение корня (см. рисунок2.9.)Рисунок 2.9 – Метод хордКоординату точки c находят по формуле:c  a  f (a)b ab ac b  f (b)f(b)  f (a)f (b)  f (a) или2.6. Нахождение длины кривойПусть функция f(x) непрерывна на отрезке [a, b]. Требуется определить длинукривой, заданной уравнением y=f(x), на этом отрезке. Задачу можно решить, еслиаппроксимировать кривую на данном отрезке ломаной, состоящей из n звеньев, и принятьза длину кривой длину ломаной (см.

рисунок 2.10).ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»23Рисунок 2.10 – Метод хорд нахождения длины кривойДля удобства алгоритмизации следует предусмотреть, чтобы проекция каждого звенана ось Ох имела одну и ту же длину. Таким образом, отрезок [a, b] окажется разбит на nотрезков равной длины, вычисляемой как (b-a)/n, – так же, как в численных методахинтегрирования. Найти длину i-го звена ломаной не представляет труда – это длинаотрезка с координатами (xi, f(xi)) и (xi+1, f(xi+1)), где xi+1= xi+(b- a)/n, xi < b.Начать разбиение отрезка можно с n=2, на следующей итерации n удвоить и т.д.Очевидно, чем больше звеньев ломанной, тем ее длина ближе к искомой длине кривой.Вычисления необходимо продолжать до достижения требуемой точности , определяемой,например, как разность между длинами ломаной, полученными на текущей и предыдущейитерациях.Контрольные вопросы1. Какой вычислительный процесс называют циклическим?2.

Какие типы циклов вы знаете?3. Какие основные этапы присутствуют в любом циклическом процессе?4. Каков порядок проектирования циклического процесса?5. Какой цикл называют вложенным? Какое правило соблюдается при построениивложенных циклов?6. Каковы основные особенности алгоритма табулирования функции?7. Какие можно привести примеры постановки задачи вычисления суммы ряда? Чтоменяется в схеме алгоритма зависимости от постановки задачи?ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»248.Чем отличаются численные методы прямоугольников и трапеций для вычисленияопределенныхинтегралов?Естьлимеждуэтимиметодамисущественноеалгоритмическое различие?9.

Каковы алгоритмические особенности численных методов отыскания корня уравнения назаданном отрезке? В чем их сходство и различие?10. Каковы особенности алгоритма определения длины кривой на заданном отрезке? Скакими из ранее изученных алгоритмов данный метод имеет наибольшее сходство?ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»25ГЛАВА 3.

МАССИВЫМассив – это упорядоченная совокупность однотипных данных, называемыхэлементами массива. Порядок следования элементов в массиве задают так называемыеиндексы. Каждому элементу сопоставлен свой индекс в случае одномерных массивов илиуникальный набор индексов в случае многомерных массивов. В большинстве случаев вкачестве индексов используют конечный ряд целых чисел.Обработка массива сводится к выполнению последовательности действий над егоэлементами. Для обращения к конкретному элементу массива необходимо указать имямассива и значение индекса (индексов) элемента. Можно выделить следующие классызадач обработки массивов:1) последовательная обработка всех элементов массива;2) выборочная обработка элементов массива;3) изменение порядка следования элементов без изменения размеров исходного массива;4) переформирование массива с изменением его размеров;5) одновременная обработка нескольких массивов или подмассивов;6) поиск в массиве элемента, отвечающего заданному условию, причем это может бытьпоиск единственного элемента, либо первого по порядку обработки элемента, либо всехэлементов массива, отвечающих условию.Каждому из перечисленных шести классов задач соответствует своя совокупностьприемов программирования.