[C로 쓴 자료구조론] 1장 연습문제-12번(멱급수) 풀이

 

 

 

 

 

 

 

 

12번 문제

 

---

S가 n개의 원소로 된 집합일 때 S의 멱집합(powerset)은 모든 가능한 S의 부분 집합이다. 즉, S = {a, b, c}이면 powerset(S) = { {}, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c} } 이다.

powerset(S)를 계산하는 순환 함수를 계산하여라.

 

---

 

 

문제가 약간 1장 3번같은 느낌이네요.

이 풀이도 참고하면 좋을 것 같습니다.

https://dokhakdubini.tistory.com/186

[C로 쓴 자료구조론] 1장 연습문제-3번(Boolean출력) 풀이

 

 

 

 

 

아무튼 같은 이론으로 진행하게 되면, 

 

 

#include <stdio.h>

void powerset(char list[], int n, int len);

int main() {
	char list[] = { 'a', 'b', 'c', 'd' };
	int i;
	int len = sizeof(list) / sizeof(char);

	printf("{ ");

	for (i = 0; i < len; i++) {
		printf("%c ", list[i]);
	}

	printf("}");

	printf("의 멱급수는 다음과 같습니다: \n");

	powerset(list, -1, len);

	return 0;
}

void powerset(char list[], int n, int len) {
	int i, j;

	if (n == -1) {
		printf("{} ");
		powerset(list, 1, len);
	}
	else if (n == 1) {
		for (i = 0; i < len; i++) {
			printf("{ %c }", list[i]);
		}
		powerset(list, n + 1, len);
	}
	else if (n == len) {
		printf("{ ");
		for (i = 0; i < len; i++) {
			printf("%c ", list[i]);
		}
		printf("}");
		printf("\n");
	}
	else {
		for (i = 0; i < len; i++) {
			printf("{ ");
			for (j = 0; j < n; j++) {
				printf("%c ", list[(i + j) % len]);
			}
			printf("}");
		}

		powerset(list, n + 1, len);
	}
}

 

이런식으로 코드를 짜주면 됩니다.

 

 

 

 

 

 

 

이렇게 배열을 늘려줘도 상관없습니다.

 

 

1.3절 연습문제가 끝이 났네요. 끝!