ヽ|∵|ゝ(Fantom) の 開発blog? ホーム »約数
このページの記事一覧

【Java】3つ以上の最大公約数を求める(ユークリッドの互除法②)  


 「ユークリッドの互除法」や「拡張ユークリッドの互除法」は「自然数 a, b 2つの最大公約数を求める」ものであるが、では3つ以上の複数の最大公約数(a, b, c, d,...)はどうやって求めるのだろうか。実はこれも英語版の Wikipedia に書いてある。説明を翻訳しなくても「gcd(a, b, c) = gcd(gcd(a, b), c)」の式を見れば十分わかるだろう。簡単に言えば「a, b の最大公約数を求め、更にその答えと c の最大公約数を求める」ということになる。更に複数のパラメタがあるときは、それを繰り返す感じになる。つまりは入れ子にすれば良いだけである。


 といっても、3つ4つ…と増やした場合は表記が面倒になるので、いっそのこと専用の関数を作ってしまおう。Java には可変引数(型...)があるので、それを使えば簡単に書ける。

●3つ以上の最大公約数を求める[ユークリッドの互除法②]
/**<h1>3つ以上の最大公約数を求める[gcd(a, b, c,...)]</h1>
* <p>ユークリッドの互除法の繰り返しで求める。</p>
* @param param : 数値1, 2, 3,... (a, b, c,...) (>0) [引数は3個以上]
* @return<b>int</b> : 最大公約数(なし=1[互いに素])
*/
public static final int gcd(final int... param) {
final int len = param.length;
int g = gcd(param[0], param[1]); //gcd(a, b) は以前作ったもの
for (int i = 1; i < len - 1; i++) {
g = gcd(g, param[i + 1]); //gcd(a, b) は以前作ったもの
}
return g;
}


//メインでは...
int a = 12;
int b = 36;
int c = 60;
int d = 96;

int g1 = gcd(a, b);
int g2 = gcd(g1, c);
int g3 = gcd(g2, d);
System.out.println("g3 = " + g3);

int g = gcd(a, b, c, d);
System.out.println("g = " + g);
System.out.println(g == g3);

g3 = 12
g = 12
true

 gcd(a, b) は以前作ったものをそのまま使って欲しい。入れ子はループで書いてあるが、いかにも再帰で書けそうな感じなので、試してみても良いかも知れない。ここでは後述する「3つ以上のパラメタに対応させた拡張ユークリッド互除法」と比較するためにもループで書いてみる。

 また、引数が1つのときは不正となるので気をつけよう。必要があれば例外処理を入れても良いかも知れない(引数が1つ=param.length(len)が1のときはエラーとするなど)。gcd() を同名でオーバーロードした場合は引数2つの場合は gcd(a, b) になり、3つ以上の場合は gcd(...) の方にディスパッチされる。ちなみに可変引数はメソッド内では配列のように扱われる。紛らわしいと感じるなら別名で関数定義しても良いだろう。

 それではもう1つ、同じように「拡張ユークリッドの互除法」を入れ子にして、複数のパラメタに対応させてみよう。

●3つ以上のパラメタに対応させた拡張ユークリッドの互除法
/**<h1>3つ以上のパラメタに対応させた拡張ユークリッド互除法[ax + by + cz +... = gcd(a, b, c,...)]</h1>
* <p>拡張ユークリッドの互除法の繰り返しで求める。</p>
* @param param : 数値 1, 2, 3,... (a, b, c,...) (>0) [引数は3個以上]
* @return<b>int[]</b> : {[0]:gcd, [1]:x, [2]:y, [3]z,...} 最大公約数(なし=1 [互いに素])と解 x, y, z...
*/
public static final int[] extgcd(final int... param) {
final int len = param.length;
final int[][] g = new int[len - 1][];
g[0] = extgcd(param[0], param[1]); //extgcd(a, b) は以前作ったもの
for (int i = 1; i < len - 1; i++) {
g[i] = extgcd(g[i - 1][0], param[i + 1]); //extgcd(a, b) は以前作ったもの
}

//解の係数を展開する
final int[] res = new int[len + 1];
res[len] = g[len - 2][2];
res[0] = g[len - 2][0]; //gcd

int k = g[len - 2][1];
for (int i = len - 3; i >= 0; i--) {
res[i + 2] = g[i][2] * k;
k *= g[i][1];
}
res[1] = k;
return res;
}


