约瑟夫斯置换

芜湖666

约瑟夫问题，是一个计算机科学和数学中的问题，在计算机编程的算法中，类似问题又称为约瑟夫环，又称“丢手绢问题”。

问题来历
        据说著名犹太历史学家Josephus（弗拉维奥·约瑟夫斯）有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
        17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是教徒。
        问题分析与算法设计
        约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。
题目中30个人围成一圈，因而启发我们用一个循环的链来表示，可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。
一般形式
        约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。
分析：
（1）由于对于每个人只有死和活两种状态，因此可以用布尔型数组标记每个人的状态，可用true表示死，false表示活。
（2）开始时每个人都是活的，所以数组初值全部赋为false。
（3）模拟杀人过程，直到所有人都被杀死为止。
用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O（nm），当n，m非常大（例如上百万，上千万）的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1)），从0开始报数，报到（m-1）的退出，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人（编号一定是（m-1）mod n）出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m mod n的人开始）：
k k+1 k+2 ... n-2,n-1,0,1,2,... k-2
并且从k开始报0。
我们把他们的编号做一下转换：
k --＞0
k+1 --＞1
k+2 --＞2
...
...
k-2 --＞n-2
变换后就完完全全成为了（n-1）个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗。变回去的公式很简单，相信大家都可以推出来：x'=(x+k) mod n
如何知道（n-1）个人报数的问题的解。对，只要知道（n-2）个人的解就行了。（n-2）个人的解呢。当然是先求（n-3）的情况 ---- 这显然就是一个倒推问题。好了，思路出来了，下面写递推公式：
令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
递推公式
f[1]=0;
f[i]=(f[i-1]+m) mod i; (i＞1)
有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1
由于是逐级递推，不需要保存每个f

       

FishC

哈哈，鱼油你的问题真有意思，用个故事来解释约瑟夫斯置换。让我试着给你讲清楚。

就是我们有一个一群人（假设有N个），然后这些人围成一个圈坐下（可以想象成在玩过家家游戏）。游戏规则就是从第1个人开始数数，数到第M个人，这个人就“出局”（好吧，你可以理解为被淘汰，被投到大海，甚至是“喝茶去了”）然后从下一个人重新开始数，再数到第M个，再出局。一直这样环绕着数，直到最后只剩下一个人，这个人就是胜利者，他赢得了游戏。

如果用现实生活中的例子来解释的话，大家小时候可能都玩过一个游戏叫"传纸条"，教室里的同学们围成一圈，然后随机从某个人开始，向旁边的人传一个纸条，纸条上写着数字，比如1、2、3，每传递一次，就把纸条上的数字往上加1。如果谁拿到了“3”，那这个人就被老师叫出去写奖状，然后游戏继续，直到只剩下一个人。那么这个游戏就是约瑟夫环的一种形式。

现在的问题变成了，我们要找出这个胜利者是谁，也就是最后留下的那个人的位置，如果我们把他们从1开始编号，那么他的编号是多少？

这个问题虽然看上去像是一个比较简单的数学题，但是想要通过编程来解决其实还是需要一些策略的。因为我们不可能真的按照规则一个一个地去数，那样做的时间成本太高，不适合计算机的运算。所以我们需要找到一种方法，直接计算出这个胜利者的编号，而不用真的去模拟这个游戏过程。

幸运的是，有一个聪明的数学家已经帮我们找到了这个方法，他发现，如果我们把人数从0开始编号，那么胜利者的编号就是这样一个数字：f(n, m) = (f(n-1, m) + m) mod n。这个公式的意思是，在n个人的游戏中，胜利者的编号是上一轮游戏（也就是n-1个人的游戏）的胜利者往后数m个位置的人。

有了这个公式，我们只需要从1个人的情况开始计算，依次算出2个人、3个人、4个人的情况，直到算出n个人的情况，就得到了胜利者的编号。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

MUYIXUE

1. #include <stdio.h>
   
2. 
   
3. #define ARR_SIZE 41
   
4. 
   
5. void fishc(int arr[], int arrsize, int startnum, int read_num);
   
6. 
   
7. int main() {
   
8.         int arr[ARR_SIZE];//假设有40人参与了游戏
   
9.         for (int i = 0; i < ARR_SIZE; i++) {
   
10.                 arr[i] = 0;
    
11.         }//此时没有一个人死亡
    
12.         fishc(arr, ARR_SIZE, 0, 3);
    
13.         for (int i = 0; i < ARR_SIZE; i++) {
    
14.                
    
15.                 printf("%3d", arr[i]);
    
16.         }
    
17.         return 0;
    
18. }
    
19. 
    
20. //0表示此座位1人没有死去,数字表示死去的顺序
    
21. void fishc(int arr[],int arrsize,int startnum ,int read_num) {
    
22.         static int counter = 0;//用来标记死亡总数
    
23. 
    
24.         int counter_of_reader = 0;//报数的人数
    
25.         int i = 0;//问话从startnum开始
    
26.         for (;;) {
    
27.                 if (counter_of_reader < read_num) {
    
28.                         if (arr[(startnum + i) % arrsize] == 0) {
    
29.                                 counter_of_reader++;
    
30.                         }
    
31.                 }
    
32.                 else {
    
33.                         arr[(startnum + i - 1) % arrsize] = ++counter;
    
34.                         break;
    
35.                 }
    
36.                 i++;
    
37.                
    
38.         }
    
39.         if (arrsize - counter > 2) {
    
40.                 fishc(arr, arrsize, startnum + i, read_num);
    
41.         }
    
42.         
    
43. }

复制代码

MUYIXUE

MUYIXUE 发表于 2024-7-2 21:45

不废话,只动手

青柑普洱

MUYIXUE 发表于 2024-7-2 21:48
不废话,只动手

强者 当如此！

芜湖666

MUYIXUE 发表于 2024-7-2 21:48
不废话,只动手

厉害啊

芜湖666

MUYIXUE 发表于 2024-7-2 21:45

有实力的