ヽ|∵|ゝ(Fantom) の 開発blog? ホーム »アルゴリズム
このページの記事一覧

【Java】数値の桁数を調べる(べき乗の桁数・べき乗のべき乗の桁を調べる)  


 数値の桁数を知りたいシーンはわりと良くあるもので、調べてみると「10で割っていく方法」や「文字列に変換する方法」「対数を使う方法」「配列にあらかじめ各桁の最大(9999のような)を入れておいて比較する方法」などあるようだが、実行速度は言語によってまちまちのようなので、簡単なアルゴリズムを色々知っておいても損はないだろうと試してみた。




■10で割っていく方法

 まずは一番オーソドックスな方法(?)でやってみよう。これは以前書いた「基数変換のアルゴリズム」と同じと言っても良い。基数変換では具体的な桁の値をリストで返しているが、それをカウントに変えるだけだ。故に基数変換の戻値のリストのサイズ(List.size())でも同じとなる。まずは基数変換のコードの一部を抜き出して少しばかり改造してみよう。

●10で割って桁数をカウントする
/**<h1>整数の桁数を求める</h1>
* <p>0 となるまで、10 で割り続ける方法。</p>
* @param value : 調べる値
* @return<b>int</b> : 桁数 (負の値は '-' を除いた桁数)
*/
public static final int length(long value) {
int cnt = 0;
do {
cnt++;
value /= 10;
} while (value != 0);
return cnt;
}


//メインでは...
int n = 1234; //4
//int n = -4321; //4
//int n = 0; //1
System.out.println(length(n));

4

 負の値のとき、マイナス記号 '-' を除外してカウントしているが、負の割り算は言語によって仕様が違うので、他の言語に移植するときは注意しよう(Ruby などは上手くいかない)。心配なら関数のはじめに絶対値(Math.abs())などで正の値にしておくと良い(Java では無くても良い)。調べる値が 0 のとき、1 桁としたいので、すぐにインクリメントしているが、while に書きなおしたいときは、はじめからカウントを 1 にしておけば良いだろう。上記の例は基数変換のコードをもとにしているが、以下のように while でシンプルに書くこともできる。

●上記の例を while に書きなおしたもの
/**<h1>整数の桁数を求める</h1>
* <p>0 となるまで、10 で割り続ける方法。</p>
* @param value : 調べる値
* @return<b>int</b> : 桁数 (負の値は '-' を除いた桁数)
*/
public static final int length(long value) {
int cnt = 1; //0 にも対応
while ((value /= 10) != 0) {
cnt++;
}
return cnt;
}


//メインでは...
int n = 1234; //4
//int n = -4321; //4
//int n = 0; //1
System.out.println(length(n));

4

 内容は全く同じで、実行速度も変わらないので、好みの書き方で選べば良い。




■文字列に変換する方法

 「10で割る方法」と同じようによく使われるのは、「文字列に変換する方法」だ。ただし、Java の場合は文字列変換は負荷が高いので、実行速度は遅くなる。しかし、Ruby をはじめ、PHP や Perl のようなスクリプト言語は文字列変換のスピードは非常に速いので、むしろ「10で割る方法」の方が遅いらしい。参考までに色々な言語でやっているページを載せておくが、私が実際に Ruby で試したところ、「loop do~break if~」の代わりに「while」に書きなおしたら、ここまでの差は出なかった(それでも文字列変換の方がわずかに速い)。他の言語から移植するときのためにも、この手のやり方には慣れておいた方が良いだろう。

(参考)
整数の桁数を求める方法

●文字列に変換し、長さを取得する
//int n = 1234;     //4
int n = -4321; //4
//int n = 0; //1

System.out.println(String.valueOf(Math.abs(n)).length());

4

 なお、値が正の数だけとわかっていれば、Math.abs() は必要ない。




■べき乗(xk)の桁数を調べる

 次に、普通に計算したらオーバーフローするような「べき乗の値の桁を調べる方法」をやってみよう。それは(常用)対数関数Math.log10())を使う方法だ。ちなみにこの方法で int や long の桁数を調べることもできるが、log() は負荷が高い関数なので、「10で割る方法」の方がよほど速い。なので、整数型では求められない値など、使い分けが必要になるだろう。

 まずは簡単に対数関数の使い方をおさらいしてみよう。といっても高校の数学の教科書そのままの内容だ(笑)。また対数関数指数関数は裏返しの関数なので、ついでにおさらいしておくとなお良い。以下の問題の解き方を丸暗記してしまえば、わりと簡単に理解できるハズだ。

【問】230は何桁の数字か。log102 = 0.3010 を用いて調べよ。

【解】
log102 = 0.3010 だから、2 = 100.3010  [指数への変換:logap = q ⇔ p = aq]
230 = (100.3010)30
  = 100.3010×30  [指数法則:(ap)q = ap×q]
  = 109.03
