Реализации алгоритмов/Быстрое возведение в степень: различия между версиями
Содержимое удалено Содержимое добавлено
Нет описания правки |
Нет описания правки |
||
Строка 3: | Строка 3: | ||
: <math>x^m=x^{m_0} \cdot \left(x^2\right)^{m_1} \cdot \left(x^{2^2}\right)^{m_2} \cdot \left(x^{2^3}\right)^{m_3} \cdot\dots\cdot \left(x^{2^k}\right)^{m_k} </math>. |
: <math>x^m=x^{m_0} \cdot \left(x^2\right)^{m_1} \cdot \left(x^{2^2}\right)^{m_2} \cdot \left(x^{2^3}\right)^{m_3} \cdot\dots\cdot \left(x^{2^k}\right)^{m_k} </math>. |
||
== [[w:Си (язык программирования)|Язык Си]] == |
|||
<source lang = cpp> |
<source lang = cpp> |
||
int power(int t, int k) // возведение t в степень k |
int power(int t, int k) // возведение t в степень k |
||
Строка 19: | Строка 19: | ||
</source> |
</source> |
||
== [[w:Паскаль (язык программирования)|Паскаль]] == |
|||
<source lang = pascal> |
<source lang = pascal> |
||
function power(t, k: integer): integer; {возведение числа t в степень k} |
function power(t, k: integer): integer; {возведение числа t в степень k} |
||
Строка 38: | Строка 38: | ||
</source> |
</source> |
||
== [[w:Python|Python]] == |
|||
<source lang = python> |
<source lang = python> |
||
def FastPow (t, k): # Быстрое возведение числа t в степень k |
def FastPow (t, k): # Быстрое возведение числа t в степень k |
Версия от 08:39, 25 октября 2011
Используется представление числа xm:
- .
Язык Си
int power(int t, int k) // возведение t в степень k
{
int res = 1;
while (k)
{
if (k & 1)
res *= t;
t *= t;
k >>= 1;
}
return res;
}
Паскаль
function power(t, k: integer): integer; {возведение числа t в степень k}
var
res:integer;
begin
res := 1;
while k > 0 do
begin
if k mod 2 = 1 then
res := res * t;
k := k div 2;
t := t * t;
end;
power := res;
end;
Python
def FastPow (t, k): # Быстрое возведение числа t в степень k
res = 1
while k:
if (k & 1):
res *= t
k = k >> 1
if k == 0:
break
t *= t
return res