OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

ユークリッドの互助法って何でしょか?

  • すぐに回答を!
  • 質問No.111701
  • 閲覧数353
  • ありがとう数5
  • 気になる数0
  • 回答数2
  • コメント数0

お礼率 75% (9/12)

学校の問題で、その方法を再帰呼び出しを持って実践するプログラムを作りなさい、と言うのが出て、そのまずユークリッドが分からないで八方塞がりingです。    余り知識が無いんで簡潔に説明して戴けたら、これ、幸いであります。 
通報する
  • 回答数2
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.2
レベル14

ベストアンサー率 30% (2593/8599)

簡潔に説明しましょう。
ユークリッド・・大昔の数学の大家。ユークリッド幾何学、非ユークリッド幾何学の名で有名。
ユークリッドの互除法・・2つの数の最大公約数を求めるのに、最も早い、すばらしい方法。互除法というのはお互いに除算(割り算)をすると言う意味。互助法ではありません。
[ユークリッドの互除法]
(1)2つの数を、A、Bとします。仮にAが大きいとします。
(2)AをBで割って余りをRとします。
(3)Rが0なら、Bが答え(最大公約数)で終わり。
(4)BとRのうち大きいほうをAに入れ、小さいほうをBに入れます。
(5)前の(2)へ飛びます。

例をあげましょう。A=18、B=12とします。
R=mod(18,12)=6
A=12、B=6
R=mod(12,6)=0 → 終わり  B=6が答え(最大公約数)
どうです。簡単でしょう。

割り算の代わりに引き算を繰り返し使う方法もあります(CASLなどでは)

この問題で、再帰処理を使うメリットは感じませんが、練習として使う事は可能です。再帰処理は質問に入っていないので、省略します。過去にも再帰処理の質問は出ています。頑張ってください。
お礼コメント
sonicgear

お礼率 75% (9/12)

 ご回答どうも有り難う御座いました! ナカナカ分かり易かったです。 感謝です。
  
投稿日時 - 2001-08-03 12:58:06
-PR-
-PR-

その他の回答 (全1件)

  • 回答No.1
レベル12

ベストアンサー率 65% (276/422)

どもども田吾作7です。 再帰法で再起不能 ↑おっさんギャグ まぁそれはそれとして、 再帰法はわかりますか? 簡単な例題を出します。 50平方の画用紙を、ある裁断機に入れると半分の大きさになります。 1平方メートル以下の大きさになるには何回通るでしょう? VBではDO~LOOPを使う方法がありますが、再帰法で行うことも出来ます。 Option Explicit � ...続きを読む
どもども田吾作7です。

再帰法で再起不能
↑おっさんギャグ

まぁそれはそれとして、
再帰法はわかりますか?

簡単な例題を出します。
50平方の画用紙を、ある裁断機に入れると半分の大きさになります。
1平方メートル以下の大きさになるには何回通るでしょう?

VBではDO~LOOPを使う方法がありますが、再帰法で行うことも出来ます。
Option Explicit

'カット回数を表すカウンタ
Private CutCount  As Long

Public Sub Main()
  'ペーパーのサイズ
  Dim PaperSize  As Double
  
  '基本の大きさ
  PaperSize = 50
  
  'カットした回数の初期値
  CutCount = 0
  
  '裁断機にかける
  Call CutPaper(PaperSize)
  
  MsgBox CutCount
End Sub


'裁断機
Private Sub CutPaper(inParper As Double)

  '用紙サイズが1m2以下なら終了
  If inParper < 1 Then Exit Sub
  
  '用紙サイズが1m2以上であれば裁断機にかけるて自分自身を呼び出す
  '(カウンタを増やし、自分自身を呼び出す)
  inParper = inParper / 2
  CutCount = CutCount + 1
  Call CutPaper(inParper)
End Sub

このように条件を満たすまで、自分自身を呼び出すのが再帰法です。
例題があまりよくないので、これはDO~LOOPの方が好ましいかも知れません。

実際使用するとしたら、「あるフォルダ以下を全て書き込み禁止にしなさい」といった処理を行う時に、再帰法がベストだと思います。フォルダの中のファイルを書込み禁止にして、その中にフォルダが存在していたら、更にそのフォルダ内を書込み禁止にして・・・・とフォルダが存在する限り、その関数を走り続けるようになります。(サンプルはちょっと面倒なので勘弁して)


この一つ目の例題と二つ目の大きな差は、同じレベルか、それとも下のレベルかという点にあります。

ペーパーはあくまで裁断されても、単に小さいペーパーであって、最初の50平方メートルのペーパーを指します。
しかしフォルダ内の書込み禁止は、フォルダの中のサブフォルダ、またはさらにその中のサブフォルダ・・・と階層があるわけです。

前置きが長くなりましたが、ユーグリッド法はわかりませんが、ユーグリッドの互助法はこの概念と共通してます。
「ある条件が満たされるまで、一つのパターンを繰り返して行く」
まさに再帰法です。

下記URLにユーグリッドの互助法による、最大公約数の求め方がありますので、そちらをのぞいてみては?
そちらにも例題があります。
[a][b][r][r1]とか書いてありますが、例題の具体例を紙に書いてやってみると、同じこと繰り返しをしているだけで、結構単純であることに気付くと思いますよ。
お礼コメント
sonicgear

お礼率 75% (9/12)

 ご回答有り難う御座います! 少し分かったような、分からないような・・・  勉強します!!
投稿日時 - 2001-08-03 12:50:17
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