명품 C언어 프로젝트 4.2장 연습문제

[1번 문제]

/*

집합 A와 집합 B에 대한 곱집합 AXB를 출력하는 프로그램을 작성한다

*/

#include <stdio.h>

 

int multiply(int a[], int s_a, int b[], int s_b, int result[]);

 

int main(void)

{

        int a[] = { 1, 3, 5, 7 };

        int b[] = { 3, 5, 8, 9, 10 };

        int result[20];

        int count, i, size_a, size_b;

        size_a = sizeof(a) / sizeof(int);

        size_b = sizeof(b) / sizeof(int);

        count = multiply(a, size_a, b, size_b, result);

        for (i = 0; i < count; i++)

               printf("%d ", result[i]);

        printf("\n");

        return 0;

}

 

int multiply(int a[], int s_a, int b[], int s_b, int result[])

{

        int i, j, cnt1 = 0, cnt2 = 0;

        int temp;

        for (i = 0; i < s_a; i++)

        {

               for (j = 0; j < s_b; j++)

               {

                       result[cnt1++] = a[i] * b[j];

               }

        }

        for (i = 0; i < cnt1; i++)

        {

               temp = result[i];

               for (j = i + 1; j < cnt1; j++) //중복검사

               {

                       if (temp == result[j] && result[j] != 0)

                       {

                              result[j] = 0;

                       }

               }

        }

        for (i = 0; i < cnt1; i++)

               if (result[i] != 0)

                       result[cnt2++] = result[i];

        return cnt2;

}

[2번 문제]

/*

합집합과 차집합을 계산하는 프로그램을 작성한다

*/

#include <stdio.h>

 

int union_set(int a[], int s_a, int b[], int s_b, int result[]);

int difference(int a[], int s_a, int b[], int s_b, int result[]);

 

int main(void)

{

        int a[] = { 1, 3, 5 };

        int b[] = { 3, 5, 8, 9 };

        int result1[20], result2[20];

        int count1, count2, size_a, size_b;

        size_a = sizeof(a) / sizeof(int);

        size_b = sizeof(b) / sizeof(int);

        count1 = union_set(a, size_a, b, size_b, result1);

        count2 = difference(a, size_a, b, size_b, result2);

        printf("합집합\n");

        for (int i = 0; i < size_a+size_b-count1; i++)

               printf("%d ", result1[i]);

        printf("\n");

 

        printf("차집합\n");

        for (int i = 0; i < size_a-count2; i++)

               printf("%d ", result2[i]);

        printf("\n");

        return 0;

}

 

int union_set(int a[], int s_a, int b[], int s_b, int result[])

{

        int i, j, cnt1 = 0, cnt2 = 0;

        for (i = 0; i < s_a; i++)

               result[i] = a[i];

        for (i = 0; i < s_b; i++)

               result[s_a + i] = b[i];

        for (i = 0; i < s_a; i++)

               for (j = 0; j < s_b; j++)

               {

                       if (a[i] == b[j])

                       {

                              result[s_a + j] = 0;

                              cnt1++;

                       }

               }

        for (i = 0; i < s_b; i++)

               if (result[s_a + i] != 0)

                       result[s_a + cnt2++] = result[s_a + i];

        return cnt1;

}

                             

int difference(int a[], int s_a, int b[], int s_b, int result[])

{

        int i, j, cnt1 = 0, cnt2 = 0;

        for (i = 0; i < s_a; i++)

               result[i] = a[i];

        for (i = 0; i < s_a; i++)

               for (j = 0; j < s_b; j++)

                       if (a[i] == b[j])

                       {

                              result[i] = 0;

                              cnt1++;

                       }

        for (i = 0; i < s_a; i++)

               if (result[i] != 0)

                       result[cnt2++] = result[i];

        return cnt1;

}

 

 

[3번 문제]

/*

세 개 이상의 집합에 대해서 합집합과 교집합을 계산하는 프로그램을 작성합니다

*/

#include <stdio.h>

 

int union_set3(int a[], int s_a, int b[], int s_b, int c[], int s_c, int result[]);

int intersection3(int a[], int s_a, int b[], int s_b, int c[], int s_c, int result[]);

 

int main(void)

{

        int a[] = { 1, 2, 3, 4 };

        int b[] = { 1, 3, 5, 7 };

        int c[] = { 1, 2, 4, 8 };

        int result[20];

        int size_a, size_b, size_c;

        int cnt1, cnt2;

 

        size_a = sizeof(a) / sizeof(int);

        size_b = sizeof(b) / sizeof(int);

        size_c = sizeof(c) / sizeof(int);

 

        cnt1 = union_set3(a, size_a, b, size_b, c, size_c, result);

 

        printf("합집합\n");

        for (int i = 0; i < cnt1; i++)

               printf("%d ", result[i]);

        printf("\n");

 

        cnt2 = intersection3(a, size_a, b, size_b, c, size_c, result);

        printf("교집합\n");

        for (int i = 0; i < cnt2; i++)

               printf("%d ", result[i]);

        printf("\n");

 

        return 0;

}

 

int union_set3(int a[], int s_a, int b[], int s_b, int c[], int s_c, int result[])

