C语言之约瑟夫
题目描述
2k 个人站成一圈，从某个人开始数数，每次数到 m 的人就被杀掉，然后下一个人重新开始数，直到最后只剩一个人。现在有一圈人，k 个好人站在一起，k 个坏人站在一起。从第一个好人开始数数。你要确定一个最小的 m，使得在 k 个坏人均被杀死时 k 个好人都存活。
输入格式
一行一个整数 k。
输出格式
一行一个整数 m。
输入 3 输出 5 输入 4 输出 30 说明/提示 0<k<14其中前 k 个人是好人（编号 1~k）
· 后 k 个人是坏人（编号 k+1~2k）
· 从第一个人（好人，编号1）开始数数
· 每次数到 m 的人被处决，然后从下一个人重新开始数
· 要求找到一个最小的 m，使得在处决完 k 个人后，剩下的 k 个人全是好人
· 换句话说：前 k 次处决必须全是坏人
#include<stdio.h> #define MAX_K 13 #define MAX_N (2*MAX_K)//代表的是总人数，最多为26个人。 int check(int k,int m) { int next[MAX_N+2],prev[MAX_N+2];//next[]表示每个人的后者，prev[]代表每个人的前者 int n=2*k;//总人数 int i; for(i=1;i<=n;i++){//给每个人都用遍历来赋上编号 next[i]=i+1;//编号为i的人的后一个人的编号为i+1 prev[i]=i-1;//编号为i的人的前一个人的编号为i-1 } next[n]=1;//编号为2k的人即为最后一个人的下一个人编号为第一个人的编号1 prev[1]=n;//编号为1的人的前一个人的编号为2k即n int p=1;//从编号1开始数 int L=n;//代表剩余人数 for(i=0;i<k;i++){//循环k次，是因为要处决k个坏人 int steps=(m-1)%L;//计算实际需要走的步数，即走这些步才数到m编号 int cur=p;//当前位置 int pre=prev[p];//当前位置的前一个 int j; for(j=0;j<steps;j++){走steps步找到被处决的人数 pre=cur;// cur=next[cur]; } if(cur<=k){//如果处决的人编号小于k即处决的是好人，不符合题意 return 0; } next[pre]=next[cur];//前一个位置的下一个即被处决的人的位置变成了被处决的人的下一个人 prev[next[cur]]=pre;//被处决的人的下一个人的前一个人变成了被处决的人的前面的人 p=next[cur];//被处决的人排除之后，下一个开始计数的位置变成了被处决的人的下一个人 L--;//剩余人数减少一个人 } return 1; } int main() { int k; scanf("%d",&k); int m; //代表数到m的人即会被处决杀死 for(m=k+1;;m++){//因为第一个人是好人，m肯定不会是应该被处决的人。对m开始进行枚举，如果碰到符合条件的m，即符合上述函数，则就输出m if(check(k,m)){ printf("%d\n",m); break;//因为要求的是最小的m，所以只要碰到第一个符合题意的输出，就不用再在后面判断了 } } return 0; }一.上述代码采用双向循环链表。
什么是双向循环链表？
双向循环链表是一种特殊的数据结构：
· 双向：每个节点既知道下一个节点，也知道上一个节点
· 循环：链表的首尾相连，形成一个环
· 链表：一系列通过指针连接的数据节点
二.for(i=0;i<k;i++){
int steps=(m-1)%L;
int cur=p;//cur永远记录开始计数的人的位置
int pre=prev[p];
int j;
for(j=0;j<steps;j++){
pre=cur;//前一个人更新为当前位置，因为当前位置的人已经被杀死了
cur=next[cur];//当前开始计时位置为之前被杀死的人的后一个人
}//循环结束，cur就是被处决的人
if(cur<=k){
return 0;
}
next[pre]=next[cur];
prev[next[cur]]=pre;
p=next[cur];
L--;
}
详细解析上述部分代码：
1.因为从编号1开始走，走到编号2只需要走1步，即找到2只需要走1步，那么找到m只需要走m-1步。所以当m-1<L时，走的步数就是m-1，当人数为L时，走L步会回到起点，当m-1大于L时，走的步数即为余数。刚好满足上述式子。
2.
为什么初始化 pre = prev[p]？
· 在后续的循环中，pre 需要始终是 cur 的前一个人
· 开始时，cur = p，所以 pre 应该是 p 的前一个人
示例：
初始状态：
p=1,//从编号1开始数数 L=6,//剩余人数 m=3//每次数到m的人就会被杀掉
steps = (3-1)%6 = 2//数到m只需要实际走steps步
循环过程：
j=0: pre=1, cur=2
j=1: pre=2, cur=3
结果：cur=3（被处决的人）
上述循环结束后，cur表示的当前位置的人被处决，然后要想办法把该处决的人的编号排除。方法即为把被处决的位置变成被处决的后一个人，但后一个人的编号不变，只是位置改变。
当steps=0时，即循环不执行，直接处决当前位置cur即p
当m=1时，总是处决当前位置，即p=1时被处决，下次计数从第二个人开始，计数1，仍被处决，即当前位置被处决。
steps = (1-1)%L = 0
cur = p（被处决）
三.最后总结一下上述代码的思路：
用遍历对每个人进行编号，因为后续要利用双循环，所以要处理边界问题。因为排除被处决的人后要重新从下一个人开始计数，所以要定义一个变量p来表示从哪一个开始计数。然后对每一个人开始进行遍历，找应该被处决的人。定义走多少步可以找到处决者，为后续遍历找处决者提供基础。肯定要定义一个变量表示被处决者，又因为有双循环，前一个，后一个，当前者，索性把被处决者定义为当前者，当前者初始化为计数的位置，而这刚好便于去除当前者后的计数位置为下一个人，同时更好找到处决者时好改变前者后者的位置。既然有前者和后者，所以要定义。最后去除当前者，改变剩余者的位置。最后直到把所有的坏人都除掉之后，当前位置变成小于k的值，跳出该函数。只要输入的m符合题意，则就会返回1,用于后续主函数的输出。
写这篇的时候好痛苦啊！！！用了两个小时。