المحتوى الرئيسي لهذه الورقة هو التنفيذ العودية وغير المستقرة لتوزيع Binomial برمجة Java ، على النحو التالي.
مصدر المشكلة:
التمرين 27 من القسم 1.1 ، الطبعة الرابعة من الخوارزمية ، القسم 1.1: العودة (1.0 - P) * ذات الحدين (n - 1 ، k ، p) + p * binomial (n - 1 ، k - 1 ، p) ؛
حساب عدد المكالمات العودية. كيف جاءت الصيغة العودية من هنا؟
توزيع الحدين:
التعريف: توزيع الاحتمالات المنفصل لـ n yes/experiments المستقلة لأوقات النجاح 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 الأفراد. كم عدد المجموعات الموجودة؟ ترتيب n الناس من أجل 1 إلى ن. إذا لم يتم اختيار KTH ، فأنت بحاجة إلى تحديد K من N-1 المتبقية ؛ إذا تم اختيار KTH ، فأنت بحاجة إلى تحديد K-1 من الأشخاص N-1 المتبقيين.
التنفيذ العودية لتوزيع الحدين في الكتاب:
pinomial الثابتة العامة الثابتة (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 24353830 15 0.25 2440764535
من النتائج ، يمكننا أن نرى أن عدد المرات التي يجب أن تُطلق عليها عدد مرات هذه الطريقة المتكررة هي كارثة هندسية ، وحتى إذا لم يتم النظر في N إلى 50.
تحسين التوزيع ذي الحدين التنفيذ العودية:
العد الطويل الثابت الخاص = 0 ؛ مزدوج ثابت ثابت [] [] م ؛ ذي الحدين الثابت الخاص الثابت (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] ؛ } pinomial الثابتة العامة (int n ، int k ، double p) {m = new double [n + 1] [k + 1] ؛ لـ (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) {double min = k ؛ مزدوج الحد الأقصى = NK ؛ مزدوج t = 0 ؛ مزدوج nn = 1 ؛ مزدوج KK = 1 ؛ if (min> max) {t = min ؛ min = max ؛ كحد أقصى = ر ؛ } بينما (n> max) {// لا يلزم حساب عامل الجزء الأكبر في المقامس nn = nn*n ؛ ن-- ؛ } بينما (min> 0) {// احسب مصنع الجزء الأصغر kk = kk*min ؛ مين-؛ } إرجاع nn/kk ؛ } // حساب قيمة التوزيع ذات الحدين الدقيقة الثابتة الثابتة (int n ، int k ، double p) {double a = 1 ؛ مزدوج ب = 1 ؛ مزدوج C = مزيج (n ، k) ؛ بينما ((nk)> 0) {// احسب قوة (nk) لـ (1-p) a = a*(1-p) ؛ ن-- ؛ } بينما (k> 0) {// حساب قوة k من p b = b*p ؛ ك- ؛ } return c*a*b ؛ }النتائج التجريبية:
قيمة توزيع NKP ذات الحدين 10 ، 5 ، 0.25 0.05839920043945312520 ، 10 ، 0.25 0.0099222752796770650 ، 25 ، 0.25 8.44919466990397e-5
مقارنة مع الخوارزمية السابقة ، تكون نتائج الحساب صحيحة وسرعة التشغيل سريعة جدًا.
لخص
ما ورد أعلاه هو المحتوى الكامل لهذه المقالة حول أمثلة رمز التنفيذ العودية وغير المتكررة لتوزيع Binomial برمجة Java. آمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى الموضوعات الأخرى ذات الصلة على هذا الموقع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها. شكرا لك يا أصدقائك لدعمكم لهذا الموقع!