숫자 m 와 숫자 n 을 지정 하여 해당 하 는 모든 배열 을 출력 합 니 다.

n 개의 수 (즉, 1, 2, 3, 4, n) 에서 m 개의 수 를 선택 하면 모두 C (n, m) 의 서열 이 있 습 니 다. 출력 은 n, m 의 모든 배열 에 있 습 니 다.
n = 5, m = 3, 즉 C (5, 3) 출력 10 가지 시퀀스
5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1
분석: 첫 번 째 숫자 부터 선택 할 수 있 습 니 다. (3, 4, 5) 와 (5, 4, 3) 는 하나의 서열 로 계산 되 기 때문에 중복 을 피하 기 위해 우 리 는 큰 것 에서 작은 것 으로 출력 할 수 있 습 니 다.
이 배열 의 수 크기 는 순서대로 줄 어 들 고, 첫 번 째 수가 가장 크 며, 마지막 수가 가장 작다.
첫 번 째 숫자 는 m 에서 n 의 (n - m + 1) 개 수 를 선택 한 다음 에 재 귀 하 는 방식 으로 하면 됩 니 다. 종료 조건 은 m = 0 일 때 입 니 다.
#include<iostream>
#include<string>
using namespace std;
//size is equal to m when function is first time
//invocated
void combination(int m,int n,int *A,int size){
	if(m==0){
		for(int i=size-1;i>=0;i--)
			cout<<A[i]<<" ";
		cout<<endl;
		return;
	}
	
	for(int i=n;i>=m;i--){
		A[m-1]=i;
		combination(m-1,i-1,A,size);
	}
}

int main(){
	int *A=new int[100];
	combination(3,6,A,3);

}

처음에는 폐 기 된 문자열 을 쓰 는 알고리즘 이 었 습 니 다.
#include<iostream>
#include<string>
using namespace std;


//int *a=new int[m];
void combination(int m,int n,string str){

if(m==0){
cout<<str;
cout<<endl;
return;
}
for(int i=n;i>=m;i--){
//cout<<i<<" ";
char buf[10];
sprintf(buf, "%d",i);
string b=buf;
if(i<n){
str=str.substr(0,str.size()-1);
}
str+=b;
combination(m-1,i-1,str);
}
}


int main(){
combination(3,6," ");


}

좋은 웹페이지 즐겨찾기