//メインでは...
int a = 12;
int b = 16;
int c = 18;
int d = 21;

int[] g1 = extgcd(a, b);
System.out.println("g1 = " + g1[0] + ", x = " + g1[1] + ", y = " + g1[2]);
int[] g2 = extgcd(g1[0], c);
System.out.println("g2 = " + g2[0] + ", x = " + g2[1] + ", y = " + g2[2]);
int[] g3 = extgcd(g2[0], d);
System.out.println("g3 = " + g3[0] + ", x = " + g3[1] + ", y = " + g3[2]);

int[] g = extgcd(a, b, c, d);
System.out.println("g = " + g[0] + ", w = " + g[1] + ", x = " + g[2] + ", y = " + g[3] + ", z = " + g[4]);

g1 = 4, x = -1, y = 1
g2 = 2, x = -4, y = 1
g3 = 1, x = -10, y = 1
g = 1, w = -40, x = 40, y = -10, z = 1

 extgcd(a, b) は以前作ったものをそのまま使って欲しい。これも gcd(...) と基本的には変わらないので、引数が1つのときはエラーとなるので注意しよう。例外処理を追加しても良い。

 拡張ユークリッドの互除法を繰り返している部分は gcd(...) はほぼ同じと言っても良いが、解も入れ子になっているので、それらを展開するために配列に1回ごとの extgcd(a, b) の答えを記録し、最後に計算している。コードが少し難しく感じるかも知れないが、元々は以下のように、1つずつの式だと思えばそれほどでないことがわかるだろう。

a = 12, b = 16, c = 18, d = 21 のとき、
g1 = extgcd(a, b) → g1 = 4, x = -1, y = 1 → 4 = 12 * -1 + 16 * 1
g2 = extgcd(g1, c) → g2 = 2, x = -4, y = 1 → 2 = 4 * -4 + 18 * 1
g3 = extgcd(g2, d) → g3 = 1, x = -10, y = 1 → 1 = 2 * -10 + 21 * 1

g = extgcd(extgcd(extgcd(a, b), c), d) のように入れ子になっているので、
1 = ((12 * -1 + 16 * 1) * -4 + 18 * 1) * -10 + 21 * 1 (式を代入する)
 = 12 * -40 + 16 * 40 + 18 * -10 + 21 * 1 (展開する)
g = a * w + b * x + c * y + d * z (対応させる)

 使う際に少しだけ気をつけないといけないのは、係数(a, b, c, d)の値の順番を入れ替えると解(w, x, y, z)は変わる点だ。というのは a, b で求めた解 w, x を用いて更に y を求め、更に z を求め…という感じで計算しているので、1つ前の答えによって後の答えが変わるからだ。もちろんどの式も検算すれば正しいことがわかる。「いちばん小さい値(全ての解の絶対値の和とか)を求めよ」などのときには、最小となるパターンを別途見つけなくてはならない。例えば、上の例の係数を順列で並び変えてみると、

