Question

C语言：有n人围成一圈，顺序排号。从第1个人开始报数（从1到3报数），凡报到3的人退出圈子，

问最后留下的是原来的第几号的那位。 （直接要答案，谢谢）

Answer 1

法一（模拟法）：

#include<iostream>
using std::cin;
using std::cout;
int main()
{
    int n;
    cout<<"请输入n= ";
    cin>>n;
    if(n<2)
    {
    cout<<"n必须大于2!\n请重新输入n= ";
    cin>>n;
    }
    bool * a = new bool [n+1];
    a[0]=false;
    for(int i=1;i<n+1;i++)
    a[i]=true;
    int x,k=n;x=i=0;//i为每次循环计数变量，x为人员序号，K为剩余人数
    while(k!=0)
    {
    x++;
    if(x>n) x=1;//当人员到达数组尾，序号重设为1
    if(a[x])i++; // 跳过已退出人员
    if(i==3)
    {a[x]=false;i=0;k--;}//当数到3时，退出人员设为false，剩余人数减1，i设为0，重新计数
    }
    cout<<"留下来的人序号为: "<<x<<"\n";
    delete [] a;
    cin.get();
    cin.get();//等待下一次键击关闭窗口
    return 0;
}

法二（递归法）：

此题可用数学方法求解。

设有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 <iostream>
using namespace std;
const int m = 3;
int main()
{
    int n,f=0;
    cin >> n;
    for (int i=2;i<=n;i++) 
    f=(f+m)%i;
    cout <<f+1<<endl;
}

Answer 2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
int n,i,j,k;
int* array;
while(scanf("%d",&n)==1 && n)
{
array = (int*)malloc(sizeof(int)*n);
memset(array,0,sizeof(int)*n);
j=-1;
for(i=0;i<n-1;i++)
{
k=3;
while(k--)
{
j = (j+1)%n;
while(array[j])
{
j = (j+1)%n;
}
}
array[j] = 1;
}
for(i=0;i<n;i++)
if(array[i]==0)
printf("Alive: %d\n",i+1);
free(array);
}
}

追问

怎么复制到vc++6.0中编译有错呢？

追答

错误信息是什么

Answer 3

#include <stdio.h>
int main()
{
int a[10],b[10];
int i=0,j=0;
int n,s=1;
int k=0;
printf("please input num:");
scanf("%d",&n);

for(i=0;i<n;i++)
{
a[i]=s;
s++;

}

while(n>2)
{
for(i=0;i<n;i++)
{
k++;

if(k!=3)
{
b[j]=a[i];

j++;
}
if(k==3)
{
k=0;

}
}
n--;
for(i=0;i<n;i++)
{
a[i]=b[i];

}
j=0;
}

printf("the num leave is %d and %d \n",a[0],a[1]);

return 0;
}
亲，求评价哦。

追问

怎么复制到vc++6.0中编译有错呢？

追答

没有错误。你看一下是不是你的运行的终端打开着，没关。