365新函数：约瑟夫环问题-暴力模拟循环过程

shaowu459

约瑟夫环问题是编程算法中的一个经典问题，本帖以一个简单例子来说明使用REDUCE函数模拟循环过程的两种公式写法。

问题描述：
有13个人围成一圈，这13个人编号分别为1~13，从编号为1的人开始报数，报到4的人出局。然后从下一个人重新报数，再次报到4的人出局。按如此方式直到剩余1个人为止。例如，第一次编号为4的人出局，下面从编号5的人开始报1，编号8的人报4，因此编号8的人出局，以此类推。

要求：
请列示出每次出局的人员编号。

注意：
本帖旨在介绍使用REDUCE函数模拟循环过程挑选每次出局人员的公式写法，不考虑效率问题。通过数学方法归纳编号规律、递归等高效率方法不在本帖讨论范围之内。

shaowu459

第一种方法：排序方法。

思路分析：13个编号，可以构造一个1~13的数组，循环13次，每次把出局的人员移动到数组底端，出局人员上方的元素移动到底端第一个出局人员的上方，循环完毕，得到的数组就是需要的结果。

下面用图示来说明分析过程，A列存储一列不变的序号，B列存储初始数组，后面y=1、y=2……的列存储循环第一次、第二次后的结果。

第一次循环：
第一次编号4的人员出局（在数组中的位置是4），因此需要把棕色单元格的4放到数组最底端，4上面的绿色1、2、3移动到4的上方，黄色部分移动到数组上方，因为下次要从5开始报数。


第二次循环：
第二次编号8的人员出局（在数组中的位置是4），因此需要把棕色单元格的8放到数组最底端，8上面的绿色5、6、7移动到4的上方，黄色部分移动到数组上方，因为下次要从9开始报数。


第三次循环：
第三次编号12的人员出局（在数组中的位置是4），因此需要把棕色单元格的12放到数组最底端，12上面的绿色9、10、11移动到4的上方，黄色部分移动到数组上方，因为下次要从13开始报数。


后面以此类推，需要注意以下几点：
1）循环到第n次，循环完毕后数组最底下的n个在下次循环的时候就不会再是绿色或黄色的一部分，是一个整体，移动也一起移动。
2）当圆圈剩余的人大于等于4个时，每次出局的人都是从上到下位置4的人。如果剩余的人数小于4人，比如3人，那出局的人就是位置1的人，可以考虑用求余数的方法求位置。
3）假设需要移动的棕色单元格位置是x，那么绿色单元格的位置都小于x，黄色单元格位置都大于x。

shaowu459

通过以上分析，我们可以写出如下公式，每次循环时使用SORTBY函数来排序，排序的依据包括：1）1~13位置数组=出局人员位置，将出局编号移动到最底端；2）1~13位置数组>14-循环次数，保持最底端的出局人员位置不动；3）1~13数组位置和出局人员位置相比的大小关系，将绿色和黄色部分上下交换。

1. =LET(s,SEQUENCE(13),REDUCE(s,s,LAMBDA(x,y,LET(u,MOD(3,14-y)+1,SORTBY(x,s=u,,s>14-y,,s<u,)))))

复制代码

公式简单说明如下：

=LET(
    s, SEQUENCE(13),      人员编号数组，也是1~13位置数组
    REDUCE(
        s,           将1~13位置数组作为x初始值，每次循环排序后更新
        s,           循环数组s中元素那么多次
        LAMBDA(x, y,
            LET(
                u, MOD(3, 14 - y) + 1,     使用余数确定出局人员位置
                SORTBY(x, s = u, , s > 14 - y, , s < u, )     按找3个标准升序排序数组
            )
        )
    )
)

shaowu459

第二种方法：扩充首尾相连的数组。

思路分析：既然是圆圈，肯定就是首尾相连的，我们可以将足够多的1~13的数组纵向堆叠在一起，每次都将第4个位置的人出局，可以将出局人员堆叠在数组下方，然后去掉数组的前4行（那么数组第一个就是下次应该报1号的人），再将数组中等于该位置人员的编号都去掉，那么剩下的人还是首尾相连，并且已经没有出局人员编号了。下次，还是将位置4的人员编号堆叠在数组下方，去掉数组的前4行，再将数组中此次出局人员编号去掉。以此类推，循环13次，所有人都出局一遍，最后剩余的数组就是所求。

参考公式如下：

1. =REDUCE(TOCOL(0/SEQUENCE(,99)+SEQUENCE(13),,1),A1:A13,LAMBDA(x,y,LET(s,INDEX(x,4),t,DROP(x,4),VSTACK(FILTER(t,t<>s),s&""))))

复制代码

公式简单说明如下：
=REDUCE(
    TOCOL(0 / SEQUENCE(, 99) + SEQUENCE(13), , 1),   1~13的数组加上若干列，扩充若干次，使用TOCOL函数转化成1列，作为x初始值
    A1:A13,      区域引用13个单元格，循环13次，不使用单元格的值，区域数量控制循环总次数13次
    LAMBDA(x, y,
        LET(
            s, INDEX(x, 4),   提取数组第4个元素的数字，为此次出局人员编号
            t, DROP(x, 4),    将数组前4行去掉生成剩余数组
            VSTACK(

                    FILTER(t, t <> s),  FILTER函数将剩余数组中此次出局人员编号去掉，形成首尾仍相连数组，并且第一个值为下次报1的人员。
                    s & "")              s&""将编号数字变成文本，避免被FILTER函数筛选去掉，堆叠在数组最下方，保存出局人员编号。   
            )
          )
       )

xlllw203

shaowu459 发表于 2023-8-11 22:50
第二种方法：扩充首尾相连的数组。

思路分析：既然是圆圈，肯定就是首尾相连的，我们可以将足够多的1~13 ...

超人老师，按照这个思路，s放在底部之后，数组t在filter之后不会再出现与s相同的数字，貌似不存在被筛去的问题，所以公式中直接写成s好像也没有问题，不知道理解的对不对

1. =REDUCE(TOCOL(0/SEQUENCE(,99)+SEQUENCE(13),,1),ROW(1:13),LAMBDA(x,y,LET(s,INDEX(x,4),t,DROP(x,4),VSTACK(FILTER(t,t<>s),s))))

复制代码

shaowu459

xlllw203 发表于 2023-8-26 14:03
超人老师，按照这个思路，s放在底部之后，数组t在filter之后不会再出现与s相同的数字，貌似不存在被筛去 ...

有道理，应该是这样的，不用弄成文本当时写的时候不知道咋想的，就想岔了

micch

1. =REDUCE(0,SEQUENCE(D2-1,,2),LAMBDA(x,y,MOD(x+E2,y)))+1

复制代码

只求最后一个人序号，不列出过程

sucx007

shaowu459 发表于 2023-8-11 22:50
第二种方法：扩充首尾相连的数组。

思路分析：既然是圆圈，肯定就是首尾相连的，我们可以将足够多的1~13 ...

第二解题思路用动态处理，方便理解，供参考

shaowu459

sucx007 发表于 2023-9-6 14:25
第二解题思路用动态处理，方便理解，供参考

这样，一步一步的循环结果，更清楚