a = 12, b = 16, c = 18, d = 21, g = 1, w = -40, x = 40, y = -10, z = 1
a = 12, b = 16, c = 21, d = 18, g = 1, w = 5, x = -5, y = 1, z = 0
a = 12, b = 18, c = 16, d = 21, g = 1, w = 30, x = -30, y = 10, z = 1
a = 12, b = 18, c = 21, d = 16, g = 1, w = -15, x = 15, y = -5, z = 1
a = 12, b = 21, c = 16, d = 18, g = 1, w = -10, x = 5, y = 1, z = 0
a = 12, b = 21, c = 18, d = 16, g = 1, w = -10, x = 5, y = 0, z = 1
a = 16, b = 12, c = 18, d = 21, g = 1, w = 40, x = -40, y = -10, z = 1
a = 16, b = 12, c = 21, d = 18, g = 1, w = -5, x = 5, y = 1, z = 0
a = 16, b = 18, c = 12, d = 21, g = 1, w = 10, x = -10, y = 0, z = 1
a = 16, b = 18, c = 21, d = 12, g = 1, w = 10, x = -10, y = 1, z = 0
a = 16, b = 21, c = 12, d = 18, g = 1, w = 4, x = -3, y = 0, z = 0
a = 16, b = 21, c = 18, d = 12, g = 1, w = 4, x = -3, y = 0, z = 0
a = 18, b = 12, c = 16, d = 21, g = 1, w = -30, x = 30, y = 10, z = 1
a = 18, b = 12, c = 21, d = 16, g = 1, w = 15, x = -15, y = -5, z = 1
a = 18, b = 16, c = 12, d = 21, g = 1, w = -10, x = 10, y = 0, z = 1
a = 18, b = 16, c = 21, d = 12, g = 1, w = -10, x = 10, y = 1, z = 0
a = 18, b = 21, c = 12, d = 16, g = 1, w = 5, x = -5, y = 0, z = 1
a = 18, b = 21, c = 16, d = 12, g = 1, w = 5, x = -5, y = 1, z = 0
a = 21, b = 12, c = 16, d = 18, g = 1, w = 5, x = -10, y = 1, z = 0
a = 21, b = 12, c = 18, d = 16, g = 1, w = 5, x = -10, y = 0, z = 1
a = 21, b = 16, c = 12, d = 18, g = 1, w = -3, x = 4, y = 0, z = 0
a = 21, b = 16, c = 18, d = 12, g = 1, w = -3, x = 4, y = 0, z = 0
a = 21, b = 18, c = 12, d = 16, g = 1, w = -5, x = 5, y = 0, z = 1
a = 21, b = 18, c = 16, d = 12, g = 1, w = -5, x = 5, y = 1, z = 0

min = 7
a = 16, b = 21, c = 12, d = 18, g = 1, w = 4, x = -3, y = 0, z = 0
a = 16, b = 21, c = 18, d = 12, g = 1, w = 4, x = -3, y = 0, z = 0
a = 21, b = 16, c = 12, d = 18, g = 1, w = -3, x = 4, y = 0, z = 0
a = 21, b = 16, c = 18, d = 12, g = 1, w = -3, x = 4, y = 0, z = 0

のようになり、最小となる解の絶対値の総和は7となる(解に0を許す場合)。

 再帰でも書いてもいいかも知れないが、特に拡張ユークリッド互除法の方はコードが複雑化し兼ねないので気をつけよう。再帰よりループの方があとから改造しやすい利点もあるしね。


(関連記事)
【Java】拡張ユークリッドの互除法
【Java】最大公約数・最小公倍数を求める(ユークリッドの互除法)
【Java】約数を求める
【Java】素因数分解をする


■参考になる書籍


スポンサーサイト

category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  約数 
tb: 0   cm: --

【Java】拡張ユークリッドの互除法  


 「ユークリッドの互除法」は「自然数 a, b の最大公約数」を求めるものだったが、「拡張ユークリッド互除法」は「ax + by = gcd(a, b) となる a, b の最大公約数を求める」ものになる。簡単な方程式の整数解を求めるのにも使える。


 ググッてみると C言語で書かれている関数で引数が extgcd(a, b, &x, &y) ['&'は参照渡しとなる] となっているものが多いが、Java はプリミティブ型で参照渡しができないので、ループ版(非再帰版)の方は英語版 Wikipedia に載っているように、引数を extgcd(a, b) にして作ってみよう。無理矢理参照渡しのようにするために、要素が1つの配列を用いる方法もあるが、それは再帰版でのサンプルを見て欲しい。ループ版も同じように書き換えることもできるが、3つ以上の係数に対応したいときなどには不便なので、用途によって使い分けても良いかも知れない。

(参考)
ユークリッドの互除法/拡張ユークリッドの互除法
拡張版ユークリッドの互除法
拡張ユークリッドの互除法 (Extended Euclidean Algorithm)
Extended Euclidean algorithm

●拡張ユークリッドの互除法(非再帰版)
/**<h1>拡張ユークリッド互除法</h1>
* <p>ax + by = gcd(a, b) となる a, b の最大公約数と解 x, y を求める。</p>
* @param a : 数値1(>0)
* @param b : 数値2(>0)
* @return<b>int[]</b> : {[0]:gcd, [1]:x, [2]:y}:最大公約数(なし=1 [互いに素])と解 x, y
*/
public static final int[] extgcd(int a, int b) {
int x0 = 1, x1 = 0;
int y0 = 0, y1 = 1;

while (b != 0) {
int q = a / b;
int r = a % b;
int x2 = x0 - q * x1;
int y2 = y0 - q * y1;

a = b; b = r;
x0 = x1; x1 = x2;
y0 = y1; y1 = y2;
}

return new int[]{a, x0, y0};
}


