アットウィキロゴ
技術見聞録
アットウィキロゴ
技術見聞録
ページ一覧

Menu > Algorithm > 数学

MoreMathクラス ってどこ行っても作ることになるんだよね。
ネットに置いてあるやつを使っていい現場だと、先人達の知恵をそのまま利用できて楽なんだけどなぁ。

目次

最大公約数（gcd）

高速なアルゴリズムは他にもあるけれど、普通に使う場合はユークリッドの互除法で大丈夫。 
  1. public static long gcd(long a, long b) {
  2.     long result = Math.max(a, b);
  3.     long n = Math.min(a, b);
  4.     long k;
  5.     do {
  6.         k = result % n;
  7.         result = n;
  8.         n = k;
  9.     } while (k != 0);
  10.     return result;
  11. }

最小公倍数（lcm）

最大公約数を用いて算出するのが簡単。
ちなみに引数の２つが十分に大きい場合は桁あふれを起こしてしまう可能性がある。
一応それを回避できるように、１つ目の数を最大公約数で割ってから２つ目の数を掛けるようにする。
（最大公約数はその性質から必ずどちらの数も割り切れる）
気休めだけどね。 
  1. public static long lcm(long a, long b) {
  2.     return a / gcd(a, b) * b;
  3. }

分数の計算

doubleで小数点を利用する計算を行っていると、だいたい丸め誤差の影響で計算値がズレる。
こういう時は簡単な Fractionクラス を作成して対応するけれど、そのメモ。

下準備

まずは重要な３つの関数を準備する。


計算では「桁あふれ」に注意すること

非常に大きな数を扱うことが想定される場合、必ず割り切れると分かっている割り算を優先すること。
例えば掛け算で 
(aの分子 * bの分子)/(aの分母 * bの分母) / (aの分子とbの分母の最大公約数 * aの分母とbの分子の最大公約数)
などとすると、分子または分母の計算で回避可能な桁あふれを起こすことがある。
ここは計算が面倒でも 
最大公約数１=aの分子とbの分母の最大公約数
最大公約数２=aの分母とbの分子の最大公約数
(aの分子/最大公約数１ * bの分子/最大公約数２)/(aの分母/最大公約数１ * bの分母/最大公約数２)
とした方が桁あふれを回避しやすい。
もっといい方法があるだろうが、私はそういうのを突き詰めるのは苦手。。

足し算

最大公約数で各分子の倍率を抑えつつ足し算する。
最小公倍数を求めれば change.bottom に直接代入できる
が、各分子に掛ける値を求めるために「最小公倍数 / 元の分母」っていう勿体無い割り算が入るので少し悲しい。 
  1. /**
  2.  * 足し算を行う.
  3.  * <p>
  4.  * 足される数は計算結果により変更される.
  5.  * </p>
  6.  * 
  7.  * @param change 足される数
  8.  * @param augend 足す数
  9.  * @return 足し算の結果. 足される数のインスタンスを返す.
  10.  */
  11. public static Fraction add(Fraction change, Fraction augend) {
  12.     long gcd = gcd(change.bottom, augend.bottom);
  13.     long left = augend.bottom / gcd;
  14.     long right = change.bottom / gcd;
  15.  
  16.     change.top = change.top * left + augend.top * right;
  17.     change.bottom = change.bottom * left;
  18.     return change;
  19. }

引き算

足し算と同様の処理。 
  1. /**
  2.  * 引き算を行う.
  3.  * <p>
  4.  * 引かれる数は計算結果により変更される.
  5.  * </p>
  6.  * 
  7.  * @param change 引かれる数
  8.  * @param subtrahend 引く数
  9.  * @return 引き算の結果. 引かれる数のインスタンスを返す.
  10.  */
  11. public static Fraction subtract(Fraction change, Fraction subtrahend) {
  12.     long gcd = gcd(change.bottom, subtrahend.bottom);
  13.     long left = subtrahend.bottom / gcd;
  14.     long right = change.bottom / gcd;
  15.  
  16.     change.top = change.top * left - subtrahend.top * right;
  17.     change.bottom = change.bottom * left;
  18.     return change;
  19. }

掛け算

掛け算の場合は
  • aの分子とbの分母
  • aの分母とbの分子
がそれぞれ約分できる可能性があるので先に各最大公約数で割っておく。

各最大公約数で割る時に括弧を付け忘れると
$$(change.top / gcd1) * multiplicand.top$$
が先に計算されてしまって危ういので忘れないように。 
  1. /**
  2.  * 掛け算を行う.
  3.  * <p>
  4.  * 掛けられる数は計算結果により変更される.
  5.  * </p>
  6.  * 
  7.  * @param change 掛けられる数
  8.  * @param multiplicand 掛ける数
  9.  * @return 掛け算の結果. 掛けられる数のインスタンスを返す.
  10.  */
  11. public static Fraction multiply(Fraction change, Fraction multiplicand) {
  12.     long gcd1 = gcd(change.top, multiplicand.bottom);
  13.     long gcd2 = gcd(multiplicand.top, change.bottom);
  14.     change.top = (change.top / gcd1) * (multiplicand.top / gcd2);
  15.     change.bottom = (change.bottom / gcd2) * (multiplicand.bottom / gcd1);
  16.     return change;
  17. }

割り算

掛け算と同様。逆数を使えば掛け算だけで計算できるけれど、ここに記載はしない。 
  1. /**
  2.  * 割り算を行う.
  3.  * <p>
  4.  * 割られる数は計算結果により変更される.
  5.  * </p>
  6.  * 
  7.  * @param change 割られる数
  8.  * @param divisor 割る数
  9.  * @return 割り算の結果. 割られる数のインスタンスを返す.
  10.  */
  11. public static Fraction divide(Fraction change, Fraction divisor) {
  12.     long gcd1 = gcd(divisor.top, change.top);
  13.     long gcd2 = gcd(change.bottom, divisor.bottom);
  14.     change.top = (change.top / gcd1) * (divisor.bottom / gcd2);
  15.     change.bottom = (change.bottom / gcd2) * (divisor.top / gcd1);
  16.     return change;
  17. }

配列のシャッフル


数学で習った通り、シャッフルで入れ替える要素は組み合わせを考慮する必要があるよ。って話。
実際書くときは忘れてるよね。
ソースを表示
「数学」をウィキ内検索
最終更新：2013年01月27日 06:36