확률 – 중복 조합 사전 순으로 나열하기

양의 정수 n과 r이 주어져 있을 때, 집합 {1,2,3,….,n}에서 반복을 허용하는 r-조합을 모두 나열하라

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include <stdio.h>
int n, r, *set, *out;
int count = 0;
// 팩토리얼 함수
int factorial(int a, int b) {
if (a == 0)
return 1;
else {
int result = 1;
for (int i = a; i > b; i--)
result *= i;
return result;
}
}
// 중복 조합 개수 구하는 함수
int over_combi_num(int n, int r) {
int temp = n; // n을 임의로 저장
n = n + r - 1; // h(n,r)=c(n+r-1,r)이므로 인수 n만 n+r-1로 바꿔줌
if (r >= 0 && r <= n) {
int denominator, numerator, answer;
denominator = factorial(n, n - r);
numerator = factorial(r, 0);
answer = denominator / numerator;
printf("▷ H(%d,%d) = %d\n\n", temp, r, answer); // 출력할 때는 원래 n사용
}
}
// 중복 조합 나열하는 함수
void over_combination(int start, int end, int index) {
// r이 0이면 처리 안 함
if (r == 0)
return 0;
int i;
// end가 0이면 out배열이 다 찼으니 출력
if (end == 0) {
for (i = 0; i < start; i++) {
printf("%d ", out[i]);
}
printf("\n");
count++;
}
// 이 else if는 두 번째 over_combination이 호출돼야지만 실행될 수 있음
// 이게 실행됐다는 것은 set의 마지막 원소까지 out에 주었다는 것이고,
// 재귀에 의해 out[r-1]=set[n-1]까지 완료됐다는 것을 의미
// 더 이상 할게 없으니 리턴함
else if (index == n) {
return;
}
else {
out[start] = set[index];
// 출력할 내용을 담는 배열 out에 값을 주기
over_combination(start + 1, end - 1, index); // index 고정해서 같은 값 들어가게 설정
// 계속 앞에 있는 것 r개만 주면 안 되니, start는 고정, index를 증가
over_combination(start, end, index + 1);
}
}
void main()
{
printf("■ 양의 정수 n과 r이 주어져 있을 때, 집합 {1,2,3,....,n}에서 반복을 허용하는 r-조합을 모두 나열하라.\n");
printf("\n□ n을 입력하시오: ");
// n 입력 받기
scanf_s("%d", &n);
// n값을 이용해서 set 지정
set = (int*)malloc(sizeof(int)*n);
for (int i = 0; i < n; i++)
set[i] = i + 1;
// r만들기 (0~n-1)
srand(time(NULL));
r = rand() % n;
printf("\n▷ r = %d\n", r);
// r이 0일 때 메모리 할당하면 오류 걸리니 패스
if (r != 0)
out = (int*)malloc(sizeof(int)*r);
// 중복 조합 문제 풀기
over_combi_num(n, r);
over_combination(0, r, 0);
printf("\n◈ 조합 나열한 것 카운트 = %d\n", count);
// 메모리 할당 해제
free(set);
free(out);
}
#include <stdio.h> int n, r, *set, *out; int count = 0; // 팩토리얼 함수 int factorial(int a, int b) { if (a == 0) return 1; else { int result = 1; for (int i = a; i > b; i--) result *= i; return result; } } // 중복 조합 개수 구하는 함수 int over_combi_num(int n, int r) { int temp = n; // n을 임의로 저장 n = n + r - 1; // h(n,r)=c(n+r-1,r)이므로 인수 n만 n+r-1로 바꿔줌 if (r >= 0 && r <= n) { int denominator, numerator, answer; denominator = factorial(n, n - r); numerator = factorial(r, 0); answer = denominator / numerator; printf("▷ H(%d,%d) = %d\n\n", temp, r, answer); // 출력할 때는 원래 n사용 } } // 중복 조합 나열하는 함수 void over_combination(int start, int end, int index) { // r이 0이면 처리 안 함 if (r == 0) return 0; int i; // end가 0이면 out배열이 다 찼으니 출력 if (end == 0) { for (i = 0; i < start; i++) { printf("%d ", out[i]); } printf("\n"); count++; } // 이 else if는 두 번째 over_combination이 호출돼야지만 실행될 수 있음 // 이게 실행됐다는 것은 set의 마지막 원소까지 out에 주었다는 것이고, // 재귀에 의해 out[r-1]=set[n-1]까지 완료됐다는 것을 의미 // 더 이상 할게 없으니 리턴함 else if (index == n) { return; } else { out[start] = set[index]; // 출력할 내용을 담는 배열 out에 값을 주기 over_combination(start + 1, end - 1, index); // index 고정해서 같은 값 들어가게 설정 // 계속 앞에 있는 것 r개만 주면 안 되니, start는 고정, index를 증가 over_combination(start, end, index + 1); } } void main() { printf("■ 양의 정수 n과 r이 주어져 있을 때, 집합 {1,2,3,....,n}에서 반복을 허용하는 r-조합을 모두 나열하라.\n"); printf("\n□ n을 입력하시오: "); // n 입력 받기 scanf_s("%d", &n); // n값을 이용해서 set 지정 set = (int*)malloc(sizeof(int)*n); for (int i = 0; i < n; i++) set[i] = i + 1; // r만들기 (0~n-1) srand(time(NULL)); r = rand() % n; printf("\n▷ r = %d\n", r); // r이 0일 때 메모리 할당하면 오류 걸리니 패스 if (r != 0) out = (int*)malloc(sizeof(int)*r); // 중복 조합 문제 풀기 over_combi_num(n, r); over_combination(0, r, 0); printf("\n◈ 조합 나열한 것 카운트 = %d\n", count); // 메모리 할당 해제 free(set); free(out); }
#include <stdio.h>