//メインでは...
int a = 12;
int b = 21;
int[] res = extgcd(a, b);
int g = res[0];
int x = res[1];
int y = res[2];
System.out.println("g = " + g + ", x = " + x + ", y = " + y);
System.out.println(a + " * " + x + " + " + b + " * " + y + " = " + g);
int sum = a * x + b * y;
System.out.println(sum == g);

g = 3, x = 2, y = -1
12 * 2 + 21 * -1 = 3
true

 出力の意味は a = 12, b = 21 のときに、12 * 2 + 21 * -1 = 3 [ax + by = gcd(a, b)] となる解 x = 2, y = -1 が存在することを表す。実はこのような解は常に存在するので、このことを利用して解く問題などもある。

 また、最大公約数がないときは 1 となるが、このとき「互いに素」であることがわかる(お互いの共通の因子を持たない)。しばしばこの性質を利用する解法も見かけるので、覚えておいた方が良いだろう。

 もう1つ、再帰でも書いてみよう。冒頭に書いた「無理矢理参照渡しのようにするために要素が1つの配列を用いる方法」の例でもある。表記が複雑になるので、少し不便だが、C言語などからの移植する際の手法の1つとして覚えておくと役に立つこともあるだろう。

●拡張ユークリッドの互除法(再帰版)
/**<h1>拡張ユークリッド互除法</h1>
* <p>ax + by = gcd(a, b) となる a, b の最大公約数と解 x, y を求める。</p>
* @param a : 数値1(>0)
* @param b : 数値2(>0)
* @param x : 解 x (参照渡し用 new int[1] で作る)
* @param y : 解 y (参照渡し用 new int[1] で作る)
* @return<b>int</b> : 最大公約数(なし=1 [互いに素])
*/
public static final int extgcd(final int a, final int b, final int[] x, final int[] y) {
int g = a;
if (b != 0) {
g = extgcd(b, a % b, y, x);
y[0] -= (a / b) * x[0];
} else {
x[0] = 1;
y[0] = 0;
}
return g;
}


//メインでは...
int a = 12;
int b = 21;
int[] x = new int[1]; //参照渡しにするため、要素1個で作る
int[] y = new int[1]; //参照渡しにするため、要素1個で作る
int g = extgcd(a, b, x, y);
System.out.println("g = " + g + ", x = " + x[0] + ", y = " + y[0]);
System.out.println(a + " * " + x[0] + " + " + b + " * " + y[0] + " = " + g);
int sum = a * x[0] + b * y[0];
System.out.println(sum == g);

g = 3, x = 2, y = -1
12 * 2 + 21 * -1 = 3
true

 ループ版と再帰版とで実行速度を比べてみると、差はほとんどないので、どちらを使っても良いだろう。


 せっかくなので、上記の extgcd() を使って練習問題を解いてみよう。

●双六(すごろく) (参考) アリ本 P.108 [解答例は載ってない]
双六(すごろく)があります。マス目には整数が書かれています。マス目は前後に無限に続いており、
0のマス目がスタートで、1のマス目がゴールなのですが、サイコロの目には a, b, -a, -b の4つの整数しかありません。
そのため、a, b の値によってはゴールに辿り着けない場合があります。

 ┌─┬─┬─┬─┬─┬─┬─┬─┬─┐
…│-4│-3│-2│-1│ 0│ 1│ 2│ 3│ 4│…
 └─┴─┴─┴─┴─┴─┴─┴─┴─┘

4つの目をそれぞれ何回出せばゴールに辿り着けますか?
複数解が存在する場合は、どれか1つを出力しなさい。解がなければ -1 を出力しなさい。

制約
・1 <= a, b <= 109

入力
a = 4, b = 11

●拡張ユークリッド互除法での解法
int a = 4;    //入力
int b = 11; //入力

int[] res = extgcd(a, b);
int g = res[0];
int x = res[1];
int y = res[2];

if (g != 1) {
System.out.println(-1);
} else {
String ans = "" + ((x >= 0) ? x : 0);
ans += " " + ((y >= 0) ? y : 0);
ans += " " + ((x < 0) ? -x : 0);
ans += " " + ((y < 0) ? -y : 0);
System.out.println(ans); //答え
}

