约瑟夫斯问题求解

[阅读材料]世界名题与小升初之：抽杀问题（約瑟夫问题）--马到成功老师在各类竞赛中，各类小升初考试中相关的世界名题出现的概率极高，这是由小升初与数学竞赛的特点决定，这特点便是：知识性，趣味性，思想性相结合。

先给大家介绍这一问题的由来。

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特後，39 個犹太人与Josephus及他的朋友躲到一個洞中，39個犹太人決定宁愿死也不要被人抓到，于是決定了一个自杀方式，41個人排成一个圆圈，由第1個人开始报数，每报数到第3人该人就必須自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他將朋友与自己安排在第16個与第31個位置，于是逃过了这场死亡游戏。

解法約瑟夫问题可用代数分析來求解，将这个问题扩大好了，假设现在您与m个朋友不幸参与了这个游戏，您要如何保护您的朋友？只要画两个圆圈就可以让自己与朋友免于死亡游戏，这两个圆圈是排列顺序，而外圈是自杀顺序，如下图所示：使用程式来求解的话，只要将阵列当作环状来处理就可以了，在列中由计数1开始，每找到三个无资料区就填入一个计数，直接计数來求解的話，只要將阵列当作环状来处理就可以了，在阵列中由計数1开始，每找到三个无资料区就填入一个計数，直而計数达41为止，然后將阵列由索引1开始列出，就可以得知每个位置的自杀順序，这就是約瑟夫排列，41個人报数3的約瑟夫排列如下所示：14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23由上可知，最后一個自杀的是在第31个位置，而倒数第二个自杀的要排在第16个位置，之前的人都死光了，所以他们也就不知道約瑟夫与他的朋友并没有遵守游戏规则了。

一问题描述1 题目内容：约瑟夫(Joseph)问题的一种描述是:编号为1,2,..., n的n 个人按顺时针方向围坐一圈, 每人持有一个密码(正整数)。

一开始选任一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将它的密码作为新的m值。

试设计一个程序求出出列顺序。

2 基本要求：利用单项循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

3 测试数据：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4（正确的出列顺序应为6，1，4，7，2，3，5）。

二需求分析程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。

输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。

输出形式：建立一个输出函数，将正确的输出序列三概要设计利用单项循环链表存储结构模拟此过程1 循环链表的抽象数据类型循环链表是单链表的一种变化形式，把单链表的最后一个节点的next指针指向第一个节点，整个链表就形成了一个环。

2 循环链表的基本操作（仅列出用在本程序的）creat(n)操作结果：构造一个长度为n的无头节点的循环链表,并返回指向最后一个节点的指针find(m,s)初始条件：循环链表存在操作结果：找到当前元素（即s）后面第m个元素print(&m,&n,&s)初始条件：循环链表存在操作结果：从s中删除约舍夫问题中下一个被删除的元素，并将此元素显示在屏幕上3 本程序包括4个模块：主程序模块；创建循环链表模块；找节点模块；删节点模块；各模块调用关系如下图所示：4 约舍夫问题的伪码算法void main( ){输入参与的人数；输入第一个密码；创建无头节点的循环链表；输出第一个出列元素；输出剩余出列元素；}四详细设计1 实现概要设计的数据类型typedef struct LNode{int data;int num;struct LNode *next;}LNode,*linklist; //无头节点的循环链表的节点类型2 每个子函数的算法linklist creat(int n){/*构造一个长度为n的无头节点的循环链表,并返回指向最后一个节点的指针*/linklist head,s; //head为头节点标记s为链表中节点int i;s=head=(linklist)malloc(sizeof(LNode)); //创建头节点for(i=1;i<n;i++) //建立循环链表{s->data=i;printf("num%d: ",i);scanf("%d",&(s->num));/*输入第i个人的密码*/while(s->num<=0){/*如果输入的s->num小于等于0,要求重新输入*/ printf("请重新输入\nnum%d: ",i);scanf("%d",&s->num);}s->next=(linklist)malloc(sizeof(LNode)); //开辟下一个节点s=s->next;}s->data=i;printf("num%d: ",i);scanf("%d",&(s->num));s->next=head;return(s);}linklist find(int m,linklist s) //找到当前元素后面第m个元素{int i;for(i=0;i<m-1;i++)s=s->next;return(s); //返回找到元素的指针}void print(into &mint &n,linklist &s){linklist p;s=find(m,s); //找到待删除的元素printf("%d ",s->next->data);/*输出找到的元素*/m=s->next->num;/*将此元素从链表中删除,并释放此节点*/ p=s->next;s->next=s->next->next;free(p);--n; //约舍夫环中节点数少一}3 主程序算法void main( ){/*解决约舍夫问题的主函数*/int n,m; //n为约舍夫环内初始人数m为初始密码printf("type in n :");scanf("%d",&n);/*输入n*/while(n<=0){/*如果输入的n小于等于0,要求重新输入*/printf("please type n in again \ntype in n :");scanf("%d",&n);}printf("type in m :");scanf("%d",&m);/*输入m*/while(m<0){/*如果输入的m小于0,要求重新输入*/printf("please type m in again \ntype in m :");scanf("%d",&m);}linklist s;s=creat(n);/*创建无头节点的循环链表,返回指向最后一个元素的指针*/printf("the sequence is ");print(m,n,s);//输出第一个出列的元素while(n){print(m,n,s);//输出剩余出列的元素}printf("\n");}4 函数调用关系图五调试分析调试过程中出现过如下问题：1 开始编程序时没考虑输入错误的问题，导致输入错误后程序出错2 编程序时删除节点子程序结束条件出错3 对开辟的节点用完后没有释放六使用说明程序运行后按提示输入n和m的值，在输入约舍夫环中每个人的密码，运行即可得到出列顺序七测试结果进入程序后要求输入n的值然后输入m的值再输入每个人的密码最后得到出列顺序八附录（源程序）这里附上两种源程序，本质上相同，只是第一个程序按老师要求写为很多子函数形式，第二个是我已开始编的，一个大函数。

