Реализации алгоритмов/Бинарный алгоритм вычисления НОД: различия между версиями
Содержимое удалено Содержимое добавлено
м Ivan Shmakov переименовал страницу Примеры реализации алгоритмов НОД в Реализации алгоритмов/Бинарный алгоритм вычисления НОД: Вынесени… |
Отмена правок до редакции 51022. |
||
Строка 1:
{{wikipedia|Наибольший общий делитель}}
== Реализации бинарного алгоритма нахождения НОД ==
{{wikipedia|Бинарный алгоритм нахождения НОД}}
=== С ===
<source lang="c">
unsigned int gcd(unsigned int u, unsigned int v)
{
int shift;
/* GCD(0,x) := x */
if (u == 0 || v == 0)
return u | v;
/* Let shift := lg K, where K is the greatest power of 2
dividing both u and v. */
for (shift = 0; ((u | v) & 1) == 0; ++shift) {
u >>= 1;
v >>= 1;
}
while ((u & 1) == 0)
u >>= 1;
/* From here on, u is always odd. */
do {
while ((v & 1) == 0) /* Loop X */
v >>= 1;
/* Now u and v are both odd, so diff(u, v) is even.
Let u = min(u, v), v = diff(u, v)/2. */
if (u < v) {
v -= u;
} else {
unsigned int diff = u - v;
u = v;
v = diff;
}
v >>= 1;
} while (v != 0);
return u << shift;
}
</source>
=== C# ===
<source lang="csharp">
long GCD(long a, long b)
{
if (a == 0) return b;
if (b == 0) return a;
if (a == b) return a;
if (a == 1 || b == 1) return 1;
if ((a % 2 == 0) && (b % 2 == 0)) return 2 * GCD(a / 2, b / 2);
if ((a % 2 == 0) && (b % 2 != 0)) return GCD(a / 2, b);
if ((a % 2 != 0) && (b % 2 == 0)) return GCD(a, b / 2);
return GCD(b, (long)Math.Abs(a - b));
}
</source>
=== Pascal/Delphi ===
<source lang="pascal">
function GCD(a, b: integer): integer;
begin
if (a = 0) then
begin
Result:= b;
Exit;
end else
if (b = 0) then
begin
Result:= a;
Exit;
end else
if (a = b) then
begin
Result:= a;
Exit;
end else
if (a = 1) or (b =1) then
begin
Result:= 1;
Exit;
end else
if (a mod 2 = 0) and (b mod 2 = 0) then
begin
Result:= 2*GCD(Trunc(a/2), Trunc(b/2));
Exit;
end else
if (a mod 2 = 0) and (b mod 2 <> 0) then
begin
Result:= GCD(Trunc(a/2), b);
Exit;
end else
if (a mod 2 <> 0) and (b mod 2 = 0) then
begin
Result:= GCD(a, Trunc(b/2));
Exit;
end;
Result:= GCD(b, Abs(a - b));
end;
</source>
[[Категория:Алгоритмы]]
| |||