约瑟夫环问题
以前写的程序，今天在整理文件的时候发现了，贴出来有需要的朋友可以参考！
问题提出：
约瑟夫环是一个数学的应用问题：已知n个人（以编号0，2，3...n-1分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。 解决方案： 约瑟夫环有递归和非递归两种解决方案。 1. 非递归可用数组和循环链表来解决。下面给出用数组解决的源码：
namespace JosephusRing
{
class Josephus
{
public int[] Jose(int total, int start, int span)
{
int[] people = new int[total];//定义存储初始人员的数组
int[] result = new int[total];//定义存储出列顺序的数组
int count = 0;//定义出列的计数器
//people数组进行初始化，编号从0开始
for (int i = 0; i < total; i++)
{
people[i] = i;
}
//每次循环，出列一个人，共有total-1次循环
for (int j = total; j > 1; j--)
{
start = (start + span - 1) % j;
//start为要出列的人的编号,%的作用是当报数超出人数时做下一轮循环处理
result[count++] = people[start];//把出列的人存储到result数组中
//此循环用于删除出列的人
for (int k = start + 1; k < j; k++)
{
people[k - 1] = people[k];
}
}
result[count] = people[0];//把剩余的最后一个人添加到result数组中
return result;
}
static void Main(string[] args)
{
Josephus jose = new Josephus();
int[] joseRing = jose.Jose(17,0,3);
foreach(int num in joseRing)
{
Console.WriteLine(num);
}
Console.ReadKey();
}
}
}2. 递归函数。先来看一下递归函数： 为了简化问题，我们假设k=0，设f(n,m,i)为n个人的环，报数为m，第i个人出环的编号 当i=1时，f(n,m,i) = (m-1)%m 当i!=1时，f(n,m,i)= ( f(n-1,m,i-1)+k )%n
下面给出C#源码：
namespace JoseRecursion
{
class Joseph
{
//total为总人数，span为步长，count为出列的计数器
public int Jose(int total,int span,int count)
{
int result;//result为第count次出列的人员编号
if (count == 1) return result = (span - 1) % total;
else return (Jose(total - 1,span,count - 1) + span) % total;
}
static void Main(string[] args)
{
Joseph jose = new Joseph();
int[] result = new int[17];
for (int i = 0; i < 17; i++)
{
result[i] = jose.Jose(17,3,i + 1);
Console.WriteLine(result[i]);
}
Console.ReadKey();
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014年03月25日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读