C#实现约瑟夫环算法

目录

1.约瑟夫环定义

2.约瑟夫环算法实现需要注意的地方

3.通过一个例子来演示这个过程

4.三人的约瑟夫环示例

4.十二人的约瑟夫环示例

---

1.约瑟夫环定义

        约瑟夫环即设有n个人坐成一个圈，从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人再次出列，如此反复循环，直到所有人都出列为止，最后按出列顺序输出。

        实现约瑟夫环算法时，最重要的是约瑟夫环的流程。约瑟夫环应该有三个重要的参数、总人数、开始报数的人、第几次报数出列的人。

2.约瑟夫环算法实现需要注意的地方

        在实现约瑟夫环问题时，有一点需要特别注意：当有人出列后，列表中的人数会减少，但下一个报数的起始位置（即index）应该基于剩余的人数进行更新。这意味着在每次有人出列后，我们都需要将index减1，然后再进行(index + 1) % people.Count的操作。

        以下是约瑟夫环算法的逻辑：

• 初始时，index是起始位置（从index=0开始计数）。
• 在每次有人出列后，将index减1，以反映列表中人数的减少。
• 使用(index + 1) % people.Count来找到下一个报数的起始位置。

3.通过一个例子来演示这个过程

        假设有3个人，起始位置是第2个人（index = 1），每次数到2的人出列。

        初始状态：

• people = [1, 2, 3]
• index = 1（第2个人）

        第一轮报数：

• 报数1：当前位置是2，不出列。
• 报数2：当前位置是3，出列。
• 更新people = [1, 2]
• 更新index = (2 - 1) % 2 = 1（因为第3个人出列了，所以剩下的人里第1个人成为新的起始位置）

        第二轮报数：

• 报数1：当前位置是1，不出列。
• 报数2：当前位置是2，出列。
• 更新people = [1]
• 更新index = (1 - 1) % 1 = 0（因为第2个人出列了，所以剩下的人里第1个人成为新的起始位置，其索引0在编程中通常表示列表的第一个元素）

        第三轮报数：

• 报数1：当前位置是1，不出列。
• 报数2：当前位置还是1，出列。（只剩一个人时要报两次数）
• 更新people = []（所有人都已经出列）

4.三人的约瑟夫环示例

// 3人的约瑟夫
class JosephusProblem
{static void Main(){int n = 3;  // 总人数int m = 2; // 起始位置（从索引1开始计数）int k = 2;  // 报数值List<int> people = [];for (int i = 1; i <= n; i++){people.Add(i);}int index = m - 1; // 转换为0基础的索引while (people.Count > 0){// 找到需要出列的人的索引index = (index + k - 1) % people.Count;// 出列该人并打印int outPerson = people[index];people.RemoveAt(index);Console.WriteLine("出列人的编号是：" + outPerson);}Console.WriteLine("所有人已出列。");}
}
//运行结果：
/*
出列人的编号是：3
出列人的编号是：2
出列人的编号是：1
所有人已出列。*/

4.十二人的约瑟夫环示例

        始终使用index = (index + m - 1) % circle.Count;计算出下一个出列的人的索引。

// 约瑟夫环算法
namespace _149
{class Program{static void Main(string[] args){ArgumentNullException.ThrowIfNull(args);Console.Write("请输入人数n：");int n = int.Parse(Console.ReadLine()!);Console.Write("请输入报数间隔m：");int m = int.Parse(Console.ReadLine()!);Console.Write("请输入开始位置k：");int k = int.Parse(Console.ReadLine()!);List<int> circle = [];for (int i = 0; i < n; i++){circle.Add(i);}int index = k - 1;while (circle.Count > 0){index = (index + m - 1) % circle.Count;int outPerson = circle[index];circle.RemoveAt(index);Console.WriteLine("出列顺序：{0}", outPerson);}}}
}
//运行结果：
/*
请输入人数n：12
请输入报数间隔m：4
请输入开始位置k：3
出列顺序：5
出列顺序：9
出列顺序：1
出列顺序：6
出列顺序：11
出列顺序：4
出列顺序：0
出列顺序：8
出列顺序：7
出列顺序：10
出列顺序：3
出列顺序：2*/