新しく発言する 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 

　　合同式による水汲み問題の解法 山中和義 2008/03/16 14:11:01  (修正1回)  ツリーへ
合同式による水汲み問題の解法 返事を書く ノートメニュー
山中和義 <drdlxujciw> 2008/03/16 14:11:01 ** この記事は1回修正されてます
!容積が17リットルと29リットルの容器を使って、１リットルの水を汲む
!方程式 17*x≡1 mod 29

FOR i=1 TO 20 !回数
PRINT i;"回目"
LET a=17*i
LET b=MOD(a,29) !合同式 a≡b (mod m)
PRINT "くみ出し";INT(a/29);"回で、"; b;"リットル"
IF b=1 THEN EXIT FOR
NEXT i

END




!１次合同式 a*x≡b (mod m) を満たす x を求める

FUNCTION congruence(a,b,m)
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


LET x=congruence(17,1,29) !17*x≡1 (mod 29)

IF x<0 THEN
PRINT "解はありません。"
ELSE
PRINT "x="; x
END IF

END




その他の解法

拡張ユークリッド互除法
SAMPLEフォルダ内EUCLID.BAS参照

過去掲示板
http://freebbs.around.ne.jp/article/b/basic/102/gypiuo/gypiuo.html
 
　　├!合同式による計算機内部の整数演算（加算器... 山中和義 2008/03/16 14:13:27  (修正1回)  ツリーへ
Re: 合同式による水汲み問題の解法 返事を書く ノートメニュー
山中和義 <drdlxujciw> 2008/03/16 14:13:27 ** この記事は1回修正されてます
!合同式による計算機内部の整数演算（加算器、減算器）

DEF cong(x)=MOD(x,m^N) !合同式 x'≡x (mod m^N)

SUB disp(x) !表記する
PRINT USING "########": x; !10進法
PRINT " (";right$(REPEAT$(" ",N-1)&BSTR$(x,2),N);")"; !Nビット符号なし2進法
PRINT " #";BSTR$(x,16) !16進法
END SUB


LET m=2 !進法
LET N=8 !桁数　※8ビット -128〜127

LET a=12
LET b=-3

PRINT "入力された値　※10進法"
PRINT "a=";a
PRINT "b=";b
PRINT



!---------- ↓↓↓↓↓ ----------
PRINT "計算機内部の値（";m;"の補数）　※レジスタ、メモリ"
LET aa=cong(a) !N桁符号あり整数へ
!!!IF a<0 THEN LET aa=a+m^N ELSE LET aa=a !N桁符号あり整数へ
LET bb=cong(b)
PRINT "a=";
CALL disp(aa)
PRINT "b=";
CALL disp(bb)
PRINT


PRINT "加算　※ALU、アキュームレータ"
PRINT USING " ########": aa
PRINT USING "＋########": bb
PRINT "-----------"

PRINT USING " ########": aa+bb !最上位桁の桁上りを考慮した計算

LET acc=cong(aa+bb) !最上位桁の桁上りは無視する
PRINT " ";
CALL disp(acc)
!---------- ↑↑↑↑↑ ----------


PRINT
PRINT "出力装置での表示"
IF acc>=m^N/2 THEN !負の数なら（MSBが1）
LET dat=MOD(acc,-m^N) !N桁符号なし整数へ
!!!LET dat=acc-m^N !N桁符号なし整数へ
ELSE
LET dat=acc !そのまま
END IF
PRINT dat



PRINT
PRINT "検算 a+b=";a+b

END
 
　　│└つづき（乗算器） 山中和義 2008/03/16 14:16:08  (修正1回)  ツリーへ
Re: !合同式による計算機内部の整数演算（加算器... 返事を書く ノートメニュー
山中和義 <drdlxujciw> 2008/03/16 14:16:08 ** この記事は1回修正されてます
つづき（乗算器）


DEF cong(x)=MOD(x,m^N) !合同式 x'≡x (mod m^N)

SUB disp(x) !表記する
PRINT USING "########": x; !10進法
PRINT " (";right$(REPEAT$(" ",N-1)&BSTR$(x,2),N);")"; !Nビット符号なし2進法
PRINT " #";BSTR$(x,16) !16進法
END SUB


LET m=2 !進法
LET N=8 !桁数　※8ビット -128〜127


LET a=12
LET b=-3

PRINT "入力された値　※10進法"
PRINT "a=";a
PRINT "b=";b
PRINT


!LET N=2*N !ビット幅は２倍になる


!---------- ↓↓↓↓↓ ----------
PRINT "計算機内部の値（";m;"の補数）　※レジスタ、メモリ"
LET aa=cong(a) !N桁符号あり整数へ　※符号拡張
LET bb=cong(b)
PRINT "a=";
CALL disp(aa)
PRINT "b=";
CALL disp(bb)
PRINT


PRINT "乗算　※ALU、アキュームレータ" !<--------------- ※加算との差異
PRINT USING " ########": aa
PRINT USING "×########": bb !<--------------- ※
PRINT "-----------"

PRINT USING "##########": aa*bb !最上位桁の桁上りを考慮した計算<--------------- ※

LET acc=cong(aa*bb) !最上位桁の桁上りは無視する<--------------- ※

PRINT " ";
CALL disp(acc)
!---------- ↑↑↑↑↑ ----------



PRINT
PRINT "出力装置での表示"
IF acc>=m^N/2 THEN !負の数なら（MSBが1）
LET dat=MOD(acc,-m^N) !N桁符号なし整数へ
!!!LET dat=acc-m^N !N桁符号なし整数へ
ELSE
LET dat=acc !そのまま
END IF
PRINT dat



PRINT
PRINT "検算 a*b=";a*b !<--------------- ※

END
 
　　└!連立１次合同方程式を解く 山中和義 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
新規発言を反映させるにはブラウザの更新ボタンを押してください。