시작지점 0번째 실린더 위치를 p, k만큼 실린더가 돕니다.
선택된 실린더 p의 죄수는 처형당하며, 사라진 죄수의 다음 위치에 p가 설정됩니다.
이 작업이 반복되면서, 마지막 남은 죄수가 몇번째 인가, 그리고 처형된 순서대로 로그에 남기는 문제입니다.
이주짜리 과제...2주나?
단일 소스 코드로, 환형 리스트,클래스없이 구현하는게 제약조건이었습니다.
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#include<stdio.h>
#include<stdlib.h>
typedef struct prisoner {
int prisonerNum;
struct prisoner* next;
}PRISONER;
typedef struct killLog {
int *log;
}KILLLOG;
PRISONER* init(int size){ //리스트 선언,초기화
int num = 1;
PRISONER* neww = (PRISONER*)malloc(sizeof(PRISONER));
PRISONER* cur,* tmp = NULL;
cur = neww;
cur->prisonerNum = num;
if (size == 1) {
cur->next = neww;
return neww;
} //죄수가 한명일때, 쓸모없지만, 문제에서 제시한 범위는 1명 이상이다.
while (num != size) {
tmp= (PRISONER*)malloc(sizeof(PRISONER));
cur->next = tmp;
cur = tmp;
cur->prisonerNum = ++num;
}
cur->next = neww;
cur->prisonerNum = num;
return neww;
}
int roll(/*cbv*/PRISONER **killPoints, int size,KILLLOG *killLog,int *killCount) {
PRISONER* tmp = *killPoints;
int count = size;
if ((*killPoints)->next == *killPoints)
return 1;// 죽일 죄수가 하나뿐일떄
while (count != 1) {
*killPoints = (*killPoints)->next;
count--;
} // 죽일 죄수를 정한다.
while (tmp->next != *killPoints)
tmp = tmp->next;//죽일 죄수의 prev로 간다.
tmp->next = (*killPoints)->next; // 죽일 죄수의 링크드 리스트를 연결을 해제
tmp = *killPoints; //죽일 죄수는 tmp포인터가 이제 지목한다.
*killPoints = tmp->next; // 다음 죽일 죄수를 위해 포인터가 다음칸으로 이동한다.
//printf("current killpoint is %d \n", (*killPoints)->prisonerNum);
tmp->next = NULL; //죽일 죄수의 노드를 말끔히 지운다.
killLog->log[(*killCount)++]=tmp->prisonerNum;//죽일 죄수의 번호를 로그에 입력
//printf("kill number is : %d \n", tmp->prisonerNum);
free(tmp);//죽인다.
return 0;
//죄수가 1명이 되면 return statement는 true가 된다, 그렇지 않으면 false가 되어 함수가 반복된다.
}
int main() {
int n, k,result=0,killCount=0;
PRISONER *killMark;
KILLLOG *killLog;
scanf("%d", &n);
//죄수의 총 숫자
scanf("%d", &k);
//순번 카운트
if (!(n > 0 && n < 1001))
return 0; //예외처리
if (!(k > 0 && k < n))
return 0; //예외처리
killLog = (KILLLOG*)malloc(sizeof(KILLLOG));
killLog->log = (int*)malloc(sizeof(int)*n);
//문제 의도대로 살해 순번을 나타내기 위해 동적 배열 생성, 짜놓고도 무식한 방법이네요.
killMark = init(n);
//싱글 환형 링크드 리스트로 세팅 완료
while(result!=1)
result = roll(&killMark, k,killLog,&killCount);
//하나 남을때까지 죽이는 함수.
printf("survived prisoner's number is %d \nkilllog : ", killMark->prisonerNum);
for (int i = 0; i < killCount; i++){
printf("%d ", killLog->log[i]);
}
//킬 로그 출력
free(killMark);
free(killLog->log);
free(killLog);
//마지막 동적 생성된 구조체를 지운다.
}
/*
Project : Assignment for DataStruct
Creator : Changwon J.
Date : Nov 06, 2017
note : n ist prisoner number, k ist number for counting,
called "요셉문제"
*/
|
댓글 없음:
댓글 쓰기