よって、109 < 230 < 1010
したがって、230 は 10桁の数字である。  [109 = 1,000,000,000 (頭 1 と 0 が 9 個で 10桁)]


 さて、上の解法を理解したら、いよいよ本題のべき乗(xk)の桁数を求めてみよう。例で使ってるのは底が10である常用対数の使い方であるが、それは言い換えればある数値 n を 10q に置き換える関数であり、桁を表していると言える。つまり、ここでは具体的な値ではなく、桁数を求めたいわけだから、10 の指数部分 q を求めれば良いわけである。

 上の例を用いれば桁数は 230 = 109.03 の 9.03 部分のことで、これは log102×30 であり、この値の小数部分を切り捨て、1 を足したものである(頭 1 と 0 が 9 個で 10桁)。この 2 を x、30乗を k と置けば、以下のようになっているとわかるだろう。

230 = 100.3010×30 = 10log102×30

(2 を x、30乗を k と置くと)
xk = 10log10x × k  … ① (←以降、この式を公式のように扱う)

(桁数は指数部分のことだから)
桁数 = floor(log10x × k) + 1

●べき乗(xk)の桁数を log10() により求める
/**<h1>x<sup>n</sup> の桁数を求める</h1>
* <p>log10() により求める。底が負のときは NaN となるので注意。</p>
* @param x : 底 (> 0)
* @param k : べき指数 (>= 0)
* @return<b>double</b> : 桁数
*/
public static final double powLength(final double x, final double k) {
return Math.floor(Math.log10(x) * k) + 1;
}


//メインでは...
int x = 2, k = 30; //10.0
//int x = 123456789, k = 99999; //809144.0
System.out.println(powLength(x, k));

10.0

 log() の引数は負の値だと NaN が返される注意しよう。必要ならエラーを投げるのも良い。引数の値によっては非常に大きな桁数になるので double のまま返しているが、値の範囲がわかっていれば整数型にキャストするのも良いだろう。Java の場合、long は 19桁の値、double は指数表現を含めて 309桁の値まで表せるが、べき乗はあっという間にオーバーフロー(Infinity)することがあるので、使う際にはあらかじめ確認しておいた方が良いだろう。




■べき乗のべき乗(xyz)の桁数を求める

 次に更にべき乗をかけた「べき乗のべき乗」の桁を調べてみよう。考え方は「べき乗(xk)の桁数を調べる」をそのままで、少しばかり拡張したものになる。その式を考えてみよう。

(xyz の指数部分 yz を log10 を使って変換すると [①を参照])
yz = 10log10y × z

(xyz の指数部分 yz を k と置き、同じように変換すると [①を参照])
xyz = xk = 10log10x × k

(k を元に戻すと)
xyz = xk = 10log10x × 10log10y × z

(桁数は指数部分のことだから)
桁数 = floor(log10x × 10log10y × z) + 1

●べき乗のべき乗(xyz)の桁数を log10() により求める
/**<h1>x<sup>y<sup>z</sup></sup> (べき乗のべき乗)の桁数を求める</h1>
* <p>log10() により求める。底が負のときは NaN となるので注意。</p>
* @param x : 底 (> 0)
* @param y : べき指数1 (>= 0)
* @param z : べき指数2 (>= 0)
* @return<b>double</b> : 桁数 (オーバーフロー: Infinity に注意)
*/
public static final double powpowLength(final double x, final double y, final double z) {
final double p = Math.log10(y) * z; //y^z
final double q = Math.log10(x); //x^p
return Math.floor(q * Math.pow(10, p)) + 1;
}


//メインでは...
int x = 2, y = 3, z = 5; //74.0
//int x = 5, y = 6, z = 7; //195667.0
System.out.println(powpowLength(x, y, z));

74.0




■2つのべき乗のべき乗(xyz, abc)の大きさを比較する

 ここでは2つのべき乗のべき乗(xyz, abc)の大小関係を比較することを考えてみよう。もちろん前述した「べき乗のべき乗(xyz)の桁数を求める」で比較しても構わないが、なぜわざわざ比較だけをピックアップしたかというと、引数によっては「べき乗のべき乗」では桁数が非常に大きくなりオーバーフロー(Infinity)しかねないので、対数のまま利用した方が良いからだ。もう一度「べき乗のべき乗(xyz)の桁数を求める」のコードを見てみよう。桁数が大きくなる原因に「Math.pow(10, p)」という部分がある。ここを変形してオーバーフローを防ぐ方法を考えてみよう。

(桁数を表す指数部分を抜き出すと)
yz = log10x × 10log10y × z

