约瑟夫问题 完整C程序代码

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《约瑟夫问题 完整C程序代码》，欢迎阅读！



1）内容： 约瑟夫(Joseph)问题的一种描述是:编号为1,2,..., n 的n 个人按顺 时针方向围坐一圈, 每人持有一个密码(正整数)。一开始选任一个正整数作为报数上限值m， 从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将它的密码作为新的m值，再从下个人开始新一轮报数，如此反复，直到剩下最后一人则为获胜者。试设计一个程序求出出列顺序。

2）要求： 利用单向循环链表存储结构模拟此过程， 按照出列的顺序印出各人的编号。 3) 测试数据: n=7，7 个人的密码依次为：3，1，7，2，4，8，4 。m的初值为20，则正确的出列顺序应为6，1，4，7，2，3，5。

完整代码：

#include #include struct person {

int num; int order;

struct person *next; };

static struct person *head=NULL; struct person *CreatList(void) {

struct person *rear; struct person *p; int k=0; while(1) {

p=(struct person*)malloc(sizeof(struct person)); p->order=++k;

printf("\n请输入一个人所持的密码,输入0则建表结束:");

scanf("%d",&p->num); if(p->num==0)break; if(head==NULL) head=p; else rear->next=p; rear=p; }

if(rear!=NULL) rear->next=head; printf("\n建表结束\n"); return head; }


void josephus(struct person *p,int m) {

int i,k;

struct person* r; if(m==1)p=p->next; else {

for(i=2;i p=p->next; }

r=p->next; k=r->num;

printf("%d ",k); printf("%d\n",r->order); p->next=r->next; free(r);

if(p!=p->next)

josephus(p->next,k); else {

printf("%d ",p->num); printf("%d\n",p->order); } }

void main() {

int m;

struct person *pos; CreatList();

printf("请输入初始值m:"); scanf("%d",&m); printf("密码 顺序\n"); pos=head;

josephus(pos,m); }

/* 测试数据，复制粘贴可用 3 1 7


2 4 8 4 0 20 */

本文来源：https://www.wddqxz.cn/fecd8a25f01dc281e53af08c.html