微信怎么群发消息给所有人-红警地图mmp

圆圈1
2023年4月1日发(作者:订票浏览器)

算法24[约瑟夫环]n个数字(0,1,…,n-1)形成一个圆圈,从

数字0开始......

/lzj509649444/article/details/7056742

题目:n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始,

每次从这个圆圈中删除第m个数字(第一个为当前数字本

身,第二个为当前数字的下一个数字)。当一个数字删除后,

从被删除数字的下一个继续删除第m个数字。求出在这个圆

圈中剩下的最后一个数字。

分析:我们完全可以用计算机来模拟上述过程,每找到一个

要删除的数,需要扫描m次,总共删除n-1个数,所以总得

扫描次数为m*(n-1)。这是一个平方级的复杂度,下面来考

虑如何对它进行改进。

改进:上述模拟过程效率低的原因是,每次找到要删除的数

都要进行m次的查找,怎么来减少查找次数?可我们又注意

到,可以通过计算来找到那个要删除的数,比如第一次删除,

(m-1)%n的结果即为要删除的数。可删除了该数以后怎么办

呢?下面的计算应当怎么进行呢?

归纳:假设在某一时刻删除的数为第k个,并且知道k前面

有A个数,k后面有B个数,那么可以对A,B进行运算而

求得下一次应当删除的数是哪一个?现在问题变为,如何统

计A,B的信息。。。。。

导致上述归纳行不通的原因自己分析如下:1.归纳基础不恰

当2.这样归纳下去得到的结果是想要的吗?3.信息不

够,导致分析不能继续进行下去,所以得从题目中挖掘出更

多的信息,明确题目最终要求的是什么。如何来过掉这道

坎?

再归纳:题目要求最后剩下的一个数(用last表示),也就是

这个数是第几个,在(0,1,…,n-1)的位置是多少。明确了题

目中的信息,所以我们要对这个数进行归纳。假设知道这个

数在剩下的k个数中的位置,怎么来求得它在剩余K+1个数

中的位置,这样一步一步推导出它在有n个数中的位置,即

为所求。为什么能这样归纳,因为这个最后剩下的数在所有

删除过程中有幸存活下来,只不过每次删除了一个数,它的

位置就变了,知道最后,它的位置为0(只剩一个数了)。

现在来分析删除第一个数后,last这个数的位置已之前有什

么样的关系。在这n个数字中,第一个被删除的数字是

(m-1)%n,为简单起见记为k。那么删除k之后的剩下n-1的

数字为0,1,…,k-1,k+1,…,n-1,并且下一个开始计数的数字是

k+1。相当于在剩下的序列中,k+1排到最前面,从而形成序

列k+1,…,n-1,0,…k-1。

k+1->0

k+2->1

n-1->n-k-2

0->n-k-1

k-1->n-2

现在我们知道了有n-1个数时last的位置,记为f(n-1,m),那

么如何来求得f(n,m)关于f(n-1,m)之间的关系?用X,Y来表

示,如下:

YX

k+1->0

k+2->1

n-1->n-k-2

0->n-k-1

k-1->n-2

y=(x+k+1)%n

k=(m-1)%n

所以y=(x+m)%n,最终关系如下:

0n=1

f(n,m)={

[f(n-1,m)+m]%nn>1

参考代码:

intLastRemaining(unsignedintn,unsignedintm)

{

if(n<1||m<1)

return-1;

intlast=0;

for(inti=2;i<=n;i++)

last=(last+m)%i;

returnlast;

}

代码来源于:

/2011/10/no-14-last-number-in-c

更多推荐

圆圈1