Реализации алгоритмов/Быстрое возведение в степень: различия между версиями
Содержимое удалено Содержимое добавлено
JenVan (обсуждение | вклад) м Откат правок 93.84.195.243 (обс.) к версии Oberstdalet |
Ошибки в исх. коде. Неправильно работает при специальных входных параметрах. Делфи-синтаксис более компактный |
||
Строка 33: | Строка 33: | ||
== [[w:Паскаль (язык программирования)|Паскаль]] == |
== [[w:Паскаль (язык программирования)|Паскаль]] == |
||
<source lang = pascal> |
<source lang = pascal> |
||
//Синтаксис - Delphi |
|||
function power( |
function power(Val, Pwr: integer): integer; {возведение числа t в степень k} |
||
var |
|||
res:integer; |
|||
begin |
begin |
||
if Val = 0 then |
|||
Result := 0 |
|||
else |
|||
if |
if Pwr = 0 then |
||
Result := 1 |
|||
else |
|||
if Pwr = 1 then |
|||
Result := Val |
|||
else |
|||
begin |
|||
Result := 1; |
|||
while Pwr > 0 do |
|||
begin |
|||
if Pwr mod 2 = 1 then |
|||
Result := Result * Val; |
|||
Pwr := Pwr div 2; |
|||
Val := Val * Val; |
|||
end; |
end; |
||
end; |
|||
end; |
end; |
||
</source> |
</source> |
Версия от 17:17, 24 апреля 2012
Используется представление числа 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;
}
Язык C++
int power(int t, int k) //возведение числа t в степень k
{
int i, res;
res=t;
t=1;
for(i=0; i<k; i++)
t*=res;
}
Паскаль
//Синтаксис - Delphi
function power(Val, Pwr: integer): integer; {возведение числа t в степень k}
begin
if Val = 0 then
Result := 0
else
if Pwr = 0 then
Result := 1
else
if Pwr = 1 then
Result := Val
else
begin
Result := 1;
while Pwr > 0 do
begin
if Pwr mod 2 = 1 then
Result := Result * Val;
Pwr := Pwr div 2;
Val := Val * Val;
end;
end;
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
JavaScript
function faststep (val, step, mod) {
mod = parseInt(mod);
s = 1; v = step; c = val;
while (v != 0) {
flag = 0;
if (v%2 == 1) {
if (!mod)
s = s*c;
else
s = (s*c) % mod;
v = (v-1)/2;
if (!mod)
c = c*c;
else
c = (c*c) % mod;
flag = 1;
}
else {
v = v/2;
}
if (!flag)
if (!mod)
c = c*c;
else
c = (c*c) % mod;
}
return s;
}