乐鑫科技19年C语言笔试题_深圳宇芯 笔试题

本文始自林夕成_MC_Wang发布于19年9月。本文作者对代码进行了优化，使其符合题目要求

花果山总共有n只猴子，猴子们确定通过以下方法选择大王：所有猴子从0到n-1进行编号，按照顺序围成一圈；
从0号开始，每隔m只猴子会依次连续淘汰k只猴，淘汰的猴会出圈（例如，最开始0到m-k-1号会被保留，m-k到m-1
号淘汰，m到2m-k-1号保留，2m-k到2m-1号淘汰，以此类推）；最后剩下1只猴未被淘汰，那只猴将会成为大王。
输入描述：
每组输入包括3个整数n,m,k其中1<=n<=1000000, k<m。
输出描述：
输出只有一行，包含一个整数，表示美猴王的号码。
示例：
输入：10 3 2
输出：6

#include <stdio.h>
#include <malloc.h>
typedef struct node{
    int data;
    struct node *prior;
    struct node *next；
}looplist;

looplist* double_looplist_create()
{
    looplist *h = (looplist *)malloc(sizeof(looplist));
    h->next = h;
    h->prior = h;
    return h;
}
void looplist_insert_head(looplist *h,int value)
{
    looplist *temp = (looplist *)malloc(sizeof(looplist));
    temp->data = value;
    if(h->next == h)
    {
        temp->next = h;
        temp->prior = h;
        
        h->next = temp;
        h->prior = temp;
    }
    else
    {
        temp->next = h->next;
        temp->prior = h;
        
        h->next->prior = temp;
        h->next = temp;
    }
}
looplist * looplist_cut_head(looplist *h)
{
    looplist *temp = h;
    while(h->next != temp)
    {
        h = h->next;
    }
    temp->next->prior = h;
    h->next = temp->next;
 
    free(temp);
    temp = NULL;
    
    return h->next；
}
void looplist_show(looplist* h)
{
    looplist *p = h; 
    do
 {
        printf("%d\t ",p->data);
  	p = p->next;
 }
    while(p != h);
    putchar(10);
}
void monkey_king(int n,int m,int k)
{
    looplist *h = double_looplist_create();
    looplist *temp = NULL;
    int i;
    for(i = n-1;i>=0;i--)
    {
        looplist_insert_head(h,i);
    }
    h = looplist_cut_head(h);
    while(h->next != h)
    {
        looplist_show(h);
        printf("\n");
        for(i = 1;i<= m;i++)
        {
            h =h->next;
        }
        for(i = 1;i<=k;i++)
        {
            if(h->prior != h)
            {
                temp = h->prior;
                
                h->prior = temp->prior;
                temp->prior->next = h;
                
                free(temp);
                temp = NULL;
                }
        else break;
        }
    }
    printf("the monkey king is%d\n",h->data);
    free(h);
    h = NULL;
}
int main()
{
    int n,m,k;
    printf("请输入参数：\n");
    scanf("%d %d %d",&n,&m,&k);
    
    if(n<1||n>99999||k>=n||k<1)
    {
        printf("输入参数有误\n");
        return -1;
    }
    else if(n==1)
    {
        printf("the monkey king is number:%d",n-1);
        return 0;
    }
    else
    {
        monkey_king(n,m,k);
        return 0;
    }
}
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
108
109
110
111
112
113
114
115
116
117
118
119
120