عدد المجموعات الممكنة

Question

ما عدد المجموعات الممكنة للمتغيرات a,b,c,d,e الممكنة إذا علمت أن:

a+b+c+d+e = 500

وأنها كلها أعداد صحيحة و >= 0، لذلك أعلم أنها محدودة.

Answer 1

@ تورلاك، @ جيسون كوهين:تعتبر العودية فكرة سيئة هنا ، لأن هناك "مشكلات فرعية متداخلة". أي إذا اخترت a مثل 1 و b مثل 2, ، ثم يتبقى لديك 3 متغيرات يجب أن يصل مجموعها إلى 497؛تصل إلى نفس المشكلة الفرعية عن طريق الاختيار a مثل 2 و b مثل 1.(إن عدد مثل هذه المصادفات ينفجر مع تزايد الأعداد).

الطريقة التقليدية لمهاجمة مثل هذه المشكلة هي البرمجة الديناميكية:قم ببناء جدول من أسفل إلى أعلى لحلول المشكلات الفرعية (بدءًا بـ "كم عدد مجموعات متغير واحد تضيف ما يصل إلى 0؟") ثم البناء من خلال التكرار (الحل لـ "كم عدد مجموعات من متغير واحد" ن المتغيرات تضيف ما يصل إلى ك؟" هو مجموع الحلول لسؤال "كم عدد المجموعات من ن-1 المتغيرات تضيف ما يصل إلى ي؟" مع 0 <= ي <= ك).

public static long getCombos( int n, int sum ) {
  // tab[i][j] is how many combinations of (i+1) vars add up to j
  long[][] tab = new long[n][sum+1];
  // # of combos of 1 var for any sum is 1
  for( int j=0; j < tab[0].length; ++j ) {
    tab[0][j] = 1;
  }
  for( int i=1; i < tab.length; ++i ) {
    for( int j=0; j < tab[i].length; ++j ) {
      // # combos of (i+1) vars adding up to j is the sum of the #
      // of combos of i vars adding up to k, for all 0 <= k <= j
      // (choosing i vars forces the choice of the (i+1)st).
      tab[i][j] = 0;
      for( int k=0; k <= j; ++k ) {
        tab[i][j] += tab[i-1][k];
      }
    }
  }
  return tab[n-1][sum];
}

$ time java Combos
2656615626

real    0m0.151s
user    0m0.120s
sys 0m0.012s

Answer 2

الجواب على سؤالك هو 2656615626.

إليك الكود الذي يولد الإجابة:

public static long getNumCombinations( int summands, int sum )
{
    if ( summands <= 1 )
        return 1;
    long combos = 0;
    for ( int a = 0 ; a <= sum ; a++ )
        combos += getNumCombinations( summands-1, sum-a );
    return combos;
}

في حالتك، summands هو 5 و sum هو 500.

لاحظ أن هذا الرمز بطيء.إذا كنت بحاجة إلى السرعة، قم بتخزين النتائج من summand,sum أزواج.

أفترض أنك تريد الأرقام >=0.إذا أردت >0, ، استبدل تهيئة الحلقة بـ a = 1 وحالة الحلقة مع a < sum.أفترض أيضًا أنك تريد التباديل (على سبيل المثال. 1+2+3+4+5 زائد 2+1+3+4+5 إلخ).يمكنك تغيير الحلقة إذا أردت a >= b >= c >= d >= e.

Answer 3

لقد قمت بحل هذه المشكلة لوالدي منذ بضعة أشهر...مدد لاستخدامك.تميل هذه إلى أن تكون مشاكل لمرة واحدة لذا لم أختار أكثر الأشياء القابلة لإعادة الاستخدام ...

أ+ب+ج+د = المجموع

أنا = عدد المجموعات

        for (a=0;a<=sum;a++)
        {
            for (b = 0; b <= (sum - a); b++)
            {
                for (c = 0; c <= (sum - a - b); c++)
                {
                    //d = sum - a - b - c;
                    i++
                }
            }
        }

Answer 4

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

مسائل النظام
إذا كان الترتيب مهمًا، فإن أي حل يحتاج إلى السماح بظهور الصفر لأي من المتغيرات؛وبالتالي فإن الحل الأكثر مباشرة هو كما يلي:

public class Combos {
    public static void main() {
        long counter = 0;

        for (int a = 0; a <= 500; a++) {
            for (int b = 0; b <= (500 - a); b++) {
                for (int c = 0; c <= (500 - a - b); c++) {
                    for (int d = 0; d <= (500 - a - b - c); d++) {
                        counter++;
                    }
                }
            }
        }
        System.out.println(counter);
    }
}

الذي يعود 2656615626.

النظام لا يهم
إذا كان الترتيب لا يهم، فإن الحل ليس أصعب بكثير حيث تحتاج فقط إلى التأكد من أن الصفر غير ممكن ما لم يتم العثور على المجموع بالفعل.

public class Combos {
    public static void main() {
        long counter = 0;

        for (int a = 1; a <= 500; a++) {
            for (int b = (a != 500) ? 1 : 0; b <= (500 - a); b++) {
                for (int c = (a + b != 500) ? 1 : 0; c <= (500 - a - b); c++) {
                    for (int d = (a + b + c != 500) ? 1 : 0; d <= (500 - a - b - c); d++) {
                        counter++;
                    }
                }
            }
        }
        System.out.println(counter);
    }
}

الذي يعود 2573155876.

Answer 5

إحدى طرق النظر إلى المشكلة هي كما يلي:

أولاً، يمكن أن تكون a أي قيمة من 0 إلى 500.ثم إذا تبع ذلك b+c+d+e = 500-a.وهذا يقلل من المشكلة بمتغير واحد.كرر حتى الانتهاء.

على سبيل المثال، إذا كانت a تساوي 500، فإن b+c+d+e=0 مما يعني أنه في حالة a = 500، هناك مجموعة واحدة فقط من قيم b وc وd وe.

إذا كانت a تساوي 300، فإن b+c+d+e=200، وهي في الواقع نفس المشكلة الأصلية، مع تقليلها بمتغير واحد فقط.

ملحوظة:وكما يشير كريس، فهذه طريقة فظيعة لمحاولة حل المشكلة فعليًا.

نص الرابط

Answer 6

إذا كانت أعدادا حقيقية فهي لا نهائية..وإلا فإنه أصعب قليلا.

(حسنًا، بالنسبة لأي تمثيل حاسوبي لعدد حقيقي، سيكون هناك عدد محدود...لكنها ستكون كبيرة!)

Answer 7

لها صيغ عامة، إذا
أ + ب + ج + د = ن
ثم سيكون عدد الحلول التكاملية غير السالبة C(N + number_of_variable - 1, N)

Answer 8

@ كريس كونواي الإجابة صحيحة.لقد اختبرت باستخدام رمز بسيط مناسب للمبالغ الصغيرة.

                    long counter = 0;
            int sum=25;

            for (int a = 0; a <= sum; a++) {
                for (int b = 0; b <= sum ; b++) {
                    for (int c = 0; c <= sum; c++) {
                        for (int d = 0; d <= sum; d++) {
                             for (int e = 0; e <= sum; e++) {
                           if ((a+b+c+d+e)==sum) counter=counter+1L;

                             }
                       }
                    }
                }
            }
            System.out.println("counter e "+counter);

Answer 9

الجواب في الرياضيات هو 504!/(500!* 4!).

رسميًا، بالنسبة لـ x1+x2+...xk=n، عدد مجموعة الأعداد غير السالبة x1،...xk هو معامل ذو الحدين:(ك-1)-مجموعة من العناصر التي تحتوي على (ن+ك-1).

الحدس هو اختيار (k-1) نقطة من (n+k-1) واستخدام عدد النقاط بين نقطتين مختارتين لتمثيل رقم في x1,..xk.

آسف بشأن إصدار الرياضيات السيئ لوقتي الأول في الإجابة على Stack Overflow.

Just a test for code block

Just a test for code block

    Just a test for code block

Answer 10

بما في ذلك السلبيات؟لانهائي.

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

كونه x النتيجة النهائية ، سيكون نطاق A من 0 إلى x ، سيكون نطاق B من 0 إلى (x - a) ، سيكون نطاق C من 0 إلى (x - a - b) ، و وهكذا حتى e.

الجواب هو مجموع كل تلك الاحتمالات.

أحاول العثور على صيغة أكثر مباشرة على Google، لكنني حقًا منخفض في Google-Fu اليوم...