打印{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开始。

  • 考虑具有n个位数的num的二进制表示形式。

  • 从代表1的最左位开始,第二位代表2,依此类推,直到代表n的第n位。

  • 打印与该位对应的数字(如果已设置)。

  • 对num的所有值执行上述步骤,直到等于0。

让我们使用一个简单的示例来详细了解 方法的工作方式-

假设输入n = 3,那么问题就从num = 2 ^ 3-1 = 7开始 

  • 7⇒的二进制表示形式

1个1个1个
  • 对应子集⇒

1个23

从num减去1;num = 6

  • 6的二进制表示⇒

1个1个0
  • 对应子集⇒

1个2

从num减去1;num = 5

  • 5的二进制表示形式⇒

1个01个
  • 对应子集⇒

1个
3

从num减去1;num = 4

  • 二进制表示形式4⇒

1个00
  • 对应子集⇒

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 }{ }

以上是 打印{1,2,3,…n}的所有子集,而无需在C程序中使用数组或循环 的全部内容, 来源链接: utcz.com/z/327275.html

回到顶部