log10x = m と置き、今までと同じように[①を参照] 10q に変形すると、m = 10log10m [m1 = 10log10m × 1

(m を元に戻すと)
10log10m = 10log10(log10x) (= log10x)

(yzの式に代入して)
yz = 10log10(log10x) × 10log10y × z = 10log10(log10x) + log10y × z [指数法則:ap×aq = ap+q]

(xyzの式に戻すと)
xyz = 1010log10(log10x) + zlog10y

(つまり、一番上の指数だけを比較すれば大小関係がわかる)
log10(log10x) + zlog10y

●べき乗のべき乗(xyz)の比較をする
/**<h1>x<sup>y<sup>z</sup></sup> (べき乗のべき乗) の log10() を返す</h1>
* <p>この値で比較すれば、大小関係がわかる。底が負のときは NaN となるので注意。</p>
* @param x : 底 (> 0)
* @param y : べき指数1 (>= 0)
* @param z : べき指数2 (>= 0)
* @return<b>double</b> : 底を10<sup>10</sup>に合わせた log10() を返す
*/
public static final double powpowLog10(final double x, final double y, final double z) {
final double p = Math.log10(y) * z; //y^z
final double q = Math.log10(Math.log10(x)); //10^q = log10 x
return p + q;
}

/**<h1>x<sup>y<sup>z</sup></sup> (べき乗のべき乗) 同士の大小の比較</h1>
* <p>比較の関係値を返す(-1, 0, 1 のみ)。差分ではない。</p>
* @param x1 : 底 a (> 0)
* @param y1 : べき指数1 a (>= 0)
* @param z1 : べき指数2 a (>= 0)
* @param x2 : 底 b (> 0)
* @param y2 : べき指数1 b (>= 0)
* @param z2 : べき指数2 b (>= 0)
* @return<b>int</b> : -1 : a < b / 1 : a > b / 0 : a == b
*/
public static final int powpowCompare(final double x1, final double y1, final double z1,
final double x2, final double y2, final double z2) {

final double a = powpowLog10(x1, y1, z1);
final double b = powpowLog10(x2, y2, z2);
if (a < b) {
return -1;
} else if (a > b) {
return 1;
} else {
return 0;
}
}


//メインでは...
int x1 = 123456, y1 = 9876543, z1 = 24356891; //Infinity
int x2 = 333333, y2 = 5555555, z2 = 22222222; //Infinity
System.out.println(powpowLength(x1, y1, z1));
System.out.println(powpowLog10(x1, y1, z1));
System.out.println(powpowLength(x2, y2, z2));
System.out.println(powpowLog10(x2, y2, z2));
System.out.println(powpowCompare(x1, y1, z1, x2, y2, z2));

Infinity
1.7036683127845693E8
Infinity
1.4988283149816477E8
1

 この方法で行けば、309桁(Double.MAX_VALUE = 1.7976931348623157E308) までは比較できる

 また、比較だけなら、Math.log10() の代わりに Math.log() を使っても良いが、値が大きくなる可能性があるので、Math.log10() を使った方が無難かも知れない(実行速度も変わらない)。もちろん引数が負の値のときは NaN となるので注意しよう。戻値は比較の関係値を返す -1, 0, 1 のみにしているが、必要なら (a - b) の差分を返すように改造しても良いだろう(ただし、型に注意。比較関数は大抵 int になっているので)。

 ちなみに同じように「べき乗のべき乗のべき乗」も考えられるが、log() を3回以上入れ子にすると負の値となってしまうので、上手く行かないようだ。式としては以下のようになる。

wxyz = 101010log10(log10(log10w)) + log10(log10x) + zlog10y

(一番上の指数だけを抜き出せば)
log10(log10(log10w)) + log10(log10x) + zlog10y

 式は無理矢理なので、正しい書き方とかは勘弁して欲しい(笑)。級数(数列の和)っぽく書けばもっとカッコイイのかも知れないが、この書き方なら高校数学の範疇なので理解できるハズだ(無理矢理感は別として)。でもまぁ、log() でもこれ以上は無理そうなので、他の方法を研究してみるのも面白いだろう。




■任意精度を使う

 最後に任意精度実数を使って桁を調べてみよう。考え方としては「文字列に変換する方法」と同じと思って良い。具体的な値を返すので、桁が大きくなるほど重くなるが、検算したいときには役に立つこともあるだろう(といっても100万桁ぐらいが限界でそれ以上はフリーズしたようになる)。なお、BigInteger を用いても構わないが、桁を調べるだけなら、文字列に変換する(toString())する必要はないので、整数部分の桁を返す BigDecimal.precision() を使った方が速い

●任意精度実数で具体的な値と桁数を調べる
int x = 2, y = 3, z = 5;
int a = (int)Math.pow(y, z);
BigDecimal b = new BigDecimal(x).pow(a);
System.out.println(b.toString());
System.out.println(b.precision());
System.out.println(powpowLength(x, y, z));

14134776518227074636666380005943348126619871175004951664972849610340958208
74
74.0

 上の例はべき乗のべき乗(235)と同じものだ。ただし、BigDecimal.pow() の引数は int 型にしか対応していない(と言っても、long でできたとして重すぎてフリーズしたようになると思うが)。具体的な値を知りたければ文字列化(toString())すれば良いが、桁が大きいときは負荷が高いので、あらかじめ値の範囲を調べた上で使った方が良いだろう。オンラインジャッジでの問題などでは、任意精度ではほとんどの場合タイムアウトすると思うので、桁数だけなら、前述の「powLength()」(べき乗の桁数)や「powpowLength()」(べき乗のべき乗の桁数)を使った方が速い。


(関連記事)
【Java】n進数変換(基数変換)・桁の分割をする
【Java】べき乗計算を高速化する(繰り返し二乗法)
【Java】任意精度整数(多倍長整数)で演算する


■参考になる書籍


スポンサーサイト

category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  べき乗  アルゴリズム 
tb: 0   cm: --

【Java】n進数変換(基数変換)・桁の分割をする  


 今回のテーマは「10進数 ←→ n進数」の相互変換(基数変換)のアルゴリズムなのだが、標準ライブラリにもあるので、確認用のためにも、まずはおさらいしてみよう。もちろん不要なら「基数変換のアルゴリズム」まで読み飛ばしても良い。




■標準ライブラリでの基数変換

●10進数→n進数変換(標準ライブラリ)
int n;
n = 46;
String bin = Integer.toString(n, 2); //10進数→2進数
//String bin = Integer.toBinaryString(n); //10進数→2進数(※同じ)
System.out.println(n + " -> " + bin + " (2)");

n = 51;
String tri = Integer.toString(n, 3); //10進数→3進数
System.out.println(n + " -> " + tri + " (3)");

n = 16;
String oct = Integer.toString(n, 8); //10進数→8進数
//String oct = Integer.toOctalString(n); //10進数→8進数(※同じ)
System.out.println(n + " -> " + oct + " (8)");

n = 30;
String hex = Integer.toString(n, 16); //10進数→16進数
//String hex = Integer.toHexString(n); //10進数→16進数(※同じ)
System.out.println(n + " -> " + hex + " (16)");

46 -> 101110 (2)
51 -> 1220 (3)
16 -> 20 (8)
30 -> 1e (16)

 標準ライブラリでは、例のように、

 Integer.toString(10進数, 基数)

で良い。long を変換したい場合は、Long.toString() になる。内容的には数値から文字列への変換となる。

 2進数、8進数、16進数に関しては以下の専用の関数もある、

 Integer.toBinaryString(10進数) 10進数→2進数
 Integer.toOctalString(10進数) 10進数→8進数
 Integer.toHexString(10進数) 10進数→16進数

 基数がわかっているなら、専用関数の方が実行速度は速い。

●n進数→10進数変換(標準ライブラリ)
int v;
String bin = "101110";
v = Integer.parseInt(bin, 2); //2進数→10進数
System.out.println(bin + " (2) -> " + v);

String tri = "1220";
v = Integer.parseInt(tri, 3); //3進数→10進数
System.out.println(tri + " (3) -> " + v);

String oct = "20";
v = Integer.parseInt(oct, 8); //8進数→10進数
System.out.println(oct + " (8) -> " + v);

String hex = "1e";
v = Integer.parseInt(hex, 16); //16進数→10進数
System.out.println(hex + " (16) -> " + v);

101110 (2) -> 46
1220 (3) -> 51
20 (8) -> 16
1e (16) -> 30

 標準ライブラリでは、例のように、

 Integer.parseInt(n進数文字列, 基数)

で良い。long に変換したい場合は、Long.parseLong() になる。内容的には文字列から数値への変換となる。

 1つだけ気をつけないといけないのは、parseInt() では負の値の表現となる文字列のパースはできない(エラーとなる)。その場合は parseUnsignedInt() を使えば負の値でパースできる。
 
String s = "11111111111111111111111111111111";  //2進数は31ビット目(最下位を0とするとき)が1のとき負の値となる
//int v = Integer.parseInt(s, 2); //エラー(NumberFormatException)
int v = Integer.parseUnsignedInt(s, 2); //-1




■コード上での n進数表記

 ちなみに、変換ではないのだが、ソースコードに直接書きたい場合は、以下のように表記できる。

●n進数表現
int b = 0b101110;    //2進数表現
System.out.println("b = " + b); //10進数

int o = 020; //8進数表現
System.out.println("o = " + o); //10進数

int h = 0x1e; //16進数表現
System.out.println("h = " + h); //10進数

b = 46
o = 16
h = 30



■基本的な基数変換のアルゴリズム

 では、ここからは本題の基数変換のアルゴリズムを考えてみよう。

●各桁の分解

 まずは、10進数の数はどのような構成でできているかを見てみよう。10進数の各桁を分解して考えると、


のように、

 各桁の数×基数k-1+・・・+各桁の数×基数1+各桁の数×基数0 (1~k 桁のとき)

となっていることがわかる。つまりは、10進数というのは「桁ごとの数字に基数[=10]を掛けたもので構成され、それらを加算したもの」でできている。桁を表すには最下位を「100(= 1)」とし、桁が上がるごとに、「×101(= 10)」「×102(= 100)」「×103(= 1000)」・・・としていけば良い。それらに各桁の数を掛けて合計すれば、1つの10進数の値となる。

 そしてこれは他の基数(n進数)でも同じで、例えば、2進数や3進数を分解してみると、



のようになる。

 これらのことをそのままコーディングすれば、「10進数 ←→ n進数」の相互変換は簡単にできることがわかる。


 
■10進数 → n進数 に変換する(基数で分解する)

 「n進数に変換」とは上記の例を見れば、「値を0になるまで基数で割り続け、余りを並べる」ことと同じである。それをそのまま作ってみよう。

●基数変換したリストを作る(各桁を分解)
import java.util.ArrayList;
import java.util.List;

/**<h1>基数変換したリストを作る(各桁を分解)</h1>
* <p>各桁の値は、下位から上位に向かって入る。</p>
* @param value : 元の数値 (10進数)
* @param radix : 変換する基数 (>= 2)
* @return<b>List<Integer></b> : 基数で割った余りのリスト
*/
public static final List<Integer> baseRemainder(int value, final int radix) {
final List<Integer> list = new ArrayList<Integer>();
int m;
do {
m = value % radix;
value /= radix;
list.add(m);
} while (value > 0);

return list;
}


//メインでは...
int n = 51;
List<Integer> list = baseRemainder(n, 3);
for (int k : list) {
System.out.print(k + " ");
}

0 2 2 1

 これは「10進数の 51 を、3進数の 1220 に変換した」ことになる。戻値のリストの要素は「下位→上位」へ向かって各桁の値が入っていることに注意しよう。慣れていないと何となく数字の各桁は左から右へ上位→下位と考えてしまいがちだが、配列などは下位→上位へインデクスは増えていくわけで、コンピュータにとってはむしろ自然な順である。任意精度整数(多倍長整数)や n進数、ビット列などを扱うような実装をしてみれば、わりと普通に使うものだったりする。頭のなかで逆向きに読めば良い(笑)。あとはこのリストを文字列にするなり、逆順に表示するなりすれば良いのである。しかし、n進数で計算などするなら、文字列に直さないでこのまま計算する方がもちろん速い

 そしてまた、基数を変換しないでそのまま使うなら、これは各桁の分解と同じことになる。例えば普通に基数を10進数にすると、

int n = 1234;
List<Integer> list = baseRemainder(n, 10);
for (int k : list) {
System.out.print(k + " ");
}

4 3 2 1

のように「下位→上位」に向かって、各桁が分解されていることがわかる。もし、どうしても桁を「上位→下位」の順位にしたければ、Collecctions.reverse() を使って反転する手もあるが、baseRemainder() の要素追加部分「list.add(m)」を「list.add(0, m)」のように修正し、常に先頭から挿入していけば良い。ただし、10進数に変換したい場合は桁を逆向きにパースしなくてはいけなくなるため、コードが冗長となり、変換を繰り返す際には実行速度の面でも劣る。「上位→下位」へ修正したものは別の関数にして使い分けた方が利口だろう。


 
■n進数 → 10進数 に変換する

 今度は「n進数を10進数に変換」してみよう。これは上記の例を見てもわかるように、これまでの桁の分解とは逆の操作になる。つまりは「各桁の値を基数のべき乗で掛けて、それらを合計する」ことで得られることがわかる。それをやってみよう。

import java.util.ArrayList;
import java.util.List;

/**<h1>各桁のリスト(n進数)を10進数に変換する</h1>
* <p>要素(各桁の値)は、下位から上位に向かって入っているものを使う。</p>
* @param list : 各桁のリスト
* @param radix : リストの基数
* @return<b>int</b> : 10進数
*/
public static final int digitsToInt(final List<Integer> list, final int radix) {
int sum = 0;
int x = 1;
final int len = list.size();
for (int i = 0; i < len; i++) {
sum += list.get(i) * x;
x *= radix;
}
return sum;
}


//メインでは...
int b = 0b101110; //2進数表現
List<Integer> list = baseRemainder(b, 2);

System.out.print("list = ");
for (int k : list) {
System.out.print(k + " ");
}
System.out.println();

int v = digitsToInt(list, 2);
System.out.println("v = " + v);

list = 0 1 1 1 0 1
v = 46

 この例では、10進数の 46 (=2進数表現:0b101110)を一旦「baseRemainder()」 で 2進数の桁に分解し、それを「digitsToInt()」で 10進数に戻す操作をしている。ただのサンプルなので無駄は大目に見て欲しい(笑)。

 リストの要素取得のループに for を用いているが、少し冗長と感じるようなら、以下のように、foreach(拡張for)に書き換えても良いだろう。

for (int v : list) {
sum += v * x;
x *= radix;
}

 実のところを言うと、オブジェクトの foreach は、その度に Iterator が生成されているのだが、このくらいのサンプルだと違いは出ないので、どちらでも構わない。しかし例えば、GC(ガベージコレクタ)が動きまくると困るようなものなら(リアルタイムなアクションゲームとか、延々とループするものとか)、オブジェクトの foreach を避けるのも1つの手かも知れない。


 単純な基数変換なら、標準ライブラリを使った方が確実だろう。ただし、標準ライブラリは基本的に数値←→文字列の変換となるため、変換を繰り返す場合は無駄が多く、実行速度は遅くなる。また、例えば「平衡三進法」や「n進数グレイコード」などを扱うなら、自分で実装した方が応用が効く。文字列に直さないで良いのなら、「baseRemainde()」や「digitsToInt()」を使って数値のままで処理した方がずっと速い。「桁の分解」として利用する分にも非常に幅広く使える。


(関連記事)
【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】式を逆ポーランド記法(後置記法)で計算する  


 今度は前回「逆ポーランド記法(後置記法)への変換」で変換された文字列を実際に計算して数値にする関数を作ろう。

 といってもコードは非常にシンプルなので驚くかも知れない。これが逆ポーランド記法がコンピュータと相性が良いと言われる所以かも知れない。ただひたすらスタックからオペランドと演算子を取り出し、その結果を再びスタックに積むという動作を繰り返すだけだ。

●逆ポーランド記法(Reverse Polish Notation)[=後置記法:postfix notation]を計算する
import java.util.ArrayDeque;
import java.util.Deque;

/**<h1>逆ポーランド記法(Reverse Polish Notation)[=後置記法:postfix notation]を計算する</h1>
* <p>スペースで区切った "10 20 30 * +" のような形式。連続した空白は1つ分の空白として処理される。
* <br>四則演算(+, -, *, /)と括弧のみ。</p>
* @param rpn : 逆ポーランド記法での計算式
* @return<b>int</b> : 計算された値
*/
public static final int parseRPN(final String rpn) {
final Deque<Integer> stack = new ArrayDeque<Integer>();

String s = rpn.replaceAll("\\s+", " "); //連続した空白文字をスペース1つ分に置き換える
final String[] arr = s.trim().split(" ");

for (String e : arr) {
if ('0' <= e.charAt(0) && e.charAt(0) <= '9') { //数字
stack.push(Integer.parseInt(e));
} else {
int a = stack.pop();
int b = stack.pop();
if (e.equals("*")) {
stack.push(b * a);
} else if (e.equals("/")) {
stack.push(b / a); //div/0 に注意
} else if (e.equals("+")) {
stack.push(b + a);
} else if (e.equals("-")) {
stack.push(b - a);
}
}
}

return stack.pop();
}


//メインでは...
String rpn = "10 20 + 30 40 - * 50 2 / +";
System.out.println(parseRPN(rpn));

-275

 注意点は前回と同じなので「式を逆ポーランド記法(後置記法)変換する」の記事を参照して欲しい。

 計算される値はとりあえず int 型になっているので、long で算出したいなら、型を修正するのも良いだろう。ゼロ除算(エラー)や剰余などは付けてないので、必要あれば追加しても良いだろう。特に負の除算や剰余に関しては、言語によって仕様が違うので、実装前に予めパースする式の符号などを確認しておく必要がある。以下に参考ページも載せておこう。参考は「負の剰余」がテーマになっているが、商と剰余は2つで1セットのようなものなので、どちらも確認しておいた方が良いだろう。

(参考)
負数の剰余を計算してはならない
こんなプログラムはいやだ: 負の剰余
負の剰余

 また、前回の「逆ポーランド記法への変換」と今回の「逆ポーランド記法を計算」の両方を同時に行うと、簡単な数式をパースして計算する関数にもなる。これは簡易的な eval() 関数やインタプリタなどにも使える。実は元々はそのために作ったものだったりする(笑)。コードを見てもらえばわかると思うが、本当にそのまま2つの関数を混ぜあわせただけだ。

●数式をパースして計算する
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

//※rpnRank は前回の Map をそのまま利用なので割愛。

/**<h1>数式をパースして計算する</h1>
* <p>逆ポーランド法で計算する。使える演算子は四則演算と括弧のみ。
* <br>スペースを含まない "(10+20)*30-(40+50)/2" のような式。空白文字は全て除去される。</p>
* @param expression : 数式の文字列
* @return<b>int</b> : 計算値
*/
public static final int parseExpression(final String expression) {
final Deque<Character> stack = new ArrayDeque<Character>();
final Deque<Integer> val = new ArrayDeque<Integer>();

String s = expression.replaceAll("\\s+", ""); //空白文字を取り除く
s = "(" + s + ")"; //末尾に")"を付けることで、最後にスタックを吐き出させる
final int len = s.length();

String tmp = "";
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
if ('0' <= c && c <= '9') {
tmp += c; //数字1文字ずつのため
} else {
if (!tmp.equals("")) {
val.push(Integer.parseInt(tmp));
tmp = "";
}

while (!stack.isEmpty() && rpnRank.get(stack.peek()) >= rpnRank.get(c) && stack.peek() != '(') {
char e = stack.pop();
int a = val.pop();
int b = val.pop();
if (e == '*') {
val.push(b * a);
} else if (e == '/') {
val.push(b / a); //div/0 に注意
} else if (e == '+') {
val.push(b + a);
} else if (e == '-') {
val.push(b - a);
}
}
if (c == ')') {
stack.pop(); //'('
} else {
stack.push(c);
}
}
}

return val.pop();
}


