ファレイ数列
ファレイ数列の定義に関しては
C#のファレイ数列を参照。
C#で難しかったのは有理数クラスの作成であって、後はLINQの機能を使用すれば簡単にファレイ数列が構成できた。
今回作成するプログラムでは、自作有理数の構造体の列に関して、
重複要素の削除とソートをどのように行うかがポイントとなる。
コード例.
まず、最大分母を指定して、網羅的に数列を構成する。
\[ A = \left\{1,\frac{1}{2},\frac{2}{2},\frac{1}{3},\frac{2}{3},\frac{3}{3},...,\frac{N}{N} \right\} \]
このとき、Aの要素数は最大分母をNとするとき、 $\displaystyle \frac{N(N+1)}{2}$ 個存在する。
後はこの集合Aを昇順ソートして、重複要素を削除すればファレイ数列が得られる。
(自作)有理数の列のソートには、stdlib.hのqsortを使用する。これは
qsort(array,要素数,要素のサイズ,比較関数)
の形で利用するが、比較関数は有理数を比較するような定義にしなければならない。
あとは重複要素の削除だが、これは自作する。いきなり重複要素削除するのは大変そうなので、 ソートされたものに限定して重複要素を削除するUniqueRというものを作成する。 これを使用して、DistinctR という 「qsort + UniqueR」の機能を持った一般的な重複要素削除関数を作成する。
重複要素の削除とソート
// ファイレイ数例を構成し表示する。自作関数は先頭が大文字。 #include <stdio.h> #include <stdlib.h> // 有理数の分子N(numerator)と分母D(denominator) typedef struct { int N; int D; }Rational; // 最大公約数 int GCD(int a, int b) { while (b != 0) { int tmp = a; a = b; b = tmp % b; } return a > 0 ? a : -a; } // 有理数を約分、また分母にマイナスが来ないように標準化。 void Normalize(Rational* r) { int gcd = GCD(r->N, r->D); r->N = r->N / gcd; r->D = r->D / gcd; if (r->D < 0) { r->N *= -1; r->D *= -1; } } // stdlib.hで用意されたqsort使用の際に利用する有理数の比較関数。 int CompareR(const void* x, const void* y) { Rational r1 = *(Rational*)x; Rational r2 = *(Rational*)y; Normalize(&r1); Normalize(&r2); int a = r1.N; int b = r1.D; int c = r2.N; int d = r2.D; // a/b - c/d = (ad-bc)/bd return a * d - b * c; } // 二つの有理数が等しいか判定する関数。等しければ1.等しくなければ0. int EqualR(Rational r1, Rational r2) { int a = r1.N; int b = r1.D; int c = r2.N; int d = r2.D; // a/b - c/d = (ad-bc)/bd return a * d - b * c == 0 ? 1 : 0; } // ソートされた有理数列から重複要素を削除する関数。ソートされていないと使えない。 void UniqueR(Rational* seq, int seqCount, int* length) { int k = 0; int i; for (i = 0; i < seqCount; i++) { seq[i] = seq[k]; int p = 1; while (k + p < seqCount && EqualR(seq[k], seq[k + p]) == 1) { p++; } k += p; if (k >= seqCount) { i++; break; } } *length = i; } // ソートしてからUniqueRを適用する関数。 void DistinctR(Rational* seq, int seqCount,int* len) { int i; for (i = 0; i < seqCount; i++) { Normalize(&seq[i]); } qsort(seq, seqCount, sizeof(Rational), CompareR); *len = 0; UniqueR(seq, seqCount, len); } int main() { Rational seq[] = { {3,1},{2,1},{1,1},{2,1},{2,1},{3,1} }; int len = 0; DistinctR(seq, sizeof seq / sizeof(seq[0]), &len); for (int i = 0; i < len; i++) { if (seq[i].D == 1) { printf("%d,", seq[i].N); } else { printf("%d/%d,", seq[i].N, seq[i].D); } } }
実行結果. 1,2,3,
ファレイ数列の構成
重複要素削除とソートができれば、ファレイ数列は簡単に構成できる。
// ファイレイ数例を構成し表示する。自作関数は先頭が大文字。 #include <stdio.h> #include <stdlib.h> // 有理数の分子N(numerator)と分母D(denominator) typedef struct { int N; int D; }Rational; // 最大公約数 int GCD(int a, int b) { while (b != 0) { int tmp = a; a = b; b = tmp % b; } return a > 0 ? a : -a; } // 有理数を約分、また分母にマイナスが来ないように標準化。 void Normalize(Rational* r) { int gcd = GCD(r->N, r->D); r->N = r->N / gcd; r->D = r->D / gcd; if (r->D < 0) { r->N *= -1; r->D *= -1; } } // stdlib.hで用意されたqsort使用の際に利用する有理数の比較関数。 int CompareR(const void* x, const void* y) { Rational r1 = *(Rational*)x; Rational r2 = *(Rational*)y; Normalize(&r1); Normalize(&r2); int a = r1.N; int b = r1.D; int c = r2.N; int d = r2.D; // a/b - c/d = (ad-bc)/bd return a * d - b * c; } // 二つの有理数が等しいか判定する関数。等しければ1.等しくなければ0. int EqualR(Rational r1, Rational r2) { int a = r1.N; int b = r1.D; int c = r2.N; int d = r2.D; // a/b - c/d = (ad-bc)/bd return a * d - b * c == 0 ? 1 : 0; } // ソートされた有理数列から重複要素を削除する関数。ソートされていないと使えない。 void UniqueR(Rational* seq, int seqCount, int* length) { int k = 0; int i; for (i = 0; i < seqCount; i++) { seq[i] = seq[k]; int p = 1; while (k + p < seqCount && EqualR(seq[k], seq[k + p]) == 1) { p++; } k += p; if (k >= seqCount) { i++; break; } } *length = i; } // ソートしてからUniqueRを適用する関数。 void DistinctR(Rational* seq, int seqCount,int* len) { int i; for (i = 0; i < seqCount; i++) { Normalize(&seq[i]); } qsort(seq, seqCount, sizeof(Rational), CompareR); *len = 0; UniqueR(seq, seqCount, len); } int main() { int maxDenom = 50; //分母の最大 int lengthSeq = maxDenom * (maxDenom + 1) / 2; Rational * seq = (Rational*)malloc(sizeof(Rational) * lengthSeq); if (seq == NULL) { exit(1); } // 分母がmaxDenomまで網羅的に要素を追加する。 int i, k; int u = 0; for (i = 1; i <= maxDenom; i++) { for (k = 1; k <= i; k++) { seq[u].N = k; seq[u].D = i; u++; } } // 重複要素の削除 int len = 0; DistinctR(seq, lengthSeq,&len); // 要素の表示 for (i = 0; i < len; i++) { printf("%d/%d,", seq[i].N, seq[i].D); } free(seq); }
実行結果.
1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,1/1,