طباعة جميع المجموعات الفرعية لـ {1,2,3،…n} دون استخدام مصفوفة أو دورة في برنامج C

للحصول على مجموعة من جميع المجموعات الفرعية لعدد صحيح n دون استخدام أي قوائم أو حلقات، يجب علينا طباعة جميع المجموعات الفرعية للعينة {1,2,3,4،... n}.

مثلما نقول لعدد أي 3 s، يجب علينا طباعة جميع المجموعات الفرعية للعينة {1،2،3}، والتي ستكون {1 2 3}، {1 2}، {2 3}، {1 3}، {1}، {2}، {3} {}.

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

النموذج

Input:　3
Output:　{　1　2　3　}{　1　2　}{　1　3　}{　1　}{　2　3　}{　2　}{　3　}{　}
Explanation:　The　set　will　be　{1　2　3}　from　which　we　will　find　the　subsets
Input:　4
Output:　{　1　2　3　4　}{　1　2　3　}{　1　2　4　}{　1　2　}{　1　3　4　}{　1　3　}{　1　4　}{　1　}{　2　3　4　}{　2　3　}{　2　4　}{　2　}{　3　4　}{　3　}{　4　}{　}

الطريقة التي سنستخدمها لحل المشكلة المقدمة-

• ابدأ من num = 2 ^ n -1 إلى 0.

• تأمل في تمثيل num الثنائي الذي يحتوي على n من الأرقام.

• ابدأ من أكثر موضع يمثل 1، الثاني يمثل 2، وهكذا حتى يمثل nth الموضع nth.

• اطبع الرقم الذي يمثل هذا الموضع (إذا كان معينًا).

• تكرر الخطوات المذكورة أعلاه لكل قيمة num حتى يصبح يساوي 0.

لنستخدم مثالاً بسيطاً لفهم كيفية عمل هذه الطريقة-

افترض أن n = 3، فإن المشكلة تبدأ من num = 2 ^ 3-1 = 7　

• تمثيل العدد 7⇒ في شكل تمثيل ثنائي

• المجموعة الفرعية الم对应⇒

استناداً إلى num قم بإزالة 1؛num = 6

• تمثيل العدد 6 في النظام الثنائي⇒

• المجموعة الفرعية الم对应⇒

من num نحسب 1؛ num = 5

• شكل ثنائي 5⇒

• المجموعة الفرعية الم对应⇒

من num نحسب 1؛ num = 4

• شكل ثنائي 4⇒

• المجموعة الفرعية الم对应⇒

بالمثل، سنقوم بالتكرار حتى num = 0 ونطبع جميع المجموعات الفرعية.

الخوارزمية

البداية
　　　الخطوة 1 → داخل وظيفة int subset(int bitn, int num, int num_of_bits)
　　　إذا bitn >= 0
　　　　　　إذا (num & (1 << bitn)) != 0
　　　　　　　　　اطبع num_of_bits - bitn
　　　　　　　　　subset(bitn - 1, num, num_of_bits);
　　　　　　آخر
　　　　　　　　　عدد 0
　　　　　　عدد 1
　　　الخطوة 2 → داخل وظيفة int printSubSets(int num_of_bits, int num)
　　　　　　إذا (num >= 0)
　　　　　　　　　اطبع "{ "
　　　　　　　　　اطباق وظيفة subset(num_of_bits - 1, num, num_of_bits)
　　　　　　　　　اطبع "}"
　　　　　　　　　اطباق وظيفة printSubSets(num_of_bits, num - 1)
　　　　　　آخر
　　　　　　　　　عدد 0
　　　　　　عدد 1
　　　الخطوة 3 → داخل وظيفة int main()
　　　　　　إعلان وتحديد int n = 4
　　　　　　اطباق وظيفة printSubSets(n, (int) (pow(2, n)) - 1)
توقف

النموذج

#include <stdio.h>
#include <math.h>
// This function recursively prints the
// subset corresponding to the binary
// representation of num.
int subset(int bitn, int num, int num_of_bits) {
　　　if (bitn >= 0) {
　　　　　　// Print number in given subset only
　　　　　　// if the bit corresponding to it
　　　　　　// is set in num.
　　　　　　if ((num & (1 << bitn)) != 0) {
　　　　　　　　　printf("%d	", num_of_bits - bitn);
　　　　　　}
　　　　　　//تحقق من البت التالي
　　　　　　subset(bitn - 1, num, num_of_bits);
　　　}
　　　else
　　　　　　return 0;
　　　　　　return 1;
}
//دالة لطباعة المجموعات
int printSubSets(int num_of_bits, int num) {
　　　if (num >= 0) {
　　　　　　printf("{ ");
　　　　　　//طباعة المجموعات المترابطة
　　　　　　//ممثلة الثنائية للعدد
　　　　　　subset(bitn - 1, num, num_of_bits);
　　　　　　printf("}");
　　　　　　//دعوة الدالة بشكل متكرر
　　　　　　//طباعة المجموعة التالية
　　　　　　printSubSets(num_of_bits, num - 1);
　　　}
　　　else
　　　　　　return 0;
　　　　　　return 1;
}
//برنامج رئيسي
int main() {
　　　int n = 4;
　　　printSubSets(n, (int) (pow(2, n)) - 1);
}

النتائج

{ 1 2 3 4 } { 1 2 3 } { 1 2 4 } { 1 2 } { 1 3 4 } { 1 3 } { 1 4 } { 1 } { 2 3 4 } { 2 3 } { 2 4 } { 2 } { 3 4 } { 3 } { 4 } }