//メインでは...
String expr = "(10+20)*(30-40)+50/2";
System.out.println(parseExpression(expr));

-275

 解説は同じものなので特に必要はないだろう。

 せっかくなので、この関数を使って練習問題を解いてみよう。問題は「プログラマ脳を鍛える数学パズル」から抜粋させて頂いた。この本では主に Ruby, JavaScript, C で解答ソースが書かれているが、アルゴリズムの本質というものは言語とは特に関係ないので(考え方の方法なので)、理解してしまえば色々応用できる。今回は Ruby ソースを Java に移植したものと考えても良いだろう。

●Q42 1つの数字で作る 1234 (IQ:100 目標時間:30分) ★★★
1つの数字だけで、四則演算によってある数を作ることを考えます。
例えば「1000」を作るとき、「1」だけを7個使って「1111-111」で表現できます。
「8」だけなら8個使って「8+8+8+88+888」、「9」だけであれば5個使って「9÷9÷999」で1000になります。
使用できるのは加減乗除だけとし、括弧は使用不可とします。また「÷」は整数の商のみとします(端数切捨て)。

「1234」を1つの数字だけで、できるだけ少ない個数で表現するとき、最も少ない個数で表現できる数字を求め、
その式をすべて答えて下さい。

●上記の parseExpression() を使った Java での解法
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Q42 {
public static void main(String[] args) throws Exception {
new Q42();
}

public Q42() throws Exception {
// n = 1000; //9/9+999, 999+9/9
n = 1234; //99999/9/9
// n = 4321; //6/6+66*66-6*6, 6/6-6*6+66*66, 66*66+6/6-6*6, 66*66-6*6+6/6
// n = 2016; //9+9+999+999, 9+999+9+999, 9+999+999+9, 999+9+9+999, 999+9+999+9, 999+999+9+9

solve();
}

static final String[] op = {"+", "-", "*", "/", ""};
int n; //作る数
boolean found = false;

void solve() {
int len = 1; //使用する桁数
while (!found) {
for (int i = 1; i <= 9; i++) {
check(len, String.valueOf(i), i);
}
len++;
}
}

//remain:桁残り, expr:ここまでの式, num:使用する数字
void check(int remain, String expr, int num) {
if (remain == 0) {
if (parseExpression(expr) == n) { //※上記の関数を使う
System.out.println(expr);
found = true;
}
} else {
for (String o : op) { //演算子 or ""
check(remain - 1, expr + o + String.valueOf(num), num);
}
}
}

//※parseExpression() は割愛(上記のものを使う)
}

