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

[1번 문제]

/*

정수 123에 대해 순열은 다음과 같이 3!=3*2*1=6개가 있습니다.

이를 확장하여 입력된 임의의 숫자 n에 대해 순열을 출력하는 프로그램을 작성합니다.

단, 같은 숫자는 입력하지 않는다고 가정합니다

*/

#include <stdio.h>

 

void permutation(int *arr, int start); //순열

 

int main(void)

{

        int arr[3];

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

               arr[i] = i+1; //123

        permutation(arr, 0); //첫번째 인덱스부터 시작

        return 0;

}

 

void permutation(int *arr, int start)

{

        if(start < 2)

        {

               for (int i = start; i <= 2; i++)

               {

                       int temp = arr[start];

                       arr[start] = arr[i];

                       arr[i] = temp;

                       permutation(arr, start+1); //시작위치를 바꾼 상태에서 다시 순열

                       //다시 원래대로

                       temp = arr[start];

                       arr[start] = arr[i];

                       arr[i] = temp;

               }

        }

        else

        {

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

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

               printf("\n");

        }

}

[2번 문제]

/*

1~9 사이의 정수 중에서 4개를 택하여 만들 수 있는 모든 경우의 숫자를 출력하는 프로그램을 작성하시오

*/

#include <stdio.h>

#include <stdlib.h>

 

int *Setn; //순열과 조합을 생성할 집합을 만들 int 포인터형 전역 변수 Setn

int *Copy; //Setn 변수를 복사(저장)할 int 포인터형 전역 변수 Copy 선언

 

int Fact(int x); //x 팩토리얼 개수를 출력하는 함수 Fact

void Swap(int *a, int *b); //순열과 조합을 구할때 원소 위치를 바꿔줄 함수 Swap

void Permutation(int *Setn, int *Copy, int n, int r, int term); //nPr 순열을 만드는 함수

void Print_Permutation(int *Setn, int n); //순열 출력을 위한 함수

 

int main(void)

{

        int num[4] = { 0, };

        Setn = (int*)malloc(sizeof(int)*4); //배열 Setn을 사용자로부터 입력받은 n 크기만큼 동적할당

        Copy = (int*)malloc(sizeof(int)*4);

 

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

        {

               printf("1~9 사이 숫자를 고르시오(중복X): ");

               scanf("%d", &num[i]);

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

               {

                       while (num[j] == num[i])

                       {

                              printf("중복된 숫자 발견!\n");

                              printf("다시입력하세요: ");

                              scanf("%d", &num[i]);

                       }

               }

               Setn[i] = num[i];

        }

 

        printf("순열(총 %d개): ", Fact(4)); //순열의 개수를 팩토리얼로 계산

        Permutation(Setn, Copy, 4, 4, 4);

        printf("\n");

        free(Setn);

        free(Copy);

        return 0;

}

 

int Fact(int x)

{

        if (x == 0)

               return 1;

        else

               return x*Fact(x - 1);

}

 

void Swap(int *a, int *b)

{

        int temp = *a;

        *a = *b;

        *b = temp;

}

 

void Permutation(int *Setn, int *Copy, int n, int r, int term)

{

        if (r == 0)

        {

               Print_Permutation(Copy, term);

               return;

        }

        else

        {

               for (int i = n - 1; i >= 0; i--) //swap 함수로 Setn[i]와 Setn[n-1]의 위치 바꾼 후

               {

                       Swap(&Setn[i], &Setn[n - 1]); //재귀 함수 호출 이용해 과정 반복

                       Copy[r - 1] = Setn[n - 1]; //그 후 swap 함수 재호출하여 Setn[i]와 Setn[n-1]의 위치 바꿈

                       Permutation(Setn, Copy, n - 1, r - 1, term); //이 과정으로 역순의 순열(큰 수부터 출력) 생성

                       Swap(&Setn[i], &Setn[n - 1]);

               }

        }

}

 

void Print_Permutation(int *Setn, int n)

{

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

        {

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

        }

        printf(", ");

}

 

[3번 문제]

/*

임의의 문자열(길이 n)에 대해 개수 r(r<=n)을 입력받아 문자열에 대한 모든 조합을

출력하는 프로그램을 작성한다

*/

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

 

//str과 output은 4.4의 Setn과 Copy와 비슷한 역할

 

void combination(char *str, char *output, int start, int next, int r, int length);

 

int main(void)

{

        char str[50];

        char *output;

        int r;

        printf("문자열 입력: ");

        scanf("%s", str);

        int length = strlen(str); //입력한 문자열 길이

        output = (char*)malloc(sizeof(char)*length);

        for (r = 1; r <= length; r++)

               combination(str, output, 0, 0, r, length);

        free(output);

        return 0;

}

 

void combination(char *str, char *output, int start, int next, int r, int length)

{

        if (next == r) //함수가 출력하는 시점

        {

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

               {

                       printf("%c", output[i]);

               }

               printf("\n");

               return;

        }

        if (start == length) //시작지점이 문자열의 끝까지 오면 끝

               return;

        output[next] = str[start];

        combination(str, output, start + 1, next + 1, r, length); //.다음 문자 포함

        combination(str, output, start + 1, next, r, length); //다음 문자 미포함

 

        //저번에 풀었던 멱급수와 비슷하다

}

[4번 문제]

/*

임의의 n자리 십진 정수를 입력받아 표현 가능한 모든 n자리의 정수를 출력하는 프로그램을 작성한다

*/

#include <stdio.h>

#include <stdlib.h>

 

int *Setn; //순열과 조합을 생성할 집합을 만들 int 포인터형 전역 변수 Setn

