Problem D: josephus问题——约瑟夫环变式

又碰到约瑟夫环的问题了，有一说一，这个经典问题确实很有意思，这道题目主要是引入了几个变量罢了，本质完全一样。但是这道题目测试点出的不够严谨，没有考虑到n=1,以及m=1的情况，使得我起初不够完善的代码也能AC，这些地方我在给出的代码已经补上去了。

Problem D: josephus问题

Time Limit: 1 Sec Memory Limit: 64 MB Submit: 755 Solved: 298

Description

josephus问题其实就是一个游戏，一群小孩围成一个圈，设置一个数，这个数是个小于小孩总数大于0的一个整数,从第一个小孩开始报数，当其中一个小孩报到你设置的那个数的时候离开那个圈，这样一来反复报下去，直到只剩下最后一个小孩的时候那个小孩就是胜利者。 现在的问题是设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n, s和m，求出这n个人的出局序列。请以n = 9, s = 1, m = 5为例，人工模拟Josephus的求解过程以求得问题的解。 出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。 本题可以对多个测试案例进行测试。

Input

第一行输入测试案例数T 以下T行,每一行是一个测试案例，分别输入n,s,m,以一个或多个空格隔开

Output

每个测试案例输出2行， 第一行输出出局顺序 第2行输出"** win.",其中**是胜利者编号，即最后出局者

Sample Input

1 9 1 5

Sample Output

5 1 7 4 3 6 9 2 8 8 win.

代码如下

#include<bits/stdc++.h> using namespace std; int main() { int t,n,s,m,a[1000]; while(cin>>t) { while(t--) { cin>>n>>s>>m; a[0]=1; for(int i=1;i<n;i++) { a[i]=i+1; } a[n]=1; int count=0,before,after=s-1; if(n==1) cout<<"1 win."<<endl; else if(m==1) { for(int i=s;i<=n;i++) cout<<i<<" "; for(int i=1;i<s;i++) cout<<i<<" "; int p; if(s==1) p=n; else p=s-1; cout<<endl<<p<<" win."<<endl; } else { while(count!=n-1) { for(int i=1;i<=m;i++) { before=after; after=a[after]; } a[before]=a[after]; cout<<after<<" "; count++; } cout<<before<<endl; cout<<before<<" "<<"win."<<endl; } } } }

本质还是链表的思想，我之前已经写过，想看的可以看这篇，我在这里就不浪费时间阐述了。

约瑟夫环——链表思想