新しく発言する EXIT インデックスへ

合同式による水汲み問題の解法

　　合同式による水汲み問題の解法 山中和義 2008/03/16 14:11:01  (修正1回)
　　├!合同式による計算機内部の整数演算（加算器... 山中和義 2008/03/16 14:13:27  (修正1回)
　　│└つづき（乗算器） 山中和義 2008/03/16 14:16:08  (修正1回)
　　└!連立１次合同方程式を解く 山中和義 2008/03/21 18:45:05
Re: 合同式による水汲み問題の解法 返事を書く ノートメニュー
山中和義 <drdlxujciw> 2008/03/21 18:45:05
!連立１次合同方程式を解く

!中国の剰余定理 (Chinese remainder theorem)

!3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か

DATA 2,3 !x≡2 (mod 3)
DATA 3,5 !x≡3 (mod 5)
DATA 2,7 !x≡2 (mod 7)

LET N=3 !数

DIM ai(N),ni(N)
FOR i=1 TO N
READ ai(i),ni(i) !x≡ai (mod ni)
NEXT i


!--------------------
!３組の１次合同式を解く
!　35*x1≡1 (mod 3)
!　21*x2≡1 (mod 5)
!　15*x3≡1 (mod 7)
LET NN=1
FOR i=1 TO N
LET NN=NN*ni(i) !n1*n2* … *nn
NEXT i

DIM ui(N)
FOR i=1 TO N
LET ui(i)=NN/ni(i)
NEXT i

DIM xi(N)
FOR i=1 TO N
LET xi(i)=congruence(ui(i),1,ni(i)) !ui*xi≡1 (mod ni)
NEXT i
MAT PRINT xi


!--------------------
LET x=0
FOR i=1 TO N
LET x=x+ui(i)*xi(i)*ai(i) !Σui*xi*ai (mod n1*n2* … *nn)
NEXT i
LET x=MOD(x,NN)
PRINT "x=";x;"(mod";NN;")" !解




FUNCTION congruence(a,b,m) !１次合同式 a*x≡b (mod m) を満たす x を求め
IF m=0 THEN LET congruence=-1

LET c=a
LET e=b
LET d=m
LET f=0

LET r=MOD(c,d)
DO WHILE r<>0
LET q=INT(c/d)
LET c=d
LET d=r
LET tmp=f
LET f=e-q*f
LET e=tmp

LET r=MOD(c,d)
LOOP
IF MOD(b,d)<>0 THEN LET congruence=-1

LET q=MOD(INT(f/d),INT(m/d))
IF q<0 THEN LET q=q+INT(m/d)
LET congruence=q
END FUNCTION


END

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