حساب الجمع لأعداد كبيرة

Question

أحاول حساب ما إذا كان مُدخل معين في الصف 100 من مثلث باسكال قابلاً للقسمة على 3 أم لا. أقوم بحساب ذلك باستخدام الصيغة nCr حيث n=100 وr هي الإدخالات المختلفة في الصف 100.أنا أستخدم الكود أدناه لحساب المجموعة

 public static double Combination(int n, int m, double comb)
    {
        for (int r = -1; ++r < m; )
            comb = comb * (n - r) / (r + 1);
        return comb;
    }

ولكن بالنسبة لقيم مثل 100C16، فأنا أحصل على عدد كبير يحتوي على علامة عشرية وe فيه.لقد بحثت على الإنترنت ووجدت أن هناك في الواقع 12 رقمًا لا يقبل القسمة على 3، لكن برنامجي يعطيني 63 رقمًا لا يقبل القسمة على 3 في الصف 100 وهذا خطأ. هل يمكن لأي أحد أن يخبرني ما الذي أنا عليه؟ فعل الخطأ.

Answer 1

أفترض أن "nCr" هو اختصار لـ n-choose-r، أو اختر r من N، أليس كذلك؟

لمعرفة ما إذا كان nCr يقبل القسمة على ثلاثة، لا تحتاج إلى حساب النتيجة، كل ما عليك فعله هو معرفة ما إذا كان يقبل القسمة على 3.عليك أن ترى كم مرة ن!يقبل القسمة على 3، ثم كم مرة ص!يقبل القسمة على 3 وكم مرة (n-r)!يكون.

انها حقا بسيطة جدا - 1!لا يقبل القسمة على 3، 2!ليس كذلك، 3!قابل للقسمة مرة واحدة.4!و5!هي أيضا قابلة للقسمة مرة واحدة.6!يقبل القسمة على مرتين، وكذلك 7!و8!.9!يقبل القسمة 4 مرات وهكذاانتقل إلى n (أو قم بحساب الصيغة دون إجراء عمليات حسابية تدريجية، فالأمر ليس بهذه الصعوبة)، وتحقق.

توضيح - دراستي في الرياضيات باللغة العبرية، لذا "كم مرة ن!قابل للقسمة على 3" قد لا تكون الطريقة الإنجليزية الصحيحة لقول ذلك.بقلم "ن!يقبل القسمة على 3 م مرة" أعني ذلك n!=3^m*k, حيث k لا يقبل القسمة على 3 على الإطلاق.

يحرر:مثال.دعونا نرى ما إذا كان 10c4 يقبل القسمة على 3.

لنصنع طاولة صغيرة نكتب فيها كم مرة ك!يقبل القسمة على 3 (ك!العمود مخصص للتوضيح فقط، ولا تحتاج إليه فعليًا عند حساب عمود قابلية القسمة):

  k      k!     Divisibility
  1       1     0
  2       2     0
  3       6     1
  4      24     1
  5     120     1
  6     720     2
  7    5040     2
  8   40320     2
  9  362880     4
 10 3628800     4

10c4 هو 10!/ (6!* 4!) .

10!قابل للقسمة 4 مرات (يعني 10!)= 3^4 * شيء غير قابل للقسمة على 3) ، 6!هو قابلة للقسمة 2 مرات 4!قابل للقسمة 1 مرة

حتى 10!(6!* 4!) يقبل القسمة على 3.وهي في الواقع 3*70.

Answer 2

أولاً، أنت تستخدم الثنائي، لا أعتقد أن هذه فكرة جيدة.سوف تعطي أرقام الفاصلة العائمة أخطاء بعد فترة.

إذا لم ينمو العدد بهذه الضخامة فيمكن استخدام الطريقة التالية:

public static long nCr (int m, int n) {
    long tmp = 1;
    int j = 2;
    int k = m-n;
    for(int i = m; i > k; i--) {
        tmp *= i;
        while(j <= n && tmp%j == 0) {
            tmp /= j++;
        }
    }
    while(j <= n) {
        tmp /= j++;
    }
    return tmp;
}

ولكن في هذه الحالة لا يزال هذا غير كاف.في هذه الحالة يمكن للمرء استخدام BigInteger هيكل في System.Numerics

public static BigInteger nCr (int m, int n) {
        BigInteger tmp = 1;
        int j = 2;
        int k = m-n;
        for(int i = m; i > k; i--) {
            tmp *= i;
            while(j <= n && tmp%j == 0) {
                tmp /= j++;
            }
        }
        while(j <= n) {
            tmp /= j++;
        }
        return tmp;
    }

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