博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
约瑟夫环算法
阅读量:5991 次
发布时间:2019-06-20

本文共 367 字,大约阅读时间需要 1 分钟。

首先阐述一下问题:n个人(编号0—n-1)围成一圈,从1开始报数,报到m的人出列,然后从出列的人的下一个人开始,从1开始报数,报到m的人出列,求出最后幸存的那个人的原始编号。

如果单纯的是模拟整个游戏过程的话,实现起来并不难。今天我学习到的是另一种算法。举个例子,第一轮以后,假设被淘汰的人编号是k-1,报数是m,那么接下来的n-1的应该是这样排序x`(x),x`表示上一轮的编号,x表示本轮的编号。那么目前的情况应该是这样的k(0)、k+1(1)、k+2(2)、……、k-2(n-2),我们可以得出这么一个公式x`=(x+k)%N因为最后一个幸存者他最后的编号一定是0,那么有此推出他的上一轮编号……直到推出一开始的编号为止

转载于:https://www.cnblogs.com/lurongrong/p/4333979.html

你可能感兴趣的文章
Servlet 单例多线程
查看>>
Java-对象多态性
查看>>
Android点击Button实现功能的几种方法
查看>>
uva 592 Island of Logic (收索)
查看>>
【转载】shell中 dd 命令
查看>>
八大排序方法汇总(选择排序,插入排序-简单插入排序、shell排序,交换排序-冒泡排序、快速排序、堆排序,归并排序,计数排序)...
查看>>
骨传导技术(转)
查看>>
Ubuntu 下忘记mysql 密码
查看>>
混沌分形之谢尔宾斯基(Sierpinski)
查看>>
java.lang.OutOfMemoryError: Java heap space错误及处理办法(收集整理、转)
查看>>
CentOS下Tmux安装和使用
查看>>
队列的存储结构和常见操作(c 语言实现)
查看>>
GitHub上整理的一些工具
查看>>
名校公开课网站汇总
查看>>
【AdaBoost算法】弱分类器训练过程
查看>>
WebService原理
查看>>
Leaf——美团点评分布式ID生成系统
查看>>
atitit..sql update语法的词法分析,与语法ast构建
查看>>
enjoy dollar vs cash dollar
查看>>
What is the largest TCP/IP network port number allowable for IPv4
查看>>