MAXimal | |
добавлено: 11 Jun 2008 11:15 Содержание [скрыть] Биномиальные коэффициентыБиномиальным коэффициентом Также биномиальные коэффициенты - это коффициенты в разложении Считается, что эту формулу, как и треугольник, позволяющий эффективно находить коэффициенты, открыл Блез Паскаль (Blaise Pascal), живший в 17 в. Тем не менее, она была известна ещё китайскому математику Яну Хуэю (Yang Hui), жившему в 13 в. Возможно, её открыл персидский учёный Омар Хайям (Omar Khayyam). Более того, индийский математик Пингала (Pingala), живший ещё в 3 в. до н.э., получил близкие результаты. Заслуга же Ньютона заключается в том, что он обобщил эту формулу для степеней, не являющихся натуральными. ВычислениеАналитическая формула для вычисления: Эту формулу легко вывести из задачи о неупорядоченной выборке (количество способов неупорядоченно выбрать Рекуррентная формула (с которой связан знаменитый "треугольник Паскаля"): Её легко вывести через предыдущую формулу. Стоит заметить особо, при СвойстваБиномиальные коэффициенты обладают множеством различных свойств, приведём наиболее простые из них:
Вычисления в программеНепосредственные вычисления по аналитической формулеВычисления по первой, непосредственной формуле, очень легко программировать, однако этот способ подвержен переполнениям даже при сравнительно небольших значениях int C (int n, int k) { int res = 1; for (int i=n-k+1; i<=n; ++i) res *= i; for (int i=2; i<=k; ++i) res /= i; } Улучшенная реализацияМожно заметить, что в приведённой выше реализации в числителе и знаменателе стоит одинаковое количество сомножителей ( int C (int n, int k) { double res = 1; for (int i=1; i<=k; ++i) res = res * (n-k+i) / i; return (int) (res + 0.01); } Здесь мы аккуратно приводим дробное число к целому, учитывая, что из-за накапливающихся погрешностей оно может оказаться чуть меньше истинного значения (например, Треугольник ПаскаляС использованием же рекуррентного соотношения можно построить таблицу биномиальных коэффициентов (фактически, треугольник Паскаля), и из неё брать результат. Преимущество этого метода в том, что промежуточные результаты никогда не превосходят ответа, и для вычисления каждого нового элемента таблицы надо всего лишь одно сложение. Недостатком является медленная работа для больших N и K, если на самом деле таблица не нужна, а нужно единственное значение (потому что для вычисления const int maxn = ...; int C[maxn+1][maxn+1]; for (int n=0; n<=maxn; ++n) { C[n][0] = C[n][n] = 1; for (int k=1; k<n; ++k) C[n][k] = C[n-1][k-1] + C[n-1][k]; } Если вся таблица значений не нужна, то, как нетрудно заметить, достаточно хранить от неё только две строки (текущую — Вычисление за O(1)Наконец, в некоторых ситуациях оказывается выгодно предпосчитать заранее значения всех факториалов, с тем, чтобы впоследствии считать любой необходимый биномиальный коэффициент, производя лишь два деления. Это может быть выгодно при использовании Длинной арифметики, когда память не позволяет предпосчитать весь треугольник Паскаля, или же когда требуется производить расчёты по некоторому простому модулю (если модуль не простой, то возникают сложности при делении числителя дроби на знаменатель; их можно преодолеть, если факторизовать модуль и хранить все числа в виде векторов из степеней этих простых; см раздел "Длинная арифметика в факторизованном виде").
|