Ключевые слова: программирование, язык программирования, вычисление, значение, многочлен, пример, скачать, c++, pascal, visual basic for applications, vba, doc, php, форма, лекции по программированию

Автор: Приходько Максим Александрович

Одной из простейших классических задач программирования является вычисление значения многочлена в точке. Эта задача позволяет наглядно проиллюстрировать понятия переменная, массив, цикл, а также рассказать о вычислении n-й степени числа, методах оптимизации программного кода и сложности алгоритмов.

Как известно из школьного курса математики, многочленом Pn(x) степени n называется выражение вида:

Очевидно, что первым шагом решения задачи является "умение" вычислять n-ую степень числа x. Сделать это можно с помощью одного конечного цикла, не забыв предварительно определить необходимые переменные (счетчик цикла, показатель степени, возводимое в степень число, переменную для хранения результата возведения в степень):

Dim X As Integer
Dim N As Integer
Dim I As Integer
Dim Y As Integer

Y = 1
For I = 1 To N
 Y = Y * X
Next

Здесь N - показатель степени, X - возводимое в степень число, Y - результат операции, I - счетчик цикла. Легко видеть, что в такой форме аглоритм вычисления N-й степени числа требует N операций умножения (самой трудоемкой арифметической операции для компьютера). Число операций можно уменьшить на единицу, если в качестве начального значения переменной Y использовать сразу первую степень числа X:

Dim X As Integer
Dim N As Integer
Dim I As Integer
Dim Y As Integer

Y = X
For I = 1 To N - 1
 Y = Y * X
Next

Таким образом, если отбросить члены c0 и c1 x, необходимо вычислить 2-ю, 3-ю, ..., N-ю степени, на что потребуется:

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

В случае многочлена высокой степени вычисление каждой из степеней приводит к существенному "замедлению" работы алгоритма. Справиться с этой проблемой легко, если заметить, что, вычисляя N-ю степень числа X, на каждом очередном шаге в качестве промежуточного значения получаются все степени от 1 до N. Воспользоватся этой особенностью можно, создав специальный массив для хранения всех степеней. Так как массив нельзя определить динамически (его размер должен быть указан в виде константы, а не переменной, далее будем предполагать, что степень многочлена N не более 10: N <= 10):

Dim X As Integer
Dim N As Integer
Dim I As Integer
Dim Y(10) As Integer

Y(0) = X
For I = 1 To N - 1
 Y(I) = Y(I - 1) * X
Next

Эта простая "уловка" позволяет снизить число умножений до N - 1 (то есть до линейной сложности алгоритма). Вычислив таким образом все степени числа X от 1 до 10, можно приступить к вычислению самого многочлена P, предварительно считав с клавиатуры значения числа X и коэффициентов многочлена C, считая их целыми числами (для коэффициентов создадим отдельный массив C на единицу большего размера, чтобы хранить дополнительный коэффициент при 0-ой степени X - c0):

Dim X As Integer
Dim N As Integer
Dim I As Integer
Dim Y(10) As Integer
Dim C(11) As Integer
Dim P As Integer

X = Val(InputBox("Введите число", "X", "2"))
N = Val(InputBox("Введите степень не более 10", "N", "10"))
For I = 1 To N + 1
 C(I - 1) = Val(InputBox("Введите коэффициент", "C(" + Str(I - 1) + ")", "1"))
Next


Y(0) = X
For I = 1 To N - 1
 Y(I) = Y(I - 1) * X
Next

P = C(0)

For I = 1 To N
 P = P + (C(I) * Y(I - 1))
Next

MsgBox("P = " + Str(P))

Функция InputBox вызывается с 3-мя необязательными параметрами, которые задают заголовок окна ввода значения, текст в окне и значение по умолчанию. Так как результатом ввода с клавиатуры является строка, необходимо полученную строку преобразовать к целому значению, чем и занимается вторая новая функция - Val.

Вот как этот код выглядит в редакторе VBA MS Word:

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

C++ (С++ Builder 4.0)

//---------------------------------------------------------------------------
#include 
#include "stdio.h"
#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
int main(int argc, char* argv[])
{
  int x;
 int n;
 int i;
 int y[10];
 int c[11];
 int p;

 printf("x = ");
 scanf("%d", &x);
 printf("n = ");
 scanf("%d", &n);
 for(i = 1; i < n + 2; i++)
 {
  printf(("c(" + IntToStr(i - 1) + ") = ").c_str());
  scanf("%d", &(c[i - 1]));
 }

 y[0] = x;
 for(i = 1; i < n; i++)
 {
   y[i] = y[i - 1] * x;
 }

 p = c[0];

 for(i = 1; i < n + 1; i++)
 {
   p = p + c[i] * y[i - 1];
 }

 printf(("p = " + IntToStr(p)).c_str());
 scanf("%d", x);
}
//---------------------------------------------------------------------------

Pascal (Turbo Pascal 7.0)

var x: integer;
var n: integer;
var i: integer;
var y: array[0..9] of integer;
var c: array[0..10] of integer;
var p: integer;

var v: integer;
var s: string;

begin
 write('x = ');
 readln(s);
 val(s, x, v);
 write('n = ');
 readln(s);
 val(s, n, v);

 for i := 1 to n + 1 do
 begin
  str(i - 1, s);
  write('c' + s + ' = ');
  readln(s);
  val(s, c[i - 1], v);
 end;

 y[0] := x;
 for i := 1 to n - 1 do
 begin
  y[i] := y[i - 1] * x;
 end;

 p := c[0];
 for i := 1 to n do
 begin
  p := p + c[i] * y[i - 1];
 end;

 write('p = ');
 str(p, s);
 write(s);
end.

PHP

Работающая форма находится по адресу: http://www.argusm.com/unipo_polynom.php

Вид формы для ввода данных:

Вы можете свободно использовать приведенные программы (исходные файлы можно скачать ниже). Убедительная просьба: при перепечатке кодов или фрагментов статьи, пожалуйста, указывайте ссылку на оригинал статьи: http://www.argusm.com/article.php?id=118 В случае возникновения вопросов или комментариев к описанной задаче свяжитесь с автором, воспользовавшись одним из Контактов.