P1996 约瑟夫问题
·
题目背景
约瑟夫是一个无聊的人!!!
题目描述
n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,……依次类推,直到所有的人都出圈,请输出依次出圈人的编号.
输入输出格式
输入格式:
n m
输出格式:
出圈的编号
输入输出样例
输入样例#1: 复制
10 3
输出样例#1: 复制
3 6 9 2 7 1 8 5 10 4
说明
m, n \le100m,n≤100
算法分析:
单循环链的数据结构,n人围成一圈,把每个人看成一个结点,n人之间的关系采用链接的的方式,即每一个节点都有一个前继节点和后继节点,每一个节点有一个指针指向下一个节点,最后一个节点指针指向第一个节点。
当m人出列时,将m节点的前继节点指针指向m的后继节点指针。
代码实现:
#include<bits/stdc++.h>
using namespace std;
#define N 105
int main()
{int a[N],n,m,p=0,ans=1,j;//p记录总共选出来来了多少数,ans记录是否到mcin>>n>>m;for(int i=1;i<n;i++)a[i]=i+1;//建立链表a[n]=1;j=n;//现在a[n]=1while(p<n){while(ans<m)//计数是否达到m{j=a[j];ans++;}cout<<a[j]<<" ";//到队,出队p++;a[j]=a[a[j]];//指向后继节点ans=1;//计数器置1}return 0;
}