При решении задач комбинаторики часто возникает необходимость в расчете биномиальных коэффициентов. Бином Ньютона, т.е. разложение также использует биномиальные коэффициенты. Для их расчета можно использовать формулу, выражающую биномиальный коэффициент через факториалы: или использовать рекуррентную формулу: Из бинома Ньютона и рекуррентной формулы ясно, что биномиальные коэффициенты — целые числа.
Одним из методов, позволяющих значительно сократить количество вычислений, является применение Фурье преобразований и дискретных Фурье преобразований.
Наличие большого числа библиотек, реализующих Фурье преобразований (во всевозможных вариантах быстрых версий), делает реализацию алгоритмов не очень сложной задачей для программирования.
Реализованные алгоритмы являются частью библиотеки с открытым исходным кодом FFTTools. Интернет-адрес: github.com/dprotopopov/FFTTools
Преобразование Фурье функции f вещественной переменной является интегральным и задаётся следующей формулой:
Разные источники могут давать определения, отличающиеся от приведённого выше выбором коэффициента перед интегралом, а также знака «?» в показателе экспоненты. Но все свойства будут те же, хотя вид некоторых формул может измениться.
Кроме того, существуют разнообразные обобщения данного понятия.
FхG(t) = SUM F(i)*G(j)|i+j=t
FхG = BFT ( FFT(F)*FFT(G) )
using System;
using System.Drawing;
using System.Linq;
using System.Numerics;
namespace FFTTools
{
public class BinomialBuilder : BuilderBase, IBuilder
{
/// <summary>
/// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources.
/// </summary>
public void Dispose()
{
}
public static void GetLongs(long[] array, long x = 1)
{
var n = array.Length - 1;
if (array.Length > 0) array[0] = 1;
for (var i = 0; i < n; i++)
array[i + 1] = x*array[i]*(n - i)/(i + 1);
}
public static void GetDoubles(double[] array, double x = 1.0)
{
var complex = new Complex[array.Length];
if (array.Length > 0) complex[0] = Complex.One;
if (array.Length > 1) complex[1] = x;
if (array.Length > 0)
{
Fourier(complex, FourierDirection.Forward);
complex = complex.Select(
value => Complex.Pow(value, array.Length - 1)/array.Length).ToArray();
Fourier(complex, FourierDirection.Backward);
}
var index = 0;
foreach (var value in complex) array[index++] = value.Real;
}
public Bitmap ToBitmap(Bitmap source)
{
throw new NotImplementedException();
}
}
}
using System;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace FFTTools.UnitTest
{
[TestClass]
public class BinomialUnitTest
{
[TestMethod]
public void BinomialTestMethod()
{
const int count = 10;
var doubles = new double[count];
var longs = new long[count];
BinomialBuilder.GetLongs(longs);
BinomialBuilder.GetDoubles(doubles);
Console.WriteLine(
string.Join(Environment.NewLine,
longs.Zip(doubles, (x, y) => string.Format("{0} - {1} = {2}", x, y, x - y))) +
Environment.NewLine);
Assert.IsTrue(doubles.Zip(longs, (x, y) => x - y).All(x => Math.Abs(x) < 0.001));
}
}
}
К сожалению, не доступен сервер mySQL