约瑟夫环问题实验报告

约瑟夫环问题实验报告在浩瀚的计算机语言中，总有一些算法——虽然码量很少，但却能完美又巧妙地解决那些复杂的问题接下来，我们要介绍的“约瑟夫环”问题就是一个很好的例子问题背景这个问题来源于犹太人约瑟夫经历过的故事，在罗马人占领乔塔帕特后，约瑟夫和他的朋友与个犹太人躲到一39个洞中，个犹太人决定宁愿死也不要被敌人抓到，于是决报39数，每报数到第人时，该人就必须自杀，然后再由下一个人3定了一个自杀方式，个人排成一个由第个人开始411重新报数，直到所有人都自杀身亡为止然而约瑟夫和他的朋友并不想遵从这个规则，于是，他们想出新的思路从一个人开始，越过个人（因为第一个k-2人已经被越过），并杀掉第个人接着，再越过个人，k k-1并杀掉第个人这个过程沿着圆圈一直进行，直到最终只剩k下一个人留下，这个人就可以继续活着问题是，给定了和，一开始要站在什么地方才能避免被处决？如果你是约瑟夫，你会站在什么样的位置呢？数数与大家一起，从运用以下两个方面来解决这个问题模拟法循环单链表实现约瑟夫环问题的基本形式为个人围成一圈，从第一个n开始报数，每报到者将被杀掉，直至只剩一个人m如N=6,M=523456I2346II12361233III由此可以很容易想到使用循环单链表来实现创建指针p,当指针移动个位置后，就该删除下一个节点，由此类推，m-1直至链表中只含一个节点02代码实现:#include stdio.h#include stdlib.htypedef longlong LL;LLk=O;typedef struct Node{LL number;structNode*next;}Node:Node*createlinkLL n{Node*head=Node*mallocsizeofNode;head-number=1;head-next=NULL;Node*cyclic=head;IVL i;for i=2;i=n;i++{Node*p=Node*mallocsizeofNode;p-number=i;p-next=NULL;cyclic-next=p;cyclic=cyclic-next;cyclic-next=head;return head;}void kilKNode*head,LL n,LL m{Node*tail=head:LL i;while tail-next!=head{tail=tail-next;Node.p headwhile p-next!=p{二for i=1;im;i++{tail=p p=p-next;tail-next=p-next;printf Round%lld:%lld\n,++k,p-number;freep;p=tail-next:、++printfn Round%lld:%lld\n k,p-number;ifk==n{printf Thewinner is%lld,\p-number;freep;int main{LL n.m;Node*head;printfMEnter thenumber ofplayers:;scanfn%lldr\n;printfHEnter thenumber ofthe decedent/*;head=createlinkn;killhead.n.m;return0;}用数组也可以实现暴力模拟约瑟夫环但是，用模拟法有一个很明显的缺陷——时间复杂度高达所以下面考虑优0nm,化算法数学法用递归法优化到复杂度On在的《具体数学》中，对的情况使Donald E.Knuth m=2用了递归的解决方法，并推出了一个常数表达式，使得此种情况下，算法的复杂度为常量同时，这种思路也可以应用于〉n的情况，但无法得出常数表达式，推广后的递归算法具体的2思路如下。