约瑟夫环问题答案,约瑟夫环问题实验原理

http://www.itjxue.com  2023-01-15 16:16  来源:未知  点击次数: 

约瑟夫环的数学问题(纯数学问题,与编程无关)

最后答案是 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();

}

(责任编辑:IT教学网)

更多

推荐编程综合文章