约瑟夫环

题目描述
n个人（0,1,2,3,4...n-1），围成一圈，从编号为k的人开始报数，报数报到m的人出队（报数是1,2,...m这样报的）。下次从出队的人之后开始重新报数，循环往复，当队伍中只剩最后一个人的时候，那个人就是大王。现在，给定n，k，m，请你求出大王的编号。

输入描述:
输入一行包含三个整数n,k,m （1<=n<=100,1<=k<=n-1,1<=m<=100）

输出描述:
输出一个整数

示例1
输入：5 1 2
输出：3

解题思路：
通常的 约瑟夫问题 从编号为0开始，可用动态规划求解：声明长度为 n 的一维数组 dp ，其中 dp[i] 表示 i 个人玩游戏的大王编号，则 dp[n] 即为题解，相应的状态转移方程为：
dp[i] = (dp[i-1] + m) mod i（i > 1），初始化状态：dp[1] = 0。
而本题并不是从编号为0开始，是从编号为 k 开始，则只需要在最后的 dp[n] 上加上 k 即可。由于 dp[n] + k 有可能超过 n 因此，还需要对 n 取余。还有一点要注意，不能在迭代初始状态加上 k ，因为上述的状态转移方程就是基于编号0开始而推导得到的。
另外，可以看出状态转移方程的当前状态只与前一个状态有关，因此利用滚动数组的思想将空间优化至

C# 代码：

using System;
class Program{
  static void Main(){
      string input;
      string[] tokens;
      while((input = Console.ReadLine()) != null){
          tokens = input.Split();
          int n = int.Parse(tokens[0]);
          int k = int.Parse(tokens[1]);
          int m = int.Parse(tokens[2]);
          int res = 0;
          for(int i = 1; i <= n; i++) res = (res + m)%i;
          Console.WriteLine((res + k)%n);
      }
  }
}