数据结构的题 有没有大佬

约瑟夫(Joseph)问题的一种描述是:设编号为1,2,…,n的n(n>0)个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。开始时任选一个整数作为报数上限值m,从一个人开始顺时针自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止。要求设计一个程序模拟此过程,求出出列顺序。
(2) 设计要求
设计一个程序,以人机交互方式执行,用户指定约瑟夫环游戏的总人数n和初始的报数上限m,然后输入每个人所持有的密码key。模拟约瑟夫环,从头开始报数,直到所有的人出列。系统按照出列顺序给出编号。
(3) 数据结构
本设计利用带头结点的单循环链表作为模拟约瑟夫环游戏的存储结构。

5个回答

 #include <iostream>
using namespace std;

struct monkey
{
int num;
monkey *next;
};

int joseph(int sum, int cycle)
{
int i;
monkey *p_old, *p_new, *head=NULL;

head = new monkey;
//此处创建一个循环链表(create a circular chained table)
head->num = 1;
p_old = head;
for(i=2; i<=sum; i++)
{
p_new = new monkey;
p_new->num = i;
p_old->next = p_new;
p_old = p_new;
}
p_new->next = head;

p_old = head;
i = 1;
//循环删除元素直到只剩下最后一个元素(delete elements circularly until the last element left)
while(1)
{
p_new = p_old->next;
i++;
if(p_new == p_old)
break;
if((i % cycle) == 0)
{
p_old->next = p_new->next;
p_new->next = NULL;
delete p_new;
i = 0;
}
else
{
p_old = p_new;
}
}

return p_new->num;
}

int main(void)
{
int n,m;
cin>>n>>m;
cout<<joseph(n,m)<<endl;
return 0;
}
Debug_dodge
Debug_dodge 去年写的代码了
大约 2 年之前 回复

基础题,百度一下就有答案了

可以google一下 哈哈

这个度娘上就有答案 百度一下就知道了

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题