ن اختيار ك وظيفة تعطل ركب

Question

لقد كتبت وظيفة 'ن اختيار ك' في ج++ ، والذي هو التواصل مع ص عبر ركب.لسبب ما أنا الحصول على 'القسمة على صفر' خطأ وقت التشغيل.يحدث ذلك عندما أحاول تقييم 30 اختر 2.

لقد حاولت تقييم كل سطر يدويا (مع إيفالكب) ، وأنا لا تزال في حيرة حول حيث القسمة على صفر يحدث.ربما شخص ما يمكن أن نشير إلى هذا بالنسبة لي أو اقتراح طريقة أفضل لكتابة ن اختيار ك?

هنا هو رمز:

// [[Rcpp::export]]                                                                                                                                  
int chooseC(int n, int k) {                                                                                                                         
  if (k > n) {                                                                                                                                      
    std::cout << "Error. k cannot be greater than n." << std::endl;                                                                                 
    return 0;                                                                                                                                       
  }                                                                                                                                                 
  int factN = std::tgamma(n + 1);                                                                                                                   
  int factK = std::tgamma(k + 1);                                                                                                                   
  int factDiff = std::tgamma(n - k + 1);                                                                                                            
  return factN/(factK*factDiff);                                                                                                                    
} 

Answer 1

باختصار:

• لا يوجد تغاما في الأمراض المنقولة جنسيا بقدر ما أستطيع أن أرى

• ص نفسها باعتبارها choose وظيفة لذلك أود فقط أن تفعل ما هو أدناه

• ص لديها أيضا توزيع غاما الخ حتى تتمكن من القيام بذلك باليد كذلك

• لماذا لم تطبع القيم فقط factN, factK, factDiff ?

حل ركب بسيط:

#include <Rcpp.h>

// [[Rcpp::export]]  
double chooseC(double n, double k) {
  return Rf_choose(n, k);
}

مثال:

R> chooseC(5,2)     
[1] 10
R> 

تحرير: بعد تعليق @بلاستفورنيس حول tgamma() في 11 دولار كندي cmath رأس ، وهنا هو نسخة إصلاحه الذي يعمل بشكل جيد بالنسبة لي:

#include <Rcpp.h>
#include <cmath>

// [[Rcpp::plugins(cpp11)]]

// [[Rcpp::export]] 
int chooseCtake2(int n, int k) {
  if (k > n) {
    Rcpp::stop("Error. k cannot be greater than n.");
  }
  int factN = std::tgamma(n + 1);
  int factK = std::tgamma(k + 1);
  int factDiff = std::tgamma(n - k + 1);
  return factN/(factK*factDiff); 
}

مثال على الاستخدام:

R> sourceCpp("/tmp/chooseC.cpp")
R> chooseCtake2(2,3)
Error: Error. k cannot be greater than n.
R> chooseCtake2(5,2)
[1] 10
R> 

Answer 2

لذا std::tgamma(x) يحسب وظيفة جاما من س.هذه الوظيفة تذهب إلى ما لا نهاية بسرعة كبيرة:

http://www.wolframalpha.com/share/clip?f=d41d8cd98f00b204e9800998ecf8427et5pmak8jtn

بالفعل في س = = 31 ، لديك عدد كبير جدا.

عند تحويل هذا مزدوج كبير جدا مرة أخرى إلى إنت ، والنتائج هي سلوك غير معروف (4.9 العائمة التحويلات لا يتجزأ [كونف.فبينت]):

يمكن تحويل قيمة برفال من نوع النقطة العائمة إلى قيمة برفال من نوع صحيح.تحويل ترن كيتس;وهذا هو ، الجزء الكسري يتم التخلص منها.السلوك غير معرف إذا تعذر على القيمة المقتطعة تكون ممثلة في نوع الوجهة.

على نظام بلدي هذا التحويل (مع إدخال {30 ، 2}) النتائج في إنت مع قيمة -2147483648.يمكن ملاحظة ذلك بسهولة عن طريق إدخال بعض العبارات المطبوعة:

int
chooseC(int n, int k)
{
    if (k > n)
    {                                                                                                                                      
        std::cout << "Error. k cannot be greater than n.\n";
        return 0;                                                                                                                                       
    }                                                                                                                                                 
    int factN = std::tgamma(n + 1);
    std::cout << "factN = " << factN << '\n';
    int factK = std::tgamma(k + 1);
    std::cout << "factK = " << factK << '\n';
    int factDiff = std::tgamma(n - k + 1);
    std::cout << "factDiff = " << factDiff << '\n';
    std::cout << "factK*factDiff = " << factK*factDiff << '\n';
    return factN/(factK*factDiff); 
}

التي بالنسبة لي المخرجات:

factN = -2147483648
factK = 2
factDiff = -2147483648
factK*factDiff = 0

كما يمكن أن يرى ، وب يؤدي في نهاية المطاف إلى القسمة على صفر ، وهو أيضا وب.ويبدو مشابها جدا للسلوك الذي تراه.

الحل لهذه المشكلة هو حساب الأشياء باستخدام الحساب المتكامل فقط ، وبطريقة لا تفيض بها الحسابات الوسيطة إذا كانت النتيجة النهائية قابلة للتمثيل في النوع المتكامل.هذا يستلزم استخدام وظيفة القاسم المشترك الأكبر.

كود المصدر المفتوح الذي يفعل هذا متاح هنا:

http://howardhinnant.github.io/combinations.html

ابحث عن"عد_كل_مجموعة".الخاص بك chooseC يمكن ترميزها من حيث count_each_combination مثل ذلك:

int
chooseC(int n, int k)
{
    if (k > n)
    {                                                                                                                                      
        std::cout << "Error. k cannot be greater than n.\n";
        return 0;                                                                                                                                       
    }                                                                                                                                                 
    return count_each_combination(n-k, k);
}

الآن chooseC(30, 2) سيعود 435.إذا count_each_combination غير قادر على تخزين النتيجة في int, ، أ std::overflow_error سيتم طرح.

إذا كنت ترغب في تقييد الخاص بك chooseC إلى k == 2, ، أو ربما تفعل ذلك مؤقتا فقط لفهم الخوارزمية بشكل أفضل ، لاحظ أن صيغة عد المجموعات هي:

عندما k == 2, ، هذا يبسط إلى:

n*(n-1)/2

الآن إما n حتى ، أو n-1 هو حتى.يمكنك اكتشاف أي منها ، ثم قسمة هذا الرقم على 2 ، بدون خطأ اقتطاع ، ثم ضرب النتيجة في الرقم الذي لم يتم تقسيمه على 2.وبالتالي تحصل على النتيجة الدقيقة مع عدم وجود احتمال لخطأ الاقتطاع ، ولا تجاوز متوسط ، باستخدام الحساب المتكامل فقط.هذه هي التقنية التي count_each_combination الاستخدامات ، ولكن معممة على أي قاسم ، لتقديم نتيجة تكون دائما دقيقة إذا كانت يمكن أن تتناسب مع النوع المتكامل المزود.