有趣的josephu（约瑟夫）问题 - 数据结构 - 机器学习
1285 人阅读 | 时间：2021年01月15日 01:07
数据结构 - 机器学习
深度学习
当前位置：首页 » 数据结构精品文章 » 正文
有趣的josephu（约瑟夫）问题
1289 人参与 2018年09月03日 22:54 分类 : 数据结构精品文章 评论
约瑟夫问题是数据结构和算法领域的一个非常出名的问题，它主要是线性表的操作问题，我们通过本章学习的顺序或者链式线性表就可以很好的解决问题。下面是对这个问题的介绍和解决方法，大家可以了解一下，学习顺序表、链表的一些方法。
Josephu问题描述：编号为 1，2，…，n的n个人顺时针围成一圈，每个人除有编号外，还持有密码，且已给定初始密码m， 约定从编号为k（1≤k≤n）的人从1 开始报数， 数到m的那个人出列，取出它的密码作为新的密码m，它的下一位又从1开始报数，数到m的那个人出列，依此类推，直到所有人出列为止，试输出出队者的编号序列。
提示：用一个不带头结点的循环链表来处理Josephu 问题，先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，记到m时，对应结点丛链表中删除，然后被删除的结点得下一个结点又从1开始记数，直到最后一个结点丛链表中删除，算法结束。
要求：输出格式：每10个一行，信息描述、结构清晰。
n由用户输出，报数的上限m由用户输出。是否进行查询由用户自行选择；
每次一个相对完整的操作结束后 是否继续执行程序由用户自己选择。
具体实现：
#include <stdio.h>
#include <malloc.h>
#include <memory.h>
//pLeft长度固定为N, 表示队伍中留下人的位置.nLeave是离开的人数, 判断结束
//输出是依次从队伍中离开的人的序号.
int fun(unsigned char *pLeft, int N, int *nLeave, int m, int nStart)
{
int nCount=0,nPoint=nStart;
if(pLeft[nPoint]==1)
nCount++;
while(nCount<m)
{
nPoint=nPoint%N+1;
if(pLeft[nPoint]==1)
nCount++;
}
(*nLeave)++;
pLeft[nPoint]=0;
return nPoint;
}
void main(int argc, char *argv[])
{
int n=0,m=0,nLeave=0,nStart=1;
printf("输入 人数n,上限m.\n");
scanf("%d,%d",&n,&m);
unsigned char *pLeft=(unsigned char *)calloc(n+1,sizeof(char));
memset(pLeft,1,(n+1)*sizeof(char));
while(nLeave<n)
printf("%d\t",nStart=fun(pLeft, n, &nLeave, m, nStart));
free(pLeft);
}运行结果：
---------输出，20个人，m=26------------
输入 人数n,上限m.
20,26
6 13 1 11 3 17 14 12 16 2
10 8 15 5 9 18 20 7 4 19
来源：我是码农，转载请保留出处和链接！
本文链接：http://www.54manong.com/?id=203
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646208",
container: s
});
})();
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646147",
container: s
});
})();
window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdPic":"","bdStyle":"0","bdSize":"16"},"share":{},"image":{"viewList":["qzone","tsina","tqq","renren","weixin"],"viewText":"分享到：","viewSize":"16"},"selectShare":{"bdContainerClass":null,"bdSelectMiniList":["qzone","tsina","tqq","renren","weixin"]}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];
数据结构 微信号：qq444848023 QQ号：444848023
加入【我是码农】QQ群：864689844（加群验证：我是码农）
- 各种排序方法的介绍与比较2018-09-03 23:14
- 什么是算法? 算法的5个基本特性是什么? 算法设计的要求？2018-08-18 09:04
- 数据结构经典面试题：多种方法实现字符串循环移位2018-08-18 09:01
- 怎样学好数据结构2018-08-18 08:52
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646186",
container: s
});
})();
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646175",
container: s
});
})();
搜索
网站分类
- 数据结构
- 数据结构视频教程
- 数据结构练习题
- 数据结构试卷
- 数据结构习题解析
- 数据结构电子书
- 数据结构精品文章
- 区块链
- 区块链精品文章
- 区块链电子书
- 大数据
- 大数据精品文章
- 大数据电子书
- 机器学习
- 机器学习精品文章
- 机器学习电子书
- 面试笔试
- 物联网/云计算
标签列表
- 数据结构 (39)
- 数据结构电子书 (20)
- 数据结构习题解析 (8)
- 数据结构试卷 (10)
- 区块链是什么 (261)
- 数据结构视频教程 (31)
- 大数据技术与应用 (12)
- 百面机器学习 (14)
- 机器学电子书 (29)
- 大数据电子书 (37)
- 程序员面试 (10)
- RFID (21)
最近发表
- 找出数组中有3个出现一次的数字
- 《百面机器学习》电子书下载
- 区块链精品电子书《深度探索区块链：Hyperledger技术与应用_区块链技术丛书》张增骏
- 区块链精品电子书《比特币：一个虚幻而真实的金融世界》
- 区块链精品电子书《图说区块链》-徐明星 & 田颖 & 李霁月
- 区块链精品电子书《是非区块链：技术、投机与泡沫》-英国《金融时报》
- 区块链精品电子书《商业区块链：开启加密经济新时代》-威廉·穆贾雅
- 区块链精品电子书《人工智能时代，一本书读懂区块链金融 (互联网_时代企业管理实战系列)》-马兆林
-
(function(){
var bp = document.createElement('script');
var curProtocol = window.location.protocol.split(':')[0];
if (curProtocol === 'https'){
bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
}
else{
bp.src = 'http://push.zhanzhang.baidu.com/push.js';
}
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(bp, s);
})();
全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试
var cnzz_protocol = (("https:" == document.location.protocol) ? "https://" : "http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1276413723'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s23.cnzz.com/z_stat.php%3Fid%3D1276413723%26show%3Dpic1' type='text/javascript'%3E%3C/script%3E"));本站资源大部分来自互联网，版权归原作者所有！
©著作权归作者所有：来自ZhiKuGroup博客作者没文化的原创作品，如需转载，请注明出处，否则将追究法律责任
来源：ZhiKuGroup博客，欢迎分享。
评论专区