链表之单链表约瑟夫问题(二)
发布日期:2021-06-29 14:01:17
浏览次数:2
分类:技术文章
本文共 555 字,大约阅读时间需要 1 分钟。
约瑟夫环()是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后[1] 结果+1即为原问题的解。
约瑟夫环:递归算法
假设下标从0开始,0,1,2 .. m-1共m个人,从1开始报数,报到k则此人从环出退出,问最后剩下的一个人的编号是多少?
现在假设m=10
0 1 2 3 4 5 6 7 8 9 k=3
第一个人出列后的序列为:
0 1 3 4 5 6 7 8 9
即:
3 4 5 6 7 8 9 0 1(*)
我们把该式转化为:
0 1 2 3 4 5 6 7 8 (**)
则你会发现: ((**)+3)%10则转化为(*)式了
也就是说,我们求出9个人中第9次出环的编号,最后进行上面的转换就能得到10个人第10次出环的编号了
设f(m,k,i)为m个人的环,报数为k,第i个人出环的编号,则f(10,3,10)是我们要的结果
当i=1时, f(m,k,i) = (m+k-1)%m
当i!=1时, f(m,k,i)=
转载地址:https://chenyu.blog.csdn.net/article/details/50444098 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月24日 04时47分10秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
领导让我整理上个季度的销售额,幸好我会Python数据分析,你猜我几点下班
2019-04-29
【Python爬虫实战】为何如此痴迷Python?还不是因为爱看小姐姐图
2019-04-29
2021年6月全国程序员薪资出炉,大佬您上榜了吗?
2019-04-29
零基础自学Python,你也可以实现经济独立!
2019-04-29
数字化转型的主干道上,华为云以“三大关键”成企业智能化推手
2019-04-29
数字化为何不走“捷”“径”?
2019-04-29
和总裁、专家交朋友,华为云助推政企智能化升级又做到前面去了
2019-04-29
BCOP章鱼船长,6月22日晚上8点上线薄饼
2019-04-29
为战疫助力,半导体功不可没
2019-04-29
了解这些操作,Python中99%的文件操作都将变得游刃有余!
2019-04-29
知道如何操作还不够!深入了解4大热门机器学习算法
2019-04-29
只有经历过,才能深刻理解的9个编程道理
2019-04-29
发现超能力:这些数据科学技能助你更高效专业
2019-04-29
AI当道,人工智能将如何改变金融业?
2019-04-29
消除性别成见,技术领域需要更多“乘风破浪的姐姐”
2019-04-29
7行代码击败整个金融业,这对20多岁的爱尔兰兄弟是如何做到的?
2019-04-29
2020十大编程博客:私藏的宝藏编程语言博客大放送!
2019-04-29
编程中的角色选择:哪类工作角色最适合你?
2019-04-29
10种算法一文打尽!基本图表算法的视觉化阐释
2019-04-29