int *Copy; //Setn 변수를 복사(저장)할 int 포인터형 전역 변수 Copy 선언

 

int Fact(int x); //x 팩토리얼 개수를 출력하는 함수 Fact

void Swap(int *a, int *b); //순열과 조합을 구할때 원소 위치를 바꿔줄 함수 Swap

void Permutation(int *Setn, int *Copy, int n, int r, int term); //nPr 순열을 만드는 함수

void Print_Permutation(int *Setn, int n); //순열 출력을 위한 함수

 

int main(void)

{

        int n, r;

 

        printf("n의 값 입력: ");

        scanf("%d", &n);

 

        while (1)

        {

               if (n > 10)

               {

                       printf("n값 재입력: ");

                       scanf("%d", &n);

               }

               else if (n < 1)

               {

                       printf("n값 재입력: ");

                       scanf("%d", &n);

               }

               else if (1 <= n <= 10)

               {

                       break;

               }

        }

        printf("r의 값 입력: "); //순열 나열할 개수

        scanf("%d", &r);

 

        while (1)

        {

               if (r > n)

               {

                       printf("r 재입력: ");

                       scanf("%d", &r);

               }

               else if (r <= n)

               {

                       break;

               }

        }

        Setn = (int*)malloc(sizeof(int)*n); //배열 Setn을 사용자로부터 입력받은 n 크기만큼 동적할당

        Copy = (int*)malloc(sizeof(int)*n);

 

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

        {

               Setn[i] = i + 1;

        }

        printf("원소의 %d-순열(총 %d개): ", r, Fact(n) / Fact(n - r)); //순열의 개수를 팩토리얼로 계산

        Permutation(Setn, Copy, n, r, r);

        printf("\n");

        free(Setn);

        free(Copy);

        return 0;

}

 

int Fact(int x)

{

        if (x == 0)

               return 1;

        else

               return x*Fact(x - 1);

}

 

void Swap(int *a, int *b)

{

        int temp = *a;

        *a = *b;

        *b = temp;

}

 

void Permutation(int *Setn, int *Copy, int n, int r, int term)

{

        if (r == 0)

        {

               Print_Permutation(Copy, term);

               return;

        }

        else

        {

               for (int i = n - 1; i >= 0; i--) //swap 함수로 Setn[i]와 Setn[n-1]의 위치 바꾼 후

               {

                       Swap(&Setn[i], &Setn[n - 1]); //재귀 함수 호출 이용해 과정 반복

                       Copy[r - 1] = Setn[n - 1]; //그 후 swap 함수 재호출하여 Setn[i]와 Setn[n-1]의 위치 바꿈

                       Permutation(Setn, Copy, n - 1, r - 1, term); //이 과정으로 역순의 순열(큰 수부터 출력) 생성

                       Swap(&Setn[i], &Setn[n - 1]);

               }

        }

}

 

void Print_Permutation(int *Setn, int n)

{

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

        {

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

        }

        printf(", ");

}

 

[5번 문제]

/*

임의의 금액을 입력받아 10원, 50원, 100원, 500원 동전을 최소 한번씩은 이용하여

입력된 금액을 나타내되 동전의 개수가 최소로 되는 조합을 구하는 프로그램을 작성합니다.

*/

#include <stdio.h>

 

void printCoin(int coin[4], int money);

 

int main(void)

{

        int coin[4] = { 500, 100, 50, 10 }; //500원 100원 50원 10원

        int money;

 

        printf("금액 입력: ");

        scanf("%d", &money);

        printCoin(coin, money - (500 + 100 + 50 + 10)); //동전들을 최소 한번씩은 사용했다

        return 0;

}

 

void printCoin(int coin[4], int money)

{

        int result[4] = { 0, 0, 0, 0 };

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

        {

               while (1)

               {

                       if (money - coin[i] >= 0) //동전을 전부 쓸 수 있을 때까지

                       {

                              money -= coin[i];

                              result[i]++;

                       }

                       else

                              break;

               }

        }

        printf("500원:%d개\n100원:%d개\n50원:%d개\n10원:%d개\n", result[0] + 1, result[1] + 1, result[2] + 1, result[3] + 1);

}

[6번 문제]

/*

아래의 그림과 같은 파스칼의 삼각형을 출력하는 프로그램을 작성합니다

*/

#include <stdio.h>

 

int Factorial(int n);

int Combination(int n, int r);

void Pascal(int n);

 

int main(void)

{

        int size;

 

        printf("삼각형 크기 입력: ");

        scanf("%d", &size);

 

        Pascal(size);

        return 0;

}

 

int Factorial(int n)

{

        if (n > 1)

               return n*Factorial(n - 1);

        else

               return 1;

}

 

int Combination(int n, int r)

{

        return Factorial(n) / (Factorial(n - r)*Factorial(r));

}

 

void Pascal(int n)

{

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

        {

               for (int j = 1; j <= (n - i); j++) //삼각형 모양을 만들기 위해서는 어느정도 공백이 있어야합니다

                       printf("  ");

               for (int j = 0; j <= i; j++) //삼각형은 숫자의 조합으로 이루어져있습니다

                       printf("%4d", Combination(i, j));

               printf("\n");

        }

        //모양 출력은 1장 연습문제와 비슷합니다

}

 

개발환경:Visual Studio 2017

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

[참고] 명품 C언어 프로젝트 안기수 저, http://realredwine.tistory.com/52

*4번 문제는 블로그에 있는 코드를 거의 그대로 가져왔고 2번 문제는 참고한 4번 문제를 기반으로 작성했습니다