初心者メモ：再帰型fuctonGCD()の考え方。

!初心者メモ：再帰型function GCD() の考え方。

!２つの数（A,B）の、ＧＣＤとＬＣＭ。
!Ａ，Ｂなる数は、それぞれ、隠れているＧＣＤ（ Greatest Common Divisor 最大公約数）
!の整数倍　同士と考える・・

!Ａ＝ＧＣＤ＊ｍ
!Ｂ＝ＧＣＤ＊ｎ
!ＬＣＭ（ Least Common Multiple 最小公倍数）＝ＧＣＤ＊ｍ＊ｎ　＝Ａ＊Ｂ／ＧＣＤ

!の関係があります。

!Ｒ＝ＭＯＤ（Ａ,Ｂ）

!Ｒも、又ＧＣＤの倍数になっています。そして、Ｒ＜Ｂです。ですから、

!Ｒ1＝ＭＯＤ（Ｂ,Ｒ）

!とすれば、Ｒ1 は、Ｒよりさらに小さくなるはずです。
!さらに、又それも、ＧＣＤの倍数になっています。ですから、

!　　ｋ回目の　Ｒk＝ＭＯＤ（Ａk,Ｂk）を使って、
!ｋ＋１回目の　Ｒk+1＝ＭＯＤ（Ｂk,Ｒk）を、計算する操作を無限に繰返せば、

!いつかは、Ｒ? が、０になります。その１つ手前のＲ?-1 が、ＧＣＤの最小の倍数、ＧＣＤ＊１です。

!Ｒ? が、０の時、それは、Ｂ?に置かれています。
!さらに繰返し、Ｒ?+1 を求めようとすると、それはＡ?+1に置かれ、Ｂ?+1は、０が入ってしまいます。
FUNCTION Rk1(Ak,Bk)
WHEN EXCEPTION IN
LET Rk=MOD(Ak,Bk)
LET w=Rk1(Bk,Rk) !　ｋ回目の Bk,Rk で k+1回目の Rk+1 を、自身へ無限に呼び出す。
!wは、不要な関数値の意味で、何でもよい、だだのダミーです。
USE
LET Rk1=Ak !　Bk=0 で入って来て、MOD(Ak,0)のエラーがでたら、Ak=ＧＣＤ＊１。
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 GCD() の考え方。	返事を書くノートメニュー
SECOND <jjqdmekgpt> 2008/01/09 03:44:21 ** この記事は3回修正されてます
!初心者メモ：再帰型function GCD() の考え方。 !２つの数（A,B）の、ＧＣＤとＬＣＭ。 !Ａ，Ｂなる数は、それぞれ、隠れているＧＣＤ（ Greatest Common Divisor 最大公約数） !の整数倍　同士と考える・・ !Ａ＝ＧＣＤ＊ｍ !Ｂ＝ＧＣＤ＊ｎ !ＬＣＭ（ Least Common Multiple 最小公倍数）＝ＧＣＤ＊ｍ＊ｎ　＝Ａ＊Ｂ／ＧＣＤ !の関係があります。 !Ｒ＝ＭＯＤ（Ａ,Ｂ） !Ｒも、又ＧＣＤの倍数になっています。そして、Ｒ＜Ｂです。ですから、 !Ｒ1＝ＭＯＤ（Ｂ,Ｒ） !とすれば、Ｒ1 は、Ｒよりさらに小さくなるはずです。 !さらに、又それも、ＧＣＤの倍数になっています。ですから、 !　　ｋ回目の　Ｒk＝ＭＯＤ（Ａk,Ｂk）を使って、 !ｋ＋１回目の　Ｒk+1＝ＭＯＤ（Ｂk,Ｒk）を、計算する操作を無限に繰返せば、 !いつかは、Ｒ? が、０になります。その１つ手前のＲ?-1 が、ＧＣＤの最小の倍数、ＧＣＤ＊１です。 !Ｒ? が、０の時、それは、Ｂ?に置かれています。 !さらに繰返し、Ｒ?+1 を求めようとすると、それはＡ?+1に置かれ、Ｂ?+1は、０が入ってしまいます。 FUNCTION Rk1(Ak,Bk) WHEN EXCEPTION IN LET Rk=MOD(Ak,Bk) LET w=Rk1(Bk,Rk) !　ｋ回目の Bk,Rk で k+1回目の Rk+1 を、自身へ無限に呼び出す。 !wは、不要な関数値の意味で、何でもよい、だだのダミーです。 USE LET Rk1=Ak !　Bk=0 で入って来て、MOD(Ak,0)のエラーがでたら、Ak=ＧＣＤ＊１。 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=23571113 LET B=7111719 PRINT "A=";A PRINT "B=";B PRINT "GCD=";Rk1(A,B);"　スマートな方→";GCD(A,B) PRINT "LCM=";A*B/Rk1(A,B) END !※このページは、全部を、貼り付けても、RUN できます。