99999/9/9

 paiza.io(オンラインIDE)で試してみると、問題の「1234」の場合、約 500ms くらいなので、ギリギリといったところか(笑)。「4321」や「2016」のように答えが多いものは 1s を超えるので、オンラインジャッジでは少しマズイ(1つだけで良いのなら、探索を中断すれば問題ない)。

 ちなみに「ScriptEngine」で外部言語として eval() を使うには以下のようなコードになる。

●「ScriptEngine」で JavaScript の eval() を使って数式を計算する
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;

public class Main {
public static void main(String[] args) throws Exception {
new Main();
}

public Main() throws Exception {
ScriptEngineManager manager = new ScriptEngineManager();
ScriptEngine engine = manager.getEngineByName("JavaScript");

String expr = "(10+20)*(30-40)+50/2";
System.out.println(engine.eval(expr));;
}
}

-275

 ただし、非常に重いので(数式2つ以上で 1s 超える(paiza.io))全探索で利用するのは難しいだろう。

 また、この「parseExpression()」を使えば、「Q02 数列の四則演算」の問題も同じような方法で解けるので挑戦してみるのも良いだろう。

●Q02 数列の四則演算 (IQ:70 目標時間:10分) ★
並んでいる数字の各桁の間に四則演算の演算子を入れて計算した結果「元の数を桁を逆から並べた数字」
と同じになるものを考えます(演算子は入れない場所があっても構いませんが、最低でも1つは入れるものとします)。
例えば、100~999 (3桁の数字) の場合、以下の 3つがあります。