约瑟夫问题的经典三个例子以下是 9 条关于约瑟夫问题的经典例子：例子 1：想想看，一群小朋友围成一圈玩游戏，就像我们小时候那样。

这时候说从某个小朋友开始报数，每隔一个人淘汰，最后剩下的那个就是胜利者。

这不就是约瑟夫问题嘛。

就好像在一个神秘的游戏圈子里，大家都紧张又兴奋地等待着命运的裁决。

例子 2：你能想象军队里士兵们站成一圈，然后用这种方式来决定谁去执行特殊任务吗？哎呀呀，那场面肯定很刺激。

每个士兵心里都七上八下的，不知道自己是不是那个“幸运儿”，这和约瑟夫问题如出一辙。

例子 3：假如在一场盛大的聚会中，大家玩这样的游戏，是不是超级有趣？就像一个魔法圈，把大家的注意力都吸引过来了。

每淘汰一个人，大家就会一阵惊呼，这不正是约瑟夫问题带来的独特体验嘛。

例子 4：你看过那种生存挑战节目吗？选手们围成一圈，然后通过类似约瑟夫问题的规则来淘汰人。

哇塞，那紧张的氛围，可不就是在经历一场残酷的竞争，这就是约瑟夫问题在现实中的精彩呈现呀！例子5：好比一群探险家在荒岛上，为了分配重要资源而采取这种方式。

每个人都祈祷自己不要被先淘汰掉，这种感觉是不是很奇妙？这就是约瑟夫问题带来的不确定性啊。

例子6：想象一下公司团建的时候玩这个，大家既期待又担心。

“哎呀，可别先轮到我呀！”“哇，我居然留下来了。

”这种种反应，不就是约瑟夫问题的魅力所在吗？例子 7：学校运动会上，各班学生围成一圈进行比赛，多刺激呀！有人欢喜有人忧，这不就是约瑟夫问题所引发的情绪波澜吗？例子 8：在一个神秘的魔法学院里，学生们也用这种方式来选拔优秀学员。

每一个人都全神贯注，这和约瑟夫问题一样充满了悬念呢！例子9：如果在一个古老的部落中，用约瑟夫问题来决定首领的继承人，那该是多么惊心动魄的场面啊。

大家的心都提到了嗓子眼，。

Wikioi : 1282 约瑟夫问题题目描述Description有编号从1到N的N个小朋友在玩一种出圈的游戏。

开始时N个小朋友围成一圈，编号为I+1的小朋友站在编号为I小朋友左边。

编号为1的小朋友站在编号为N的小朋友左边。

首先编号为1的小朋友开始报数，接着站在左边的小朋友顺序报数，直到数到某个数字M时就出圈。

直到只剩下1个小朋友，则游戏完毕。

现在给定N,M，求N个小朋友的出圈顺序。

输入描述Input Description唯一的一行包含两个整数N,M。

（1<=N,M<=30000）输出描述Output Description唯一的一行包含N个整数，每两个整数中间用空格隔开，第I个整数表示第I个出圈的小朋友的编号。

分析：由题意也可以看出，算法明确的分为两部分：模拟约瑟夫+ 求取原始序号。

1. 约瑟夫模拟：使用相对坐标(相对于环内)，例如当前被踢位置为k，下一个被踢的是+m，则k被踢掉以后，原本的k+1就成了k(相对坐标嘛)。

这样下一个位置就应该是新K + m-1 。

再考虑到循环意义：next = (k + m-1 - 1) % 人数+ 1。

当m为负向时，同理，只是要注意保证求得的下一次位置值是个正值。

2. 取原始序号：这个直接看下面的代码( update() )Code：#include <iostream>#include <cstdio>using namespace std;#define LL long longconst int N = 30001*4;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1int sum[N<<2];int tree[N<<2][2];void PushUp(int rt){sum[rt] = sum[rt<<1] + sum[rt<<1|1];}void build(int l,int r,int rt){tree[rt][0] = l;tree[rt][1] = r;if(l == r){sum[rt] = 1;return;}int m = (l+r)>>1;build(lson);build(rson);PushUp(rt);}int update(int p,int rt){sum[rt] --;if(tree[rt][0] == tree[rt][1]){sum[rt] = 0;return tree[rt][0];//从绝对位置剔除}if(p <= sum[rt<<1]) return update(p,rt<<1);else return update(p-sum[rt<<1],rt<<1|1);PushUp(rt);}int main(){int n,m;scanf("%d%d",&n,&m);build(1,n,1);int pos = 1;int seq = 1;for(int i = 0 ; i < n ; i++){seq = (seq + m - 1) % sum[1];//seq 只是相对位置if(seq == 0) seq = sum[1];pos = update(seq,1);cout<<pos<<" ";}return 0;}。

