출력 {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} {}.

하지만 우리는 어떤 반복문이나 배열도 사용하지 않고 이 작업을 수행해야 합니다. 따라서 이러한 문제를 해결하는 유일한 방법은 배열이나 반복문을 사용하지 않고 재귀만을 사용하는 것입니다.

예제

입력:　}　3
출력:　{　1　2　3　}{　1　2　}{　1　3　}{　1　}{　2　3　}{　2　}{　3　}{　}
설명: 점집합은 {1　2　3그로부터 우리는 점집합의 부집합을 찾을 수 있습니다
입력:　}　4
출력:　{　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 -10부터 시작합니다.

• n비트를 가진 num의 2진 표현 형식을 고려합니다

• 대표1의 가장 왼쪽 비트에서 시작하여 두 번째 비트는2그리고 이어서 n의 n번째 비트를 대표하는까지 계속합니다

• 그리고 해당 비트에 해당하는 숫자를 출력합니다(설정된 경우)

• num의 모든 값에 대해 0까지 반복하여 위의 단계를 수행합니다

이 방법의 작동 방식을 더 잘 이해하기 위해 간단한 예제를 사용해 보겠습니다-

입력 값 n을 가정하겠습니다 3그럼 num = 2 ^ 3-1 = 7시작　

• 7⇒의 2진 표현 형식

• 대응 부분집합⇒

num에서1；num = 6

• 6의 2진 표현⇒

• 대응 부분집합⇒

num에서1；num = 5

• 5의 2진 표현 형식⇒

• 대응 부분집합⇒

num에서1；num = 4

• 2진 표현 형식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
　　　　　　　　　"{ "을 출력
　　　　　　　　　function subset(num_of_bits　-　1, num, num_of_bits)
　　　　　　　　　"}"을 출력
　　　　　　　　　function printSubSets(num_of_bits, num　-　1)
　　　　　　다른 경우
　　　　　　　　　0을 반환
　　　　　　반환　1
　　　단계　3　→ 함수 int main() 내에서
　　　　　　int n을 선언하고 초기화합니다　4
　　　　　　fucntion printSubSets(n, (int) (pow(2,　n))　-1)
정지

예제

#include <stdio.h>
#include <math.h>
//　이 함수는 재귀적으로 다음과 같이 출력합니다
//　2진수에 해당하는 부분집합
//　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　}{　}