※当サイトの記事には、広告・プロモーションが含まれます。

Java に限らないと思うけど、最大公約数(GCD:Greatest Common Divisor)を求めるには、ユークリッドの互除法 というものが良さ気らしい

f:id:ts0818:20190720104401j:plain

「エイドリア~ン!【映画:ロッキー】(監督:シルベスター・スタローン)」

ピエト・モンドリアンピート・モンドリアン、Piet Mondrian、本名ピーテル・コルネーリス・モンドリアーン Pieter Cornelis Mondriaan 1872年3月7日 - 1944年2月1日)は、19世紀末-20世紀オランダ出身の画家ワシリー・カンディンスキーカジミール・マレーヴィチらと並び、本格的な抽象絵画を描いた最初期の画家とされる。

ピエト・モンドリアン - Wikipedia

はい~、皆様ご存知、「ピエト・モンドリアン」の絵画の画像ですね。抽象絵画の傑作でございます、あ、どうもボクです。

というわけで、 今回は、

アレクサンドリアエウクレイデス古代ギリシャ語ΕὐκλείδηςEukleídēsラテン語Euclīdēs英語Euclidユークリッド)、紀元前3世紀? - )は、古代エジプトギリシャ系数学者天文学者とされる。数学史上最も重要な著作の1つ『原論』(ユークリッド原論)の著者であり、「幾何学の父」と称される。 

エウクレイデス - Wikipedia

⇧  ユークリッドさん が生み出したと言われる、「ユークリッドの互除法」のお話です。

ちなみに、全然関係ない話ですが、

ccse2019.peatix.com

⇧  行って参りました~。数学が重要になってくるという話が多かったですかね...私は文系ですが、何か?(涙)

 

そんでは、レッツトライ~。

 

ユークリッドの互除法 とは?

Wikipedia さんは、今日も答えてくれた。 

ユークリッドの互除法ユークリッドのごじょほう、Euclidean Algorithm)は、2 つの自然数最大公約数を求める手法の一つである。

2 つの自然数 ab (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。

明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである。

ユークリッドの互除法 - Wikipedia

⇧  う~ん...、言葉にするとなんだかなぁ~な感じなんですが、

www.yukisako.xyz

⇧  上記サイト様の図が分かりやすかったので、流用させていただきました。

ということらしいっす。 

なんか、再帰処理でイケそうなロジックですかね~と思っていたところ、

qiita.com

⇧  上記サイト様によりますと、イケるらしいです。

 

ユークリッドの互除法は、視覚的に捉えると、アハ!体験的に、エウレカ!ってなる感じですかね。

 

  

Javaユークリッドの互除法

んでは、Java で実装してみますか~。

qiita.com

⇧  上記サイト様を写経させていただきました。

Eclipseで適当に、Javaプロジェクトを作成し、クラスも作成。

f:id:ts0818:20190720120338p:plain

ソースはこんな感じで。
 

package main;

import java.math.BigInteger;
import java.util.stream.Stream;

public class Euclidean {

  public static void main(String[] args) {
    // 最大公約数を求めたい、数
    BigInteger[] bigIntArr = {
        BigInteger.valueOf(290021904), 
        BigInteger.valueOf(927964716), 
        BigInteger.valueOf(826824516), 
        BigInteger.valueOf(817140688)
    };
    // 実際の処理と結果
    System.out.println(gcd(bigIntArr));
  }
  
  public static BigInteger gcd(BigInteger[] arr) {
    return Stream.of(arr)
    .reduce(BigInteger::gcd)
    .orElse(BigInteger.ZERO);
  }
}
    

で動かしてみる。

f:id:ts0818:20190720120202p:plain

f:id:ts0818:20190720120120p:plain

よく分からんけど、StreamAPIの reduce メソッドと、orElse メソッドの組み合わせで再帰処理のようなことを行っている?らしいと思う。

んで、後から思ったんだけど、最大公約数が、BigInteger みたいな大きな値になることは無いと思われるので、戻り値としては、int で十分だったかなと...このへんも数学の知識が無いからよく分からんですが...

というわけで、数学的な知識が欲しいな~と常に思う今日この頃です。

今回はこのへんで。

 

2020年1月2日(水)追記:↓  ここから

標準入力からの数値文字列に対しての最大公約数を求められるようなバージョンでコーディングしてみました。

onlinejudge.u-aizu.ac.jp

package main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.stream.Stream;

public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] strArr = in.readLine().split("\\s");
    BigInteger[] bigIntArr = new BigInteger[strArr.length];
    for (int index = 0; index < strArr.length; index++) {
     bigIntArr[index] = BigInteger.valueOf(Long.valueOf(strArr[index]));
    }
    // 実際の処理と結果
    System.out.println(gcd(bigIntArr));
   }

   public static BigInteger gcd(BigInteger[] arr) {
    return Stream.of(arr)
    .reduce(BigInteger::gcd)
    .orElse(BigInteger.ZERO);
   }
}

f:id:ts0818:20200102090437p:plain

とりあえず、Aizu Online Judgeの判定では、OKっぽいです。

f:id:ts0818:20200102090740p:plain

 

2020年1月2日(水)追記:↑  ここまで