阅读材料世界名题与小升初之：抽杀问题约瑟夫问题--马到成功老师在各类竞赛中,各类小升初考试中相关的世界名题出现的概率极高,这是由小升初与数学竞赛的特点决定,这特点便是：知识性,趣味性,思想性相结合;先给大家介绍这一问题的由来;据说着名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特後,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止;然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏;解法约瑟夫问题可用代数分析来求解,将这个问题扩大好了,假设现在您与m个朋友不幸参与了这个游戏,您要如何保护您的朋友只要画两个圆圈就可以让自己与朋友免于死亡游戏,这两个圆内圈是排列顺序,而外圈是自杀顺序,如下图所示：使用程式来求解的话,只要将阵列当作环状来处理就可以了,在陈列中由计数1开始,每找到三个无资料区就填入一个计数,直接计数来求解的话,只要将阵列当作环状来处理就可以了,在阵列中由计数1开始,每找到三个无资料区就填入一个计数,直而计数达41为止,然后将阵列由索引1开始列出,就可以得知每个位置的自杀顺序,这就是约瑟夫排列,41个人报数3的约瑟夫排列如下所示：14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23由上可知,最后一个自杀的是在第31个位置,而倒数第二个自杀的要排在第16个位置,之前的人都死光了,所以他们也就不知道约瑟夫与他的朋友并没有遵守游戏规则了;小升初常见抽杀考题例举：例1：把1～999这999个自然数按顺时针的方向依次排列在一个圆圈上如下图;从1开始按顺时针的方向,保留1,擦去2；保留3,擦去4……这样每隔一个数擦去一个数,转圈擦下去;问：最后剩下一个数时,剩下的是哪个数马到成功解析：可通过找规律得出,如果有2n个数,那么转一圈擦去一半,剩下2n-1个数,起始数还是1；再转一圈擦去剩下的一半,又剩下2n-2个数,起始数还是1……转了n圈后,就剩下一个数是1;如果有2n+dd＜2n个数,那么当擦去d个数时,剩下2n个数,此时的第一个数是最后将剩下的数;因为擦去的第d个数是2d,所以2d+1就是最后剩下的整数;999=29+487,最后剩下的一个数是487×2+1=975;例2：1000个学生坐成一圈,依次编号为1,2,3,…,1000;现在进行1,2报数：1号学生报1后立即离开,2号学生报2并留下,3号学生报1后立即离开,4号学生报2并留下……学生们依次交替报1或2,凡报1的学生立即离开,报2的学生留下,如此进行下去,直到最后还剩下一个人;问：这个学生的编号是几号分析：这个问题与上面这题非常相似,只不过本例是报1的离开报2的留下,而上题相当于报1的留下报2的离开,由上题的结果可以推出本例的答案;本例中编号为1的学生离开后还剩999人,此时,如果原来报2的全部改报1并留下,原来报1的全部改报2并离开,那么,问题就与上面这题完全一样了;因为剩下999人时,第1人是2号,所以最后剩下的人的号码应比上题大1,是975＋1=976号;为了加深理解,我们重新解这道题;解：如果有2n个人,那么报完第1圈后,剩下的是2的倍数号；报完第2圈后,剩下的是22的倍数号……报完第n圈后,剩下的是2n的倍数号,此时,只剩下一人,是2n号;如果有2n＋d1≤d＜2n人,那么当有d人退出圈子后还剩下2n人;因为下一个该退出去的是2d＋1号,所以此时的第2d＋1号相当于2n人时的第1号,而2d号相当于2n人时的第2n 号,所以最后剩下的是第2d号;由1000=29＋488知,最后剩下的学生的编号是488×2=976号;例3：有100张的一摞卡片,玲玲拿着它们,从最上面的一张开始按如下的顺序进行操作：把最上面的第一张卡片舍去,把下一张卡片放在这一摞卡片的最下面;再把原来的第三张卡片舍去,把下一张卡片放在最下面;反复这样做,直到手中只剩下一张卡片,那么剩下的这张卡片是原来那一摞卡片的第几张分析与解：这100张卡片如果用线串起来,其实还是一个围成一圈的约瑟夫问题;如果上面几题的解法看不太懂,可学学这题,从最简单的情况开始找规律;下面从简单的不失题目性质的问题入手,寻找规律;列表如下：设这一摞卡片的张数为N,观察上表可知：1当N=2aa=0,1,2,3,…时,剩下的这张卡片是原来那一摞卡片的最后一张,即第2a张；2当N=2a+mm＜2a时,剩下的这张卡片是原来那一摞卡片的第2m张;取N=100,因为100=26+36,2×36=72,所以剩下这张卡片是原来那一摞卡片的第72张;总结上题及例1例2：可归纳为两种情况：1、留1,杀2类：剩下号＝总数－小于总数最大的2的次方数×2＋12、杀1,留2类：剩下号＝总数－小于总数最大的2的次方数×2记住留1要加1,杀1不用加1,总发现有学生在这点上分辨不清;因此可对照：例1：为“留1”类,可用：999－512×2＋1＝975例2：为“杀1”类,可用1000－512×2＝976例3：为“杀1”类,可用100－64×2＝72上面的512,64都是小于总数的最大的2的次方数;再看一道经变化的逆推题：例4：如下左图,七枚棋子围成一个圆圈,从①开始,每隔一个取一个,依次取走①、③、⑤、⑦、④、②,最后剩下⑥.二十枚棋子围成一个圆圈如右图,从开始,每隔一个取一个,最后将只剩下一枚棋子是⑥.实际上例就是抽杀问题的“杀1留2类”,右图可假设先从1开始取起,那根据规律留下的为：20－16×2＝8号,想留下6号得逆时针倒推2枚棋子;则最后结果为19号开始; 试试我们玩的扑克牌：例5：有两副扑克牌,每副牌的排列顺序均按头两张是大王、小王,然后是黑桃、红桃、方块、梅花四种花色排列;每种花色的牌又按1,2,3,…,J,Q,K 顺序排列;某人把按上述排列的两副扑克牌上下叠放在一起,然后把第一张丢掉,把第二张放在最底层,再把第三张丢掉,把第四张放在最底层,…….如此进行下去,直至最后只剩下一张牌;试问所剩的这张牌是哪一张解：注意到：如果手中只有64张牌,按这样规则丢牌,那么后剩下的应该是第64张牌;现在手中有108张牌,多出108－64＝44张,我们只需按此规定丢掉44张后,把88张牌放在手中牌的最底层时,这时手中牌恰为64张;这样,再丢下去,最后留下的就是原牌顺序的第88张,接下来的难点就涉及周期问题了,是哪张牌呢先去掉一副,再去掉黑桃、红桃各十三张,即为88-54-2×26＝6;按照花色排列应为方块6;来个再难点的三个数一组的题：例6：连续自然数1,2,3,…,8899排成一列;从1开始,留1划掉2和3,留4划掉5和6……这么转圈划下去,最后留下的是哪个数可仿例1与例2;这道题留1划2和3,每次留下三分之一,显然与3的N 次方有关了;当有3n 个数时,留下的数是1号;小于8899的形如3n 的数是38=6561,故从1号开始按规则划数,划了8899-6561=2338个数后,还剩下6561个数;这划去的数中的最后一个2338÷2×3=3507,故最后留下6561个数中的第一个就是3508;这道题也可归纳出一个规律：“留1,杀2,3”型留下的这个数为＝总数－小于总数的最大的3的次方数÷2×3＋1考一考：连续自然数1,2,3,…,8899排成一列;从1开始,划掉1和2,留下3,划掉4和5留下6……这么转圈划下去,最后留下的是哪个数这道题可定为“杀1,2留3”型,其中的规律与答案就留给你自己去研究了;另外在最前面约瑟夫的介绍中的类型可说成为“留1、2杀3型”你探索一下这道题有什么规律; 最后见识一下隐形抽杀问题：例7：在纸上写着一列自然数1,2,……,99,100;一次操作是指将这列数中最前面的两个数划去,然后把这两个数的和写在数列的最后面,例如一次操作后得到3,4,…,99,100,3；而两次操作后得到5,6,…,99,100,3,7;这样不断进行下去,最后将只剩下一个数;问：最后剩下的数是多少最初的100个数连同后面写下的数,纸上出现的所有数的总和是多少① ③ ② ④ ⑤ ⑥ ⑦ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ⑾ ⑿ ⒀ ⒁ ⒂ ⒃ ⒄ ⒅ ⒆ ⒇马到成功解析：在每次操作过程中,数列中添加的数等于划去的两个数之和,因此数列中所有数的和保持不变,于是当最后只剩下一个数时,它就是原来的100个数之和,为1+2+…+99+100=5050;当数列中有2n个数时,经过n次操作后将被全部划去,同时出现n个新数,并且这n 个新数之和等于原来2n个数的和;这提示我们去考虑数列包含2,2 ×2,2 ×2 ×2,…项的时刻;6个2连乘是64,当经过100-64=36次操作后,原来的数1,2,…,71,36×2=72被划去,划去的数的和是1+2+…+71+72=2628;此时数列中共有64个数,并且这64个数的和与原来100个数的和相等,是5050;从该时刻起,依次再经过32,16,8,4,2,1次操作后,纸上出现的新数的个数依次为32,16,8,4,2,1;根据前面的分析,每一轮出现的所有新数的和都是5050;从数列中有64个数变为只有1个数,操作共进行了6轮;综上所述,纸上写出的所有数之和为2628+5050+5050×6=37978;学会了抽杀问题的思路再来理解这题的设计就比较容易了;。

