Question

M个人围成一圈报数，报到N的人出列，输出出列顺序!用C语言实现!

Answer 1

此题可用数学方法求解。

设有n个人（编号0~(n-1)），从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数  （用数学方法解的时候需要注意应当从0开始编号，因为取余会取到0解。）

实质是一个递推，n个人中最终留下来的序号与n-1个人中留下来的人的序号有一个递推关系式。

假设除去第k个人，则

0, 1, 2, 3, ..., k-2, k-1, k, ..., n-1　         // 原始序列　(1)

0, 1, 2, 3, ..., k-2,      , k, ..., n-1　　      // 除去第k人，即除去序号为k-1的人   (2)

k, k+1, ..., n-1,    0,    1,        ..., k-2　　// 以序号k为起始，从k开始报0  (3)

0, 1,     ..., n-k-1, n-k, n-k+1, ..., n-2　  // 作编号转换，此时队列为n-1人　 (4)

变
换后就完完全全成为了(n-1)个人报数的子问题，注意(1)式和(4)式，是同一个问题，不同的仅仅是人数。比较(4)和(3)，不难看
出，0+k=k, 1+k=k+1, ... ，(3)式中'0'后面的数字，（(n-3)+k）%n=k-3,（(n-2)+k）%n=k-2,
对于(3)式中'0'前面的数字，由于比n小，也可看作(0+k)%n=k,  (1+k)%n=k+1,  故可得出规律：

设(3)中某一数为x' , (4)中对应的数为x，则有：x'=(x+k)%n.

设x为最终留下的人序号时，队列只剩下1人时，显然x=0; 此时可向前回溯至2人时x对应的序号，3人时x对应的序号……直至n人时x的序号，即为所求。

#include <stdio.h>
int main()
{    
int n,m,s=0;    
scanf("%d%d",&n,&m);    
for (int i=2;i<=n;++i)    
{s=(s+m)%i;    
printf("%d\n",s+1);}    
return 0;
}

Answer 2

//M个人围成一圈报数，报到N的人出列，输出出列顺序

#include<stdio.h>
#define MaxNumOfPerson 100

void main()
{
int Array[MaxNumOfPerson];
int M,N;

printf("请输入报数人数(M):\n");
scanf("%d",&M);
printf("请输入报点(N):\n");
scanf("%d",&N);

for(int i= 0;i<M;i++)
Array[i]= i+1;

int Total,RecordCount;
Total = 0;
RecordCount = 0;

printf("出圈顺序为:\n");

while(Total<M)
{
for(i=0;i<M;i++)
{
if(Array[i])
{
RecordCount++;
if( RecordCount % N ==0)
{
printf("%d ",Array[i]);
Array[i] = 0;
}
}
}
}
}

Answer 3

//约瑟夫问题，利用二个数组，一个前指，一个后指，模拟指针。
#include<stdio.h>

#define MAX 100
int main()
{
int n,m;//n个人,报到m
scanf("%d%d",&n,&m);
int next[MAX];
int pre[MAX];
int i,k;
next[0]=1;
for(i=1;i<=n;i++) {next[i]=i+1;pre[i]=i-1;}
next[n]=1;pre[1]=n;
k=0;
while(k!=next[k])
{
for(i=1;i<=m;i++)
k=next[k];
next[pre[k]]=next[k];
pre[next[k]]=pre[k];
}
printf("%d\n");

return 0;
}