|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 15 Sep 2001 19:15:12
To : Azamat Kalimullin
Subject : Получение коэффициентов.
--------------------------------------------------------------------------------
Replying to a message of Azamat Kalimullin to All:
AK> Делал как-то свою курсовую и столкнулся с одной проблемой. Имеются два
AK> числа A и B. Hужно найти такие коэффициенты x и y, чтобы A*x + B*y = 1.
AK> Как говорится, долго дуамал. В итоге получилось:
AK> Сначала x и y равны по единице.
AK> Берем разность |A| - |B| = C
AK> Если |C| < |B|, тогда C = C + |A|, увеличиваем x
AK> Если |C| > |B|, тогда C = C - |B|, увеличиваем y
AK> Если |C| = |B|, тогда считаем, что единицу получить нельзя, потому что
AK> получится ноль.
[...]
AK> И вопрос. А есть ли еще более просто решение?
Есть. Все то же самое, только вместо вычитания используешь деление. И получаешь
в результате /расширенный алгоритм Евклида/.
===cut===
Hахождение коэффициентов представления (n,m) = a*n + b*m
Расширенный алгоритм Евклида:
x_0 = n, x_1 = m, a_0 = 1, a_1 = 0, b_0 = 0, b_1 = 1
y_i = [ x_{i-1} / x_i ] ( [ ] - целая часть )
x_{i+1} = x_{i-1} mod x_i = x_{i-1} - x_i * y_i
a_{i+1} = a_{i-1} - a_i * y_i
b_{i+1} = b_{i-1} - b_i * y_i
Итерируешь (i=1,2,...) до тех пор, пока не получишь x_{k+1}=0. Тогда
a = a_k, b = b_k - искомые.
P.S. Hа каждом шаге, естественно, нужно знать только два предыдущих члена.
Поэтому никакие массивы для вычислений не нужны.
===cut===
===cut===
function gcd(m,n:longint;var a,b:longint):longint;
var t,t2,a2,b2,u:longint;
begin
if m=0 then
begin
a:=0; b:=1;
gcd:=n;
end else
begin
a:=0; b:=1;
a2:=1; b2:=0;
repeat
t:=n div m;
t2:=m; m:=n mod m; n:=t2;
u:=a2; a2:=a-t*a2; a:=u;
u:=b2; b2:=b-t*b2; b:=u;
until m=0;
gcd:=n;
end;
end;
===cut===
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.6
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Получение коэффициентов. 
