打印{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: 3Output: { 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开始。
考虑具有n个位数的num的二进制表示形式。
从代表1的最左位开始,第二位代表2,依此类推,直到代表n的第n位。
打印与该位对应的数字(如果已设置)。
对num的所有值执行上述步骤,直到等于0。
让我们使用一个简单的示例来详细了解 方法的工作方式-
假设输入n = 3,那么问题就从num = 2 ^ 3-1 = 7开始
7⇒的二进制表示形式
1个 | 1个 | 1个 |
对应子集⇒
1个 | 2 | 3 |
从num减去1;num = 6
6的二进制表示⇒
1个 | 1个 | 0 |
对应子集⇒
1个 | 2 |
|
从num减去1;num = 5
5的二进制表示形式⇒
1个 | 0 | 1个 |
对应子集⇒
1个 | 3 |
从num减去1;num = 4
二进制表示形式4⇒
1个 | 0 | 0 |
对应子集⇒
1 |
同样,我们将迭代直到num = 0并打印所有子集。
算法
StartStep 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 }{ }
以上是 打印{1,2,3,…n}的所有子集,而无需在C程序中使用数组或循环 的全部内容, 来源链接: utcz.com/z/327275.html