新しく発言する  EXIT  インデックスへ
拡張ユークリッド互除法

  拡張ユークリッド互除法 山中和義 2008/01/08 11:40:31  (修正1回)

拡張ユークリッド互除法  返事を書く  ノートメニュー
山中和義 <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 に対して 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参照

  別解(繰り返し、MAT文による) 山中和義 2008/01/10 16:10:41 

 インデックスへ  EXIT
新規発言を反映させるにはブラウザの更新ボタンを押してください。