프로 그래 밍 도전 (6)

2352 단어 프로 그래 밍
조합 알고리즘: 배열 을 열 면 아래 표 시 는 1 에서 m 의 수 를 나타 내 고 배열 요소 의 값 은 1 로 다음 표 시 된 숫자 가 선택 되 었 음 을 나타 내 며 0 이면 선택 되 지 않 았 습 니 다.
 먼저 초기 화 합 니 다. 배열 앞 n 개의 요 소 를 1 로 설정 하고 첫 번 째 조합 이 n 개의 수 임 을 표시 합 니 다.그 다음 에 왼쪽 에서 오른쪽으로 배열 요소 값 의 '10' 조합 을 스 캔 하고 첫 번 째 '10' 조합 을 찾 아 '01' 조합 으로 바 꾸 는 동시에 왼쪽 에 있 는 모든 '1' 을 배열 의 맨 왼쪽 으로 이동 합 니 다.첫 번 째 '1' 이 배열 의 m - n 위치, 즉 n 개의 '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
void output1(int value[], char* middle, int length)

{

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

	{

		if(middle[i] == '1')

		{

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

		}

	}

	printf("
"); } bool find10(char* middle, int M, int* index) { bool find = false; for(int i=0; i<M; i++) { if (middle[i] == '1' && middle[i + 1] == '0') { *index = i; find = true; break; } } return find; } void move1(char* middle, int index) { int count = 0; for(int i=0; i<index; i++) { if (middle[i] == '1') { swap(middle[count++], middle[i]); } } } // M N void enumkind(int value[], int M, int N) { char *middle = new char[M + 1]; middle[M] = '\0'; memset(middle, '1', N); memset(middle + N, '0', M - N); printf("%s: ", middle); output1(value, middle, M); int index = 0; while(find10(middle, M, &index)) { swap(middle[index], middle[index+1]); move1(middle, index); printf("%s: ", middle); output1(value, middle, M); } delete middle; } int _tmain(int argc, _TCHAR* argv[]) { int value[5] = {1,2,3,4,5}; enumkind(value, sizeof(value)/sizeof(int), 4); getchar(); return 0; }

 

좋은 웹페이지 즐겨찾기