กำหนดจำนวนเต็มบวก n เราต้องพิมพ์ชุดย่อยทั้งหมดของชุด {1, 2, 3, 4,... n} โดยไม่ต้องใช้อาร์เรย์หรือลูปใดๆ
เช่นเดียวกับที่เราให้ตัวเลขใดๆ ที่บอกว่า 3 วินาที เราต้องพิมพ์เซตย่อยทั้งหมดในเซต {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 และไปเรื่อยๆ จนถึงบิตที่ n ซึ่งแทน n
- พิมพ์ตัวเลขที่ตรงกับบิตหากมีการตั้งค่าไว้
- ทำตามขั้นตอนข้างต้นสำหรับค่า num ทั้งหมดจนกว่าจะเท่ากับ 0
มาทำความเข้าใจวิธีการที่ระบุไว้โดยละเอียดว่ามันทำงานอย่างไรโดยใช้ตัวอย่างง่ายๆ −
สมมติว่าอินพุต n =3 ดังนั้นปัญหาเริ่มต้นจาก num =2^3 - 1 =7
- การแทนไบนารีของ 7 ⇒
| 1 | 1 | 1 |
- ส่วนย่อยที่สอดคล้องกัน ⇒
| 1 | 2 | 3 |
ลบ 1 จาก num; num =6
- การแทนแบบไบนารีของ 6 ⇒
| 1 | 1 | 0 |
- ส่วนย่อยที่สอดคล้องกัน ⇒
| 1 | 2 | |
ลบ 1 จาก num; num =5
- การแทนไบนารีของ 5 ⇒
| 1 | 0 | 1 |
- ส่วนย่อยที่สอดคล้องกัน ⇒
| 1 | | 3 |
ลบ 1 จาก num; num =4
- การแทนไบนารีของ 4 ⇒
| 1 | 0 | 0 |
- ส่วนย่อยที่สอดคล้องกัน ⇒
| 1 | | |
ในทำนองเดียวกัน เราจะวนซ้ำจนถึง num =0 และพิมพ์ชุดย่อยทั้งหมด
อัลกอริทึม
Start
Step 1 → In function int subset(int bitn, int num, int num_of_bits)
If bitn >= 0
If (num & (1 << bitn)) != 0
Print num_of_bits - bitn
subset(bitn - 1, num, num_of_bits);
Else
Return 0
Return 1
Step 2 → In function int printSubSets(int num_of_bits, int num)
If (num >= 0)
Print "{ "
Call function subset(num_of_bits - 1, num, num_of_bits)
Print "}"
Call function printSubSets(num_of_bits, num - 1)
Else
Return 0
Return 1
Step 3 → In function int main()
Declare and initialize int n = 4
Call fucntionprintSubSets(n, (int) (pow(2, n)) -1)
Stop ตัวอย่าง
#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);
}
// Check the next bit
subset(bitn - 1, num, num_of_bits);
}
else
return 0;
return 1;
}
//function to print the subsets
int printSubSets(int num_of_bits, int num) {
if (num >= 0) {
printf("{ ");
// Printint the subsets corresponding to
// the binary representation of num.
subset(num_of_bits - 1, num, num_of_bits);
printf("}");
// recursively calling the function to
// print the next subset.
printSubSets(num_of_bits, num - 1);
}
else
return 0;
return 1;
}
//main program
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 }{ } 