C++에서 조합 수 를 구 하 는 여러 가지 방법 에 대한 상세 한 설명
6574 단어 c + +조합 수 를 구하 다
문제 설명:자연수 1,2,n 에서 r 개 수 를 취 하 는 모든 조합 을 찾 아 라.예 를 들 어 n=5,r=3 의 모든 조합 은:
1,2,31,2,4 1,3,4 2,3,4 1,2,5 1,3,5 2,3,5 1,4,5 2,4,5 3,4,5
프로그램 으로 실현 하 는 몇 가지 방법 이 있다.
1)궁 거 법
프로그램 은 다음 과 같 습 니 다[프로그램]\#include
int main(){ for(i=1;i<=r ;i++) for(j=i+1;j<=r+1;j++) for( k=j+1;k<=r+2;k++){ counts++; printf("%4d%4d%4d/n",i,j,k); }printf("%d",counts);return 0;}그러나 이 프로그램 은 모두 문제 가 있 습 니 다.r 가 변화 할 때 순환 중수 가 바 뀌 면 이 문제 의 풀이 에 영향 을 주 었 습 니 다.즉,일반성 이 없습니다.
2)재 귀 법 은 열 거 된 10 개의 조합 을 분석 하고 이러한 재 귀 사상 으로 조합 함 수 를 구 하 는 알고리즘 을 고려 할 수 있다.함 수 를 void 로 설정 하 다 comb(int m,int k)는 자연수 1,2,...,m 에서 k 개 수 를 취 하 는 모든 조합 을 찾기 위해 서 입 니 다.그룹의 첫 번 째 숫자 를 선택 할 때 그 다음 의 숫자 는 남 은 m-1 개의 숫자 에서 k-1 수의 조합 이다.이 는 m 개 수 에서 k 개 수 를 구 하 는 조합 문 제 를 m-1 개 수 에서 k-1 개 수 를 구 하 는 조합 문제 로 전환시킨다.함수 도입 작업 배열 a[]에서 구 한 조합의 숫자 를 저장 하고 약속 함 수 는 확 정 된 k 개의 숫자 조합의 첫 번 째 숫자 를 a[k]에 두 고 한 조합 이 구 한 후에 야 a[]중의 한 조합 을 출력 합 니 다.첫 번 째 수 는 m,m-1,.................................................................................또는 조합의 모든 요 소 를 확 정 했 기 때문에 이 조합 을 출력 합 니 다.자세 한 내용 은 다음 프로그램의 함수 comb 를 보십시오.[프로그램]\#include
using namespace std;
# define MAXN 100int a[MAXN];int counts=0;
void printtime(void)/현재 시간 을 인쇄 하 는 함수{ char tmpbuf[128]; time_t ltime; struct tm *today;
time(<ime); today = localtime(<ime ); strftime(tmpbuf,128,"%Y-%m-%d %H:%M:%S",today); cout<
int main(){
int m,r; cout<<"m"<
이것 은 내 가 인터넷 에서 찾 은 프로그램 으로 조금 수정 했다.프로그램 은 간결 하고 통용 성 이 있어 문 제 를 해결 했다.
3)역 추적 법
역 추적 법 으로 문 제 를 해결 하고 찾 은 조합 을 작은 것 에서 큰 순서 로 a[0],a[1],a[1],a[r-1]에 저장 하 며 조합의 요 소 는 다음 과 같은 성질 을 만족시킨다.
（1） a[i+1]>a[i],뒤의 숫자 가 이전 보다 크다.(2） a[i]-i<=n-r+1。역 추적 법의 사상 에 따라 해답 을 찾 는 과정 은 다음 과 같다. 우선 그룹 수가 r 인 조건 을 포기 하고 후보 그룹 은 하나의 숫자 1 부터 시작한다.이 후보 해 가 문제 규 모 를 제외 한 모든 조건 을 충족 시 켜 규 모 를 확대 하고 이 를 충족 시 키 기 때문에 후보 조합 은 1,2 로 바 뀌 었 다.이 과정 을 이 어가 후보 그룹 1,2,3 을 얻 었 다.이 후보 해 는 문제 규 모 를 포함 한 모든 조건 을 충족 시 켜 하나의 해 다.이 해 를 바탕 으로 다음 후 보 를 선정 하여 a[2]상의 3 조정 이 4 로 조정 되 었 고 앞으로 5 로 조정 하여 문제 의 모든 요 구 를 만족 시 켰 기 때문에 1,2,4 와 1,2,5 를 풀 었 다.5 에 대해 더 이상 조정 할 수 없 기 때문에 a[2]에서 a[1]로 거 슬러 올 라 가 야 한다.이때 a[1]=2 는 3 으로 조정 하고 앞으로 탐색 하여 1,3,4 를 풀 수 있다.상기 한 탐색 과 뒤로 거 슬러 올 라 가 a[0]에서 다시 거 슬러 올 라 갈 때 까지 문제 의 모든 해 를 찾 았 다 는 것 을 설명 한다.
인터넷 에서 저 는 정상적으로 실행 할 수 있 는 완전한 프로그램 을 찾 지 못 했 습 니 다.그래서 저 는 하루 동안 이 프로그램 을 작성 하고 출력 을 0 에서 시작 하 는 것 이 아니 라 1 부터 시작 하 는 것 을 바 꾸 었 습 니 다.이렇게 하 는 목적 은 프로그램의 용 도 를 확장 하고 c/c+언어의 수요 에 적응 하기 위해 서 입 니 다.그러면 출력 은 선택 할 조합 배열 의 주소 서열 로 볼 수 있 습 니 다.길이 가 n 인 임의의 유형의 배열 에 대해 r 개의 조합 을 찾 을 수 있 습 니 다.나 는 그것 을 최적화 시 켰 다.만약 당신 이 최적화 할 수 있 는 곳 이 있다 고 생각한다 면,가르침 을 아 끼 지 마 세 요.^ ^
#include
# define MAXN 100int a[MAXN]; //포 지 셔 닝 배열 은 요소 집합 배열 의 위 치 를 표시 하 는 데 사 용 됩 니 다.요소 집합 배열 0 시작 void comb(int m,int r){를 선택 하 십시오. int cur;//배열 에서 어떤 멤버 가 이동 하고 있 는 지 표시 합 니 다.
unsigned int count=0;
//포 지 셔 닝 배열 초기 화,0 시작 위치,시작 선택 은 위치 0,1,2 입 니 다. for(int i=0;i
do{ if (a[cur]-cur<=m-r ){
count++; /* for (int j=0;j
void printtime(void)/현재 시간 을 인쇄 하 는 함수{ char tmpbuf[128]; time_t ltime; struct tm *today;
time(<ime); today = localtime(<ime ); strftime(tmpbuf,128,"%Y-%m-%d %H:%M:%S",today); cout<
int m,r; cout<<"m"<
위의 재 귀 프로그램 과 비교 하여 g+o 2 로 최적화 합 니 다.n=40,r=11 로 출력 을 차단 하고 얻 은 결 과 는 모두 2311801440 항 이 며 재 귀 프로그램 은 23~24 초,역 추적 은 19~20 초 걸 렸 다.
4)배열 활용
정의:n 개 수 에서 m 개 수의 조합 을 추출 합 니 다. 구현 메커니즘:먼저 문자열 배열 을 만 듭 니 다.아래 표 시 는 1 에서 n 개 수 를 표시 합 니 다.배열 요소 의 값 은 1 로 표시 되 어 있 으 며,아래 표 시 된 숫자 가 선택 되 었 음 을 표시 합 니 다.0 이면 선택 되 지 않 았 습 니 다. 그리고 초기 화 합 니 다.배열 의 앞 m 개 요 소 를 1 로 설정 하면 첫 번 째 조합 이 앞 m 개 임 을 표시 합 니 다. 그 다음 에 왼쪽 에서 오른쪽으로 배열 요소 값 의 10 조합 을 스 캔 하여 첫 번 째'10'을 찾 은 후에 1 과 0 의 위 치 를 교환 하고 01 로 바 꾼 다음 에 이 10 조합 전의 1 과 0 을 재 조합(1 은 앞 에 놓 고 그 개 수 는 10 조합 전 1 의 개수 이 고 0 은 뒤에 놓 으 며 그 개 수 는 10 전 0 의 개수 이 고 10 의 반전 조합 01)한다.m 개 1 이 모두 오른쪽 끝 으로 이동 하면 마지막 조합 을 얻 을 수 있다. 예 를 들 어 5 중 3 의 조합 을 구 합 니 다. 1 1 1 0 0 //1,2,3 1 1 0 1 0 //1,2,4 1 0 1 1 0 //1,3,4 0 1 1 1 0 //2,3,4 1 1 0 0 1 //1,2,5 1 0 1 0 1 //1,3,5 0 1 1 0 1 //2,3,5 1 0 0 1 1 //1,4,5 0 1 0 1 1 //2,4,5 0 0 1 1 1 //3,4,5
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu 1717 소수 화 점수 2 (수학)소수 화 점수 2 레이 는 수학 시간 에 선생님 의 말씀 을 듣 고 모든 소수 가 점수 로 표시 되 는 형식 이 라 고 말 했다. 그 는 녹 기 시 작 했 고 곧 완성 되 었 다. 그러나 그 는 또 하나의 문 제 를...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