int n, r, *set, *out;
int count = 0;

// 팩토리얼 함수
int factorial(int a, int b) {
	if (a == 0)
		return 1;

	else {
		int result = 1;
		for (int i = a; i > b; i--)
			result *= i;
		return result;
	}
}

// 중복 조합 개수 구하는 함수 
int over_combi_num(int n, int r) {
	int temp = n; // n을 임의로 저장 
	n = n + r - 1; // h(n,r)=c(n+r-1,r)이므로 인수 n만 n+r-1로 바꿔줌 
	if (r >= 0 && r <= n) {
		int denominator, numerator, answer;
		denominator = factorial(n, n - r);
		numerator = factorial(r, 0);
		answer = denominator / numerator;

		printf("▷ H(%d,%d) = %d\n\n", temp, r, answer); // 출력할 때는 원래 n사용
	}
}

// 중복 조합 나열하는 함수 
void over_combination(int start, int end, int index) {
	// r이 0이면 처리 안 함
	if (r == 0)
		return 0;

	int i;
	// end가 0이면 out배열이 다 찼으니 출력 
	if (end == 0) {
		for (i = 0; i < start; i++) {
			printf("%d ", out[i]);
		}
		printf("\n");
		count++;
	}
	// 이 else if는 두 번째 over_combination이 호출돼야지만 실행될 수 있음
	// 이게 실행됐다는 것은 set의 마지막 원소까지 out에 주었다는 것이고,
	// 재귀에 의해 out[r-1]=set[n-1]까지 완료됐다는 것을 의미
	// 더 이상 할게 없으니 리턴함 
	else if (index == n) {
		return;
	}
	else {
		out[start] = set[index];
		// 출력할 내용을 담는 배열 out에 값을 주기
		over_combination(start + 1, end - 1, index); // index 고정해서 같은 값 들어가게 설정 
		// 계속 앞에 있는 것 r개만 주면 안 되니, start는 고정, index를 증가 
		over_combination(start, end, index + 1);
	}

}


void main()
{
	printf("■ 양의 정수 n과 r이 주어져 있을 때, 집합 {1,2,3,....,n}에서 반복을 허용하는 r-조합을 모두 나열하라.\n");
	printf("\n□ n을 입력하시오: ");

	// n 입력 받기
	scanf_s("%d", &n);

	// n값을 이용해서 set 지정 
	set = (int*)malloc(sizeof(int)*n);

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

	// r만들기 (0~n-1)
	srand(time(NULL));
	r = rand() % n;
	printf("\n▷ r = %d\n", r);

	// r이 0일 때 메모리 할당하면 오류 걸리니 패스
	if (r != 0)
		out = (int*)malloc(sizeof(int)*r);

	// 중복 조합 문제 풀기
	over_combi_num(n, r);
	over_combination(0, r, 0);
	printf("\n◈ 조합 나열한 것 카운트 = %d\n", count);

	// 메모리 할당 해제
	free(set);
	free(out);
}

확률 코드 패키지

조합 사전 순으로 나열하기

중복 조합 사전 순으로 나열하기

중복 순열 사전 순으로 나열하기

순열 사전 순으로 나열하기

Leave a Reply

Your email address will not be published. Required fields are marked *