Приемы, используемые для минимизации вычислений

Одним из критериев, характеризующим качество составленной программы, является объем выполняемых ею вычислений для достижения требуемого результата. Чем он меньше, тем, как правило, быстрее будет работать программа. Существуют разные приемы, применение которых позволяет сократить объем вычислений за счет уменьшения в первую очередь количества вызовов функций, затем – количества операций типа умножения, и, наконец, – количества операций типа сложения. Вот некоторые из них, рассмотренные отдельно, хотя, как правило, они используются в сочетании.

Вынесение общих множителей за скобки. Например, вместо оператора

65. Z:=Sin(X)*Y-Sin(X)*Sqr(Y)*Y+Sqr(X)*X+X;

лучше использовать оператор

66. Z:=Sin(X)*Y*(1-Sqr(Y))+X*(Sqr(X)+1);

Использование схемы Горнерадля полиномов. Например, полином

преобразованный по схеме Горнера, примет вид

((((2X-5)X+2)X+7)X-4)X+6

где явно меньше число операций умножения, если считать, что возведение в степень выполняется через умножение. В программе по второму варианту записи полинома будем иметь выражение

67. ((((2*X-5)*X+2)*X+7)*X-4)*X+6,

а по первому –

68. 2*IntPower(X,5)-5*IntPower(X,4)+2*IntPower(X,3)+7*IntPower(X,2)-4* X+6

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

Другой пример, где также применима схема Горнера:

1+2!+3!+4!+5! = 1+2(1+3(1+4(1+5)))

Использование дополнительных переменных. Например, при вычислении значения функциицелесообразно предварительно вычислитьи, а исходную формулу преобразовать к виду. В этом случае в программе будут использованы три оператора присваивания:

69. A:=X-Y;

70. B:=Sqr(A);

71. Z:=A*(1+A*B)/(1+B);

Пример 1.1 выполнения задания

Найти коэффициенты k0, k1, k2, k3 представления числа Х (0≤X≤80) в троичной системе счисления:

Х=k3*3³+k2*3²+k1*3+k0 (1.1)

используя операции modиdiv. Для контроля результатов выполнить вычисление Х непосредственно по формуле (1.1) для найденных коэффициентов, а также после преобразования выражения в формуле (1.1) по схеме Горнера. Вывести все результаты вычислений в наглядной форме с поясняющими текстами. Проверить работу программы на значениях

X=(0; 1; 2; 10; 27; 48; 80).

72. program Project1_1;

73. {$APPTYPE CONSOLE}

74. uses

75. SysUtils;

76. var

77. X, k0, k1, k2, k3, X1, X2:Byte;

78. begin

79. {Ввод исходных данных}

80. Write('Введите X : '); ReadLn(X);

81. {Вычисление коэффициентов разложения}

82. k0:=X mod 3; X:=X div 3; //k0:=X mod 3;

83. k1:=X mod 3; X:=X div 3; //k1:=X div 3 mod 3;

84. k2:=X mod 3; //k2:=X div 9 mod 3;

85. k3:=X div 3; //k3:=X div 27;

86. {Вывод вычисленных коэффициентов разложения числа Х по степеням 3

87. с поясняющими текстами}

88. WriteLn;

89. WriteLn('Кэффициенты разложения введённого числа по степеням 3');

90. WriteLn ('k3 = ',k3,'k2 = ':7,k2,'k1 = ':7,k1,'k0 = ':7,k0);

91. {Вычисление непосредственно по формуле (1.1)}

92. X1:=k3*27+k2*9+k1*3+k0;

93. {Вывод результатов}

94. WriteLn('Вычислено по формуле (1.1) непосредственно');

95. WriteLn (k3,'*27+',k2,'*9+',k1,'*3+',k0,' = ',X1);

96. {Вычисление по формуле (1.1), преобразованной по схеме Горнера}

97. X2:=((k3*3+k2)*3+k1)*3+k0;

98. {Вывод результатов}

99. WriteLn('Вычислено по формуле(1.1), представленной по схеме Горнера');

100. WriteLn('((',k3,'*3+',k2,')*3+',k1,')*3+',k0,' = ',X2);

101. ReadLn;

102. end.