U E D R , A S I H C RSS

수학의정석/집합의연산/조현태

느낀점 및 설명

음.. 저번 것과 마찬가지로 입력받는 부분은 시간계산에 포함하지 않는다. (사용자의 입력시간이 결정하기 때문.)
또한 오버헤드를 줄인다는 명목하에 함수로 나누지도 않았따. (귀차니즘.ㅎ)
아우.. 27시간 동안 깨있었더니 죽겠... 인상태에서 만들어 졌으며, 그래서 소스가 지저분 할 수 있다.

알고리즘은 1과 0으로 수를 저장, 한칸씩 옮겨가면서 모든 경우의 수를 찾는 것이다.
또한 예를 들어 7개일 경우는 1개일때, 2개일때, ... 7개일때 이런식으로 나누어서 연산을 한다.

숫자의 수 걸리는 시간(초)
9개 0.078
10개 0.172
11개 0.375
12개 0.781

음 영호선배의 페이지를 보니 이 페이지의 설명이 부족한듯 해서 덧붙인다.
예를 들어 9Set을 하면..
배열1 - 1,2,3,4,5,6,7,8,9
배열2 - 1 0 0 0 0 0 0 0 0
이렇게 세팅후 1인 경우에 출력한다. 한차례연산후
배열2 - 0 1 0 0 0 0 0 0 0
배열2 - 0 0 1 0 0 0 0 0 0
배열2 - 0 0 0 1 0 0 0 0 0
배열2 - 0 0 0 0 1 0 0 0 0
배열2 - 0 0 0 0 0 1 0 0 0
배열2 - 0 0 0 0 0 0 1 0 0
배열2 - 0 0 0 0 0 0 0 1 0
배열2 - 0 0 0 0 0 0 0 0 1
이런식의 연산을 거치게 된다.
그후 2개로 증가시켜서 계산...
배열2 - 1 1 0 0 0 0 0 0 0
배열2 - 1 0 1 0 0 0 0 0 0
배열2 - 1 0 0 1 0 0 0 0 0
배열2 - 1 0 0 0 1 0 0 0 0
배열2 - 1 0 0 0 0 1 0 0 0
배열2 - 1 0 0 0 0 0 1 0 0
배열2 - 1 0 0 0 0 0 0 1 0
배열2 - 1 0 0 0 0 0 0 0 1
배열2 - 0 1 1 0 0 0 0 0 0
배열2 - 0 1 0 1 0 0 0 0 0
배열2 - 0 1 0 0 1 0 0 0 0
배열2 - 0 1 0 0 0 1 0 0 0
배열2 - 0 1 0 0 0 0 1 0 0
배열2 - 0 1 0 0 0 0 0 1 0
배열2 - 0 1 0 0 0 0 0 0 1
배열2 - 0 0 1 1 0 0 0 0 0
.
.
(후략)
이런식으로 연산을 하여 모든 경우의 수를 찾아낸다.^^
질문이나 부족한 점에 대해서는 글을 남겨주세요.^^*



소스

~cpp 
#include <time.h>  
#include <stdio.h>
#include <iostream>

int* input_and_return_number(int*);
void process(int*, int);

int main()  
{  
	int time_in;   // 초기 시작 시간.  
	/////
	int gaesu;
	int *temp_gaesu=&gaesu;
	int *numbers=input_and_return_number(&gaesu);
	/////
	time_in = clock();   // 초기 시작 시간을 입력한다.
    process(numbers,gaesu);
	free(numbers);
	printf("CPU CLOCKS = %d\n", clock() - time_in);   // 끝났을때 시간 - 초기 시작시간 = 프로그램 실행 시간  
	return 0;    // 프로그램 종료.  
}  

int* input_and_return_number(int *number_gaesu)
{
	printf("입력할 숫자의 개수는?>>");
	fflush(stdin);
	scanf ("%d",number_gaesu);
	int *numbers=(int*)malloc(sizeof(int)*(*number_gaesu));
	for (register int i=0; i<*number_gaesu; ++i)
	{
		printf("%d번째의 숫자를 입력해주세요.>>",i+1);
		fflush(stdin);
		scanf("%d",numbers+i);
	}
	return numbers;
}

void process(int *numbers, int gaesu)
{
	int *temp_where=(int*)malloc(sizeof(int)*gaesu);
	for (register int temp_gaesu=1; temp_gaesu<=gaesu; ++temp_gaesu)
	{
		int bun_ja=1; 
		int bun_mo=1; 
		for (register int i=0; i<temp_gaesu; ++i) 
		{ 
			bun_ja*=gaesu-i; 
			bun_mo*=i+1; 
		}
		int combination=bun_ja/bun_mo;
		for (register int i=0; i<gaesu; ++i)
		{
			if (i<temp_gaesu)
				temp_where[i]=1;
			else
				temp_where[i]=0;
		}
		for (register int i=0; i<combination; ++i)
		{
			printf("{");
			int end=gaesu-1;
			for (register int j=0; j<gaesu; ++j)
			{
				if(1==temp_where[j])
					printf(" %d ",numbers[j]);
			}
			printf("} ");
			int find_last=end;
			for (; find_last>=0; --find_last)
			{
				if (1==temp_where[find_last])
					break;
			}
			if (find_last==end)
			{
				int gaesu_of_one=0;
				int find_zero=0;
				for (register int j=end; j>=0; --j)
				{
					if (0==temp_where[j])
						find_zero=1;
					else
					{
						temp_where[j]=0;
						if (0==find_zero)
							++gaesu_of_one;
						else
						{
							for (register int k=j+1; k<j+2+gaesu_of_one; ++k )
								temp_where[k]=1;
							break;
						}
					}
				}
			}
			else
			{
				temp_where[find_last]=0;
				temp_where[find_last+1]=1;
			}
		}
	}
	free(temp_where);
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:30:15
Processing time 0.0142 sec