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

2022-07-14 03:10:11 第一文档网 [ 字体：小中大 ] [

阅读： ] [

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。下载word有问题请添加QQ：admin处理，感谢您的支持与谅解。

【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《约瑟夫问题完整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.dywdw.cn/fecd8a25f01dc281e53af08c.html