在上周的总结中，好像提了一个问题。
有N个人围成一圈，第m个人的序号是m.从第1个人开始顺序报号1、2、3、4、......, 凡报到3的倍数的人出圈。请计算最后留在圈子里的人的序号。
（N <= 10000）.
后来想了一下这个问题好像有点僵化，于是又做了一些改动。
有N个人围成一圈，第m个人的序号是m.从第1个人开始顺序报号1、2、3、4、......, 凡报到K的倍数的人出圈。请计算最后留在圈子里的人的序号。
（N <= 10000， K <= 10000）.
对于这个问题，有很多解决问题的方案，不妨来看看。
数组标记
这个思路很好理解。我们用一个数组标记第i个人有没有出队，每当走过K个没有被标记的人时，就使当前的人出队，直到剩下一个人。如果到达了最后一个人，便从第一个人继续计数。
点击查看代码
#include<stdio.h>
#include<string.h>
#define N 10010;
int st[N];//st数组中0表示未出列， 1表示已出列
int main(){
int n, k;
scanf("%d%d", &n, &k);
int num = n, per = 1;//num表示还有多少人,per表示走到了第几个人
while(num > 1){
int t = 0;//t表示这次报数中已经有几个人报数
while(t < k){
if(!st[per]){
per ++;
t ++;
}
else{
per ++;
}
if(per == n + 1)per = 1;//如果走到了最后一个人便回到开头
}
st[per] = 1;//表示第per个人出列
num --;
}
for(int i = 1;i <= n;i ++)
if(!st[i]){
printf("%d", i);
break;
}
return 0;
}
数组的删除是非常麻烦的，需要把某一个位置的元素删除，然后其余之后的元素全都向前移动。
在上述方法中，用了一个数组标记的方法来体现成员是否已经出列，可以说是比较巧妙了。
链表实现成员出入
链表下的删除是比较简单的，只需把前一项的指针指向后一项的地址，并释放该项的内存即可。
点击查看代码
#include<stdio.h>
#include<stdlib.h>
typedef struct person{
int data;
struct person *next;
}PERSON;
int main(){
int n, k;
scanf("%d%d", &n, &k);
PERSON *head = NULL, *p = NULL, *q = NULL;
for(int i = 1;i <= n;i ++){
p = (PERSON*)malloc(sizeof(PERSON));
p -> data = i;
p -> next = NULL;
if(head == NULL){
head = p;
q = head;
}
else{
q -> next = p;
q = q -> next;
}
}
q -> next = head;
PERSON *t = head;
while(t -> next != t){
for(int i = 1;i < k - 1;i ++)t = t -> next;//从当前人向后走过k - 2个人
PERSON *out = t -> next;//out是第k个人
PERSON *ne = out -> next;//ne是第k + 1个人
t -> next = ne;//让第k - 1个人下面的人变为第k + 1个人
t = t -> next;// 走向下次报数的第一个人
free(out);
}
printf("%d", t -> data);
return 0;
}
想起来好久没写链表了，写链表是真的麻烦。这种链表的形式无疑是最形象描述出列的方式。
不过做题的时候个人不喜欢写链表，因为写链表真的麻烦，而且指针空间操作也比较消耗时间。
模拟队列
这是个人最喜欢的做法。一方面这个做法好写，另一方面这种算法确确实实运用到了队列FIFO的性质。
把i个人看成正在排队的i个人，如果排到队头的人的队号是k的倍数，就让他出队，否则让他继续在后面排队，当队伍里只有一个人时，这个人的编号便是答案了。
在这里，我们用数组模拟队列。
点击查看代码
#include<stdio.h>
#define N 10010;
int main(){
int hh = 1, tt;//hh(head)表示队头，tt(tail)表示队尾
int q[N];
int n, x;
scanf("%d%d", &n, &x);
tt = n;
for(int i = 1;i <= n;i ++){
q[i] = i;
}
while(tt > hh){//只要队尾在队头之后，就说明队伍里不止有一个人
if(hh % x != 0){
tt ++;
q[tt % N] = q[hh % N];//让队头的人重新回到队尾，并对N取模防止数组空间不够
hh ++;
}
else{
hh ++;
}
}
printf("%d", q[tt % N]);
return 0;
}
这种写法码量极小，真是棒极了！
以上是个人提供的三种做法，如果各位有更好的做法，可以一起交流讨论。
标签：个人,int,per,next,链表,++,出队,关于,报数 From： https://www.cnblogs.com/Joci-zhuoxue/p/16990337.html