Быстрое возведение в степень
Для возведения числа x в степень n, как правило, используют стандартный метод, т. е. число x умножают n раз само на себя. В задачах математического толка, решаемых при помощи бумаги и ручки, такой метод вполне приемлем, ведь степенная функция быстро растет и поэтому сомнительно, что придется производить затруднительные операции вручную.
Другое дело программирование, где важно не только решить поставленную задачу, но и составить оптимальное решение, удовлетворяющее предусмотренному диапазону входных данных. Так, в частности, для операции возведения числа в степень имеется алгоритм, позволяющий значительно сократить число требуемых операций. Он достаточно прост и основывается на математических свойствах степеней.
Пусть имеется некоторая степень xn, где x – действительное число, а n – натуральное. Тогда для xn справедливо равенство:
xn = (xm)k
При этом m*k=n. Например: 36=(33)2, 57=(57)1. Это свойство является одним из основных степенных свойств, и именно на нем основывается рассматриваемый метод. Далее, заметим, что в случае, если n является четным числом, то верно следующее равенство:
xn = (xn/2)2 = xn/2 * xn/2
Так, если x=3, а n=6, то имеем 36 = (36/2)2 = 36/2 * 36/2. Используя это свойство, удастся существенно уменьшить число операций необходимых для возведения x в степень n. Теперь адаптируем формулу для случая с нечетным n. Для этого понадобиться просто перейти к степени на единицу меньшей. Например: 57 = 56*5, 125 = 124*12. Общая форма равенства перехода:
xn = xn-1*x
В программе, реализующей алгоритм быстрого возведения в степень, используются указанные свойства: если степень n четная, то переходим к степени вдвое меньшей, иначе заменяем нечетную степень четной.
Код программы на C++:
float bpow(float x, int n) //быстрое возведение в степень
{
float count=1;
if (!n) return 1;
while (n)
{
if (n%2==0)
{
n/=2;
x*=x;
}
else
{
n--;
count*=x;
}
}
return count;
}
void main() //главная функция
{
float x; int n;
cout<<"Основание > "; cin>>x;
cout<<"Степень > "; cin>>n;
cout<<x<<"^"<<n<<"="<<bpow(x, n);
}
Код программы на Pascal:
var x: real; n: integer;
function bpow(x: real; n: integer): real; {быстрое возведение в степень}
var count: real;
begin
if n=0 then
begin
bpow:=1;
exit;
end;
count:=1;
while n>0 do
begin
if n mod 2=0 then
begin
n:=n div 2;
x:=x*x;
end
else
begin
n:=n-1;
count:=count*x;
end;
end;
bpow:=count;
end;
begin {основной блок программы}
write('Основание > ');
read(x);
write('Степень > ');
read(n);
write(x, '^', n, '=', bpow(x, n));
end.