销售类网站开发架构,全球十大软件公司,泉州做网站排名,陕西城乡建设网目录
1.约瑟夫环定义
2.约瑟夫环算法实现需要注意的地方
3.通过一个例子来演示这个过程
4.三人的约瑟夫环示例
4.十二人的约瑟夫环示例 1.约瑟夫环定义 约瑟夫环即设有n个人坐成一个圈#xff0c;从某个人开始报数#xff0c;数到m的人出列#xff0c;接着从出列的下一…目录
1.约瑟夫环定义
2.约瑟夫环算法实现需要注意的地方
3.通过一个例子来演示这个过程
4.三人的约瑟夫环示例
4.十二人的约瑟夫环示例 1.约瑟夫环定义 约瑟夫环即设有n个人坐成一个圈从某个人开始报数数到m的人出列接着从出列的下一个人开始重新报数数到m的人再次出列如此反复循环直到所有人都出列为止最后按出列顺序输出。 实现约瑟夫环算法时最重要的是约瑟夫环的流程。约瑟夫环应该有三个重要的参数、总人数、开始报数的人、第几次报数出列的人。
2.约瑟夫环算法实现需要注意的地方 在实现约瑟夫环问题时有一点需要特别注意当有人出列后列表中的人数会减少但下一个报数的起始位置即index应该基于剩余的人数进行更新。这意味着在每次有人出列后我们都需要将index减1然后再进行(index 1) % people.Count的操作。 以下是约瑟夫环算法的逻辑
初始时index是起始位置从index0开始计数。在每次有人出列后将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; // 报数值Listint 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()!);Listint 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);}}}
}
//运行结果
/*
请输入人数n12
请输入报数间隔m4
请输入开始位置k3
出列顺序5
出列顺序9
出列顺序1
出列顺序6
出列顺序11
出列顺序4
出列顺序0
出列顺序8
出列顺序7
出列顺序10
出列顺序3
出列顺序2*/
