简化递归解决约瑟夫环问题

hanasamo

约瑟夫环问题：X个人围城一圈，每间隔Y个人淘汰一人，以此类推，最后剩余一名获胜者，请问这位获胜者初始应该站在几号位置？

我自己编写了一个递归的公式，X代表剩余的人数，Y代表间隔的人数，我实验了一些情况，都能正确计算出最后的结果。可是我觉得我这样反复嵌套IF的方式太傻了，需要考虑剩余人数X大于Y，等于Y，比Y小1，等于1，还有介于1和比Y小1之间的数字5种情况。

请问有没有大佬可以帮我分析一下，怎么简化这个公式。

1. =LET(fx,LAMBDA(fx,x,y,IF(ROWS(x)=1,x,fx(fx,IF(ROWS(x)>y,VSTACK(DROP(x,y),TAKE(x,y-1)),IF(ROWS(x)=y,DROP(x,-1),
   
2. IF(ROWS(x)=y-1,DROP(x,1),IF(ROWS(x)=2,IF(ISEVEN(y),DROP(x,-1),TAKE(x,-1)),VSTACK(TAKE(x,MOD(y,ROWS(x))-ROWS(x)),TAKE(x,MOD(y,ROWS(x))-1)))))),y))),fx(fx,B2#,3))

复制代码

alan57

1. =LET(f,LAMBDA(f,m,n,IF(ROWS(m)=n,VSTACK(TAKE(m,-1),DROP(m,-1)),LET(a,INDEX(m,n),c,VSTACK(DROP(m,n),TAKE(m,n-1)),VSTACK(a,f(f,c,n))))),f(f,SEQUENCE(10),3))

复制代码

cnmlgb9998

alan57 发表于 2024-7-17 09:59

我原以为 头像是超级玛莉64的是大神，原来方丈您是大神中的大神。。。。

咔咔乱坠

仅结果

1. =LET(f,LAMBDA(f,n,m,IF(ROWS(UNIQUE(n))=1,@n,f(f,FILTER(DROP(n,m),DROP(n,m)<>INDEX(n,m)),m))),f(f,MOD(SEQUENCE(A2*99)-1,A2)+1,B2))

复制代码

列过程

1. =LET(f,LAMBDA(f,n,m,k,LET(a,DROP(n,m),b,INDEX(n,m),IF(ROWS(n)=1,k,f(f,FILTER(a,a<>b,@n),m,VSTACK(k,b))))),DROP(f(f,MOD(SEQUENCE(A1*99)-1,A1)+1,B1,0),1))

复制代码

突然发现超人老师已经做了这方面的解答

1. https://club.excelhome.net/thread-1670026-1-1.html?_dsign=c8016590

复制代码

alan57

1. =LET(x,8,y,4,o,TOCOL(0/SEQUENCE(,99)+SEQUENCE(x),,1),f,LAMBDA(f,m,n,LET(a,INDEX(m,n),b,DROP(m,n),_c,FILTER(b,b<>a),IF(ROWS(UNIQUE(_c))=1,VSTACK(a,@_c),VSTACK(a,f(f,_c,n))))),f(f,o,y))

复制代码

通用的递归。

hanasamo

alan57 发表于 2024-7-17 09:59

非常感谢！

不过我实验了一些数字，发现有一些错误，比如f(sequence(5),4)的情况，最后应该活下来的应该是1号，可是你的公式给出的答案是2号。

shaowu459

你是要用递归并且只得到最后的号码吗？不需要列出来每次淘汰的人员情况？如果是的话，普通循环公式改成递归就成：


这个链接的7楼

shaowu459

直接翻译楼上的循环为递归：

1. =LET(f,LAMBDA(f,x,n,IF(n=D2,x,f(f,MOD(x+E2,n+1),n+1))),f(f,0,1))+1

复制代码

hanasamo

shaowu459 发表于 2024-7-17 14:20
直接翻译楼上的循环为递归：

万分感谢，真的很优雅的办法，可是我不太理解，能劳烦给解释一下吗？

1. =TOROW(LET(s,SEQUENCE(C2),REDUCE(s,SEQUENCE(C4),LAMBDA(x,y,LET(i,MOD(C3-1,C2+1-y)+1,SORTBY(x,s=i,,s>C2+1-y,,s<i,))))))

复制代码

这个方案也很棒，我从你另一个帖子里翻到的，尤其是SORTBY的用法让我茅塞顿开。

shaowu459

hanasamo 发表于 2024-7-17 23:31
万分感谢，真的很优雅的办法，可是我不太理解，能劳烦给解释一下吗？

你看下7楼索引的那个循环公式吧，理解一下，可以百度约瑟夫环，那个数学规律就能找到了，求余数的规律。

reduce循环是确定为二参元素数量那么多次，改成递归加了个计数器n，到了次数就退出，和那个循环一样，关键是mod那部分的数学规律。