ExMurasakiGCD - デカルト言語 - 並列ロジック プログラミング言語 Wiki - デカルト言語 - 並列ロジック プログラミング言語

←　前のページに戻る

0.3 ユークリッドの互除法

ユークリッドの互除法を使って最大公約数を求めるプログラムを作ります。

// ユークリッドの互除法

// 最大公約数を求める

#xは、#xと0の最大公約数です。

#a >= #bが成立し、
#c = #a % #bを計算し、
#xは、#bと#cの最大公約数である場合、
#xは、#aと#bの最大公約数です。

#c = #a % #bを計算し、
#xは、#aと#cの最大公約数である場合、
#xは、#aと#bの最大公約数です。

// 実行
#xは、30と12の最大公約数ですか。
#xは、511639100と258028360の最大公約数ですか。

論理的かつ宣言的に書けます。

本当にこれで最大公約数が得られるか実行してみましょう。

上のプログラムはsamples/gcd.mrsに入っているとします。

$ descartes murasaki samples/gcd.mrs

#xは、30と12の最大公約数ですか。
6は、30と12の最大公約数です。

#xは、511639100と258028360の最大公約数ですか。
20は、511639100と258028360の最大公約数です。

うまくいきました。

日本語プログラム「紫」は、定められた構文の日本語の記述をデカルト言語に変換して実行します。

このユークリッドの互除法は、次に示すデカルト言語に変換されて実行されます。 元のプログラムと見比べてみてください。

 <M2 最大公約数 #x (#x 0)>
        ;
 <M2 最大公約数 #x (#a #b)> 
      <compare #a >= #b> 
      <let #c = #a % #b> 
      <M2 最大公約数 #x (#b #c)>
        ;
 <M2 最大公約数 #x (#a #b)> 
      <let #c = #a % #b> 
      <M2 最大公約数 #x (#a #c)>
        ;

? <printf '#xは、30と12の最大公約数ですか。' <\_n>>;
? <回答 (<M2 最大公約数 #x (30 12)>)>;
? <print>;
? <printf '#xは、511639100と258028360の最大公約数ですか。' <\_n>>;
? <回答 (<M2 最大公約数 #x (511639100 258028360)>)>;
? <print>;

--

--