约瑟夫环

据说著名历史学家Josephus（约瑟夫）经历过以下故事：在罗马人占领乔塔帕特后，40个犹太人和Josephus躲在一个山洞中， 40个犹太人决定宁死也不被敌人抓到，于是决定集体自杀，大家经过决定了一个自杀方式，41个人转成一圈，由第1个人开始报数， 每报数到3的人必须自杀，然后再由下一个人重新开始报数，直到所有人都自杀身亡为止，然而Josephus并不想遵从这个规则， 不想自杀，于是Josephus先假装同意该方案，然后坐到圆圈的第31个位置，最后逃过了这场死亡游戏。

总人数：

数到几出列：

计算

结果：

核心代码

using System;
namespace Niunan.Tool.Web.Models
{
	/// <summary>
	/// 约瑟夫环
	/// </summary>
	public class JueSeFuSolution
	{
		/// <summary>
		/// 约瑟夫环解决
		/// </summary>
		/// <param name="m">数到m出列</param>
		/// <param name="n">总人数</param>
		/// <returns></returns>
		public string JieJue(int m, int n) {
			string str = "";
			int[] man = new int[n];//保存出列的序号，0表示未出列
			for (int x = 0; x < man.Length; x++)
			{
				man[x] = 0;  //刚开始所有人都未出列
			}
			int count = 1; //出列计数器
			int i = 0; // 报数计数器
			int pos = -1; // 位置计数器 
			while (count<=n)
			{
				do {
					pos=(pos+1)% n; //求余，进行环状处理
					if (man[pos]==0)
					{
						//若编号pos还未出列，报数
						i++;
					}
					if (i==m)
					{
						//初始化计数器，又从1开始报数
						i = 0;
						break;
					}
				} while (true);
				man[pos] = count; //保存出列序号
				count++;
			}
			str += $"<div>{n} 个人转成一圈，数到 {m} 出列：</div>";
			str += "<div style='margin-left:2em;'>";
			for (int j = 0; j < n; j++)
			{
				str += $"位置{j+1}-第{man[j]}个出列&nbsp;&nbsp;&nbsp;&nbsp;";
			}
			str += "</div>";
			//找最后一个出列的人
			for (int k = 0; k < n; k++)
			{
				if (man[k]>n-1)
				{
					str += $"<div style='font-weight:bold;'>位置 {k+1} 的人是第 {man[k]} 个出列，也是最后一个人！！！</div>";
				}
			}
			return str;
		}
	}
}