东方博易oj——3119 - 约瑟夫问题2（链表）

---

题目

题目描述

约瑟夫问题：有$ｎ$只猴子，按顺时针方向围成一圈选大王（编号从$\mathrm{１}$到$ｎ$），从第$\mathrm{１}$号开始报数，一直数到$ｍ$，数到$ｍ$的猴子退出圈外，剩下的猴子再接着从$1$开始报数。

就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入$ｎ，ｍ$后，输出最后猴王的编号。

输入

每行是用空格分开的两个整数，第一个是 $n$, 第二个是$m(0<m,n<=300)$。

最后一行是：0 0

输出

对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号。

样例

输入

6 2
12 4
8 3
0 0

输出

5
1
7

标签

链表

AC代码

#include<bits/stdc++.h>
using namespace std;
void ysf(int n,int m) {int llist[10005],id,i,j;for(i=0; i<n; i++)	{llist[i]=i+1;	}llist[n]=1;for(i=1; i<=n; i++) {j=1;while(j<m) {id=llist[id],j++;	}llist[id]=llist[llist[id]];}cout<<llist[id]<<endl;
}
int main() {int n=1,m=1;while(n!=0&&m!=0) {cin>>n>>m;if(n==0&&m==0)break; ysf(n,m);}return 0;
}