Основным содержанием этой статьи является рекурсивная и нерекурсирующая реализация биномиального распределения программирования Java следующим образом.
Источник проблемы:
Упражнение 27 Раздела 1.1, 4 -е издание алгоритма, раздел 1.1: возврат (1,0 - P) * Биномиал (N - 1, K, P) + P * Binomial (N - 1, K - 1, P);
Рассчитайте количество рекурсивных вызовов. Как рекурсивная формула появилась отсюда?
Биномиальное распределение:
Определение: дискретное распределение вероятностей N Независимого да/неэкспенсированных времен успеха k, вероятность успеха в каждом эксперименте составляет P, которая обозначена как B (N, P, K).
Формула вероятности: p (ξ = k) = c (n, k) * p^k * (1-p)^(nk)
Где c (n, k) = (nk)!/(K! * (Nk)!), Обозначается как ξ ~ b (n, p), ожидание: eξ = np, дисперсия: dξ = npq, где q = 1-p.
В статистике вероятности существует рекурсивная формула:
Это источник рекурсивной формы в вопросе.
Рекурсивная формула происходит от: c (n, k) = c (n-1, k)+c (n-1, k-1). Фактический сценарий - выбрать K из N лиц. Сколько существует комбинаций? Органируйте люди в порядке от 1 до n. Если KTH не выбран, вам нужно выбрать K из оставшихся людей N-1; Если выбран KTH, вам нужно выбрать K-1 из оставшихся людей N-1.
Рекурсивная реализация биномиального распределения в книге:
Публичный статический двойной биномиальный (int n, int k, double p) {count ++; // Записать количество рекурсивных вызовов, если (n == 0 && k == 0) {return 1.0; } if (n <0 || k <0) {return 0.0; } return (1.0 - p) * Binomial (n - 1, k, p) + p * binomial (n - 1, k - 1, p); }Экспериментальные результаты:
NKP Количество вызовов 10 5 0,25 246720 10 0,25 243553830 15 0,25 2440764535
Из результатов мы видим, что количество раз, когда этот рекурсивный метод должен быть вызван, является геометрической катастрофой, и даже если N до 50 не рассматривается.
Улучшение биномиального распределения рекурсивной реализации:
Частный статический длинный счет = 0; Частный статический двойной [] [] m; Частный статический двойной биномиальный (int n, int k, double p) {count ++; if (n == 0 && k == 0) {return 1.0; } if (n <0 || k <0) {return 0.0; } if (m [n] [k] == -1) {// Сохранить результат расчета и использовать расчетные непосредственно, без рекурсивного расчета m [n] [k] = (1,0 - p) * биномиал (n - 1, k, p) + p * binomial (n - 1, k - 1, p); } return m [n] [k]; } public static double binomial (int n, int k, double p) {m = new Double [n + 1] [k + 1]; for (int i = 0; i <= n; i ++) {for (int j = 0; j <= k; j ++) {m [i] [j] = -1; }} return binomial (n, k, p); }Экспериментальные результаты:
NKP Количество вызовов 10 5 0,25 10120 10 0,25 45230 15 0,25 120350 25 0,25 3204100 50 0,25 5205
Из экспериментальных результатов мы видим, что количество вызовов значительно уменьшено, и можно использовать алгоритм.
Нерекурсивное реализация биномиального распределения:
Фактически, вместо использования рекурсии, непосредственно расчет комбинированных чисел и факториалов более быстрее.
// Рассчитайте количество комбинаций Публичная статическая двойная комбинация (двойная n, двойная k) {двойной мин = k; Double max = nk; двойной t = 0; двойной nn = 1; двойной kk = 1; if (min> max) {t = min; мин = макс; max = t; } while (n> max) {// факториал большей части в знаменателе не нужно рассчитывать nn = nn*n; N--; } while (min> 0) {// рассчитать фактор меньшей части kk = kk*min; мин-; } вернуть nn/kk; } // Рассчитайте значение биномиального распределения Публичное статическое двойное биномиальное (int n, int k, double p) {double a = 1; двойной b = 1; двойной c = комбинация (n, k); while ((nk)> 0) {// вычислять (NK) мощность (1-p) a = a*(1-p); N--; } while (k> 0) {// Рассчитать k мощность p b = b*p; k--; } вернуть C*a*b; }Экспериментальные результаты:
NKP Биномиальное распределение.
Сравнивая с предыдущим алгоритмом, результаты расчета верны, а скорость бега очень быстрая.
Суммировать
Выше приведено все содержание этой статьи о рекурсивном и нерекурсивном коде реализации примеров биномиального распределения программирования Java. Я надеюсь, что это будет полезно для всех. Заинтересованные друзья могут продолжать ссылаться на другие связанные темы на этом сайте. Если есть какие -либо недостатки, пожалуйста, оставьте сообщение, чтобы указать это. Спасибо, друзья, за вашу поддержку на этом сайте!