12. c언어 재귀함수 - 순열, 조합 구하기

[ c언어 재귀함수 12 -1 ] 순열 구하기

n개의 수를 사용해서 가능한 순열을 모두 구하라.

예를 들어 1, 2, 3을 나열하는 방법은 다음과 같이 여섯 가지가 있다.

 123    132     213     231    312     321

 이를 순열이라 하고, 서로 다른 n개의 수를 나열하는 순열은 n!가지가 있다.

[교과서 정의 ] 순열이란 서로 다른 n개에서 r개를 택하여 일렬로 나열하는 것을 n개에서 r개를 택하는 순열이라 하고, 그 순열의 수를 기호로 nPr와 같이 나타낸다.

 

◈ 입력 형식

첫 줄에 10이하의 자연수 n이 주어진다.

 

◈ 출력 형식

첫번째 줄부터 생성된 순열을 한줄에 하나씩 출력한다.

 

 ◈ 입력과 출력의 예

입력의 예	출력의 예
3	1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

-------------------------------------------------------------------------

※ 숫자 1, 2, 3으로 만들수 있는 3자리수를 모두 출력해봅시다.

111   112   113    211  ........ 333 입니다

경우의 수와 재귀함수의 갯수는 같습니다. 지금 경우의 수는 1, 2, 또는 3  (3가지)입니다. 그럼 (재귀함수 3개)가 필요합니다.

아래 더보기를 눌러 소스를 보세요

#include <stdio.h>
void rec(int);
int n;
int dap[20];
int main()
{
	rec(0);
	return 0;
}

void rec(int x)
{
	if(x == 3)
	{
		for(int i=0;i<3;i++)
		{
			printf("%d ", dap[i]);
		}
		printf("\n");
		return;
	}
	
	dap[x] = 1;
	rec(x+1);
	
	dap[x] = 2;
	rec(x+1);
	
	dap[x] = 3;
	rec(x+1);
}

 

그럼, (1, 2, 3, 4)로 만들수 있는 4자리 수를 모두 출력할려면 (재귀함수4개)가 필요하고

(1, 2, 3, 4, 5)로 만들수 있는 5자리 수를 모두 출력할려면 (재귀함수5개)가 필요합니다.

for문을 이용하면 쉽게 할수 있습니다. 

아래 더보기를 눌러 소스를 보세요

#include <stdio.h>
void rec(int);
int n;
int dap[20];
int main()
{
	scanf("%d", &n);
	rec(0);
	return 0;
}

void rec(int x)
{
	if(x == n)
	{
		for(int i=0;i<n;i++)
		{
			printf("%d ", dap[i]);
		}
		printf("\n");
		return;
	}
	
	for(int i=0;i<n;i++)
	{
		dap[x] = i +1;
		rec(x+1);
	}
}

 

이젠 중복된 숫자를 제거해 보겠습니다. 

n=3일때 중복된 숫자를 제거하고 다음과 같이 출력해보세요 

 123    132     213     231    312     321

 

 

[ c언어 재귀함수 12 -1 ] 순열 구하기 소스보기

#include <stdio.h>
void rec(int);
int n;
int dap[20], check[20]={0,};
int main()
{
	scanf("%d", &n);
	rec(0);
	return 0;
}

void rec(int x)
{
	if(x == n)
	{
		for(int i=0;i<n;i++)
		{
			printf("%d ", dap[i]);
		}
		printf("\n");
		return;
	}
	
	for(int i=0;i<n;i++)
	{
		if(check[i] == 0)
		{
			check[i]=1;
			dap[x] = i +1;
			rec(x+1);
			check[i]=0;
		}
	}
}

 

-------------------------------------------------------------------------

 

[ c언어 재귀함수 12 -2 ] 조합 구하기

  n과 r을 입력받아 n개의 숫자 중 r개를 택하는 조합을 구하는 프로그램을 작성하시오.

◈ 입력 형식

첫째 줄에 n과 r이 주어진다. N은 20이하의 자연수이며 r은 n이하의 자연수이다.

 ◈ 출력 형식

 첫째 줄에 총 조합의 개수를 출력한다. 그 다음 줄부터 한 줄에 하나씩 조합을 출력한다. 

◈ 입력과 출력의 예

입력의 예	출력의 예
4 2	1 2 1 3 1 4 2 3 2 4 3 4

 

[ c언어 재귀함수 12 -2 ] 조합 구하기 소스

#include <stdio.h>
void rec(int, int);
int n, r;
int dap[20], check[20]={0,};
int main()
{
	scanf("%d %d", &n, &r);
	rec(0,0);
	return 0;
}

void rec(int x, int t)
{
	if(x == r)
	{
		for(int i=0;i<r;i++)
		{
			printf("%d ", dap[i]);
		}
		printf("\n");
		return;
	}
	
	for(int i=t;i<n;i++)
	{
		if(check[i] == 0)
		{
			check[i]=1;
			dap[x] = i+1;
			rec(x+1,i);
			check[i]=0;
		}
	}
}