2878: 【例60.2】 约瑟夫问题

内存限制：64 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：3 解决：3

题目描述

传说约瑟夫当年活下来就是靠快速计算这个问题。
$n$个人围成一圈，编号依次为 $1$,$2$,$3$…$n$。从第一个人开始报数，数到 $m$的人出列，再由下一个人重新从$1$开始报数，数到$m$的人再出圈。以此类推，直到所有的人都出列。请输出依次出圈人的编号。

输入

两个整数 $n$,$m$($1≤n,m≤100$)。

输出

$n$ 个用空格分隔的整数，表示出圈人的编号。

样例输入 复制 

6 4

样例输出 复制 

4 2 1 3 6 5

提示

#include<iostream>
using namespace std;
main()
{
    bool a[101]={0};
    int n,m,i,f=0,t=0,s=0;
    cin>>n>>m;
    do
    {
        ++t;//逐个枚举圈中的所有位置
        if(t>n)
            t=1;//数组模拟环状，最后一个与第一个相连
        if(!a[t])
            s++;//第t个位置上有人则报数
        if(s==m)//当前报的数是m
        {
            s=0;//计数器清零
            cout<<t<<' ';//输出被杀人编号
            a[t]=1;//此处人已死，设置为空
            f++;//死亡人数+1
        }
    }while(f!=n);//直到所有人都被杀死为止
    return 0;
}

来源/分类

提交提交记录统计露一手!