3 0 0 1

 答えは左から a, b, -a, -b に対応させて、右へ 4(a)×3回、左へ 11(b)×1回 進めば、1 (gcd(a, b)) のマス目(ゴール)に辿り着けることを表している。ちなみに a = 11, b = 4 と入れ替えて試してみると、答えは「0 3 1 0」となり意味は同じとなる。では逆に辿り着けない例はどうなるだろうか。例えば gcd が2となる a, b を与えれば(両方偶数など)、1には辿り着けない。全探索で見つけるまでもなく一瞬で求められるのは非常に有り難い(笑)。


(関連記事)
【Java】3つ以上の最大公約数を求める(ユークリッドの互除法②)
【Java】最大公約数・最小公倍数を求める(ユークリッドの互除法)
【Java】約数を求める
【Java】素因数分解をする


■参考になる書籍


category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  約数  練習問題 
tb: 0   cm: --

【Java】最大公約数・最小公倍数を求める(ユークリッドの互除法)  


 以前ちらりと書いたが、「エラトステネスの篩」と同じように、コンピュータが存在する以前からある「最大公約数」(Greatest Common Divisor) を求めるアルゴリズムに「ユークリッドの互除法」というものがある。最古のアルゴリズムとも言われているが、コンピュータ時代になっても健在で、簡単でしかも高速なアルゴリズムとしてもよく利用されている。


 概要は「正の整数 a, b (a >= b) について「a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる」(Wikipedia) となっているが、Wikipedia の右端にあるアニメーションを見た方がわかりやすい気がする(笑)。

 書き方もループで書いたもの再帰で書いたものをよく見かけるが、比較のためにも両方書いてみよう。

●最大公約数を求める [ユークリッドの互除法](非再帰版)
/**<h1>最大公約数を求める(Greatest Common Divisor)[ユークリッドの互除法]</h1>
* @param a : 数値1(>0)
* @param b : 数値2(>0)
* @return<b>int</b> : 最大公約数 (なし=1 [互いに素])
*/
public static final int gcd(int a, int b) {
//a > b にする(スワップ)
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}

//ユークリッドの互除法
int r = -1;
while (r != 0) {
r = a % b;
a = b;
b = r;
}

return a; //b には r=0 の値が入るため、a を返す
}


//メインでは...
int a = 1920;
int b = 1080;
int d = gcd(a, b);
System.out.println("d = " + d); //最大公約数
System.out.println(a + "/" + b + " = " + (a / d) + "/" + (b / d)); //約分に利用

d = 120
1920/1080 = 16/9

 例では 1920 と 1080 の最大公約数 d は 120 であり、それぞれを最大公約数(120)で割ると、約分と同じ意味になることを表している。1920x1080 はアスペクト比で有名なので、16 : 9 (16/9) が正しいのは検算しなくてもわかるだろう。

 関数冒頭で、a, b の大小関係を調べてスワップしているが、ユークリッドの互除法は「a, b が正の値で a >= b とするとき」となっているので、既知ならば削除しても構わない。

 また、最大公約数がないときは 1 となるが、このとき「互いに素」であることがわかる(お互いの共通の因子を持たない)。実はしばしばこの性質を利用する解法も見かけるので、覚えておいた方が良いだろう。

 もう1つ、ユークリッドの互除法は再帰の例としても挙げられるが、確かに非常に簡潔に書けるので、あまり負荷のかからない処理なら、こちらでも構わないだろう。

●最大公約数を求める [ユークリッドの互除法](再帰版)
/**<h1>最大公約数を求める(Greatest Common Divisor)[ユークリッドの互除法](再帰版)</h1>
* @param a : 数値1(>0)
* @param b : 数値2(>0)
* @return<b>int</b> : 最大公約数 (なし=1 [互いに素])
*/
public static final int gcd(final int a, final int b) {
return (b == 0) ? a : gcd(b, a % b);
}


//メインでは...
int a = 1920;
int b = 1080;
int d = (a >= b) ? gcd(a, b) : gcd(b, a); //a >= b にする
System.out.println("d = " + d); //最大公約数
System.out.println(a + "/" + b + " = " + (a / d) + "/" + (b / d)); //約分に利用

