FC2ブログ
ヽ|∵|ゝ(Fantom) の 開発blog? ホーム » C# »【C#】最大公約数を求める/分数の約分をする(ユークリッドの互除法)

【C#】最大公約数を求める/分数の約分をする(ユークリッドの互除法)  


 ちょっとアプリを作っていて、画面解像度のアスペクト比(整数)を計算させようと思ったのだが、C# ではユークリッドの互除法のライブラリを作ってなかった…。

 というわけで、以前に作った Java のコードをそのまま移植してみた。私はライブラリに関しては、割と古い書き方をするので、ほぼ Java → C# への移植はコピペに近い感じでできる。Java8 なら、LINQ 的なもできるけど、C# とは互換性あまり無いし、実行速度の問題もある。ライブラリは古い書き方で、メインコードは LINQ や Rx など新しい書き方で、なんて使い分けも実はオススメだ(笑)。




■最大公約数を求める(ユークリッドの互除法)[非再帰版]

 ユークリッドの互除法の実装を調べると、非再帰と再帰でのやり方が出てくると思うが、一応両方書いておこう。普通に使うなら、非再帰版で良いと思うが、シンプルに書きたいときなどは再帰版でも良いかもね。

●最大公約数を求める(ユークリッドの互除法)[非再帰版]
/// <summary>
/// 最大公約数を求める(Greatest Common Divisor).
/// ユークリッドの互除法 (非再帰版).
/// 2020/11/12 Fantom (Java から移植)
/// http://fantom1x.blog130.fc2.com/blog-entry-384.html
/// http://fantom1x.blog130.fc2.com/blog-entry-215.html
/// </summary>
/// <param name="a">数値1 (>0)</param>
/// <param name="b">数値2 (>0)</param>
/// <returns>最大公約数 (なし=1 [互いに素])</returns>
public static int Gcd(this 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 を返す
}

●メインコード例
using System;

int a = 1920;
int b = 1080;
int d = Gcd(a, b);
Console.WriteLine("d = " + d); //最大公約数
Console.WriteLine(a + "x" + b + " => " + (a / d) + ":" + (b / d)); //約分に利用

d = 120
1920x1080 => 16:9

 a > 0, b > 0 となっているので注意(特に負の剰余は言語によって結果が違うので注意)。

 Java からのそのまま移植なので、解説は以前の記事を見て欲しい。ユークリッド互除法に関する説明も Wikipedia で良いだろう(アニメーションがとてもわかり易い)。数学的なものはこの辺りの例を見ればわかるだろう。

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



■最大公約数を求める(ユークリッドの互除法)[再帰版]

●最大公約数を求める(ユークリッドの互除法)[再帰版]
/// <summary>
/// 最大公約数を求める(Greatest Common Divisor).
/// [ユークリッドの互除法] (再帰版).
/// 2020/11/12 Fantom (Java から移植)
/// http://fantom1x.blog130.fc2.com/blog-entry-384.html
/// http://fantom1x.blog130.fc2.com/blog-entry-215.html
/// </summary>
/// <param name="a">数値1 (>0) (a >= b)</param>
/// <param name="b">数値2 (>0)</param>
/// <returns>最大公約数 (なし=1 [互いに素])</returns>
public static int GcdRec(int a, int b)
{
return (b == 0) ? a : GcdRec(b, a % b);
}

●メインコード例
using System;

int a = 1920;
int b = 1080;
int d = (a >= b) ? GcdRec(a, b) : GcdRec(b, a); //a >= b にする
Console.WriteLine("d = " + d); //最大公約数
Console.WriteLine(a + "x" + b + " => " + (a / d) + ":" + (b / d)); //約分に利用

d = 120
1920x1080 => 16:9

 a > 0, b > 0 となっているので注意(特に負の剰余は言語によって結果が違うので注意)。
 また、再帰版は、a >= b を関数内でチェックしてないので少し注意だ。

 また、シンプルなので再帰的な書き方は好まれる傾向があるが、再帰というのは自身のメソッドを呼ぶたびにスタックを積むため、メモリ的には優しくない。特にスマホみたいなメモリが小さいものには要注意だ。Gcd ではそれほど深くはならないかもだが、フィボナッチ数などで大きな数になると、かなりの深さになることもある。もし使わなくても書けるなら、使わない方が良い(フィボナッチ数も動的計画法を使うと良い)。



■分数の約分をする

 Gcd の使用例で約分しているが、それを簡単にまとめたものを作ってみよう。引数 a, b を分数の分子/分母に見立てただけのものである。これが分数の約分計算と同等になる。

