Submit: 323 Solved: 164
Description
你听说过约瑟夫问题吗？问题大致如下：首先n个人围成一个圈，标记为1到n号。接着，从1号开始报数（从1开始），然后2号报数，然后3号。。。当有人报到到m时，这个人就要踢出比赛，然后从被踢出的人的下一个人开始，重新报数（从1开始）。这样经过n-1次后，就只剩下了一个人，问最后剩下的那个人是几号？
Input
第1行为T，表示有T组数据；
第2行到第T+1开始,每行输入n和m，n表示有几个人，m为上述的每报数m次就要踢出一个人
1<=n<=100, 1<=m<=100
Output
一个数，表示最后剩下了几号
Sample Input
2
5 3
6 4
Sample Output
4
5
瞎几把乱写的，竟然还可以运行。。。
这个是注释版，最下面有没有注释的版本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/*
日期：2019.1.3 17:46 修改版
*/
using namespace std;
const int mx=103;
struct Node
{
int x;//序号
Node *bef;//上一个
Node *next;//下一个
};
Node *create(int n)//创建
{
Node *head=NULL,*p,*p2;
int sz=sizeof(Node);
for (int i=1;i<=n;++i)
{
p=(Node *)malloc(sz);//给当前这个p分配空间
p->x=i;
p->next=NULL;//p的下一个是NULL，因为现在不清楚下一个是什么
if (head==NULL)
{
p->bef=NULL;//head的上一个先暂定为NULL，因为不知道最后一个是什么
head=p;//head等于当前这个p
p2=head;//p2等于head
}
else
{
p->bef=p2;//当前这个p指向上一个p2
p2->next=p;//上一个p2指向当前这个p
p2=p;//p2等于p，接替当前的p
}
}
head->bef=p;//指定head的上一个，使链表形成一个环
p->next=head;//循环出来后的当前的p的下一个指向head，与上一句共同使链表形成一个环
return head;//返回head的地址，因为是malloc出来的空间，不会因为函数的结束而消失，需手动free()
}
Node *delt(Node *np)//删除
{
Node *p,*p2;
p=np->bef;//p等于要删除的np的上一个
p2=np->next;//p2等于要删除的np的下一个
p->next=p2;//p的下一个指向p2
p2->bef=p;//p2的上一个指向p
free(np);//释放当前np的空间
return p2;//返回p2的地址，即要删除的np的下一个
}
int main()
{
int t,n,m;
cin>>t;
while (t--)
{
cin>>n>>m;
Node *head=NULL,*p,*p2;
head=create(n);//返回head的地址，方便开头
for (int i=1;i<n;++i)//n个人，(n-1)轮循环决出最后一人
{
int k=0;//想了想还是从0开始数比较直观，好看，从1开始数的代码太丑陋了。。。
p=head->bef;
while (k<m)
{
p2=p->next;//p2等于p的下一个
p=p2;//p等于p2
k++;//我用了比较土的方法是，数数。。。
}
head=delt(p2);//新一轮的head等于要删除的结点的下一个
}
printf("%d\n",head->x);
free(head);//释放head的空间
}
}
去注释版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/*
日期：2019.1.3 17:53 修改去注释版
*/
using namespace std;
const int mx=103;
struct Node
{
int x;
Node *bef;
Node *next;
};
Node *create(int n)
{
Node *head=NULL,*p,*p2;
int sz=sizeof(Node);
for (int i=1;i<=n;++i)
{
p=(Node *)malloc(sz);
p->x=i;
p->next=NULL;
if (head==NULL)
{
p->bef=NULL;
head=p;
p2=head;
}
else
{
p->bef=p2;
p2->next=p;
p2=p;
}
}
head->bef=p;
p->next=head;
return head;
}
Node *delt(Node *np)
{
Node *p,*p2;
p=np->bef;
p2=np->next;
p->next=p2;
p2->bef=p;
free(np);
return p2;
}
int main()
{
int t,n,m;
cin>>t;
while (t--)
{
cin>>n>>m;
Node *head=NULL,*p,*p2;
head=create(n);
for (int i=1;i<n;++i)
{
int k=0;//想了想还是从0开始数比较直观，好看，从1开始数的代码太丑陋了。。。
p=head->bef;
while (k<m)
{
p2=p->next;
p=p2;
k++;
}
head=delt(p2);
}
printf("%d\n",head->x);
free(head);
}
}