d = 120
1920/1080 = 16/9

 こちらは随分簡潔になっているが、非再帰版は a, b の大小関係はチェックしてないので、注意しよう。心配ならサンプルのようにメインコードで調べれば良い。

 また、ループ版と再帰版とで実行速度を比べてみると、やはりループ版の方がわずかに速いが、それほど差はないので、計算量の小さいものなら問題なく使えるだろう。


 上の例では gcd() を約分に利用しているが、他にも色々と応用できる。例えば「線分上の格子点の個数」を求めてみよう。

●線分上の格子点の個数 (参考) アリ本 P.107 [解答例は載ってない]
平面の2つの格子点 P1 = (x1, y1), P2 = (x2, y2) が与えられます。
線分 P1, P2 上には P1, P2 以外にいくつの格子点が存在しますか?
(格子点とは) 座標平面(or 座標空間)において,各成分が全て整数であるような点。

制約
・-109 <= x1, x2, y1, y2 <= 109

入力例
P1 = (1, 11), P2 = (5, 3)

● 線分上の格子点の個数を求める gcd() での解法
int x1 = 1, y1 = 11;    //P1
int x2 = 5, y2 = 3; //P2

int a = Math.abs(x1 - x2);
int b = Math.abs(y1 - y2);
int g = 1;

if (x1 == x2 && y1 == y2) {
//0
} else if (x1 == x2) {
g = b;
} else if (y1 == y2) {
g = a;
} else {
g = gcd(a, b);
}
System.out.println(g - 1); //答え

//以下は具体的な座標の出力
int x = x1, y = y1, dx = 0, dy = 0;
if (x1 <= x2) {
dx = (x2 - x1) / g;
dy = (y2 - y1) / g;
} else {
x = x2; y = y2;
dx = (x1 - x2) / g;
dy = (y1 - y2) / g;
}
for (int i = 1; i < g; i++) {
if (i > 1) {
System.out.print(", ");
}
System.out.print("(" + (x + i * dx) + ", " + (y + i * dy) + ")");
}
System.out.println();

3
(2, 9), (3, 7), (4, 5)

 単純に (x1, y1)-(x2, y2) の線分上でかつ整数となる点を全て調べても良いが、線分が大きくなると計算量が間に合わなくなる。その点、gcd() なら非常に軽い。gcd() は0で除算できない(P1, P2 が同じ点、または x 軸, y 軸のどちらかが同じ)ことだけ注意しよう。

- - - - - - - - - - - - - - - - - - 
●最小公倍数を求める

 ついでにもう1つ、最小公倍数(Least Common Multiple)も求めてみよう。

 Wikipedia にも書いてあるように「正の整数a, bに対して、最大公約数gcd(a, b)と最小公倍数lcm(a, b)との間には、gcd(a, b)×lcm(a, b) = ab という関係がある」となっているので、「gcd()」ができていれば、非常に簡単に作れる。

●最小公倍数を求める
/**<h1>最小公倍数を求める(Least Common Multiple)</h1>
* @param a : 数値1(>0)
* @param b : 数値2(>0)
* @return<b>int</b> : 最小公倍数
*/
public static final int lcm(final int a, final int b) {
return a * b / gcd(a, b);
}


//メインでは...
int h = 16;
int v = 9;
int m = lcm(h, v);
System.out.println("m = " + m);

m = 144

 こちらも「gcd()」のおかげで随分と簡潔だ。内容は式を変形しただけのものに過ぎないので、説明はいらないだろう。

 「ユークリッド互除法」には「ax + by = gcd(a, b) となる a, b の最大公約数を求める」という「拡張ユークリッド互除法」というものもある。解となる整数 x, y の組を見つけることができるものなので、数学的な問題には役に立つことがあるかも知れない。実装は gcd() とそれほど変わらないので。覚えておいても損はないだろう。


■約分・最大公約数・最小公倍数 計算機
ユークリッドの互除法で約分・最大公約数(gcd)・最小公倍数(lcm)を求める(JavaScript版)
元の分数を入力:
/



約分された分数:
/

最大公約数(gcd):
最小公倍数(lcm):


(関連記事)
【Java】3つ以上の最大公約数を求める(ユークリッドの互除法②)
【Java】拡張ユークリッドの互除法
【Java】約数を求める
【Java】素因数分解をする
【Java】素数判定①(試し割り法)


