'Membership' 카테고리의 글 목록

« 2024/05 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

(10 ^ 7)! 의 자리수를 어떻게 구할 수 있을까? (0)	2015.03.29
기본적인 LinkedList 구현 (0)	2015.01.20
루트값 까지 배수를 제외해서 소수값 구하는방법 (0)	2015.01.16
백트래킹 기초 주사위 굴리기 (0)	2015.01.15
재귀로 글래스파이어 활용 (0)	2015.01.12

(10 ^ 7)! 의 자리수를 어떻게 구할 수 있을까?

Membership/알고리즘 2015. 3. 29. 00:21 |

(10 ^ 7)! 의 자리수를 어떻게 구할 수 있을까?

- log를 이용하면 자리수를 쉽게 구할 수 있다.

log1010 = 1,

log10100 = 2,

log101000 = 3

...

이렇게 log는 자리수를 나타 낼 수 있다.

이를 이용하여

팩토리얼의 자리수를 구한다면,

10! 은 1*2*3*4*5*6*7*8*9*10이다.

1*2 = 2;

2*3 = 6

6*4 = 24

24*5 = 120

120 * 6 = 720

720 * 7 = 5040

5040 * 8 = 40320

40320 * 9 = 362880

362880 * 10 = 3628800

이렇게 7자리 수가 된다.

하지만 이렇게 구한다면 10^7 팩토리얼의 자리수인 65657060 자리수를 표현해야한다.

long long형을 사용하여도 9223372036854775807i64(8바이트,64비트)까지 밖에 표현 못한다.

이때 log를 이용하여 팩토리얼 계산시 자리수를 double 형으로 계산한다면 10^7의 값인 천만 팩토리얼의 자리수도 연산가능하다.

(정확히 개념이 이해가 되질 않지만, 일단 적어본다...ㅜㅜ)

'Membership > 알고리즘' 카테고리의 다른 글

유클리드 호제법 정리 (2)	2015.04.15
기본적인 LinkedList 구현 (0)	2015.01.20
루트값 까지 배수를 제외해서 소수값 구하는방법 (0)	2015.01.16
백트래킹 기초 주사위 굴리기 (0)	2015.01.15
재귀로 글래스파이어 활용 (0)	2015.01.12

Posted by *me

:

(10 ^ 7)! 의 자리수를 어떻게 구할 수 있을까? (0)	2015.03.29
기본적인 LinkedList 구현 (0)	2015.01.20
백트래킹 기초 주사위 굴리기 (0)	2015.01.15
재귀로 글래스파이어 활용 (0)	2015.01.12
재귀의 기초 0의 갯수 출력 (0)	2015.01.12