约瑟夫问题详解（CC++）Josephus 约瑟夫问题假设n个竞赛者排成一个环形，依次顺序编号1，2，…，n。

从某个指定的第1号开始，沿环计数，每数到第m个人就让其出列，且从下一个人开始重新计数，继续进行下去。

这个过程一直进行到所有的人都出列为止。

最后出列者为优胜者。

无论是用链表实现还是用数组实现来解约瑟夫问题都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较麻烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。

注意到原问题仅仅是要求出最后的胜利者的序号，而不是要模拟整个过程。

因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。

求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）: k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。

现在我们把他们的编号做一下转换：k --> 0k+1 --> 1k+2 --> 2......k-2 --> n-2变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x 是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？变回去的公式很简单：x'=(x+k)%n如何知道(n-1)个人报数的问题的解？显然，只要知道(n-2)个人的解就行了。

(n-2)个人的解呢？当然是先求(n-3)的情况---- 这显然就是一个倒推问题！递推公式：令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]递推公式f[1]=0;f[i]=(f[i-1]+m)%i; (i>1)有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。

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

例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。

最后剩下1号。

假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。

举个例子：有64名战士被敌人俘虏了。

敌人命令他们拍成一圆圈，编上号码1，2，3…，64。

敌人把1号杀了，又把3号杀了，他们隔着一个杀一个这样转着圈杀。