■参考になる書籍


category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  約数  練習問題  アルゴリズム 
tb: 0   cm: --

【Java】約数を求める  


 ついてなので、「素因数分解」や「素数の試し割り」とあまり変わらない方法で、「約数」も求めてみよう。

 約数は「整数 n の約数あるいは因数、因子とは、n を割り切る整数の総称である」(Wikipedia)となっているが、「素因数分解の要素の掛けあわせパターン」とも考えても良いし、「約数が奇数個のときは平方数になる」などという性質があると覚えておくと、たまに役立つことがあるかも知れない。

●約数のリストを作る(掛けあわせの順)
import java.util.ArrayList;
import java.util.List;

/**<h1>約数のリストを作る</h1>
* <p>先頭の要素は 1 で、例えば、n = 12 のとき、1, 12, 2, 6, 3, 4 のようになる(1×12, 2×6, 3×4)。</p>
* @param n : 約数を作る値
* @return<b>List<Integer></b> : 約数のリスト
*/
public static final List<Integer> divisor(final int n) {
final List<Integer> list = new ArrayList<Integer>();

for (int i = 1; i * i <= n; i++) { //√n
if (n % i == 0) {
list.add(i); //a x b
if (i != n / i) {
list.add(n / i); //b x a (逆向き)
}
}
}
return list;
}


//メインでは...
int n = 12;
List<Integer> div = divisor(n);
for (int v : div) {
System.out.print(v + " ");
}

1 12 2 6 3 4

 要素の順番は「掛けあわせのペアの順」になっているので、偶数個のとき、先頭から2つずつ取り出して乗算すれば元の値になる。
 つまり、

 n = 12 のとき、
 1×12, 2×6, 3×4(4×3, 6×2, 12×1)

となることを表している。ちなみに n が平方数の場合、例えば、

 n = 64 のとき、
 1 64 2 32 4 16 8
  ↓
 1×64, 2×32, 4×16, 8×8(16×4, 32×2, 64×1)

となり、8 が 8×8 と被るので奇数個になることもわかる。

 また、約数の要素を昇順に並び替えたい場合はソートしても良いが、上記のコードを少し改造して、要素を挿入する位置を常にリストの中心にすれば、ソートしたものと同じになる。以下に例を挙げよう。

●約数のリストを作る(昇順)
import java.util.ArrayList;
import java.util.List;

/**<h1>約数のリストを作る(昇順)</h1>
* <p>先頭の要素は 1 で、要素は昇順になる。例えば、n = 12 のとき、1, 2, 3, 4, 6, 12 のようになる。</p>
* @param n : 約数を作る値
* @return<b>List<Integer></b> : 約数のリスト
*/
public static final List<Integer> divisor(final int n) {
final List<Integer> list = new ArrayList<Integer>();

int p = 0; //挿入位置
for (int i = 1; i * i <= n; i++) { //√n
if (n % i == 0) {
list.add(p++, i); //常に中心に入れていく
if (i != n / i) {
list.add(p, n / i); //常に中心に入れていく
}
}
}
return list;
}


//メインでは...
int n = 12;
List<Integer> div = divisor(n);
for (int v : div) {
System.out.print(v + " ");
}

1 2 3 4 6 12

 戻値が「掛けあわせ順」か「昇順」が良いかは、用途に応じて使い分ける方が良いだろう。この上記の2つの例の場合、単純に要素を追加している「掛けあわせ順」の方がわずかに速いが、それほど大きな差はない。

 実際に数学関連の問題を解くときや、全探索で計算量が間に合わないときなどには、その答えをダンプして、その値を「素因数分解」や「約数」などを利用して分析してみると一定の法則が見えたりすることがある。例えば平方数がある一定の差分(2乗倍など)で出ていれば、二分探索のような手法で解けることもある。数値分析の手軽な方法として、この手のライブラリはいくつか作っておくと、色々役立つこともあるだろう。


(関連記事)
【Java】最大公約数・最小公倍数を求める(ユークリッドの互除法)
【Java】拡張ユークリッドの互除法
【Java】素因数分解をする
【Java】素数判定①(試し割り法)


■参考になる書籍


category: Java

thread: プログラミング

janre: コンピュータ

tag: 約数  算術関数 
tb: 0   cm: --


プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop