用C#写约瑟夫环问题
时间: 2024-10-12 18:06:14 浏览: 10
约瑟夫环问题是一个经典的算法问题,它描述了这样一个场景:一群人围成一圈,从某个人开始报数,每次跳过一个人,如果数到特定数字(如7),那么这个人就会被淘汰出圈,然后从下一个人继续,直到只剩最后一个人。用C#编写这个程序,可以按照以下步骤:
```csharp
using System;
class JosephusProblem
{
static int josephus(int n, int k)
{
if (n <= 0 || k <= 0) return -1; // 输入检查
// 初始化数组和当前索引
int[] people = new int[n];
for (int i = 0; i < n; i++)
people[i] = i + 1;
int currentIndex = 0; // 当前轮到的人
while (people.Length > 1)
{
currentIndex = (currentIndex + k - 1) % people.Length; // 跳过k-1人并取模
people = RemoveAt(people, currentIndex); // 删除当前位置的人
}
Console.WriteLine("剩下的最后一个人是:", people[0]);
return people[0]; // 返回最后剩余的人
}
static int[] RemoveAt(int[] arr, int index)
{
int length = arr.Length;
Array.Copy(arr, index + 1, arr, index, length - index - 1);
return arr.Take(length - 1).ToArray(); // 或者直接返回新的数组,不保留已删除元素
}
public static void Main(string[] args)
{
int numPeople = 10, killStep = 4; // 修改这两个值来改变问题规模和淘汰步长
Console.WriteLine($"当人数为{numPeople},每{k}人淘汰一次时,最后一个存活的人是:{josephus(numPeople, killStep)}");
}
}