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

1 二项式系数（binomial coefficient）

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

二项式系数表为在我国被称为贾宪三角或杨辉三角，一般认为是北宋数学家贾宪所首创。
它记载于杨辉的《详解九章算法》(1261)之中。
在阿拉伯数学家卡西的著作《算术之钥》(1427)中也给出了一个二项式定理系数表，他所用的计算方法与贾宪的完全相同。
在欧洲，德国数学家阿皮安努斯在他1527年出版的算术书的封面上刻有此图。
但一般却称之为帕斯卡三角形，因为帕斯卡在1654年也发现了这个结果。
无论如何，二项式定理的发现，在我国比在欧洲至少要早300年。
1665年，牛顿把二项式定理推广到n为分数与负数的情形，给出了展开式。
二项式定理在组合理论、开高次方、高阶等差数列求和，以及差分法中有广泛的应用。

2 7种计算方法的源代码

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<int>[] 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<int>[] dp = new List<int>[n + 1];

			for (int i = 0; i < (n + 1); i++)
			{
				dp[i] = new List<int>();
				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 arr
						break;
					}
					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<int, int> prime_pow = new Dictionary<int, int>();

			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 TRUFFER.CN
BY 315SOFT.COM