351 → 3×51 = 153
621 → 6×21 = 126
886 → 8×86 = 688

1000~9999 (4桁の数字) のうち、上記の条件を満たす数を求めて下さい。

[答え] 5931 (→ 5×9×31 = 1395)
[>>クリックでコードを見る]


※なお、問題文などは以下の書籍からお借りしている(ただし、書籍の解答例は Ruby, JavaScript, C などで書かれているので購入の際はご注意)。パズルっぽい問題の解法パターンを勉強するには良いかも。



(関連記事)
【Java】式を逆ポーランド記法(後置記法)に変換する


category: Java

thread: プログラミング

janre: コンピュータ

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

【Java】8クイーンを解く[8クイーン問題]  


 もう1つ、再帰の用例としてよく挙げられる「8クイーン(エイト・クイーン)」というパズル(チェス)がある。こちらは「ハノイの塔」と違って、オーソドックスな深さ優先探索という感じで、「バックトラック法」や、マスの襲撃状態を、行や列・斜め方向など効率的に調べる例としても有用なので、よく使われるのだろう。この手法は色々と応用できるので、覚えておいて損はない。

●8クイーン問題 深さ優先探索での解法
public class EightQueensProblem {

public static void main(String[] args) throws Exception {
new EightQueensProblem();
}

static final int N = 8; //ボードのサイズ
int[][] input; //与えられたクイーン(初期配置)

QueensBoard board = new QueensBoard();

public EightQueensProblem() {
input = new int[][]{
{2, 2},
{5, 3},
};// y x (0~N-1)

dfs(0);
}

//深さ優先探索
boolean dfs(int y) {
if (y == N) {
if (board.checkInput(input)) {
System.out.println(board);
return true;
}
return false;
}

for (int x = 0; x < N; x++) {
if (!board.isAttacked(x, y)) {
board.setQueen(x, y, true);
if (dfs(y + 1)) {
return true;
}
board.setQueen(x, y, false);
}
}
return false;
}

//クイーンの配置ボード クラス
class QueensBoard {
boolean[] row = new boolean[N]; //行(─)の襲撃を表す
boolean[] col = new boolean[N]; //列(│)の襲撃を表す
boolean[] pos = new boolean[2 * N - 1]; //斜め(/)の襲撃を表す
boolean[] neg = new boolean[2 * N - 1]; //逆斜め(\)の襲撃を表す
boolean[][] board = new boolean[N][N]; //クイーンの配置を表す

//配置によるフラグのセット
void setQueen(int x, int y, boolean flg) {
row[y] = flg;
col[x] = flg;
pos[y + x] = flg;
neg[y - x + N - 1] = flg;
board[y][x] = flg;
}

//既に襲撃フラグがあるか?
boolean isAttacked(int x, int y) {
if (row[y] || col[x] || pos[y + x] || neg[y - x + N - 1]) {
return true;
}
return false;
}

//与えられたクイーン配置と照合する
boolean checkInput(int[][] input) {
for (int i = 0; i < input.length; i++) {
int y = input[i][0];
int x = input[i][1];
if (!board[y][x]) {
return false;
}
}
return true;
}

//クイーン配置を文字列化
@Override
public String toString() {
final StringBuilder sb = new StringBuilder(N * N + N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sb.append(board[i][j] ? "Q" : ".");
}
sb.append("\n");
}
return sb.toString();
}
}
}

