拡張ユークリッド互除法

!問い
!29リットル入るバケツと17リットル入るバケツがある。
!この2つのバケツを使って、別のバケツに1リットルの水を入れる。

!答え
!17リットルのバケツで12回くみ入れた後、29リットルのバケツで7回くみ出す

LET a=17
LET b=29
CALL ExGCD(a,b ,s,t,c)
PRINT s;"*";a;" + ";t;"*";b;"=";c

END

EXTERNAL SUB ExGCD(a,b, s,t,c) !a>0,b>0 に対して s*a+t*b=c となる s,t,c=Gcd(a,b) を求める
IF b=0 THEN
LET s=1
LET t=0
LET c=a
ELSE
LET q=INT(a/b) !Qi　※Rk-1 = Qk*Rk + Rk+1より
LET r=MOD(a,b) !Ri
CALL ExGCD(b,r, u,v,c) !k=n-1,…,3,2 まで続ける
LET s=v
LET t=u-v*q
END IF
END SUB

samplesフォルダ内EUCLID.BAS参照

拡張ユークリッド互除法	返事を書くノートメニュー
山中和義 <drdlxujciw> 2008/01/08 11:40:31 ** この記事は1回修正されてます
!問い !29リットル入るバケツと17リットル入るバケツがある。 !この2つのバケツを使って、別のバケツに1リットルの水を入れる。 !答え !17リットルのバケツで12回くみ入れた後、29リットルのバケツで7回くみ出す LET a=17 LET b=29 CALL ExGCD(a,b ,s,t,c) PRINT s;"";a;" + ";t;"";b;"=";c END EXTERNAL SUB ExGCD(a,b, s,t,c) !a>0,b>0 に対して sa+tb=c となる s,t,c=Gcd(a,b) を求める IF b=0 THEN LET s=1 LET t=0 LET c=a ELSE LET q=INT(a/b) !Qi　※Rk-1 = QkRk + Rk+1より LET r=MOD(a,b) !Ri CALL ExGCD(b,r, u,v,c) !k=n-1,…,3,2 まで続ける LET s=v LET t=u-vq END IF END SUB samplesフォルダ内EUCLID.BAS参照