●分数の約分をする
/// <summary>
/// a / b の約分をする
/// 2020/11/12 Fantom
/// http://fantom1x.blog130.fc2.com/blog-entry-384.html
/// </summary>
/// <param name="a">分子 (>0)</param>
/// <param name="b">分母 (>0)</param>
/// <returns></returns>
public static (int, int) Reduce(this int a, int b)
{
int d = Gcd(a, b); //最大公約数
return (a / d, b / d);
}

●メインコード例
using System;

int width = 1920;
int height = 1080;
var aspect = Reduce(width, height);
Console.WriteLine($"{width}x{height} => {aspect.Item1}:{aspect.Item2}");

1920x1080 => 16:9

 a > 0, b > 0 となっているので注意(特に負の剰余は言語によって結果が違うので注意)。

 .NET 4.x の書き方となっているので、.NET 3.5 以前なら、

public static int[] Reduce(this int a, int b)
{
int d = Gcd(a, b); //最大公約数
return new int[]{ a / d, b / d };
}

にして、[0]分子/[1]分母 にすれば良いだろう。

 これを使えば、アスペクト比(整数)の計算も簡単だ(笑)。

 ちなみに、.NET 4.x の方の書き方の戻値に (int, int) を使っているが、これはタプルと言い、C#7.3 以降からは値型の ValueTuple がデフォルトとなり、メモリパフォーマンスも良くなったようだ(以前は参照型で、パフォーマンスも悪かったらしい)。また、ここでは .Item1, .Item2,... のアクセサを使っているが、名前を付けることもできる。

 Unity の場合、2018.3 以降ではデフォルトで使えるようになっているので、int[] よりタプルの方が良いかも知れない(int[] は参照型なので、無駄にヒープを使うため)。詳しい内容は以下に参考資料を載せておくので、確認してみるのも良いだろう。

(参考)
タプル記法 (ValueTuple)
タプル型 (C# リファレンス)
C# のメモリ管理
Unity と C# のバージョン



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

 もう1つ、ついでに3つ以上の数の最大公約数を求めるユークリッドの互除法も作っておこう。テスト用のコードには2つの Gcd との計算比較も書いておくので、それをまとめたものということもわかるだろう。

●3つ以上の最大公約数を求める(ユークリッドの互除法②)
/// <summary>
/// 3つ以上の最大公約数を求める[gcd(a, b, c,...)].
/// ユークリッドの互除法の繰り返しで求める.
/// 2020/11/12 Fantom (Java から移植)
/// http://fantom1x.blog130.fc2.com/blog-entry-384.html
/// http://fantom1x.blog130.fc2.com/blog-entry-220.html
/// </summary>
/// <param name="param">数値1, 2, 3,... (a, b, c,...) (>0) [引数は3個以上]</param>
/// <returns>最大公約数(なし=1[互いに素])</returns>
public static int Gcd(params int[] param) {
int len = param.Length;
int g = Gcd(param[0], param[1]);
for (int i = 1; i < len - 1; i++)
{
g = Gcd(g, param[i + 1]);
}
return g;
}

●メインコード例
using System;

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);
Console.WriteLine("g3 = " + g3);

int g = Gcd(a, b, c, d);
Console.WriteLine("g = " + g);
Console.WriteLine(g == g3);

g3 = 12
g = 12
true

 a > 0, b > 0 となっているので注意(特に負の剰余は言語によって結果が違うので注意)。

 これも Java コードそのままなので、解説は以前の記事を参照して欲しい。

【Java】3つ以上の最大公約数を求める(ユークリッドの互除法②)
The case of more than two numbers (Wikipedia)



 私は以前、アルゴリズム系の問題をよく Java で解いていたが、ちょっとしたとき、便利なアルゴリズムなんかもあったりするので、興味あったら勉強してみるのも良いかもね。アルゴリズム自体を完全理解しなくても(物によっては数学的に難しいものもある)、使い方だけ覚えておけば、色々なものに応用できることもある。アルゴリズム自体は特に言語に関係ないしね。1冊くらい何か読んでおくのはオススメ。







(関連記事)
【Unity】【C#】画面解像度とアクペクト比(整数)を求める
【C#】最小公倍数を求める(ユークリッドの互除法)
【Java】最大公約数・最小公倍数を求める(ユークリッドの互除法)
【Java】3つ以上の最大公約数を求める(ユークリッドの互除法②)
【Java】拡張ユークリッドの互除法


関連記事
スポンサーサイト



category: C#

thread: プログラミング

janre: コンピュータ

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


トラックバック

トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/384-8e9c77d4
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop