Question

c语言编写n个人围成一圈，按1、2、3报数，报到3的人退出，求最后留在圈中的人是最初n个人中的第几个(用指

c语言编写n个人围成一圈，按1、2、3报数，报到3的人退出，求最后留在圈中的人是最初n个人中的第几个(用指针实现）

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>
const int M = 3;
int main()
{
    int n, s = 0;
    scanf("%d", &n);
    for (int i = 2; i <= n; ++i)
        s = (s+M)%i;
    printf("%d\n", s+1);
    return 0;
}

Answer 2

以前做过的，贴一个给你，人数和报的数都可以输入的 #include<stdio.h> #include<stdlib.h>//应用函数调用来实现 void Fun_Kill(int *pa,int n,int m){for(int i=0;i<n;i++){*(pa+i)=i+1;//给每个人编号}i=0;int mCount=0; int iCount=0; while(iCount<n-1)//控制循环条件：出局人数小于总人数{if(*(pa+i)!=0)//报数条件,编号不为0{mCount++;}if(mCount==m){printf("%d is out!\n",*(pa+i));//输出出局者的编号 mCount=0;//重新开始报数 iCount++;//出局人数统计 *(pa+i)=0;//出局者编号改为0,下次报数不进入计数}i++;//报数的同时指针也开始走动if(i==n){i=0;//当i==n的时候，让i=0，让指针重新指向第一个人，循环计数}}for(i=0;i<n;i++){if(*(pa+i)!=0){printf("%d is survival!",*(pa+i));}}}int main(){int n,m;printf("请输入总人数:"); scanf("%d",&n); printf("请输入要报的数:"); scanf("%d",&m); int *pKill=(int *)malloc(sizeof(int)*n); Fun_Kill(pKill,n,m);