最后只剩下一个人，这个人就是约瑟夫斯。

请问约瑟夫斯是多少号？（这就是“约瑟夫斯”问题。

）这个问题解答起来比较简单：敌人从1号开始，隔一个杀一个，第一圈把所有的奇数号码的战士圈杀光了。

剩下的32名战士需要重新编号，而敌人在第二圈杀死的是重新编号的奇数号码。

由于第一圈剩下的全部是偶数号2，4，6，…，64。

把它们全部用2去除，得1，2，3，…，32。

这是第二圈编的号码。

第二圈杀过以后，又把奇数号码都杀掉了，还剩16个人。

如此下去，可以想到最后剩下的必然是64号。

$64=2^6$，它可以连续被2整除6次，是从1到64中能被2整除次数最多的数，因此，最后必然把64 号留下。

如果有65名战士被俘，敌人还是按上述的方法残杀战士，最后还会剩下约瑟夫斯吗？经过计算，很容易得到结论，不是。

因为第一个人被杀后，也就是1号被杀后，第二个被杀的是必然3号。

如果把1号排除在外，那么还剩下的仍是64人，新1号就是3号。

这样原来的2号就变成了新的64 号，所以剩下的必然是2号。

进一步的归类，不难发现如果原来有$2^k$个人，最后剩下的必然$2^k$号；如果原来有$2^k+1$个人，最后剩下2号；如果原来有$2^k+2$个人，最后剩下4号……如果原来有$2^k+m$个人，最后剩下2m号.比如：原来有100人，由于$100=64+36=2^6+36$，所以最后剩下的就是36×2=72号；又如：原来有11 1人，由于$100=64+47=2^6+47$，所以最后剩下的就是47×2=94号传说古代有一批人被蛮族俘虏了，敌人命令他们排成圆圈，编上号码1，2，3，…然后把1号杀了，把3号杀了，总之每隔一个人杀一个人，最后剩下一个人，这个人就是约瑟夫斯。

约瑟夫斯问题约瑟夫问题维基百科，⾃由的百科全书跳到导航跳到搜索约瑟夫问题（有时也称为约瑟夫斯置换），是⼀个出现在计算机科学和数学中的问题。

在计算机编程的算法中，类似问题⼜称为约瑟夫环。

⼈们站在⼀个等待被处决的圈⼦⾥。

计数从圆圈中的指定点开始，并沿指定⽅向围绕圆圈进⾏。

在跳过指定数量的⼈之后，处刑下⼀个⼈。

对剩下的⼈重复该过程，从下⼀个⼈开始，朝同⼀⽅向跳过相同数量的⼈，直到只剩下⼀个⼈，并被释放。

问题即，给定⼈数、起点、⽅向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

历史这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的⼀名犹太历史学家。

他在⾃⼰的⽇记中写道，他和他的40个战友被罗马军队包围在洞中。

他们讨论是⾃杀还是被俘，最终决定⾃杀，并以抽签的⽅式决定谁杀掉谁。

约瑟夫斯和另外⼀个⼈是最后两个留下的⼈。

约瑟夫斯说服了那个⼈，他们将向罗马军队投降，不再⾃杀。

约瑟夫斯把他的存活归因于运⽓或天意，他不知道是哪⼀个。

[1]解法⽐较简单的做法是⽤循环单链表模拟整个过程，时间复杂度是O(n*m)。

如果只是想求得最后剩下的⼈，则可以⽤数学推导的⽅式得出公式。

且先看看模拟过程的解法。

