مجموعات n من العناصر بواسطة k هي مركبات يمكن تشكيلها من عناصر n ، وتجميع عناصر k في كل اتصال ؛ بينما تختلف الروابط عن بعضها البعض فقط من خلال العناصر نفسها (لا يؤخذ الاختلاف في ترتيب ترتيبها في الاعتبار).
& nbsp؛
على سبيل المثال ، يمكن تشكيل المجموعات التالية من 3 عناصر (أ ، ب ، ج) (أ ، ب ، ج) 2 لكل عنصر: أب ، أ ، ق.
& nbsp؛
يُشار إلى عدد جميع التركيبات الممكنة التي يمكن تكوينها من عناصر n بواسطة k بالرمز  & nbsp؛ وتحسب بالصيغة: نبسب ؛
هناك طريقتان للعثور على عدد التركيبات & nbsp؛ & nbsp؛
1. ابحث عن n !، k !، (n & ndash؛ k)! ووفقًا للصيغة أعلاه ، نحسب الكمية ، ولكن من & ndash؛ بسبب الفائض المحتمل ، يمكن استخدام هذه الطريقة مع n & lt؛ = 12.
& nbsp؛
2. مع البرمجة الديناميكية.
& nbsp؛
سيبدو DP مثل مثلث باسكال ، مع وجود واحد في الأعلى والحواف ، وكل رقم يساوي مجموع العددين أعلاه.
دالة تحسب عدد التركيبات باستخدام البرمجة الديناميكية في O (n ^ 2):
int C ( int n، int ك)
{
متجه & lt؛ vector & lt؛ int & gt؛ & GT. dp (n + 1، vector & lt؛ int & gt؛ (n + 1، 1))؛ // إنشاء مصفوفة dp بالحجم (n + 1، n + 1)
لـ ( int i = 0؛ i & lt؛ = n؛ i ++) // املأ السطر الأول من المصفوفة
{
لـ ( int j = 1؛ j & lt؛ i؛ j ++)
{
dp [i] [j] = dp [i - 1] [j - 1] + dp [i - 1] [j] ؛ // إعادة حساب (i؛ j) الموضع من خلال (i - 1؛ j - 1) و (i - 1؛ j)
}
}
إرجاع dp [n] [k]؛ // قيمة الإرجاع
}
|