Module: مجموعات


Problem

1 /3


عدد التركيبات

Theory Click to read/hide

مجموعات 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  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]؛  // قيمة الإرجاع 
}

Problem

أرقام معطاة n و k ( \ (0 & lt؛ = k & lt؛ = n \) ، & nbsp؛ \ (0 & lt؛ n & lt؛ = 12 \) ) حساب عدد التركيبات & nbsp؛ & nbsp؛ \ (C_n ^ k \) .
نبسب ؛

نبسب ؛

أمثلة <الجسم>
# إدخال الإخراج
1 2 8 28