2017년 11월 21일 화요일

c 룰렛게임?

죄수 n ( 1이상 1000이하) 명, 회전 횟수 k ( 1이상 n 이하)가 있으며,
시작지점 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 "요셉문제" 
*/

댓글 없음:

댓글 쓰기