{

        int cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0, cnt5=0;

        int idx = 0;

 

        for (int i = 0; i < s_a; i++)

               result[i] = a[i];

        for (int i = 0; i < s_b; i++)

               result[i + s_a] = b[i];

        for (int i = 0; i < s_c; i++)

               result[i + s_a + s_b] = c[i]; //일단 다 넣는다

 

 

        for (int i = 0; i < s_a; i++)

        {

               for (int j = 0; j < s_b; j++)

               {

                       if (a[i] == b[j])

                       {

                              result[s_a + j] = 0;

                              cnt1++;

                       }

               }

        }

 

        for (int i = 0; i < s_b; i++)

        {

               for (int j = 0; j < s_c; j++)

                       if (b[i] == c[j])

                       {

                              result[s_a + s_b + j] = 0;

                              cnt2++; //b와 c가 겹치는 갯수

                       }

        }

 

        for (int i = 0; i < s_a; i++)

        {

               for (int j = 0; j < s_c; j++)

               {

                       if (a[i] == c[j])

                       {

                              result[s_a + s_b + j] = 0;

                              cnt3++; //a와 c가 겹치는 갯수

                       }

               }

        }

 

        for (int i = 0; i < s_a; i++)

        {

               for (int j = 0; j < s_b; j++)

               {

                       for (int k = 0; k < s_c; k++)

                       {

                              if (a[i] == b[j] && a[i] == c[k] && b[j] == c[k])

                                      cnt4++; //a와 b와 c 다 겹치는 수는 다시 더한다

                       }

               }

        }

 

        cnt5 = s_a + s_b + s_c - cnt1 - cnt2 - cnt3 + cnt4;

 

        for (int i = 0; i < s_b + s_c; i++)

               if (result[s_a + i] != 0)

                       result[s_a + idx++] = result[s_a + i]; //겹치지 않는 숫자만 배열에 넣는다

 

        return cnt5;

}

 

int intersection3(int a[], int size_a, int b[], int size_b, int c[], int size_c, int result[])

{

        int cnt = 0;

 

        for (int i = 0; i < size_a; i++)

        {

               for (int j = 0; j < size_b; j++)

               {

                       for (int k = 0; k < size_c; k++)

                       {

                              if (a[i] == b[j] && b[j] == c[k] && a[i] == c[k]) //2개 집합의 교집합을 구하는 것과 별다를게 없다

                                      result[cnt++] = a[i];

                       }

               }

        }

 

        return cnt;

}

[4번 문제]

/*

집합 A에 대해 모든 부분 집합류(멱집합, power set)를 출력하는 프로그램을 작성한다.

예를 들어 집합 A가 A={1, 2, 3}일 때 멱집합 PA는 8(2^3)개의 원소를 가지며,

다음과 같다. 다음에는 {}는 공집합을 의미한다

 

PA={{}, [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]}

*/

#include <stdio.h>

// 부분집합 출력.

void print_subset(int set[], int n) {

        int i;

        // 부분집합의 원소 출력.

        printf(",{");

        for (i = 0;i<n - 1;++i)

               printf("%d,", set[i]);

        printf("%d}", set[n - 1]);

}

 

// c(n,r)=c(n-1,r-1)+c(n-1,r) 을 이용한 부분집합 구하기

// m은 구해야할 부분집합의 크기

// r은 현재까지 구한 부분집합의 갯수

void comb(int subset[], int n, int k, int m, int r) {

 

        // 만약 남아있는 원소의 갯수가 구해야할 원소보다 작거나

        if (n - k<m - r) return;

 

        // 혹은 이미 모든 원소를 다 선택했다면 순환호출을 멈춘다.

        // 모든 원소를 다 구했을 경우 즉 r==m일 때만 출력을 해준다.

        if (r == m) {

               print_subset(subset, m);

               return;

        }

 

        // 만약 앞으로 더 구해야할 원소가 남았고, 또 가능하다면

        // k번째 원소를 선택한 경우와 선택하지 않은 두가지 경우를 각각

        // 순환호출로 돌려준다.

 

        // subset의 r번째 원소로 k번째 set의 원소를 넣어 준다.

        subset[r] = k + 1;

 

        // 지금까지 선택한 원소가 r개 였고, 지금 1개 선택했으므로 r+1개를 선택하였다.

        comb(subset, n, k + 1, m, r + 1);

 

        // k번째 원소를 선택하지 않았다. 여전히 r개를 가지고 호출을 한다.

        // 위에서 넣었던 r번째 원소는 다음 순환호출 때 다른 값이 들어 가기 때문에

        // 걱정하지 않아도 좋다.

        comb(subset, n, k + 1, m, r);

}

int main() {

 

        // subset는 r개의 원소를 뽑아넣은 부분집합이다.

        int subset[32] = { 0, };

        int i, n, r;

 

        // set의 크기를 입력받는다. 원소는 1부터 n까지 이다.

        printf("최대값 : ");

        scanf("%d", &n);

 

        printf("[{}");

        for (i = 1;i<n + 1;++i)

               comb(subset, n, 0, i, 0);

        printf("]");

        printf("\n");

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 명품 C언어 프로젝트 안기수 저, http://blog.daum.net/here8now/262

*4번 문제는 블로그에 게시된 코드를 그대로 가져왔습니다(멱집합에 대한 이해는 아직 부족한 것 같습니다)

멱집합 참고할만한 사이트 http://swlock.blogspot.kr/2016/03/power-set.html