当前位置:首页 » 数据结构精品文章 » 正文

有趣的josephu(约瑟夫)问题

1601 人参与  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

数据结构  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!