В.А. Антонюк, А.П. Иванов - Программирование и информатика (Краткий конспект лекций) (1109543), страница 3
Текст из файла (страница 3)
Вычислятьзначение будем по значениям функции () в некоторых точках . Значения эти будемсчитать известными.Как известно, геометрическая интерпретация смысла определённого интеграла – площадькриволинейной трапеции под графиком функции = () над отрезком [, ] (в случае отрицательных значений функции часть площади учитывается со знаком минус). Этот отрезокразбивается на части точками деления 1 , .
. . , −1 ; 0 = , = . Вместо площади под графиком будем приближённо находить суммарную площадь узких полосок над/под отрезкамиразбиения [−1 , ], = 1, . . . , .Формулы, по которым приближённо вычисляются значения определённых интегралов, называются квадратурными формулами.3.1.Квадратурные формулы левых и правых прямоугольниковОснованием каждого прямоугольника служит отрезок [−1 , ], высотой в первом случае (формула левых прямоугольников) является значениефункции в точке −1 , во втором (формула правых прямоугольников) – значение в точке . В первом случае площадь прямоугольника будет равна = (−1 )( − −1 ),во втором = ( )( − −1 ).Суммируя по всем отрезкам разбиения (т.е., по от 1 до ), получаем квадратурную формулу левых прямоугольников : ≈ =∑︁=1 (−1 )( − −1 )и квадратурную формулу правых прямоугольников : ≈ =∑︁=1 ( )( − −1 ).Ошибки имеют в этих формулах разные знаки, в чём легко убедиться,рассматривая для простоты сначала случай монотонной функции: видно,что прямоугольники в одном методе имеют площади немного большие, чемнужно, а в другом – немного меньшие.
Можно попытаться взаимно скомпенсировать эти ошибки, взяв полусумму и в качестве приближённогозначения интеграла11 ∑︁ ≈ ( + ) =( (−1 ) + ( ))( − −1 ).22 =1То, что получилось – формула трапеций (см. далее).143.2.Квадратурная формула центральных прямоугольниковВ качестве высот рассматриваемых прямоугольников выберем высоты изсередин отрезков, т.е. из точек1− 1 = (−1 + ).22Площадь прямоугольника будет равна = (− 1 )( − −1 ),2откуда ≈ =∑︁=1 (− 1 )( − −1 ).2Когда отрезки разбиения одинаковы (длина одного – ℎ = ( − )/), тогда≈ℎ∑︁ (− 1 ).=12Возникающая ошибка подсчёта интеграла на отрезке зависит от знака второй производной в середине отрезка (прямоугольник равновелик трапеции, верхней стороной которойслужит касательная к графику функции в срединной точке): ′′ (− 1 ) < 0 → < 0, ′′ (− 1 ) > 0 → > 0.23.3.2Квадратурная формула трапецийПлощадь под графиком функции на отрезке заменяется на площадь трапеции, тогда1 ∑︁( (−1 ) + ( ))( − −1 ).
≈ =2 =1Если все отрезки одинаковы, то ≈ =ℎ ∑︁( (−1 ) + ( )).2 =1В этой сумме все значения функции ( ) – кроме (0 ) = и ( ) = –встречаются два раза, поэтому можно написать и так: ≈ =−1∑︁ℎ( () + () + 2 ( )).2=1Говорят, что формула трапеций имеет второй порядок точности, т.к. при удвоении числаотрезков оценка ошибки уменьшается вчетверо, т.е., как вторая степень длины отрезка ℎ.Легко заметить, что знаки ошибок и – противоположны, поэтому можно скомбинировать формулы трапеций и центральных прямоугольников.
Поскольку, как известно,оценки этих ошибок различаются в два раза ( ≈ 2 ), ошибки /2 и будут примернокомпенсировать друг друга.1 ≈ = (2 + ).3На отрезке [−1 , ]:111(2 (− 1 ) + ( (−1 ) + ( ))) = ( (−1 ) + 4 (− 1 ) + ( )),2232615поэтому (для случая одинаковых отрезков разбиения) ≈ =ℎ ∑︁( (−1 ) + 4 (− 1 ) + ( )).26 =1Оказывается, получилась формула Симпсона – четвёртого порядка точности.3.4.Квадратурная формула Симпсона (формула парабол)Эту формулу можно получить и «честно», приближая интегрируемуюфункцию на каждом отрезке [−1 , ] фрагментом параболы (квадратнымтрёхчленом) так, чтобы парабола имела в точках −1 , и середине отрезка− 1 те же значения, что и функция, а в качестве приближенного значения2интеграла от функции на отрезке используя значение интеграла для этогофрагмента параболы.Поскольку три точки (−1 , (−1 )), (− 1 , (− 1 )), ( , ( )) однозначно22задают некоторую параболу с коэффициентами , , , для определенияэтих коэффициентов можно записать такую систему:⎧⎪⎪⎨ 2−1 + −1 + = (−1 ) 2− 1 + − 1 + = (− 1 )222⎪⎪⎩ 2 + + = ( )Значение неизвестного интеграла от функции () на отрезке [−1 , ]затем аппроксимируется интегралом от функции 2 + + на этом отрезке: ≈∫︁2( + + ) = −1∫︁∫︁2 + −1 + −1∫︁ = −1⃒ 3 ⃒⃒2 ⃒⃒⃒⃒+ ⃒+ ⃒−1−1−132Далее можно, конечно, решать систему и находить неизвестные , , для этого отрезка,выражая с их помощью нужный интеграл, но мы поступим немного по-другому: мы перегруппируем слагаемые полученной приближённой формулы и увидим, что этот результатможет быть выражен только через значения (−1 ), (− 1 ), ( ) и − −1 .23 ⃒2 ⃒⃒ + ⃒⃒+ ⃒⃒= ≈ ⃒⃒−13 −12 −133−1−32 − 2−1+ + ( − −1 )2Вынося из последнего полученного выражения общий множитель 16 ( − −1 ), преобразуемоставшийся сомножитель 2 (2−1 + −1 + 2 ) + 3 (−1 + ) + 6 далее:2 2−1 + 2 −1 + 2 2 + −1 + + 2 −1 + 2 + + + 4 == 2−1 + −1 + + 2 + + + 2−1 + 2 −1 + 2 + 2 −1 + 2 + 4 =⏟⏞ (−1 )⏟⏞ ( )−1 + = (−1 ) + ( ) + 42⏟(︂)︂2−1 + + 4 = (−1 ) + 4 (− 1 ) + ( )22⏞+ 44 (− 1 )2Таким образом, для случая одинаковых отрезков разбиения ( − −1 = ℎ, = 1, .
. . , )оценка интеграла по всему отрезку [, ] будет равна:≈∑︁=1 =ℎ ∑︁( (−1 ) + 4 (− 1 ) + ( )).26 =1164.4.1.Алгоритмы поискаПоиск элемента в массивеРазберём две простейших задачи: 1) поиска минимального элемента в последовательности(массиве) и 2) поиска номера минимального элемента в массиве.Мы не знаем, какой элемент в массиве является минимальным, поэтому нам придётся просмотреть их все, сравнивая с каким-то «предполагаемым минимальным». Пусть, например,это будет первый элемент массива.Min = a[0];for (i = 1; i < size; i++)if (a[i] < Min)Min = a[i];Для поиска номера – всё аналогично:0aMinI = 0;for (i = 1; i < size; i++)if (a[i] < a[MinI])MinI = i;size−1i······sizeПо завершении просмотра массива мы будем иметь в соответствующих переменных значения искомого элемента или индекса соответственно.В приведённой реализации мы начинали просмотр от начала массива, но с таким же успехомможно было начинать и от конца.
Вообще, если неизвестен порядок следования элементов,то нет никакого предпочтительного порядка просмотра элементов при поиске элемента, минимального/максимального по значению. А вот если бы элементы массива располагались впорядке возрастания, то ни минимальный, ни максимальный элемент искать было бы не нужно, поскольку они располагались бы в начале и конце массива соответственно.Если бы в массиве присутствовали повторяющиеся значения, то – в зависимости от порядкапросмотра – были бы найдены правые или левые минимальные/максимальные значения илиих позиции.Что изменилось бы в наших примерах, если бы мы искали конкретное значение или его положение в массиве? Цикл просмотра всё равно остался бы (только теперь был бы полным,т.е., начинался бы с нулевого индекса), а вот смысл проверки должен был быть другим,поскольку нужна проверка на равенство.
Заметим, что, поскольку поиск конкретного значения может быть и безрезультатным, в качестве первоначального значения индекса уженельзя брать 0 – необходимо другое, «невозможное» значение индекса, с помощью которого можно понять, что после просмотра ничего не найдено. В качестве такого значенияможно использовать −1.В случае повторяющихся значений в массиве поиск конкретного значения может завершиться«множественными» совпадениями, поэтому для такой ситуации нужно знать, что делать с1получаемыми результатами (сохранять или использовать по мере обнаружения совпадения).Если бы значения в массиве были отсортированы, то искать конкретное значение в нём можнобыло бы гораздо эффективнее, чем простым перебором всех значений.17Поскольку в программах текстовая информация представлена также в виде числовых значений отдельных символов, то разбираемые примеры подходят для реализации поискаотдельных символов в последовательностях символов (текстах). Можно таким же образомпытаться решить и более сложную задачу: поиска нескольких символов подряд, т.е., послеобнаружения первого символа проверять на совпадение следующего со вторым и так далее,а в случае неудачи – переходить к проверке следующей позиции.
Однако, такой «наивный»алгоритм весьма неэффективен: существуют более интересные альтернативы.4.2.Алгоритм Бойера-МураЭтот алгоритм предложен в 1977 году (Boyer, Moore) и считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки (иногда именуемой шаблоном) в строке. Основа его преимущества его в том, что ценой некоторыхпредварительных вычислений над шаблоном (подстрокой) сравнение шаблона со строкой(текстом) производится не во всех позициях – часть проверок пропускается из-за явнойневозможности совпадения.Просмотр строки производится слева направо, а сравнение с подстрокой – справа налево.Сначала совмещается начало текста (строки) и шаблона (подстроки), а проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнениепредпоследнего символа шаблона с символом текста и так далее. Если все символы совпали– подстрока найдена.
Если же какой-то символ шаблона не совпадает с соответствующимсимволом строки, шаблон сдвигается на несколько символов вправо и проверка опять начинается с последнего символа. На сколько производится сдвиг – зависит от символа строкив позиции несовпадения и от того, встречается ли совпавшая часть шаблона в самом шаблоне повторно. Для иллюстрации эффективности этой процедуры рассмотрим «хороший»случай: символ в строке не совпал при сравнении, но в шаблоне (искомой подстроке) егонет. Тогда сдвиг вправо можно делать сразу на длину шаблона! В приводимом примере –это переход от шага 3 к шагу 4: сразу на три позиции.Текст:Шаблон:А Б Р А К А Д А Б Р Ашаг 1 Б Р Ашаг 2Б Р Ашаг 3Б Р Ашаг 4Б Р Ашаг 5Б Р АПримечание 1Примечание 2Примечание 3Примечание 4Примечание 51.Совпадения последнего символа нет, но символ текста на этом месте – часть шаблона.Сдвиг – на одну позицию (длина шаблона минус позиция символа в шаблоне).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
