13.5. Пример линейной программы

Пример 1. Программа вычисления площади круга, вписанного в треугольник и площади круга, описанного около треугольника.

Program Triangle; {программа вычисляет площади, вписанного в треугольник и описанного около треугольника кругов}

Const Pi = 3.1415926;

Line = ‘_______________________________’;

Var a, b, c : Real;

Sint, Sout : Real;

S, p : Real;

Begin

 { ввод данных }

Write (‘введите стороны треугольника a b c ‘);

Readln (a, b, c);

{ вычисления }

p := (a + b + c)/2;

S := Sqrt(p*(p – a)*(p – b)*(p – c));

Sout := Pi*sqrt(a*b*c/4/S);

Sint := Pi*sqrt(2*S/p);

{ печать ответа }

Writeln; Writeln (Line);

Writeln(‘Sвпис = ‘, Sout); Writeln(Line);

Writeln(‘Sопис = ‘, Sint); Writeln(Line)

End .

Для оформления вывода в операторах Write, Writeln можно использовать строку. Например: writeln(‘***’, ‘площадь вписанной окружности = ‘, sint, ‘***’).

13.5.1. Понятие сложности выражения. Оптимизация вычислений

Основной критерий качества программы – ее правильность. Строгое математическое понятие правильности программы пока выходит за рамки нашего рассмотрения. Будем предполагать, что наши программы выполняют именно те действия, которые мы от них ожидаем.

В этом предположении критериями качества программы являются, например, ее размер, объем памяти, отведенной под данные, скорость выполнения и т.д.

Скорость выполнения неветвящейся программы определяется количеством вычислений, необходимых для получения значений выражений, содержащихся в операторах присваивания и операторах вывода.

Количество вычислений, необходимых для получения значения выражения, будем называть его сложностью. Рассмотрим пример:

U := X*Cos(Alfa) + Y*Sin(Alfa) (1)

V := –X*Sin(Alfa) + Y*Cos(Alfa) (2)

Для вычисления значения U неoбходимо выполнить два вычисления значения триго­но­мет­рической функции, два умножения и одно сложение. Это и есть сложность правой части опера­тора (1). Правая часть оператора (2) имеет по существу ту же сложность, что и оператора (1).

Разумеется, скорости вычислений значений элементарных функций, операций умножения и сложения различны и зависят от реализации языка программирования. Однако реально предпо­лагать, что скорости вычислений всех элементарных трансцендентных функций равны между собой, скорости выполнения мультипликативных операций равны, и скорости выполнения аддитивных операций также равны.

Пусть T_f, T_m и T_a – времена вычисления соответственно функций, умножений и сложений, а T(U) – время вычисления значения U. Тогда

T(U) = 2T_f + 2T_m + T_a, T(V) = T(U) (3)

Время вычисления значения выражения и есть мера его сложности. Понятно, что программист должен заботиться об уменьшении сложности выражений, входящий в программу. Для этого используют:

 а)Тождественные пребразования, уменьшающие сложность;

 б) Предварительные вычисления общих подвыражений;

Примеры:

U := 4*Sin(X)*Cos(X) + 3  U := 2*Sin(2*X) + 3

U := Sin(X)^2 – 3*Sin(X) + 2  U := (Sin(X) – 2)*(Sin(X) – 1)  Y := Sin(X); U := (Y – 2)*(Y – 1)

 Между величинами T_f, T_m и T_a существуют соотношения

T_f >> T_m > T_a (4)

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

Следующий пример по существу определяет оптимальную форму записи многочлена для задачи вычисления его значения.

 Пример 2 ( Схема Горнера)

Вычислить значение Y = a₀x³ + a₁x² + a₂x + a₃;

Поскольку операции возведения в степень в языке нет, можно заменить его умножениями:

Y = a₀*x*x*x + a₁*x*x + a₂*x + a₃;

В этом варианте T(Y) = 6T_m + 3T_а;

Вынося x за скобки там, где это возможно, получим:

Y = ((a₀x + a₁)x + a₂)x + a₃; {Схема Горнера}. T(Y) = 3T_m + 3T_а.

Можно показать, что схема Горнера вычисления многочлена является оптимальной.