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

두비니

·

2020. 5. 1. 02:17

 

 

 

 

 

 

 

 

1장 연습문제-3번(Boolean출력) 풀이입니다.


3. n개의 Boolean 변수 x1, x2, x3, ... ,xn이 주어졌을 때, 이 변수들이 가질 수 있는 가능한 모든 진리 값의 조합을 구하고자 한다. 예를 들어 n=2이면 <true, true>, <true, false>, <false, true>, <false, false>와 같은 네 가지 경우가 존재한다. 이를 구하는 C프로그램을 작성하여라.


 

정말 '이 문제를 어떻게 풀면 좋을까'를 조금 생각해보면

Boolean은 true혹은 false의 값만 가능하기 때문에 전체 경우의 수는 2^n개입니다.

이 경우들을 어떻게 출력하면 좋을까 생각했는데, 수형도를 이용하는 방법으로 구현을 해보았습니다.

 

일단 위 경우는 n=3일때 가능한 수형도입니다. 첫 번째 경우의 수부터 여덟번째 경우의 수까지 순서대로 출력하면 될 것 같네요! 이런 수형도의 꼴을 출력시킬 때는 재귀함수의 꼴로 구현을 하면 좋습니다. 다음은 구현 코드입니다.

 

#include <stdio.h>
#include <math.h>		//pow함수 쓰기위해서

void TruthValueSet(int* list, int n, int size);
void print(int* list, int size);

int main() {
	int n, *list;

	printf("변수의 개수를 입력하시오: ");
	scanf(" %d", &n);
	list = (int*)malloc(sizeof(int)*n);

	for (int i = 0; i < n; i++)
		list[i] = 0;

	printf("가능한 총 경우의 수는 %.0f개이며, \n", pow(2.0, (double)n));
	printf("가능한 경우의 수는 다음과 같습니다.\n");

	TruthValueSet(list, n, n);

	return 0;
}

void TruthValueSet(int* list, int n, int size) {
	if (n == 0)
		print(list, size);
	else {
		TruthValueSet(list, n - 1, size);
		list[n - 1] = 1;
		TruthValueSet(list, n - 1, size);
		list[n - 1] = 0;
	}
}

void print(int* list, int size) {
	int i = size - 1;
	printf("< ");

	for (; i >= 0; i--) {
		if (list[i] == 0)
			printf("FALSE ");
		else
			printf("TRUE ");
	}
	printf(">\n");
}

 

우선 TruthValueSet이라는 함수를 구현했는데, 이는 true와 false를 각 케이스에 맞춰 지정해 줄 수 있도록 해주었고, 다 설정을 해준 후 출력시키는 함수를 따로 구현했습니다.

지금 다 해놓고 생각해보니 그냥 bool형태로 list를 구현하고 출력시켰어도 됐었겠네요. 아무튼 상관은 없습니다.

 

잘 모르겠는 사람은 저 TruthValueSet이라는 함수 대신에 정말 함수에 해당하는 코드 부분을 써내려가보세요. 노가다지만 그렇게 쓰는게 제일 이해하는데 직빵입니다.

 

 

 

 

재귀함수식으로 코드를 작성하는거는 많이 해서 익숙해지는 방법이 최선이기때문에 하노이타워나 피보나치수열 구현, 팩토리얼 구현 등등으로 연습하는것도 좋을 것 같습니다.