admin 管理员组

文章数量: 1184232

约瑟夫环

约瑟夫问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。

解法一：数组法

#include<stdio.h>
#include<malloc.h>
int main(void)
{int *person,i,node,n,m;scanf("%d%d",&n,&m);person=(int*)malloc(sizeof(int)*(n+1));for(i=1; i<n; i++)//初始化圈{person[i]=i+1;//i表示编号为i的人,person[i]的值表示编号为i的人的下一个人的编号}person[n]=1;//编号为n的下一个人的编号是1node=1;while(node != person[node])//如果某个人的下一个人不是自己,意味着人数超过1人{for(i=1; i<m-1; i++)//这个循环终止于被杀的人的前一个人{node=person[node];//下一个人的编号为node,node的值来自于前一个人的person[node]}printf("%d号被杀\n",person[node]);//输出被杀的人编号person[node]=person[person[node]];//修改被杀的人的前一个人的person[node]为被杀的人的后一个人的编号node=person[node];//这句话中的node是被杀的人后一个人}printf("幸存者为%d号",node);//输出最后幸存者的编号return 0;
}

解法二：单向环形链表法

#include <stdio.h>
#include <malloc.h>
#define LEN sizeof(struct node)//定义struct node这个类型的长度
struct node
{int num;struct node *next;
};
struct node *create(int m)
{struct node *head,*p1,*p2;int i;p1=p2=(struct node*)malloc(LEN);head=p1;head->num=1;for(i=1,p1->num=1;i<m;i++){p1=(struct node*)malloc(LEN);p1->num=i+1;p2->next=p1;p2=p1;}p2->next=head;return head;
}
struct node *findout(struct node *start,int n)
{int i;struct node *p;i=n;p=start;for(i=1;i<n-1;i++)p=p->next;return p;
}
struct node *letout(struct node *last)
{struct node *out,*next;out=last->next;last->next=out->next;next=out->next;free(out);return next;
}
int main(void)
{int m,n,i,king;struct node *p1,*p2;scanf("%d",&m);scanf("%d",&n);if(n==1){king=m;}else{p1=p2=create(m);for(i=1;i<m;i++){p2=findout(p1,n);p1=p2;p2=letout(p1);p1=p2;}king=p2->num;free(p2);}printf("最后剩下的人的编号是：%d\n",king);return 0;
}

解法三：数学解法
开始报数，不断重复。第一个出列的人的编号一定是（M-1）%n，当有人出列后，下一个位置的人又从0开始报数。即将出列一人后的数据重新组成了0到（N-2）共N-1个人的列表，继续求N-1个参与人员，按报数到M-1出列，求解最后一个出列者在圆形队列中的编号。
易得出递推公式：

F(1)=0
F(N)=[F(N-1)+M-1]%N (N>1)

用C语言代码实现如下：

#include<stdio.h>
#include<string.h>int josephus(int n,int m);int main(void)
{int n,m,i,s=0;printf("输入参与人数N和出列位置M的值：");scanf("%d%d",&n,&m);printf("最后出列的人初始位置是%d\n",josephus(n,m)+1);return 0;
}int josephus(int n,int m)//递归函数 
{if(n==1)return 0;else return (josephus(n-1,m),m)%n; 
}

又因使用递归函数会占计算机较多内存，当递归层次太深时可能导致程序不能运行，因此，可以将程序直接编写为以下的递推形式：

#include<stdio.h>
int main(void)
{int n,m,i,s=0;printf("输入参与人数N和出列位置M的值：");scanf("%d%d",&n,&m);for(i=2;i<=n;i++){s=(s+m)%i;} printf("最后出列的人的初始位置是：%d",s+1); 
}

两段代码输出结果相同。
水平有限，如有不足请指出。

本文标签： 约瑟夫环

版权声明：本文标题：约瑟夫环 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1699178140a334865.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。