Python版本-- coding: utf-8 --class Node(object):def init(self, value):self.value = valueself.next = Nonedef create_linkList(n):head = Node(1)pre = headfor i in range(2, n+1):newNode = Node(i)pre.next= newNodepre = newNodepre.next = headreturn headn = 5 #总的个数m = 2 #数的数⽬if m == 1: #如果是1的话，特殊处理，直接输出print (n)else:head = create_linkList(n)pre = Nonecur = headwhile cur.next != cur: #终⽌条件是节点的下⼀个节点指向本⾝for i in range(m-1):pre = curcur = cur.nextprint (cur.value)pre.next = cur.nextcur.next = Nonecur = pre.nextprint (cur.value)using namespace std;typedef struct _LinkNode {int value;struct _LinkNode* next;} LinkNode, *LinkNodePtr;LinkNodePtr createCycle(int total) {int index = 1;LinkNodePtr head = NULL, curr = NULL, prev = NULL;head = (LinkNodePtr) malloc(sizeof(LinkNode));head->value = index;prev = head;while (--total > 0) {curr = (LinkNodePtr) malloc(sizeof(LinkNode));curr->value = ++index;prev->next = curr;prev = curr;}curr->next = head;return head;}void run(int total, int tag) {LinkNodePtr node = createCycle(total);LinkNodePtr prev = NULL;int start = 1;int index = start;while (node && node->next) {if (index == tag) {printf("%d\n", node->value);prev = node->next;node->next = NULL;node = prev;} else {prev->next = node->next;node->next = NULL;node = prev->next;}index = start;} else {prev = node;node = node->next;index++;}}}int main() {if (argc < 3) return -1;run(atoi(argv[1]), atoi(argv[2]));return 0;}数学推导解法我们将明确解出{\displaystyle k=2}k=2时的问题。

题目：约瑟夫（Joseph）问题的一种描述是：编号为1，2，......，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个开始重新从1报数，如此下去，直至年有人全部出列为止。

试设计一个程序求出出列顺序。

班级：姓名：学号：完成日期：一、需求分析1．本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的编号和密码）。

2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示"提示信息"之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。

3．程序执行的命令包括：1)构造单向循环链表；2）4．测试数据m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6（正确的出列顺序为6，1，4，7，2，1，3，5）。

二、概要设计1．单向循环链表的抽象数据类型定义为：ADT List｛数据对象：D=｛ai | ai∈正整数，I=1，2，......，n,n≥0｝数据关系：R1=｛< ai-1，ai > |，ai-1，ai∈D,I=1，2，......，n｝基本操作：Init List(&L)操作结果：构造一个空的线性表L。

List Insert(&L,i,e)初始条件：线性表L已存在，1≤i≤List Length(L)+1.操作结果：在L中第i个位置之前插入新的数据无素e，L长度加1。

List Delete(&L,i,&e)初始条件：线性表L存在非空，1≤i≤List Length(L).操作结果：删除L的第i个元素，并用e返回其值，L长度减1。

