Мансуров. Основы программирования в среде Lazarus. 2010
.pdfГлава 1 Основы программирования
____________________________________________________________________
Составление программы (кодирование).
Под этим этапом подразумевается непосредственная запись полученных ранее алгоритмов на выбранном языке программирования. Современные сис-
темы программирования позволяют значительно облегчить этот процесс, хотя этот этап по-прежнему остается одним из самых трудоемких. Разумеется, этот этап предполагает хорошее знание того языка программирования, на котором ведутся работы.
В последующих разделах книги мы собственно и займемся изучением од-
ного из самых популярных языков программирования, каким является язык
Pascal.
Отладка и тестирование программы.
Под этим понимается поиск и исправление ошибок в программе. Причем под отладкой понимается исправление ошибок непосредственно в процессе ко-
дирования. Огромную помощь программисту в этом деле оказывает компиля-
тор, который указывает программисту место возникновения ошибки и характер ошибки. Однако факт того, что компилятор не сообщил об ошибке и программа стала работать, еще не гарантирует от отсутствия ошибок. Это так называемые логические ошибки или ошибки времени исполнения. Для выявления таких ошибок разрабатываются система тестов – специальным образом подобранные контрольные примеры, для которых решение задачи известно.
В крупных проектах программы подразделяются на версии. Альфа-версия это первая работоспособная версия программы. Бета-версия это версия или вер-
сии, которые передаются заказчику для дополнительного тестирования в уже реальных условиях функционирования программы.
31
1.3 Примеры разработки алгоритмов
____________________________________________________________________
1.3.Примеры разработки алгоритмов
1.3.1Решение квадратного уравнения.
Найти корни квадратного уравнения AX2+BX+C=0, коэффициенты A, B, C за-
даны и вводятся с клавиатуры.
Из элементарной математики известна формула для нахождения корней этого уравнения:
X1,2 |
B B 2 4 AC |
, |
(1.8) |
|
2 A |
||||
|
|
|
Однако эта формула применима только для случая действительных корней.
Но мы считаем, что коэффициенты A, B, C могут быть произвольными, поэтому необходимо произвести анализ задачи и определить возможные варианты вы-
числений. Анализ задачи и определение возможных ситуаций, возникающих в ходе вычислений, является одной из важнейших функций программиста. По-
пытка запрограммировать только формулу (1.8) может привести к неопреде-
ленной ситуации, если A=0, или B2-4AC<0. Именно программист должен преду-
смотреть возможность возникновения таких ситуаций и явным образом указать порядок вычислений в каждом конкретном случае.
Если A=0, это означает, что исходное уравнение выродилось в линейное
BX+C=0. В этом случае решением его будет
X |
B |
, |
(1.9.) |
|
C |
||||
|
|
|
Если дискриминант B2-4AC<0, уравнение будет иметь комплексные со-
пряженные корни. Каждое комплексное число можно представить парой дейст-
вительных чисел, одно из которых изображает действительную часть, другое -
мнимую часть комплексного числа.
Действительные части обоих корней равны.
Re X1 Re X 2 |
B |
, |
(1.10) |
|
2A |
||||
|
|
|
32
Глава 1 Основы программирования
____________________________________________________________________
А мнимые будут иметь разные знаки, и вычисляться по формуле
Im X 1 |
(B 2 |
4 AC) |
|
, |
|
|
|
Im X |
|
|
Im X1 , |
(1.11) |
||||||||||
|
2 A |
|
|
|
2 |
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Исходя из этих рассуждений, нетрудно составить блок-схему алгоритма |
||||||||||||||||||||||
вычисления корней квадратного уравнения: |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
начало |
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
A, B, C |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
да |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A=0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
нет |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
D=B2-4AC |
|
|
|
|
|
X |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
C |
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
да |
|
D<0 |
|
|
|
|
|
X |
||
|
|
|
|
|
|
|
B |
|
|
нет |
|
REX1 |
|
|
|
|
|
2 A |
|
|
|
|
|
|
|
|
B |
D |
|
|
B |
X1 |
|||
REX 2 |
2 A |
|
|||
2 A |
|
|
|
||
|
|
|
B |
D |
|
|
D |
X |
|
||
IMX1 |
2 |
2 A |
|
||
2 A |
|
|
|
||
|
|
|
|
|
|
IMX 2 |
D |
|
|
|
|
2 A |
X1, X2 |
|
|||
|
|
||||
|
|
|
|
|
|
ReX1, ReX2, |
|
|
|
|
|
ImX1, ImX2 |
|
|
|
|
конец
Рис. 1.9. Алгоритм вычисления корней квадратного уравнения
33
1.3 Примеры разработки алгоритмов
____________________________________________________________________
1.3.2 Вычисление интегралов
b
Вычислить интеграл f (x)dx по формуле Симпсона с точностью 10 5 .
a
Формула Симпсона, как известно, имеет вид [1,2]:
b |
b a |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f (x)dx |
( y |
|
y |
|
2( y |
|
y |
|
... y |
|
) 4( y |
y |
|
... y |
|
)) |
, |
(1.12) |
|
|
0 |
n |
2 |
4 |
n 2 |
3 |
n 1 |
||||||||||||
|
n 3 |
|
|
|
|
1 |
|
|
|
|
|
||||||||
a |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Для достижения требуемой точности применим метод двойного пересчета,
суть которого заключается в следующем. Пусть n=4 – число точек разбиения интервала (a, b).
Вычисляем интеграл I4. Затем увеличиваем n в два раза, (n=8) и вычисляем
I8.
Если |I4-I8|≤,то требуемая точность достигнута. В качестве результата бе-
рем I8. Если же |I4-I8|> , то снова увеличиваем n в два раза (n=16) вычисляем I16,
затем если |I8-I16|≤, то точность достигнута. Если нет, то повторяем вышеука-
занный процесс до достижения требуемой точности. Блок-схема алгоритма вы-
числения интеграла по формуле Симпсона методом двойного пересчета будет выглядеть следующим образом:
34
Глава 1 Основы программирования
____________________________________________________________________
K=1
S1=S
H=H/2
Начало
A, B, N,
K=0
H=(B-A)/N
X=A
X=X+H
S=0
S=S+f(x)+2f(X+H)
X=X+2H
да
X<B-H
нет
S=2S
S= H3 (f(A)+f(B)+S)
нет
K=1
да
|S1-S|≤
нет
да
S
Конец
Рис.1.10. Алгоритм вычисления определенного интеграла по формуле Симпсона
35
1.3 Примеры разработки алгоритмов
____________________________________________________________________
1.3.3 Обработка результатов эксперимента
При решении инженерных и экономических задач часто возникает необхо-
димость в получении математических зависимостей между различными пара-
метрами, характерными для данной задачи. Исходной информацией для уста-
новления этих зависимостей является физический эксперимент или экономиче-
ские показатели. Как в том, так и другом случае мы располагаем либо таблич-
ными данными, либо точками на графике. Пусть имеется зависимость Pi , полу-
ченная при дискретных значениях Z i . Значения Pi получены из эксперимента с некоторыми погрешностями. Требуется найти зависимость P f (Z ) .
P
7
i
3
2
1
Z |
Z2 Z3 |
Zi |
Z7 |
Z |
1 |
|
|
|
Рис. 1.11. График функции
Учитывая, что P f (Z ) имеет явно выраженную нелинейную зависимость,
запишем уравнение кривой второго порядка.
P X 0 X1Z X 2 Z 2 |
(1.13) |
В этом уравнении X 0 , X 1 , |
X 2 неизвестные пока коэффициенты. Для нахо- |
ждения этих коэффициентов запишем для всех имеющихся значений Pi зави-
симость вида (1.13).
P X |
0 |
X |
Z |
1 |
X |
2 |
Z 2 |
1 |
1 |
|
|
1 |
P X |
0 |
X |
Z |
2 |
X |
2 |
Z |
2 |
2 |
1 |
|
|
|
2 |
..………………
36
Глава 1 Основы программирования
____________________________________________________________________
P |
X |
|
X Z |
|
X Z |
2 |
||
i |
|
0 |
1 |
|
i |
2 i |
(1.14 |
|
|
|
|
||||||
……………………. |
||||||||
P |
X |
0 |
X |
Z |
7 |
X |
Z |
2 |
7 |
|
1 |
|
2 |
|
7 |
Получена система из 7 уравнений с 3 неизвестными. Необходимо таким
методом найти X 0 , X 1 , X 2 , чтобы зависимость (1.13) лучшим способом описала результаты, представленные на графике.
Для нахождения трех неизвестных предстоит решить систему из 7 уравне-
ний. Если мы отбросим какие-либо 4 лишних уравнений, мы найдем значения неизвестных без учета этих отброшенных уравнений. С другой стороны, систе-
ма (1.14) может быть несовместной, т.е. при ее решении мы можем не получить тождества и при подстановке найденных значений неизвестных в уравнения
системы получим разницу между левой и правой частями.
Обозначим |
эти разницы в соответствии с номерами уравнений через |
1 , 2 ... i ,..., 7 и |
будем называть их невязками. Невязка представляет собой |
разницу между аналитической зависимостью и значениями Pi , заданными в ка-
честве исходной информации в дискретных точках Z i .
Для того чтобы аналитическая зависимость наиболее полно отражала ре-
зультаты эксперимента, будем минимизировать величину:
7
S |
|
2 |
|
|
i |
|
|
|
|
(1.15) |
|
|
i 1 |
|
|
|
|
|
Невязки взяты в квадрат для того, чтобы любая невязка получалась с од-
ним положительным знаком, при этом соотношения малых и больших невязок увеличатся. Минимизация S будет выражать наилучшее приближение анали-
тической зависимости к экспериментальным точкам (при заданной степени по-
линома). Рассмотренный нами метод носит название метода наименьших квад-
ратов [3].
Общая формулировка задачи:
необходимо решить систему n-линейных уравнений с m неизвестными.
37
1.3 Примеры разработки алгоритмов
____________________________________________________________________
a11x1+a12x2+…+a1jxj+…a1mxm=b1 a21x1+a22x2+…+a2jxj+…a2mxm=b2
(1.16)
ai1x1+ ai2x2+…+aijxj +…aimxm =bi
……………………………………………………..
an1x1+an2x2+…+anjxj+…anmxm=bn
Запишем i-ое уравнение в более компактном виде:
|
|
m |
|
|
|
|
|
|
|
|
|
|
a ijxj = bi |
|
|
|
(1.17) |
||
|
|
j |
1 |
|
|
|
|
|
|
|
|
n |
n |
m |
|
|
|
|
|
тогда |
S |
2 |
( |
a |
ij |
x |
j |
b )2 |
(1.18) |
|
|
i |
|
|
|
i |
|
||
|
|
i 1 |
i 1 |
j 1 |
|
|
|
|
|
Для минимизации S возьмем от этой величины частные производные по каждой переменной xj и приравняем к 0.
s |
|
n |
m |
|
|
2 |
( |
aij x j bi )aij , |
(1.19) |
||
|
|||||
x j |
|||||
|
i 1 |
j 1 |
|
s0 , отсюда:
x j
n |
m |
|
( |
aij x j bi )aij 0 , |
(1.20) |
i 1 |
j 1 |
|
Таких уравнений будет столько, сколько неизвестных xj и получим систему n-линейных алгебраических уравнений с n неизвестными, которые решаются методом исключения с выделением главного элемента.
38
Глава 1 Основы программирования
____________________________________________________________________
1.3.4 Решение системы линейных алгебраических уравнений
Будем рассматривать систему из n уравнений с n неизвестными. Методы численного решения систем линейных уравнений подразделяются на две груп-
пы: прямые (конечные) и итерационные (бесконечные). Естественно, никакой практический метод решения не может быть бесконечным. Мы имеем в виду только то, что прямые методы могут в принципе (с точностью до ошибок ок-
ругления) дать такое решение, если оно существует, с помощью конечного чис-
ла арифметических операций. С другой стороны, при использовании итераци-
онных методов, для получения точного решения теоретически требуется беско-
нечное число арифметических операций. Значит, при практическом исследова-
нии итерационных методов появляются ошибки ограничения. Это не значит,
что прямые методы лучше, т.к. ошибки округления, появляющиеся в прямых методах, играют большую роль. В некоторых случаях из-за ошибок округления могут быть получены бессмысленные результаты. Несмотря на неизбежную ошибку ограничения, итерационные методы могут оказаться наиболее удобны-
ми, т.к. при его использовании ошибки округления не накапливаются.
Рассмотрим один из прямых методов называемых методом исключения
(метод Гаусса).
Для иллюстрации метода рассмотрим систему из 3 уравнений с 3 неиз-
вестными:
a11x1+a12x2+a13x3=b1 (1)
a21x1+a22x2+a23x3=b2 (2) (1.21) a31x1+a32x2+a33x3=b3 (3)
Здесь хотя бы один из коэффициентов a11, a21, a31 должен быть отличен от
0, иначе мы бы имели дело с 3 уравнениями с двумя неизвестными. Пусть a11≠0, если, это не так мы можем переставить местами уравнения, так чтобы ко-
39
1.3 Примеры разработки алгоритмов
____________________________________________________________________
эффициент при x1 в первом уравнении был отличен от 0. Перестановка уравне-
ний систему не изменит. Теперь введем множитель:
m2 |
a21 |
(1.22) |
|
a11 |
|||
|
|
Умножим 1-е уравнение (1.21) на m2 и вычтем его из 2-го уравнения (1.21).
Имеем:
(a21 |
m2a11)x1 |
(a22 |
|
m2a12 )x2 |
(a23 |
m2a13 )x3 |
b2 |
m2b1 |
(1.23) |
|||||
Но |
a |
|
m a |
a |
|
|
a21 |
a |
0 |
|
|
|
(1.24) |
|
|
|
|
|
|
|
|
||||||||
|
|
21 |
|
2 11 |
|
21 |
|
a11 11 |
|
|
|
|
|
|
Обозначим |
|
|
a22 |
|
a22 |
|
m2a12 |
|
|
|
|
|
||
|
|
|
|
a23 |
|
a23 m2a13 |
|
|
|
(1.25) |
||||
|
|
|
|
b2 |
b2 |
m2b1 |
|
|
|
|
|
Тогда 2-е уравнение (1.21) приобретет вид:
a22 x2 a23 x3 b2 |
(1.26) |
Заменим это уравнение в (1.21) уравнением (1.26), получим систему:
a11x1+a12x2+a13x3=b1 |
(1) |
|
|||
a22 x2 |
a23 x3 |
b2 |
(4) |
(1.27) |
|
a31x1+a32x2+a33x3=b3 |
(3) |
|
|||
Умножим теперь (1) |
в (1.27) на m3 |
|
a31 |
и вычтем из (3) |
|
|
a11 |
||||
|
|
|
|
|
|
a32 |
a32 |
m3a12 |
|
|
|
40