Computer >> 컴퓨터 >  >> 프로그램 작성 >> C 프로그래밍

C 프로그램에서 배열이나 루프를 사용하지 않고 {1,2,3,…n}의 모든 하위 집합 인쇄

<시간/>

양의 정수 n이 주어지면 배열이나 루프를 사용하지 않고 {1, 2, 3, 4,… n} 집합의 모든 하위 집합을 인쇄해야 합니다.

임의의 숫자가 3이라고 말한 것처럼 {1 2 3}, {1 2}, {2 3}, {1 3}인 집합 {1, 2, 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번째 비트까지 계속됩니다.
  • 비트가 설정된 경우 해당 비트에 해당하는 숫자를 인쇄합니다.
  • 0이 될 때까지 num의 모든 값에 대해 위의 단계를 수행합니다.

간단한 예를 사용하여 설명된 접근 방식이 어떻게 작동하는지 자세히 이해합시다 -

입력 n =3이라고 가정하면 문제는 num =2^3 - 1 =7부터 시작됩니다.

  • 7의 이진 표현 ⇒
1 1 1
  • 해당 부분집합 ⇒
1 2 3

숫자에서 1 빼기; 숫자 =6

  • 6의 이진 표현 ⇒
1 1 0
  • 해당 부분집합 ⇒
1 2

숫자에서 1 빼기; 숫자 =5

  • 5의 이진 표현 ⇒
1 0 1
  • 해당 부분집합 ⇒
1
3

숫자에서 1 빼기; 숫자 =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 }{ }