2．程序包含四个模块：1）主程序模块：三详细设计typedef struct LNode{int password; //密码int No; //序号struct LNode *next; //下一成员指针}member; //成员结构体typedef int status;#define OVERFLOW -2#define OK 1#define ERROR 0#include <stdio.h>#include <stdlib.h>status CreateList_Circle(member **,int);status DeleteNode(member **);status main(){int n,m;member *head=NULL,*p=NULL; //头指针即首成员地址，遍历指针p printf ("Please enter number of people:\n");scanf ("%d",&n); //总成员数while (n<=0){printf ("n must be positive, please enter again:\n");scanf ("%d",&n);}if(!CreateList_Circle(&head,n)) //创建循环链表，返回头指针head return OVERFLOW;printf ("Please enter initial m:\n");scanf ("%d",&m); //初始mwhile (m<=0){printf ("m must be positive, please enter again:\n");scanf ("%d",&m);}printf ("\nThe order is:\n");p=head;while (n>=2) //寻找出列成员{int i;m=(m%n==0)?n:m%n; //化简m值for (i=1;i<m;i++)p=p->next; //p指向出列成员printf ("%d\n",p->No); //输出出列成员序号m=p->password; //修改mDeleteNode(&p); //删除链表中的出列成员n--; //成员数自减}printf ("%d\n",p->No); //输出最后一个成员序号return OK;}status CreateList_Circle(member **p_head,int n){//此算法创建一个无头结点的循环链表，结点数n,*p_head返回链表头指针即首结点地址int i;member *tail,*p;*p_head=(member *)malloc(sizeof(member));if (!(*p_head)) return OVERFLOW;(*p_head)->No=1; //储存成员一序号printf ("Please enter password of No. 1:\n");scanf ("%d",&(*p_head)->password); //储存成员一密码tail=*p_head;tail->next=NULL;for (i=2;i<n+1;i++){p=(member *)malloc(sizeof(member));if (!p) return OVERFLOW;p->No=i; //储存成员序号printf ("Please enter password of No. %d:\n",i);scanf("%d",&(p->password)); //储存成员密码tail->next=p;tail=p;}tail->next=*p_head;return OK;}status DeleteNode(member **pp){//此算法删除链表中的结点*pp,操作实质是将*pp下一结点复制到*pp后将其free member *temp;(*pp)->password=((*pp)->next)->password;(*pp)->No=((*pp)->next)->No;temp=(*pp)->next;(*pp)->next=(*pp)->next->next;free(temp);return OK;}四、调试分析程序的编写和调试基本正常。

工程管理科内控制度第一部分：绪论工程管理是一门综合性学科，涉及范围广泛，工程管理科内控制度是保障项目实施质量和效率的重要保障措施。

合理的内控制度可以有效地规范工程管理活动，提高工程管理水平，确保项目进展顺利。

本文将从内控制度的概念、内控制度的重要性、内控制度的基本要素和内控制度的实施过程等方面进行探讨。

第二部分：内控制度的概念内控制度是指一个企业或组织为了达成其目标而制订的控制措施和程序。

在工程管理科领域，内控制度是为了规范与管理项目管理活动而制订的一系列内部控制规定和程序。

内控制度的实施可以有效地防范风险，提高工作效率，保障工程管理的质量和安全。

第三部分：内控制度的重要性工程管理科内控制度的建立和实施对于确保项目的顺利进行至关重要。

首先，内控制度可以规范管理流程，明确责任分工，提高工作效率。

其次，内控制度可以有效防范风险，降低项目管理风险，确保项目按期、按质完成。

再次，内控制度可以提高工程管理科的整体形象，增强内部员工的工作积极性和责任心。

总之，内控制度的建立和实施对于保障工程管理科的顺利运转和发展至关重要。

第四部分：内控制度的基本要素内控制度的建立和实施包括以下几个基本要素：1. 控制目标：明确工程管理科的目标和任务，确立明确的工作目标和目标任务。

2. 控制环境：建立健全的内部环境，包括组织结构、内部管理制度、企业文化等。

3. 风险评估：对工程管理科所面临的各种风险进行评估和分析，制定相应的风险应对策略。

4. 控制活动：制定具体的控制措施和程序，规范工程管理活动的开展和执行。

5. 信息与沟通：建立健全的信息系统和内部沟通机制，确保信息的畅通和及时传达。

6. 监督和评价：建立监督和评价机制，对内控措施和程序进行监督和检查，及时发现问题并加以解决。

第五部分：内控制度的实施过程内控制度的实施是一个系统性和持续性的过程，需要在全体员工共同努力下不断推进。

具体实施过程如下：1. 制定内控制度规定：在工程管理科领导的指导下，建立内控制度规定，明确制度内容和执行规范。

约瑟夫问题(数学解法及数组模拟)约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。

在计算机编程的算法中，类似问题又称为约瑟夫环。

又称“丢手绢问题”.）据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从。

首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。

接着，再越过k-1个人，并杀掉第k个人。

这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。

问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

? 以上来自百度百科约瑟夫问题是个很有名的问题：N个人围成一个圈，从第一个人开始报数，第M个人会被杀掉，最后一个人则为幸存者，其余人都将被杀掉。

例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。

约瑟夫问题其实并不难，但求解的方法多种多样；题目的变化形式也很多。

接下来我们来对约瑟夫问题进行讨论。

1.模拟解法优点 : 思维简单。

?缺点：时间复杂度高达O(m*n)当n和m的值较大时，无法短时间内得到答案。

为了叙述的方便我们将n个人编号为：1- n ，用一个数组vis 来标记是否存活：1表示死亡 0表示存活 s代表当前死亡的人数? cnt 代表当前报了数的人数用t来枚举每一个位置(当tn时 t=1将人首尾相连)? 那么我们不难得出核心代码如下：bool vis[1000]; --标记当前位置的人的存活状态int t = 0; --模拟位置int s = 0; --死亡人数int cnt = 0; --计数器if(t n) t = 1;if(!vis[t]) cnt++; --如果这里有人,计数器+1if(cnt == m) --如果此时已经等于m,这这个人死去cnt = 0; --计数器清零s++; --死亡人数+1vis[t] = 1 --标记这个位置的人已经死去coutt" "; --输出这个位置的编号}while(s != n);接下来我们来看另一种更为高效快速的解法数学解法我们将这n个人按顺时针编号为0~n-1，则每次报数到m-1的人死去，剩下的人又继续从0开始报数，不断重复，求最后幸存的人最初的编号是多少？我们只需要将最后求得的解加1就能得到原来的编号。

“约瑟夫”问题及若干变种例1、约瑟夫问题(Josephus)[问题描述]M只猴子要选大王，选举办法如下：所有猴子按1…M编号围坐一圈，从第1号开始按顺序1，2，…，N 报数，凡报到N的猴子退出到圈外，再从下一个猴子开始继续1~ N报数，如此循环，直到圈内只剩下一只猴子时，这只猴子就是大王。

M和N由键盘输入，1≤N,M≤10000，打印出最后剩下的那只猴子的编号。

例如，输入8 3，输出：7。

[问题分析1]这个例题是由古罗马著名史学家Josephus提出的问题演变而来的，所以通常称为Josephus(约瑟夫)问题。

在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m个元素的数组monkey来实现。

利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkey[k]=1表示第k只猴子仍在圈中，monkey[k]=0则表示第k只猴子已经出圈。

程序采用模拟选举过程的方法，设变量count表示计数器，开始报数前将count置为0，设变量current 表示当前报数的猴子编号，初始时也置为0，设变量out记录出圈猴子数，初始时也置为0。

每次报数都把monkey[current]的值加到count上，这样做的好处是直接避开了已出圈的猴子（因为它们对应的monkey[current]值为0），当count=n时，就对当前报数的猴子作出圈处理，即：monkey[current]：=0，count：=0，out：=out+1。

然后继续往下报数，直到圈中只剩一只猴子为止（即out=m-1）。

参考程序如下：program josephus1a {模拟法，用数组下标表示猴子的编号}const maxm=10000;var m,n,count,current,out,i:integer;monkey:array [1..maxm] of integer;beginwrite('Input m,n:');readln(m,n);for i:=1 to m do monkey[i]:=1;out:=0; count:=0; current:=0;while out<m-1 dobeginwhile count<n dobeginif current<m then current:=current+1 else current:=1;count:=count+monkey[current];end;monkey[current]:=0; out:=out+1; count:=0end;for i:=1 to m doif monkey[i]=1 then writeln('The monkey king is no.',i);readlnend.[运行结果]下划线表示输入Input m，n:8 3The monkey king is no.7 {时间：0秒}Input m，n:10000 1987The monkey king is no.8544 {时间：3秒}[反思]时间复杂度很大O(M*N)，对于极限数据会超时。

约瑟夫斯问题
问题描述
约瑟夫斯问题是一个经典的数学问题，也被称为约瑟夫环问题。

问题的描述如下：有n个人围成一圈，从第一个人开始报数，报到m的人出列，然后从出列的下一个人开始重新报数，再次报到m的人出列，如此循环，直到所有人都出列为止。

那么，最后剩下的人在原来的顺序中编号是几？
算法思路
为了解决约瑟夫斯问题，可以使用一种常用的数学技巧来计算最后剩下的人的编号。

假设n个人的编号分别为0, 1, 2, …, n-1，那么可以得到一个递推公式：
f(n, m) = (f(n-1, m) + m) % n
其中f(n, m)表示有n个人时最后剩下的人的编号。

根据这个递推公式，可以进行递归计算。

算法实现
下面是使用Python语言实现约瑟夫斯问题的算法：
```python def josephus(n, m): if n == 1: return 0 else: return (josephus(n-1, m) + m) % n
测试样例
n = 7 # 总人数 m = 3 # 报数到m时出列 survivor = josephus(n, m) print(。

约瑟夫环问题的两种解法（循环链表和公式法）问题描述这⾥是数据结构课堂上的描述：N people form a circle, eliminate a person every k people, who is the final survior?Label each person with 0, 1, 2, ..., n - 1, denote(表⽰，指代) J(n, k) the labels of surviors when there are n people.(J(n, k)表⽰了当有 n 个⼈时幸存者的标号)First eliminate the person labeled k - 1, relabel the rest, starting with 0 for the one originally labeled k.0 1 2 3 ... k-2 k-1 k k+1 ... n-1... k-2 0 1 ...Dynamic programmingJ(n, k) = J(J(n - 1, k) + k) % n, if n > 1,J(1, k) = 0⽤中⽂的⽅式简单翻译⼀下就是 (吐槽：为啥课上不直接⽤中⽂呢？淦！) 有 n 个⼈围成⼀圈，从第⼀个⼈开始，从 1 开始报数，报 k 的⼈就将被杀死，然后从下⼀个⼈开始重新从 1 开始报数，往后还是报 k 的⼈被杀掉，杀到最后只剩⼀个⼈时，其⼈就为幸存者。

(上⾯的英⽂是从 0 开始的，是因为我们写程序时使⽤了数组，所以下标从 0 开始)解决⽅案循环链表⽅法算法思路很简单，我们这⾥使⽤了循环链表模拟了这个过程：节点 1 指向节点 2，节点 2 指向节点 3，...，然后节点 N 再指向节点 1，这样就形成了⼀个圆环。

如图所⽰，n 取 12，k 取 3，从 1 开始报数，然后依次删除 3, 6, 9, 12：#include<stdio.h>#include<stdlib.h>typedef struct Node // 节点存放⼀个数据和指向下⼀个节点的指针{int data;struct Node *next;} *NList; // NList为指向 Node 节点的指针// 创建⼀个节点数为 n 的循环链表NList createList(int n){// 先创建⼀个节点NList p, tmp, head;p = (NList)malloc(sizeof(struct Node));head = p; // 保存头节点p->data = 1; // 第⼀个节点for (int i = 2; i <=n ; i++){tmp = (NList)malloc(sizeof(struct Node));tmp->data = i;p->next = tmp;p = tmp;}p->next = head; // 最后⼀个节点指回开头return head;}// 从编号为 1 的⼈开始报数，报到 k 的⼈出列，被杀掉void processList(NList head, int k){if (!head) return;NList p = head;NList tmp;while (p->next != p){for (int i = 0; i < k - 1; i++){tmp = p;p = p->next;}printf("%d 号被杀死\n", p->data);tmp->next = p->next;free(p);p = NULL; // 防⽌产⽣野指针，下同p = tmp->next;}printf("幸存者为 %d 号", p->data);free(p);p = NULL;}int main(){NList head = createList(11);processList(head, 3);return 0;}测试结果：易知，这个算法的时间复杂度为O(nk)，显然，这不是⼀个好的算法。