C#，二项式系数（Binomial Coefficient）的七种算法与源代码

二项式系数（ ），或组合数，在数学里表达为：(1 + x)ⁿ展开后x的系数（其中n为自然数）。从定义可看出二项式系数的值为整数。

二项式系数表为在我国被称为贾宪三角或杨辉三角，一般认为是北宋数学家贾宪所首创。

它记载于杨辉的《详解九章算法》(1261)之中。

在阿拉伯数学家卡西的著作《算术之钥》(1427)中也给出了一个二项式定理系数表，他所用的计算方法与贾宪的完全相同。

在欧洲，德国数学家阿皮安努斯在他1527年出版的算术书的封面上刻有此图。

但一般却称之为帕斯卡三角形，因为帕斯卡在1654年也发现了这个结果。

无论如何，二项式定理的发现，在我国比在欧洲至少要早300年。

1665年，牛顿把二项式定理推广到n为分数与负数的情形，给出了展开式。

二项式定理在组合理论、开高次方、高阶等差数列求和，以及差分法中有广泛的应用。

源代码

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public static partial class Algorithm_Gallery{public static int Binomial_Coeffient(int n, int k){if (k > n){return 0;}if (k == 0 || k == n){return 1;}return Binomial_Coeffient(n - 1, k - 1) + Binomial_Coeffient(n - 1, k);}public static int Binomial_Coeffient_Second(int n, int k){int[,] C = new int[n + 1, k + 1];for (int i = 0; i <= n; i++){for (int j = 0; j <= Math.Min(i, k); j++){if (j == 0 || j == i){C[i, j] = 1;}else{C[i, j] = C[i - 1, j - 1] + C[i - 1, j];}}}return C[n, k];}public static int Binomial_Coeffient_Third(int n, int k){int[] C = new int[k + 1];C[0] = 1;for (int i = 1; i <= n; i++){for (int j = Math.Min(i, k); j > 0; j--){C[j] = C[j] + C[j - 1];}}return C[k];}private static int Binomial_Coeffient_Utility(int n, int k, List[] dp){if (dp[n][k] != -1){return dp[n][k];}if (k == 0){dp[n][k] = 1;return dp[n][k];}if (k == n){dp[n][k] = 1;return dp[n][k];}dp[n][k] = Binomial_Coeffient_Utility(n - 1, k - 1, dp) + Binomial_Coeffient_Utility(n - 1, k, dp);return dp[n][k];}public static int Binomial_Coeffient_Fourth(int n, int k){List[] dp = new List[n + 1];for (int i = 0; i < (n + 1); i++){dp[i] = new List();for (int j = 0; j <= k; j++){dp[i].Add(-1);}}return Binomial_Coeffient_Utility(n, k, dp);}public static int GCD(int a, int b){if (b == 0){return a;}return GCD(b, (a % b));}public static int Binomial_Coeffient_Fifth(int n, int r){if (r > n){return 0;}if (r > n - r){r = n - r;}int mod = 1000000007;int[] arr = new int[r];for (int i = n - r + 1; i <= n; i++){arr[i + r - n - 1] = i;}long ans = 1;for (int k = 1; k < r + 1; k++){int j = 0, i = k;while (j < arr.Length){int x = GCD(i, arr[j]);if (x > 1){arr[j] /= x;i /= x;}if (i == 1){// If i becomes 1, no need// to search arrbreak;}j += 1;}}foreach (int i in arr){ans = (ans * i) % mod;}return (int)ans;}private static long pow(long b, long exp, long mod){long ret = 1;while (exp > 0){if ((exp & 1) > 0){ret = (ret * b) % mod;}b = (b * b) % mod;exp >>= 1;}return ret;}public static int Binomial_Coeffient_Sixth(int n, int r){if (r > n){return 0;}if ((n - r) > r){r = (n - r);}int[] SPF = new int[n + 1];for (int i = 1; i <= n; i++){SPF[i] = i;}for (int i = 4; i <= n; i += 2){SPF[i] = 2;}for (int i = 3; i * i < (n + 1); i += 2){if (SPF[i] == i){for (int j = i * i; j < (n + 1); j += i){if (SPF[j] == j){SPF[j] = i;}}}}Dictionary prime_pow = new Dictionary();for (int i = r + 1; i < (n + 1); i++){int t = i;while (t > 1){if (prime_pow.ContainsKey(SPF[t])){prime_pow[SPF[t]] = prime_pow[SPF[t]] + 1;}else{prime_pow.Add(SPF[t], 1);}t /= SPF[t];}}for (int i = 1; i < (n - r + 1); i++){int t = i;while (t > 1){if (prime_pow.ContainsKey(SPF[t])){prime_pow[SPF[t]] = prime_pow[SPF[t]] - 1;}t /= SPF[t];}}long ans = 1;long mod = 1000000007;foreach (int i in prime_pow.Keys){ans = (ans * pow(i, prime_pow[i], mod)) % mod;}return (int)ans;}public static int Binomial_Coeffient_Seventh(int n, int r){if (r > n){return 0;}long m = 1000000007;long[] inv = new long[r + 1];inv[0] = 1;if (r + 1 >= 2){inv[1] = 1;}for (int i = 2; i <= r; i++){inv[i] = m - (m / i) * inv[(int)(m % i)] % m;}int ans = 1;for (int i = 2; i <= r; i++){ans = (int)(((ans % m) * (inv[i] % m)) % m);}for (int i = n; i >= (n - r + 1); i--){ans = (int)(((ans % m) * (i % m)) % m);}return ans;}}
}

————————————————————

POWER BY .CN

BY .COM