......Q.
Q.......
..Q.....
.......Q
.....Q..
...Q....
.Q......
....Q...

 今回の例では答えは1つのパターンとしているので、解が見つかったら探索を強制終了している。複数の解を見つけたいなら、「dfs()」の戻値をすべて「false」にしてしまうのも良いだろう。また入力として、初めから配置してあるクイーンを input[][] という配列で設定し、照合するようにしてある。すべての解を見つけるなら照合する必要はない(board.checkInput() を呼び出している部分をコメントアウトなどすれば良い)。

 あとは先に述べた襲撃状態の探索の効率化も考えてみよう。この8クイーンは深さ優先探索でのバックトラックでマスに置けるか調べているわけだが、1つ1つのマスで、既に置かれているクイーンから襲撃を受けているか否かを調べていたら非常に骨が折れる(例えば配置したい位置から8方向にループで他のクイーンから襲撃を受けているかを調べていたら、手間がかかる)。だから、襲撃を表す8方向についてフラグを設定することによって、効率化を図っているというわけだ。フラグを設定している QueensBoard.setQueen() は何を意味しているか図に表してみよう。




 つまりクイーンを置く(x, y) に対応する col[i]、row[i]、pos[i]、neg[i] の配列のインデクス i を図に対応するように計算して、8方向への襲撃状態を表現すれば、各マスに対する他のクイーンからの襲撃も容易に取得できる。上下左右斜めの探索は不要になるというわけだ。

 今回は非常にオーソドックスな手法で書いているので、バックトラック法や更なる高速化などをもっと知りたければ、参考資料も載せておこう。N クイーンとして、高速化してどこまで N を上げられるか?なんてこともよく研究されている。ちなみにこのサンプルコードでは N = 15(ボードサイズが 15)で約 1.5 秒ほど、N = 16 で約 8 秒かかる(Windows10/Intel Core i5 x64 2.9GHz)。ビット演算などで高速化もできるそうなので、余力があったらやってみるのも良いだろう。

(参考)
バックトラック法
Puzzle DE Programming (N Queens Problem)


(関連記事)
【Java】ハノイの塔を解く
【Java】15パズルを解く [A*(A-star)アルゴリズム]


■参考になる書籍


category: Java

thread: プログラミング

janre: コンピュータ

tag: アルゴリズム  深さ優先探索  パズル解法 
tb: 0   cm: --
IS<インフィニット・ストラトス> アーキタイプ・ブレイカー
キルドヤ


プロフィール

Twitter

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop