移動式の「デカルト座標」、「因数」と言えば、そうだね、映画『CUBE(監督:ヴィンチェンゾ・ナタリ)』だね!はい、どうもボクです。
というわけで、今回も Java の話です。
最小公倍数とは
今日も、Wikipediaさんに聞いてみた。
とあり、
公倍数(こうばいすう)とは、2つ以上の整数に共通な倍数。例えば、との公倍数は-18,-12,-6,0,6,12,18などである。ただし、算数では、倍数にを含めないので、公倍数にもを含めない。
公倍数のうち、正で最小のものを最小公倍数という。上の例でいうと、との最小公倍数はである。
であると。
んで、2つの整数の場合だと、
が成りたつんだと。
つまり、最大公約数が求まれば、自ずと、最小公倍数が求まるのだと。
だが、しかし!
しかし、この関係式は3つ以上の正整数に対しては一般には成立しない。例えば、とすると、であるが、である。
とあるように、3つ以上の整数になってくると成り立たないらしい...
3つ以上の整数になってくると、
って感じになるらしいですと...。
↓ 3つの整数だと、
x(x+1)(x-1) 、 x(x-1) + (x-1)((x+1)(x+1)-x)
x(x+1)(x+1) 、 (x-1)(x+(x+1)(x+1)-x)
x(x+1)(x+1) 、 (x-1)(x+1)(x+1)
↓ 最小公倍数は、
x(x+1)(x+1)(x-1)
ってことらしい...
っていうか、3次元以上の場合どうすれば良いんですかね...
ちなみに、4次元までしか、公式が存在しないらしい...
再帰処理で最小公倍数が求まるらしい
言語はPHPになるけれども、
⇧ 上記サイト様が、3つ以上の整数の場合の最小公倍数を求めてますね。
というわけで、Javaを使って求めてみますか。
ちなみに、最大公約数は、
⇧ この回の記事で求めていますが、今回は、最小公倍数を求めるために、最大公約数の求め方も修正してます。
というわけで、Eclipse を起動し、適当なJavaプロジェクトを作成し、クラスも作成。
ソースコードはこんな感じで。
package main; import java.math.BigInteger; import java.util.Objects; import java.util.stream.Stream; public class LeastCommonMultiple { public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ // 最小公倍数を求めたい、数 BigInteger[] bigIntArr = { BigInteger.valueOf(290021904), BigInteger.valueOf(927964716), BigInteger.valueOf(826824516), BigInteger.valueOf(817140688) }; // BigInteger[] bigIntArr = { // BigInteger.valueOf(2), // BigInteger.valueOf(12), // BigInteger.valueOf(36), // BigInteger.valueOf(18) // }; // 最大公約数 System.out.println("最大公約数: " + gcd(bigIntArr)); // 最小公倍数 System.out.println("最小公倍数: " + lcm(bigIntArr)); } // 最小公倍数(対象のすべての整数) public static BigInteger lcm(BigInteger... arr) { return Stream.of(arr).reduce((x, y) -> createLcm(x, y)).orElse(BigInteger.ONE); } //最小公倍数(指定した2つの整数) public static BigInteger createLcm(BigInteger x, BigInteger y) { return x.multiply(y) .divide(Objects.nonNull(creategcd(x, y)) ? creategcd(x, y) : BigInteger.ONE); } // 最大公約数(指定した2つの整数) public static BigInteger creategcd(BigInteger x, BigInteger y) { return (Objects.nonNull(x) ? x : BigInteger.ONE).gcd(y); } // 最大公約数(対象のすべての整数) public static BigInteger gcd(BigInteger[] arr) { return Stream.of(arr) .reduce(BigInteger::gcd) .orElse(BigInteger.ZERO); } }
んで、実行してみる。
最小公倍数が上手くいってるのか分かりづらいので、配列の要素の整数を小さい値にしてみて実行。
「2」「12」「36」「18」の最小公倍数は、「36」になっているので、なんとなく上手くいってるような気がするということで。
なんか、もっとエレガントなコーディングができるようになりたいもんですね...
ちなみに、勘違いしてたんだけど、reduce 自体は、再帰処理じゃないらしい...
reduce(BinaryOperator<T> accumulator)
とあり、
リダクション操作(折りたたみとも呼ばれる)は、一連の入力要素を受け取り、結合操作を繰り返し適用することでそれらを結合し、単一のサマリー結果を出力します(一連の数値の合計または最大値の検索や、リストへの要素の蓄積など)。ストリーム・クラスには、reduce()
、collect()
と呼ばれる複数の形式の汎用リダクション操作と、sum()
、max()
、count()
など、複数の特殊化されたリダクション形式が含まれています。
もちろん、そのような操作は、次のように単純な順次処理ループとして簡単に実装できます。
int sum = 0;
for (int x : numbers) {
sum += x;
}
つまり、単なるループ処理だと(涙)。
なので、再帰処理じゃなくても、最小公倍数を求めていけるってことですかね...
う~ん、なんかモヤモヤ感が今日もまた残るけど...
今回はこのへんで。
2021年4月20日(水)追記:↓ ここから
「StreamAPI 」とか使わずに実装しておられる方もおりました~。
2021年4月20日(水)追記:↑ ここまで