约瑟夫环问题答案,约瑟夫环问题实验原理
约瑟夫环的数学问题（纯数学问题,与编程无关）
最后答案是 2 ，没错（编程得出的）
但没什么通用的规律。。。。
不过 百度百科 里有 数学分析方法！！！
但 没有通用公式或规律 ！！！！！
C语言约瑟夫环问题
#include?stdio.h
?
#define?N?17??????????????//人数
#define?M?11??????????????//出局人号码
?
void??main()
{
????int?a[N],?i,?call_n?=?0,?out_n?=?0;
????for?(i?=?0;?i??N;?i++)??a[i]?=?0;
????i?=?0;
????while?(1)??{??????????//循环报数
??????if(a[i]?==?0)??{????//如果健在
????????if?(out_n?==?(N?-?1))??break;?//如果仅剩一人
????????call_n++;?????????//报数
????????call_n?%=?M;??????//最大为M，到了M就从0开始
????????if(call_n?==?0)?{
??????????a[i]?=?1;???????//出局标记
??????????out_n++;
??????????printf("%d??",?i?+?1);//显示出局人号码
????????}
??????}
??????i++;???i?%=?N;??????//循环转向下一人
????}
????printf("\n最后剩余者的编号是：%d\n",?i?+?1);
}
约瑟夫环问题的数学解
下午和朋友聊天的时候，有朋友提到了约瑟夫环问题。你和另外 n-1 个人围成一个圈，按 1，2，...，n 依次编号。第一个人从 1 开始报数，数到 k 的人会被杀掉，然后下一个人重新从 1 开始报数。如此往复，直到最后只剩下一个人。问题是，你应该如何选择自己的初始位置，才能保证最后不被杀掉呢？
速度越快的算法当然越好，毕竟这是一个生死攸关的问题。下面你将会看到，我们如何通过一些基本的数学推导最终得到这个问题的递推解。
考虑这样一种相对简单的情况：总共有 5 个人，数到 3 的人被杀掉。那么，死亡过程如下图所示：
经过一番模拟之后，我们已经对约瑟夫环问题有了一个大概的直观理解。下面，尝试使用数学语言来描述这个问题。
哦对了，假如圆圈里只有你自己，那么你肯定就是最后的幸存者，这是一个极其有用的特殊情况。
这些是我们的 已知条件 ：
这个是我们的 未知数 ：
现在考虑一种泛化情形：总共有 n 个人，数到 k 的人被杀掉，其中 n = k。幸存者的位置为 p n 。
显而易见，初始位置为 k 的人将会第一个被杀掉。此时，经过重新排序之后，问题变成了 n-1 个人的情形。幸存者的位置为 p n-1 。如果能够找到从 p n-1 到 p n 的递推关系，那么问题就解决了。
重新排序之后，每个人的位置发生了下面这些变化：
很容易我们能得到这样一个关系式：p n = (p n-1 + k) % n 。再加上刚才讨论的特例，只有一个人的情况时，p 1 = 1 。递推式就已经很明显了。
当然上文只讨论了 n=k 的情形，实际上对于 nk 的情形，刚才所得到的递推式依然适用，我们就不展开讨论了。
既然递推式这么简洁明确，那么编码实现就不用写了吧？
约瑟夫环
约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
链表方法：这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p-link=head 解决问题的核心步骤：（程序的基本算法） 1.建立一个具有n个链结点，无头结点的循环链表； 2.确定第1个报数人的位置； 3.不断地从链表中删除链结点，直到链表为空。 void JOSEPHUS(int n,int k,int m) //n为总人数，k为第一个开始报数的人，m为出列者喊到的数 { /* p为当前结点 r为辅助结点，指向p的前驱结点 list为头节点*/ LinkList p,r,list; /*建立循环链表*/ for(int i=0；in；i++) { p=(LinkList)malloc(sizeof(LNode)); p-data=i; if(list==NULL) list=p; else r-link=p; r=p; } p-link=list; /*使链表循环起来*/ p=list; /*使p指向头节点*/ /*把当前指针移动到第一个报数的人*/ for(i=0;ik;i++) { r=p； p=p-link; } /*循环地删除队列结点*/ while(p-link!=p) { for(i=0;im-1;i++) { r=p; p=p-link; } r-link=p-link; printf("被删除的元素：%4d ",p-data); free(p); p=r-link; } printf("\n最后被删除的元素是：%4d",P-data); }
约瑟夫问题答案
typedef struct node
{
int num,code;
struct node *next;
}lnode;
void main()
{
int i,j,key,n; /*i,j为记数器,key为输入的密码,n为人的总个数*/
lnode *p,*s,*head;
head=(lnode *)malloc(sizeof(lnode)); /*为头结点分配空间*/
p=head;
printf("Please enter the num of the person:"); /*输入人的总个数*/
scanf("%d",n);
for(i=1;i=n;i++)
{
printf("Person %d",i);
printf(" code: ");
scanf("%d",key); /*输入各个人的密码*/
s=p;
p=(lnode *)malloc(sizeof(lnode)); /*创建新的结点*/
s-next=p;
p-num=i;
p-code=key;
}
p-next=head-next;
p=head;
head=head-next;
free(p);
p=head;
do
{
printf("\nPerson%d Code:%d",p-num,p-code); /*输出链表*/
p=p-next;
}while(p!=head);
printf("\nPlease enter your first key:"); /*输入第一个数*/
scanf("%d",key);
do
{
j=1; /*j为记数数*/
p=head;
while(jkey)
{
s=p;
p=p-next;
j++;
}
i=p-num;
key=p-code;
printf("\nThe out of the num:");
printf("Person%d",i);
s-next=p-next;
head=p-next; /*重新定义head,下次循环的开始结点*/
free(p);
n--; /*每循环一次人是减1*/
}while(n0);
getch();
}