约瑟夫问题

描述17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围... 描述17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。这个故事的问题是经典的约瑟夫问题。 现在我们知道有n个教徒和非教徒，其中非教徒数为m，将他（她）们按从1到n的次序放置到圆圈中，报数为k，要将所有非教徒投入大海，请按递增次序给出非教徒在圆圈中的次序。输入每行是用空格分开的三个整数，第一个是 n, 第二个是 m，第三个是k ( 0 < m

1个回答

2024-08-07 06:12

//约瑟夫环：
//这并告个程序有点小问题，你自己看看吧，现在没时间改了，起始位置有点问题

#include
#include
int flag;
typedef struct node
{int data;
struct node *next;
}LNode,* Linklist;
Linklist CreatFromHead() //链表的初始化
{ Linklist L=NULL,s;
LNode *r=NULL;
int x=1;
s=(Linklist)malloc(sizeof(LNode));
L = s;
r= L;

printf("请输入请厅丛输入报数的人数");
scanf_s("%d",&flag);
while(x!=flag+1)
{s=(Linklist)malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s;
x++;
}
s->next=L;

if(r!=NULL) r->next=NULL;
return L;
}
Linklist Getlist(Linklist L,int i) //链表的查找函数
{Linklist p;
int j;

p=L;j=0;
while(p->next!=NULL&&j { p=p->next;
j++;
}
if(i==j)return p;
else return NULL;
}
Linklist treat(Linklist L,Linklist s,int k,int i) //约瑟夫环算法
{
int j=0;
if(s==NULL)
{
s=L->扮蔽樱next;
}
while(j {
s=s->next;
j++;
if(s==NULL)
{
s=L->next;
}
}
return s;
}
int Del_Linklist(Linklist L,Linklist p) //链表结点删除函数
{Linklist s;
s=L;
while((s->next->data != p->data))
{
s=s->next;
}
s->next=s->next->next;
free(p);
return 1;
}
void main() //主函数
{Linklist L;
Linklist p,s;
int i,k,m,n;
L=CreatFromHead();
printf("请输入查找的元素位置");
scanf_s("%d",&i);
printf("请输入相隔的位置：");
scanf_s("%d",&k);
m=0;

s=Getlist(L,i);
printf(".");

while(m{
p=treat(L,s,k,i);

printf("%d\t",p->data);
s=p->next;

n=Del_Linklist(L,p);
m++;
}
}