int first=0,last=0,state;//큐에서 사용
typedef struct List{
	int htime;
	int mtime;
	char name[20];
	List *next;
}linkedList;
linkedList* queue[20]={NULL};//크기 20짜리 큐
linkedList* createList(int* time,char* putName){
	linkedList* makeList;
	makeList = (linkedList*)malloc(sizeof(linkedList));
	makeList->htime = time[0];
	makeList->mtime = time[1];
	strcpy(makeList->name,putName);
	makeList->next = NULL;
	return makeList;
}
void insertList(linkedList* list,int* time, char* name){
	linkedList* insertNode;
	linkedList* temp;
	insertNode = createList(time,name);
	int timeSum,newtimeSum;
	while(1){
		timeSum = list->htime*60 + list->mtime;
		newtimeSum = time[0]*60 + time[1];
		if(timeSum>newtimeSum){
			insertNode->next=list;
			temp ->next = insertNode;
			//printf("중간에 삽입");
			break;
		}
		else if(list->next == NULL){
			list->next = insertNode;
			//printf("마지막에 삽입");
			break;
		}
		temp = list;
		list = list->next;
	}
}
void pushQue(linkedList* list){
	last = (last+1)%sizeof(queue);//값을 넣을 last+1의 위치
	if(last == first){//값을 넣을곳에 아직 pop하지 않은 값이있으면 큐는 가득참
		printf("Queue Full!\n");
		last--;
	}else{
		queue[last]= list;//큐에 데이터를 넣는다.
		state++;
		printf("%d%d:%d%d %s 등록 push\n",queue[last]->htime /10,queue[last]->htime%10,queue[last]->mtime/10,queue[last]->mtime%10,queue[last]->name);
	}
}
linkedList* popQue(){
	first = first%sizeof(queue);//pop할 위치의 first값
	if(first==last){//first가 last와 일치한다는것은 큐에 아무것도 없음을 의미한다.
		/*printf("Queue Empty!!\n");*/
		return NULL;
	}else{
		++first;
		--state;
		return queue[first];//last와 일치 하지 않는다면 큐의 값을 pop한다 이때 +1된 first값을 pop해야 다시한번 pop했을때 조건을 정확히 확인 가능하다.
	}
}
void problem2(){
	//리스트는 저장시 시간이 빠른순으로 저장하도록 하였고, 리스트 데이터는 problem2에서 임의로 만들어 놓았습니다.
	linkedList* root;
	int time[2] = {NULL};//리스트에서 사용할 시간 저장용 변수
	char name[20] = {NULL};//이름저장용
	root=createList(time,name);//루트노드를 만듭니다.
	/* 시간 역순으로 입력한다
	00:09 김영희 등록 push
	00:08 김소멤 등록 push
	00:07 홍길동 등록 push 
	*/
	time[0]=0;
	time[1]=9;
	strcpy(name,"김영희");
	insertList(root,time,name);

time[0]=0;
	time[1]=8;
	strcpy(name,"김소멤");
	insertList(root,time,name);

time[0]=0;
	time[1]=7;
	strcpy(name,"홍길동");
	insertList(root,time,name);
			
	/* 00:11 김철수 등록 push
	00:12 김삿갓 등록 push
	00:15 이지은 등록 push
	00:18 강개리 등록 push
	*/
	time[0]=0;
	time[1]=11;
	strcpy(name,"김철수");
	insertList(root,time,name);

time[0]=0;
	time[1]=12;
	strcpy(name,"김삿갓");
	insertList(root,time,name);

time[0]=0;
	time[1]=15;
	strcpy(name,"이지은");
	insertList(root,time,name);

time[0]=0;
	time[1]=18;
	strcpy(name,"강개리");
	insertList(root,time,name);

int t=0,m=0;
	root=root->next;//root는 널값이기 때문에 다음 노드부터 사용한다.
	for(t=0;t<24;t++){
		for(m=0;m<60;m++){
			linkedList* r;
			if(m%10 == 0){//매 10분 마다
				printf("%d%d:%d%d분\n",t/10,t%10,m/10,m%10);// 시간 출력

r=popQue();//pop를 한다
				if(r!=NULL){//pop가 null 이 아니면
					printf("%s 처리 pop\n",r->name);//출력
					r=popQue();//두번해야한다
					if(r!=NULL)
						printf("%s 처리 pop\n",r->name);//출력
				}
				//등록현황확인
				if(state>0){//큐 데이터 개수인 state가 존재한다면
					printf("큐의 상황( ");//현재 상황을 출력한다
					int temp;
					temp = first;//큐 pop는 first를 사용하기에 임시로 값을 복사한다

for(++temp;temp!=(last+1);(++temp)%sizeof(queue)){//temp가 last와 만날때 즉 모든 큐의 값을 출력했을때까지 반복
						printf("%s ",queue[temp]->name);//큐내의 값을 출력
					}
					printf(")\n");
				}

}
			if(root!=NULL && (root->htime == t&& root->mtime == m)){//리스트에 있는 값을 순환한다. 
				pushQue(root);//리스트에 저장되어있는 노드의 시간과 분이 현재시간과 일치할때 해당 노드를 큐에 저장한다
				root = root->next;//리스트는 다음 노드를 가리킨다.
			}
		}
	}

}

'Membership > 알고리즘' 카테고리의 다른 글

기본적인 LinkedList 구현 (0)	2015.01.20
루트값 까지 배수를 제외해서 소수값 구하는방법 (0)	2015.01.16
백트래킹 기초 주사위 굴리기 (0)	2015.01.15
재귀로 글래스파이어 활용 (0)	2015.01.12
재귀의 기초 0의 갯수 출력 (0)	2015.01.12

Posted by *me

:

..

Notice

Category

Tags

Recent Posts

Recent Comments

Archives

Links

'Membership'에 해당되는 글 8건

유클리드 호제법 정리

'Membership > 알고리즘' 카테고리의 다른 글

(10 ^ 7)! 의 자리수를 어떻게 구할 수 있을까?

'Membership > 알고리즘' 카테고리의 다른 글

기본적인 LinkedList 구현

'Membership > 알고리즘' 카테고리의 다른 글

루트값 까지 배수를 제외해서 소수값 구하는방법

'Membership > 알고리즘' 카테고리의 다른 글

백트래킹 기초 주사위 굴리기

'Membership > 알고리즘' 카테고리의 다른 글

재귀로 글래스파이어 활용

'Membership > 알고리즘' 카테고리의 다른 글

재귀의 기초 0의 갯수 출력

'Membership > 알고리즘' 카테고리의 다른 글

연결리스트와 큐를 이용한 프로그램

'Membership > 알고리즘' 카테고리의 다른 글

티스토리툴바