新しく発言する  EXIT  インデックスへ
初心者メモ:再帰型fuctonGCD()の考え方。

  初心者メモ:再帰型fucton GCD() の考え方。 SECOND 2008/01/09 03:44:21  (修正3回)

初心者メモ:再帰型fucton GCD() の考え方。  返事を書く  ノートメニュー
SECOND <jjqdmekgpt> 2008/01/09 03:44:21 ** この記事は3回修正されてます
!初心者メモ:再帰型function GCD() の考え方。

!2つの数(A,B)の、GCDとLCM。
!A,B なる数は、それぞれ、隠れているGCD( Greatest Common Divisor 最大公約数 )
!の整数倍 同士と考える・・

!A=GCD*m
!B=GCD*n
!LCM( Least Common Multiple 最小公倍数 )=GCD*m*n =A*B/GCD

!の関係があります。

!R=MOD(A,B)

!Rも、又GCDの倍数になっています。そして、R<B です。ですから、

!R1=MOD(B,R)

!とすれば、R1 は、Rよりさらに小さくなるはずです。
!さらに、又それも、GCDの倍数になっています。ですから、

!  k回目の Rk=MOD(Ak,Bk)を使って、
!k+1回目の Rk+1=MOD(Bk,Rk)を、計算する操作を無限に繰返せば、

!いつかは、R? が、0になります。その1つ手前のR?-1 が、GCDの最小の倍数、GCD*1です。

!R? が、0の時、それは、B?に置かれています。
!さらに繰返し、R?+1 を求めようとすると、それはA?+1に置かれ、B?+1は、0が入ってしまいます。
FUNCTION Rk1(Ak,Bk)
WHEN EXCEPTION IN
LET Rk=MOD(Ak,Bk)
LET w=Rk1(Bk,Rk) ! k回目の Bk,Rk で k+1回目の Rk+1 を、自身へ無限に呼び出す。
!wは、不要な関数値の意味で、何でもよい、だだのダミーです。
USE
LET Rk1=Ak ! Bk=0 で入って来て、MOD(Ak,0)のエラーがでたら、Ak=GCD*1。
END WHEN
END FUNCTION

!エラー前に、止めれば、Sample Program に有る様、もっとスマートです。
FUNCTION GCD(Ak,Bk)
LET Rk=MOD(Ak,Bk)
IF Rk<>0 THEN LET w=GCD(Bk,Rk) ELSE LET GCD=Bk
!wは、上記と同様。
END FUNCTION

LET A=2*3*5*7*11*13
LET B=7*11*17*19
PRINT "A=";A
PRINT "B=";B
PRINT "GCD=";Rk1(A,B);" スマートな方→";GCD(A,B)
PRINT "LCM=";A*B/Rk1(A,B)

END

!※このページは、全部を、貼り付けても、RUN できます。

  fuctonではなく、functionです。^^; SECOND 2008/01/09 15:20:25 

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